00001 #ifndef SKIPROPE_H_INCLUDED
00002 #define SKIPROPE_H_INCLUDED
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include <stdlib.h>
00034 #include <new>
00035 #include <vector>
00036 #include <portable_io.h>
00037
00038 namespace cxxtls
00039 {
00040
00041
00057
00058 #ifndef SKIPROPE_MAX_BLOCKSIZE
00059 # define SKIPROPE_MAX_BLOCKSIZE (32000)
00060 #endif
00061
00062 template<class T> class skiprope_debugger;
00063
00064 template<class T> class skiprope_const_iterator;
00065 template<class T> class skiprope_iterator;
00066 template<class T> class skiprope;
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080 template<class T>
00081 class skiprope_node
00140 {
00141 int levels_;
00142
00143 std::vector<T> data_;
00144
00145 typedef typename std::vector<T>::iterator iterator;
00146 typedef typename std::vector<T>::const_iterator const_iterator;
00147
00148
00149
00150
00151 friend class skiprope<T>;
00152 friend class skiprope_const_iterator<T>;
00153 friend class skiprope_iterator<T>;
00154
00155 friend class skiprope_debugger<T>;
00156
00157 struct link_info
00158 {
00159 skiprope_node<T> *next_;
00160 skiprope_node<T> *prev_;
00161 ptrdiff_t width_;
00162
00163
00164
00165
00166
00167 };
00168
00169 public:
00170
00171 typedef skiprope_node<T> self;
00172
00173 iterator begin() { return data_.begin(); }
00174 const_iterator begin() const { return data_.begin(); }
00175
00176 iterator end() { return data_.end(); }
00177 const_iterator end() const { return data_.end(); }
00178
00179 void insert(T const &d, ptrdiff_t o);
00180 void insert(T const *f, T const *l, ptrdiff_t o);
00181 #ifdef _AIX
00182 void insert(const_iterator f, const_iterator l, ptrdiff_t o);
00183 #endif
00184 void push_back(T const *f, T const *l);
00185 void erase(ptrdiff_t o);
00186 void erase(ptrdiff_t o, ptrdiff_t cnt);
00187 void erase(typename std::vector<T>::iterator b, typename std::vector<T>::iterator e);
00188
00189 void adjust_widths(ptrdiff_t);
00190
00191 ptrdiff_t size() const { return data_.size(); }
00192 int levels() const { return levels_; }
00193
00194 static self * new_node(int max_possible_level)
00201 {
00202
00203
00204 int l = 1;
00205
00206 while(l < max_possible_level)
00207 {
00208 int v = rand();
00209 int m = RAND_MAX/3;
00210
00211 if(v > m)
00212 break;
00213 ++l;
00214 }
00215
00216
00217
00218 self *rv = (self*)(new char[ sizeof(self) + (l-1)*sizeof(link_info) ]);
00219
00220
00221
00222 rv->levels_ = l;
00223
00224 new (&rv->data_) std::vector<T>;
00225
00226 for(int i=0; i < l; ++i)
00227 {
00228 rv->link_[i].next_ = 0;
00229 rv->link_[i].prev_ = 0;
00230 rv->link_[i].width_ = 0;
00231 }
00232
00233 return rv;
00234 }
00235
00236 static void discard(self *victim)
00237 {
00238 typedef std::vector<T> MyVector;
00239
00240 MyVector *p = &victim->data_;
00241
00242 p->MyVector::~MyVector();
00243
00244 delete [] (char*)(victim);
00245
00246 }
00247
00248 private:
00249 void *operator new(size_t);
00250 void operator delete(void*p);
00251
00252
00253
00254
00255 link_info link_[1];
00256
00257
00258
00259 };
00260
00261 template<class T>
00262 void skiprope_node<T>::adjust_widths(ptrdiff_t amount)
00263
00266
00267 {
00268 link_info *first = &link_[0];
00269 link_info *last = first + levels_;
00270
00271 while(first != last)
00272 {
00273 first->width_ += amount;
00274 ++first;
00275 }
00276
00277 }
00278
00279
00280 template<class T>
00281 void skiprope_node<T>::insert(T const &d, ptrdiff_t o)
00282 {
00283 data_.insert(data_.begin()+o,d);
00284 adjust_widths(o);
00285 }
00286
00287 template<class T>
00288 void skiprope_node<T>::insert(T const *f, T const *l, ptrdiff_t o)
00289 {
00290 data_.insert(data_.begin()+o, f, l);
00291 adjust_widths(l - f);
00292 }
00293
00294 #ifdef _AIX
00295 template<class T>
00296 void skiprope_node<T>::insert(typename skiprope_node<T>::const_iterator f,
00297 typename skiprope_node<T>::const_iterator l,
00298 ptrdiff_t o)
00299 {
00300 data_.insert(data_.begin()+o, f, l);
00301 adjust_widths(l - f);
00302 }
00303 #endif
00304
00305
00306 template<class T>
00307 void skiprope_node<T>::push_back(T const *f, T const *l)
00308 {
00309 data_.insert(data_.end(),f,l);
00310 adjust_widths(l - f);
00311 }
00312
00313 template<class T>
00314 void skiprope_node<T>::erase(ptrdiff_t o)
00315 {
00316 data_.erase(data_.begin()+o, data_.begin()+(o+1));
00317 adjust_widths(-1);
00318 }
00319 template<class T>
00320 void skiprope_node<T>::erase(ptrdiff_t o, ptrdiff_t cnt)
00321 {
00322 data_.erase(data_.begin()+o, data_.begin()+(o+cnt));
00323 adjust_widths(-cnt);
00324 }
00325 template<class T>
00326 void skiprope_node<T>::erase(typename std::vector<T>::iterator b,
00327 typename std::vector<T>::iterator e)
00328 {
00329 data_.erase(b,e);
00330 adjust_widths(-(e - b));
00331 }
00332
00333 template<class T>
00334 class skiprope_iterator
00335
00339
00340 {
00341 typedef skiprope<T> rope;
00342
00343 skiprope_node<T> *node_;
00344 ptrdiff_t offset_;
00345 rope *rope_;
00346
00347 friend class skiprope_const_iterator<T>;
00348 friend class skiprope<T>;
00349 friend class skiprope_debugger<T>;
00350
00351 public:
00352
00353 typedef skiprope_iterator<T> self;
00354
00355 skiprope_iterator(): node_(0), offset_(0), rope_(0) {}
00356
00357 skiprope_iterator(self const &r): node_(r.node_), offset_(r.offset_), rope_(r.rope_) {}
00358
00359 skiprope_iterator(skiprope_node<T> *n, ptrdiff_t o, skiprope<T> *r, int normal=1);
00360
00361 T &operator*() { return *(node_->begin() + offset_); }
00362 T const &operator*() const { return *(node_->begin() + offset_); }
00363
00364
00365
00366
00367
00368
00369
00370 self begin() { return self(node_,0); }
00371 self end() { return self(node_, node_->data_.size()); }
00372
00373 self const begin() const { return self(node_,0); }
00374 self const end() const { return self(node_, node_->data_.size()); }
00375
00376 int operator==(self const &r) const
00377 {
00378 return node_ == r.node_ && offset_ == r.offset_;
00379 }
00380
00381 int operator!=(self const &r) const
00382 {
00383 return node_ != r.node_ || offset_ != r.offset_;
00384 }
00385
00386 self &operator=(self const &r)
00387 {
00388 node_ = r.node_;
00389 offset_ = r.offset_;
00390 rope_ = r.rope_;
00391 return *this;
00392 }
00393
00394 self &operator++();
00395 self operator++(int);
00396 self &operator--();
00397 self operator--(int);
00398
00399 };
00400
00401 template<class T>
00402 skiprope_iterator<T>::
00403 skiprope_iterator(skiprope_node<T> *n, ptrdiff_t o, skiprope<T> *r, int normal)
00404 : node_(n), offset_(o), rope_(r)
00405 {
00406 if(node_ == 0)
00407 {
00408 offset_ = 0;
00409 return;
00410 }
00411
00412 if(!normal)
00413 {
00414 return;
00415
00416
00417 }
00418
00419 int s = n->size();
00420
00421 while(node_ && offset_ >= s)
00422 {
00423 offset_ -= s;
00424 node_ = node_->link_[0].next_;
00425 if(node_)
00426 s = node_->size();
00427 }
00428 if(node_ == 0)
00429 {
00430 node_ = rope_->last_;
00431
00432 if(node_)
00433 {
00434 offset_ = node_->size();
00435 }
00436 else
00437 {
00438 offset_ = 0;
00439 }
00440 }
00441 }
00442
00443
00444 template<class T>
00445 class skiprope_const_iterator
00446
00450
00451 {
00452 typedef skiprope<T> rope;
00453 skiprope_node<T> const *node_;
00454 ptrdiff_t offset_;
00455 rope const *rope_;
00456
00457 friend class skiprope<T>;
00458 friend class skiprope_debugger<T>;
00459
00460 public:
00461
00462 typedef skiprope_const_iterator<T> self;
00463
00464 skiprope_const_iterator(): node_(0), offset_(0), rope_(0) {}
00465
00466 skiprope_const_iterator(self const &r)
00467 : node_(r.node_),
00468 offset_(r.offset_),
00469 rope_(r.rope_)
00470 {
00471 }
00472
00473 skiprope_const_iterator(skiprope_node<T> const *n, ptrdiff_t o, rope const* r);
00474
00475 skiprope_const_iterator(skiprope_iterator<T> i)
00476 : node_(i.node_),
00477 offset_(i.offset_),
00478 rope_(i.rope_)
00479 {
00480 }
00481
00482 self &operator=(self const &r)
00483 {
00484 node_ = r.node_;
00485 offset_ = r.offset_;
00486 rope_ = r.rope_;
00487 return *this;
00488 }
00489
00490 self &operator=(skiprope_iterator<T> const &r)
00491 {
00492 node_ = r.node_;
00493 offset_ = r.offset_;
00494 rope_ = r.rope_;
00495 return *this;
00496 }
00497
00498
00499 T const &operator*() const { return *(node_->begin() + offset_); }
00500
00501
00502
00503
00504
00505
00506
00507
00508 self begin() { return self(node_,0); }
00509 self end() { return self(node_, node_->data_.size()); }
00510
00511 self const begin() const { return self(node_,0); }
00512 self const end() const { return self(node_, node_->data_.size()); }
00513
00514 int operator==(self const &r) const
00515 {
00516 return node_ == r.node_ && offset_ == r.offset_;
00517 }
00518
00519 int operator!=(self const &r) const
00520 {
00521 return node_ != r.node_ || offset_ != r.offset_;
00522 }
00523
00524 int operator==(skiprope_iterator<T> const &r) const
00525 {
00526 return node_ == r.node_ && offset_ == r.offset_;
00527 }
00528
00529 int operator!=(skiprope_iterator<T> const &r) const
00530 {
00531 return node_ != r.node_ || offset_ != r.offset_;
00532 }
00533
00534 self &operator++();
00535 self operator++(int);
00536 self &operator--();
00537 self operator--(int);
00538
00539 };
00540
00541 template<class T>
00542 skiprope_const_iterator<T>::
00543 skiprope_const_iterator(skiprope_node<T> const *n, ptrdiff_t o, rope const* r)
00544 : node_(n),
00545 offset_(0),
00546 rope_(r)
00547 {
00548 if(node_ == 0)
00549 {
00550 offset_ = 0;
00551 return;
00552 }
00553
00554 ptrdiff_t s = node_->size();
00555
00556 while(node_ && offset_ >= node_->size())
00557 {
00558 offset_ -= s;
00559 node_ = node_->link_[0].next_;
00560 }
00561 if(node_ == 0)
00562 {
00563
00564 node_ = rope_->last_;
00565
00566 if(node_)
00567 {
00568 offset_ = node_->size();
00569 }
00570 else
00571 {
00572 offset_ = 0;
00573 }
00574
00575 }
00576 }
00577
00578
00579 template<class T>
00580 struct skiprope_level_desc
00581 {
00582 typedef skiprope_node<T> node;
00583
00584 node *head_;
00585 ptrdiff_t offset_;
00586
00587 skiprope_level_desc(): head_(0) {}
00588
00589 };
00590
00591 template<class T>
00592 class skiprope
00639
00640 {
00641 friend class skiprope_debugger<T>;
00642 friend class skiprope_iterator<T>;
00643 friend class skiprope_const_iterator<T>;
00644
00645
00646 enum max_block_size_ { max_block_size=SKIPROPE_MAX_BLOCKSIZE };
00647
00648 enum index_levels_ { max_index_levels=32 };
00649
00650 enum chunk_size_ { chunk_size =
00651 (sizeof(T) > max_block_size
00652 ?
00653 1
00654 :
00655 max_block_size / sizeof(T)
00656 )
00657 };
00658
00659 typedef skiprope_node<T> node;
00660 typedef typename skiprope_node<T>::link_info link_info;
00661
00662 typedef skiprope_level_desc<T> level_desc;
00663
00664 level_desc level_[max_index_levels];
00665
00666
00667 node *last_;
00668
00669
00670
00671 int active_levels_;
00672
00673 ptrdiff_t size_;
00674
00675 int nodes_;
00676
00677 public:
00678
00679 int visited_levels_;
00680
00681 typedef skiprope<T> self;
00682 typedef int size_t;
00683
00684 typedef skiprope_iterator<T> iterator;
00685
00686 typedef skiprope_const_iterator<T> const_iterator;
00687
00688 skiprope(): last_(0), active_levels_(0), size_(0), nodes_(0) {}
00689 skiprope(self const &r);
00690
00691 ~skiprope();
00692
00693 ptrdiff_t size() const { return size_; }
00694
00695 iterator begin();
00696 iterator end();
00697 iterator find(ptrdiff_t offset);
00698 ptrdiff_t find(iterator);
00699 T& operator[] (ptrdiff_t i) { return *find(i); }
00700
00701
00702 const_iterator begin() const;
00703 const_iterator end() const;
00704 const_iterator find(ptrdiff_t offset) const;
00705 ptrdiff_t find(const_iterator) const;
00706 T const& operator[] (ptrdiff_t i) const { return *find(i); }
00707
00708 iterator insert(iterator, T const* first, T const * last);
00709 iterator insert(iterator i, T const &r);
00710 void erase(iterator location);
00711 void erase(iterator first, iterator last);
00712
00713 void push_back(T const *first, T const *last);
00714 void push_back(T const &r);
00715 iterator push_front(T const *first, T const *last);
00716 iterator push_front(T const &r);
00717 T& front() { return *begin(); }
00718 T const& front() const { return *begin(); }
00719 T& back() { iterator t = end(); --t; return *t; }
00720 T const& back() const { const_iterator t = end(); --t; return *t; }
00721
00722
00723 private:
00724
00725 void insert_node(node *before, node *after);
00726
00727 void split_node(node *n, ptrdiff_t offset);
00728
00729
00730
00731 public:
00732 struct node_info
00736 {
00737 node *node_;
00738 ptrdiff_t offset_;
00739
00740 node_info(node*n, ptrdiff_t o): node_(n), offset_(o) {}
00741
00742 node_info(){}
00743
00744 };
00745
00746 friend struct node_info;
00747
00748 private:
00749
00750 node_info find_node_before(ptrdiff_t location, int level);
00751
00752
00753
00754 int predecessors(node *n, node_info *pred);
00755
00756
00757
00758 int prednodes(node *, node_info *pred);
00759
00760 void predoffsets(node_info*pred, int levels);
00761
00762 };
00763
00764 template<class T>
00765 skiprope<T>::~skiprope()
00766 {
00767 node *scan = level_[0].head_;
00768
00769 while(scan)
00770 {
00771 node *next = scan->link_[0].next_;
00772
00773 node::discard(scan);
00774
00775 scan = next;
00776
00777 }
00778
00779 }
00780
00781 template<class T>
00782 skiprope<T>::skiprope(typename skiprope<T>::self const &r)
00783 : last_(0),
00784 active_levels_(0),
00785 size_(0)
00789 {
00790 node *scan = r.level_[0].head_;
00791
00792 while(scan)
00793 {
00794 push_back(scan->begin(), scan->end());
00795
00796 scan = scan->link_[0].next_;
00797 }
00798
00799 }
00800
00801 template<class T>
00802 typename skiprope<T>::iterator
00803 skiprope<T>::begin()
00804 {
00805 return iterator(level_[0].head_, 0, this);
00806 }
00807
00808 template<class T>
00809 typename skiprope<T>::const_iterator
00810 skiprope<T>::begin() const
00811 {
00812 return const_iterator(level_[0].head_, 0);
00813 }
00814
00815 template<class T>
00816 typename skiprope<T>::iterator
00817 skiprope<T>::end()
00818 {
00819 return iterator(last_, last_?last_->size():0, this);
00820 }
00821
00822 template<class T>
00823 typename skiprope<T>::const_iterator
00824 skiprope<T>::end() const
00825 {
00826 return const_iterator(last_, last_?last_->size():0);
00827 }
00828
00829 template<class T>
00830 void skiprope<T>::push_back(T const &r)
00831 {
00832 push_back(&r, &(r)+1);
00833 }
00834
00835 template<class T>
00836 typename skiprope<T>::iterator
00837 skiprope<T>::insert(typename skiprope<T>::iterator where, T const &r)
00838 {
00839 return insert(where, &r, &(r)+1);
00840 }
00841
00842
00843 template<class T>
00844 typename skiprope<T>::iterator
00845 skiprope<T>::find(ptrdiff_t offset)
00864
00865 {
00866
00867 int level;
00868 node *n;
00869 ptrdiff_t p=0;
00870
00871 for(level = active_levels_-1; level >= 0 && offset < (p=level_[level].offset_); --level);
00872
00873 if(level >= 0)
00874 {
00875
00876
00877 n = level_[level].head_;
00878
00879 while(level >= 0)
00880 {
00881 while(n->link_[level].next_ &&
00882 offset >= (p + n->link_[level].width_)
00883 )
00884 {
00885 p += n->link_[level].width_;
00886 n = n->link_[level].next_;
00887 }
00888
00889 if(offset < p + n->size())
00890 {
00891 return iterator(n, offset - p, this);
00892 }
00893
00894 --level;
00895 ++visited_levels_;
00896 }
00897
00898
00899 }
00900
00901 return end();
00902
00903 }
00904
00905 template<class T>
00906 typename skiprope<T>::node_info
00907 skiprope<T>::find_node_before(ptrdiff_t offset, int search_level)
00911
00912 {
00913
00914 int level;
00915 node *n;
00916 ptrdiff_t p=0;
00917
00918 for(level = active_levels_-1; level >= search_level && offset < (p=level_[level].offset_); --level);
00919
00920 if(level >= 0)
00921 {
00922
00923
00924 n = level_[level].head_;
00925
00926 while(level >= 0)
00927 {
00928 while(n->link_[level].next_ &&
00929 offset >= (p + n->link_[level].width_)
00930 )
00931 {
00932 p += n->link_[level].width_;
00933 n = n->link_[level].next_;
00934 }
00935
00936 if(offset < p + n->size())
00937 {
00938 return node_info(n,p);
00939 }
00940
00941 --level;
00942 }
00943
00944 }
00945
00946 return node_info(0,0);
00947
00948 }
00949
00950
00951 template<class T>
00952 typename skiprope<T>::const_iterator
00953 skiprope<T>::find(ptrdiff_t offset) const
00954 {
00955 self *unconst = this;
00956
00957 return unconst->find(offset);
00958 }
00959
00960 template<class T>
00961 void
00962 skiprope<T>::push_back(T const *first, T const *last)
00963
00965
00966
00967 {
00968
00969 ptrdiff_t insert_count = last - first;
00970
00971 if(last_)
00972 {
00973
00974
00975 ptrdiff_t avail = chunk_size - last_->size();
00976
00977 if(avail > insert_count)
00978 {
00979 last_->push_back(first, last);
00980 size_ += insert_count;
00981 return;
00982 }
00983 else
00984 {
00985 last_->push_back(first, first+avail);
00986 first += avail;
00987 insert_count -= avail;
00988 size_ += avail;
00989 }
00990 }
00991
00992
00993
00994
00995
00996 while(insert_count)
00997 {
00998
00999 node *n = node::new_node(max_index_levels);
01000 ptrdiff_t max_insert = insert_count;
01001
01002 if(max_insert > chunk_size)
01003 {
01004 max_insert = chunk_size;
01005 }
01006
01007 n->push_back(first, first+max_insert);
01008
01009 insert_count -= max_insert;
01010
01011 first += max_insert;
01012
01013 if(last_)
01014 {
01015 insert_node(last_, n);
01016 }
01017 else
01018 {
01019
01020
01021 last_ = n;
01022
01023 size_ += max_insert;
01024 ++nodes_;
01025
01026 int i;
01027
01028 active_levels_ = n->levels();
01029
01030 for(i=0; i < n->levels(); ++i)
01031 {
01032 level_[i].head_ = n;
01033 level_[i].offset_ = 0;
01034 }
01035
01036
01037 }
01038
01039 }
01040
01041 }
01042
01043 template<class T>
01044 int skiprope<T>::
01045 prednodes(typename skiprope<T>::node *n,
01046 typename skiprope<T>::node_info *pred
01047 )
01048 {
01049 int level=0;
01050
01051 while(level < active_levels_)
01052 {
01053
01054
01055
01056 while( level < n->levels() )
01057 {
01058 pred[level].node_ = n;
01059 ++level;
01060 }
01061
01062
01063
01064 if(level >= active_levels_)
01065 break;
01066
01067
01068
01069
01070
01071
01072
01073 node *old_n = n;
01074
01075 while(n->link_[level-1].prev_ &&
01076 n->levels() <= level
01077 )
01078 {
01079 if(n->levels() < level )
01080 {
01081 printf("prev(%p) points to lower level node\n", n);
01082 exit(1);
01083 }
01084 n = n->link_[level-1].prev_;
01085 }
01086
01087 if( ( old_n == n || (n == 0 && level != active_levels_) ) )
01088 {
01089 break;
01090 }
01091
01092 }
01093
01094 return level;
01095
01096 }
01097
01098 template<class T>
01099 void skiprope<T>::
01100 predoffsets(typename skiprope<T>::node_info *pred, int level)
01101
01106
01107 {
01108 --level;
01109
01110 ptrdiff_t offset = level_[level].offset_;
01111
01112 node *n = level_[level].head_;
01113
01114 while(level >= 0)
01115 {
01116
01117
01118 while(n->link_[level].next_ && n != pred[level].node_ )
01119 {
01120
01121
01122 offset += n->link_[level].width_;
01123 n = n->link_[level].next_;
01124 }
01125
01126 pred[level].offset_ = offset;
01127
01128 --level;
01129
01130 while(level >= 0 && pred[level].node_ == n)
01131 {
01132 pred[level].offset_ = offset;
01133 --level;
01134 }
01135
01136
01137 }
01138
01139 }
01140
01141
01142 template<class T>
01143 int skiprope<T>::predecessors(typename skiprope<T>::node *n,
01144 typename skiprope<T>::node_info *pred
01145 )
01146
01155
01156 {
01157
01158
01159 int level=prednodes(n, pred);
01160
01161
01162
01163
01164
01165
01166 predoffsets(pred, level);
01167
01168 return level;
01169
01170 }
01171
01172 template<class T>
01173 void skiprope<T>::
01174 insert_node(typename skiprope<T>::node *before,
01175 typename skiprope<T>::node *after
01176 )
01177
01192 {
01193
01194
01195 ptrdiff_t after_size = after->size();
01196
01197 size_ += after_size;
01198
01199 if(last_ == before)
01200 {
01201 last_ = after;
01202 }
01203
01204 node_info pred[max_index_levels];
01205
01206 int pred_level = predecessors(before, pred);
01207
01208 int after_levels = after->levels();
01209
01210 ptrdiff_t after_location = pred[0].offset_ + pred[0].node_->size();
01211
01212 int i;
01213
01214 ++nodes_;
01215
01216 for(i=0; i < pred_level; ++i)
01217 {
01218
01219
01220
01221 if( i >= after_levels )
01222 {
01223 pred[i].node_->link_[i].width_ += after_size;
01224 continue;
01225 }
01226
01227 ptrdiff_t pred_width;
01228 ptrdiff_t after_width;
01229
01230 pred_width = after_location - pred[i].offset_;
01231
01232 if(pred[i].node_->link_[i].next_)
01233 {
01234 after_width= pred[i].offset_ + pred[i].node_->link_[i].width_ +
01235 after_size - after_location;
01236 }
01237 else
01238 {
01239 after_width = after_size;
01240 }
01241
01242 after->link_[i].next_ = pred[i].node_->link_[i].next_;
01243 after->link_[i].prev_ = pred[i].node_;
01244 pred[i].node_->link_[i].next_ = after;
01245
01246 after->link_[i].width_ = after_width;
01247 pred[i].node_->link_[i].width_ = pred_width;
01248
01249 if(after->link_[i].next_)
01250 {
01251 after->link_[i].next_->link_[i].prev_ = after;
01252 }
01253
01254 }
01255
01256 while( i < after_levels && i < active_levels_ )
01257 {
01258
01259
01260
01261
01262
01263
01264
01265
01266
01267
01268
01269
01270
01271
01272
01273
01274
01275 if(after_location < level_[i].offset_)
01276 {
01277
01278
01279 after->link_[i].width_ = level_[i].offset_ - after_location + after_size;
01280 after->link_[i].next_ = level_[i].head_;
01281
01282 if(level_[i].head_)
01283 level_[i].head_->link_[i].prev_ = after;
01284
01285 level_[i].offset_ = after_location;
01286 level_[i].head_ = after;
01287 }
01288 else
01289 {
01290
01291
01292
01293
01294
01295
01296
01297 after->link_[i].width_ = after_size + level_[i].offset_ - after_location;
01298 after->link_[i].next_ = level_[i].head_;
01299 level_[i].offset_ = after_location;
01300 level_[i].head_ = after;
01301
01302 if(after->link_[i].next_)
01303 {
01304 after->link_[i].next_->link_[i].prev_ = after;
01305 }
01306
01307 }
01308
01309 ++i;
01310
01311 }
01312
01313 while(i < active_levels_ )
01314 {
01315
01316 level_[i].offset_ += after_size;
01317 ++i;
01318 }
01319
01320 while(active_levels_ < after_levels)
01321 {
01322
01323
01324 level_[active_levels_].head_ = after;
01325 level_[active_levels_].offset_ = after_location;
01326 ++active_levels_;
01327 }
01328
01329 }
01330
01331 template<class T>
01332 skiprope_iterator<T> &
01333 skiprope_iterator<T>::
01334 operator++()
01335 {
01336 ++offset_;
01337
01338 if(offset_ >= node_->size() )
01339 {
01340 offset_ = 0;
01341
01342 node_ = node_->link_[0].next_;
01343
01344 if(node_ == 0)
01345 *this = rope_->end();
01346 }
01347 return *this;
01348 }
01349
01350 template<class T>
01351 skiprope_iterator<T>
01352 skiprope_iterator<T>::
01353 operator++(int)
01354 {
01355 self rv(*this);
01356
01357 ++offset_;
01358
01359 if(offset_ >= node_->size() )
01360 {
01361 offset_ = 0;
01362
01363 node_ = node_->link_[0].next_;
01364
01365 if(node_ == 0)
01366 *this = rope_->end();
01367
01368 }
01369
01370 return rv;
01371 }
01372
01373 template<class T>
01374 skiprope_iterator<T> &
01375 skiprope_iterator<T>::
01376 operator--()
01377 {
01378 if(*this == rope_->end())
01379 {
01380 node_ = rope_->last_;
01381
01382 if(node_)
01383 offset_ = node_->size() -1;
01384 else
01385 offset_ = 0;
01386
01387
01388
01389
01390 }
01391 else
01392 {
01393 if(offset_ == 0)
01394 {
01395 node_ = node_->link_[0].prev_;
01396
01397 if(node_ != 0)
01398 offset_ = node_->size() - 1;
01399
01400
01401 }
01402 else
01403 {
01404 --offset_;
01405 }
01406 }
01407 return *this;
01408 }
01409
01410 template<class T>
01411 skiprope_iterator<T>
01412 skiprope_iterator<T>::
01413 operator--(int)
01414 {
01415 self rv(*this);
01416
01417 if(*this == rope_->end())
01418 {
01419 node_ = rope_->last_;
01420
01421 if(node_)
01422 offset_ = node_->size() -1;
01423 else
01424 offset_ = 0;
01425
01426
01427
01428
01429 }
01430 else
01431 {
01432 if(offset_ == 0)
01433 {
01434 node_ = node_->link_[0].prev_;
01435 if(node_)
01436 offset_ = node_->size() - 1;
01437 }
01438 else
01439 {
01440 --offset_;
01441 }
01442 }
01443
01444
01445 return rv;
01446 }
01447
01448
01449 template<class T>
01450 skiprope_const_iterator<T> &
01451 skiprope_const_iterator<T>::
01452 operator++()
01453 {
01454 ++offset_;
01455
01456 if(offset_ >= node_->size() )
01457 {
01458 offset_ = 0;
01459
01460 node_ = node_->link_[0].next_;
01461
01462 if(node_ == 0)
01463 *this = rope_->end();
01464 }
01465 return *this;
01466 }
01467
01468 template<class T>
01469 skiprope_const_iterator<T>
01470 skiprope_const_iterator<T>::
01471 operator++(int)
01472 {
01473 self rv(*this);
01474
01475 ++offset_;
01476
01477 if(offset_ >= node_->size() )
01478 {
01479 offset_ = 0;
01480
01481 node_ = node_->link_[0].next_;
01482
01483 if(node_ == 0)
01484 *this = rope_->end();
01485
01486 }
01487
01488 return rv;
01489 }
01490
01491 template<class T>
01492 skiprope_const_iterator<T> &
01493 skiprope_const_iterator<T>::
01494 operator--()
01495 {
01496 if(*this == rope_->end())
01497 {
01498 node_ = rope_->last_;
01499
01500 if(node_)
01501 offset_ = node_->size() -1;
01502 else
01503 offset_ = 0;
01504
01505
01506
01507
01508 }
01509 else
01510 {
01511 if(offset_ == 0)
01512 {
01513 node_ = node_->link_[0].prev_;
01514 if(node_)
01515 offset_ = node_->size() - 1;
01516 }
01517 else
01518 {
01519 --offset_;
01520 }
01521 }
01522 return *this;
01523 }
01524
01525 template<class T>
01526 skiprope_const_iterator<T>
01527 skiprope_const_iterator<T>::
01528 operator--(int)
01529 {
01530 self rv(*this);
01531
01532 if(*this == rope_->end())
01533 {
01534 node_ = rope_->last_;
01535
01536 if(node_)
01537 offset_ = node_->size() -1;
01538 else
01539 offset_ = 0;
01540
01541
01542
01543
01544 }
01545 else
01546 {
01547 if(offset_ == 0)
01548 {
01549 node_ = node_->link_[0].prev_;
01550
01551 if(node_)
01552 offset_ = node_->size() - 1;
01553 }
01554 else
01555 {
01556 --offset_;
01557 }
01558 }
01559
01560
01561 return rv;
01562 }
01563
01564 template<class T>
01565 typename skiprope<T>::iterator
01566 skiprope<T>::push_front(T const &r)
01567 {
01568 return push_front(&r, (&r)+1);
01569 }
01570
01571
01572 template<class T>
01573 typename skiprope<T>::iterator
01574 skiprope<T>::push_front(T const *first, T const *last)
01575
01622
01623 {
01624 if(last_ == 0)
01625 {
01626 push_back(first, last);
01627 return end();
01628 }
01629
01630 ptrdiff_t count = last - first;
01631
01632 node *n = level_[0].head_;
01633
01634 ptrdiff_t avail = chunk_size - n->size();
01635
01636
01637
01638 if(count <= avail)
01639 {
01640 level_[0].head_->insert(first, last, 0);
01641 size_ += count;
01642
01643 for(int i=n->levels(); i < active_levels_; ++i)
01644 {
01645 level_[i].offset_ += count;
01646 }
01647
01648 return iterator(n, count, this);
01649
01650 }
01651
01652
01653
01654 node *new_node = node::new_node(max_index_levels);
01655
01656 ++nodes_;
01657
01658 ptrdiff_t first_node_size = count > chunk_size ? chunk_size : count;
01659
01660 new_node->insert(first, first + first_node_size, 0);
01661
01662 size_ += first_node_size;
01663
01664 int i;
01665
01666 int extant_levels = new_node->levels();
01667
01668 if(extant_levels > active_levels_)
01669 extant_levels = active_levels_;
01670
01671 for(i=0; i < extant_levels; ++i)
01672 {
01673 new_node->link_[i].next_ = level_[i].head_;
01674 level_[i].head_->link_[i].prev_ = new_node;
01675 new_node->link_[i].width_ += level_[i].offset_;
01676
01677 level_[i].head_ = new_node;
01678 level_[i].offset_ = 0;
01679 }
01680
01681 while(i < active_levels_ )
01682 {
01683 level_[i].offset_ += first_node_size;
01684 ++i;
01685 }
01686
01687 while(active_levels_ < new_node->levels())
01688 {
01689 level_[active_levels_].offset_ = 0;
01690 level_[active_levels_].head_ = new_node;
01691 ++active_levels_;
01692 }
01693
01694
01695
01696
01697 count -= first_node_size;
01698 first += first_node_size;
01699
01700 if(count)
01701 {
01702 return insert( iterator(new_node->link_[0].next_, 0, this),
01703 first,
01704 last
01705 );
01706 }
01707
01708 return iterator(new_node, new_node->size(), this);
01709
01710 }
01711
01712
01713 template<class T>
01714 typename skiprope<T>::iterator
01715 skiprope<T>::insert(typename skiprope<T>::iterator where,
01716 T const *first,
01717 T const *last
01718 )
01719
01739 {
01740
01741
01742
01743
01744 if(where == end())
01745 {
01746 push_back(first, last);
01747 return end();
01748 }
01749 else if(where == begin())
01750 {
01751 return push_front(first, last);
01752 }
01753
01754 node *n = where.node_;
01755 ptrdiff_t count = last - first;
01756 ptrdiff_t avail = chunk_size - n->size();
01757
01758 if(count <= avail)
01759 {
01760
01761
01762
01763
01764
01765
01766
01767
01768
01769
01770
01771
01772
01773
01774
01775
01776
01777
01778
01779 n->insert(first, last, where.offset_);
01780
01781 size_ += last - first;
01782
01783 node_info pred[max_index_levels];
01784
01785 int pred_levels = prednodes(n,pred);
01786
01787
01788
01789 int i = n->levels();
01790
01791 while(i < pred_levels)
01792 {
01793 pred[i].node_->link_[i].width_ += count;
01794 ++i;
01795 }
01796
01797 while(i < active_levels_)
01798 {
01799 level_[i].offset_ += count;
01800 ++i;
01801 }
01802
01803 where.offset_ += count;
01804
01805 return where;
01806 }
01807
01808
01809
01810
01811
01812
01813
01814
01815
01816
01817
01818
01819
01820
01821
01822
01823
01824
01825 split_node(n, where.offset_);
01826
01827 avail = chunk_size - n->size();
01828
01829 if(avail > count)
01830 avail = count;
01831
01832
01833
01834
01835
01836
01837 insert(iterator(n,where.offset_, this, 0), first, first + avail);
01838
01839 where = iterator(n, where.offset_ + avail, this);
01840
01841
01842 first += avail;
01843 count -= avail;
01844
01845 while(count)
01846 {
01847 avail = count > chunk_size ? chunk_size : count;
01848
01849 node *new_node = node::new_node(max_index_levels);
01850
01851 new_node->insert(first, first + avail, 0);
01852
01853 insert_node(n, new_node);
01854
01855 where = iterator(new_node, avail, this);
01856
01857 first += avail;
01858 count -= avail;
01859 }
01860
01861 return where;
01862
01863 }
01864
01865 template<class T>
01866 void
01867 skiprope<T>::
01868 split_node(typename skiprope<T>::node *n, ptrdiff_t offset)
01869
01911
01912 {
01913 if(offset >= n->size())
01914 {
01915 return;
01916 }
01917
01918
01919
01920
01921
01922 node_info pred[max_index_levels];
01923
01924 int pred_levels = prednodes(n, pred);
01925
01926
01927
01928
01929
01930
01931 node *new_node = node::new_node(max_index_levels);
01932
01933 new_node->insert(&(*(n->begin() + offset)),
01934 &(*(n->begin()+n->size())),
01935 0);
01936
01937 ptrdiff_t deleted_amount = n->size() - offset;
01938
01939 n->erase(n->begin() + offset, n->end());
01940
01941
01942
01943
01944 int i;
01945
01946 for(i = n->levels(); i < pred_levels; ++i)
01947 {
01948 pred[i].node_->link_[i].width_ -= deleted_amount;
01949 }
01950
01951 while(i < active_levels_ )
01952 {
01953 level_[i].offset_ -= deleted_amount;
01954 ++i;
01955 }
01956
01957
01958
01959
01960
01961 size_ -= deleted_amount;
01962
01963 insert_node(n, new_node);
01964
01965
01966 }
01967
01968 template<class T>
01969 void skiprope<T>::
01970 erase(typename skiprope<T>::iterator location)
01971 {
01972 node *n = location.node_;
01973
01974
01975
01976
01977
01978
01979 n->erase(location.offset_, 1);
01980 size_ -= 1;
01981
01982 node_info pred[max_index_levels];
01983
01984 int pred_levels = prednodes(n, pred);
01985
01986 int i;
01987
01988
01989 if(n->size() == 0)
01990 {
01991
01992
01993 int n_levels = n->levels();
01994
01995 for(i=0; i < n_levels; ++i)
01996 {
01997
01998 if(n->link_[i].next_)
01999 {
02000 n->link_[i].next_->link_[i].prev_ = n->link_[i].prev_;
02001 }
02002
02003 if(n->link_[i].prev_)
02004 {
02005
02006 n->link_[i].prev_->link_[i].next_ = n->link_[i].next_;
02007 n->link_[i].prev_->link_[i].width_ += n->link_[i].width_;
02008
02009 }
02010
02011 if(n == level_[i].head_)
02012 {
02013 if(n->link_[i].next_)
02014 {
02015 level_[i].head_ = n->link_[i].next_;
02016 level_[i].offset_ += n->link_[i].width_;
02017 }
02018 else
02019 {
02020 level_[i].head_ = 0;
02021 level_[i].offset_ = 0;
02022 if(i < active_levels_)
02023 active_levels_ = i;
02024 }
02025 }
02026 }
02027
02028 for(; i < pred_levels; ++i)
02029 {
02030
02031
02032
02033 if(pred[i].node_->link_[i].next_)
02034 {
02035 pred[i].node_->link_[i].width_ -= 1;
02036 }
02037
02038 }
02039
02040 while(i < active_levels_)
02041 {
02042 level_[i].offset_ -= 1;
02043 ++i;
02044 }
02045
02046 if(n == last_)
02047 {
02048 last_ = n->link_[0].prev_;
02049 }
02050
02051
02052 node::discard(n);
02053 --nodes_;
02054
02055 }
02056 else
02057 {
02058
02059
02060 for(i=n->levels(); i < pred_levels; ++i)
02061 {
02062 pred[i].node_->link_[i].width_ -= 1;
02063 }
02064
02065 while(i < active_levels_)
02066 {
02067 level_[i].offset_ -= 1;
02068 ++i;
02069 }
02070
02071 }
02072
02073 }
02074
02075 }
02076
02077 #endif