skiprope.h

Go to the documentation of this file.
00001 #ifndef SKIPROPE_H_INCLUDED
00002 #define SKIPROPE_H_INCLUDED
00003 
00004 
00005 //
00006 // Copyright 2002, Lowell Boggs Jr.
00007 //
00008 // This file or directory, containing source code for a computer program,
00009 // is Copyrighted by Lowell Boggs, Jr.  987 Regency Drive, Lewisville
00010 // TX (USA), 75067.  You may use, copy, modify, and distribute this
00011 // source file without charge or obligation so long as you agree to
00012 // the following:
00013 //
00014 //  1.  You must indemnify Lowell Boggs against any and all financial
00015 //      obligations caused by its use, misuse, function, or malfunction.
00016 //      Further, you acknowledge that there is no warranty of any kind,
00017 //      whatsoever.
00018 //
00019 //  2.  You agree not to attempt to patent any portion of this original
00020 //      work -- though you may attempt to patent your own extensions to
00021 //      it if you so choose.
00022 //
00023 //  3.  You keep this copyright notice with the file and all copies
00024 //      of the file and do not change it anyway except language translation.
00025 //
00026 // You are responsible for enforcing your own compliance with these
00027 // conditions and may not use this source file if you cannot agree to the
00028 // above terms and conditions.
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) /* bytes, change only for testing */
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 //  A skiprope is an array of pointers to node lists.  The skiprope has
00070 //  approximately vector semantics but instead of random accesses being O(1)
00071 //  they are O(N).  See class skiprope below for more complexity numbers
00072 //
00073 //  All of the nodes appear in array index[0] list.  About 1/6 appear in
00074 //  index[1] list, about 1/36 appear in index[2] list, etc.  This allows for
00075 //  binary searches to find a given address within the simulated vector.
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   // array link_ is defined at the bottom of this structure see note LAST
00149   // about it below
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>; // testing tool
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); // adjust link_[*].width_
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     // pick the level
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     // allocate space
00217 
00218     self *rv = (self*)(new char[ sizeof(self) + (l-1)*sizeof(link_info) ]);
00219 
00220     // construct the data members
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;  // overcome portability issues 
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);   // not implemented, don't use this
00250   void operator delete(void*p); // not implemented, don't use this
00251 
00252 //NOTE(LAST);  The following data structure must be the last piece of data in this structure
00253 //
00254 
00255   link_info link_[1]; // really contains levels_ elements
00256 
00257 // STOP!  See note, "LAST", above
00258 //        Put _no_ data below this line
00259 }; // put no data above this line
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_;  // needed to get end() when out of data
00346 
00347   friend class skiprope_const_iterator<T>;
00348   friend class skiprope<T>;
00349   friend class skiprope_debugger<T>;       // testing tool
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   // The begin and end methods provide a way of finding out the range
00365   // of data quickly addressable by this node.  In other words, an iterator
00366   // has fast access to the data in the node specified during the iterator's
00367   // creation.  If you wish to make use of this faster access, you can use the
00368   // begin and end methods to get iterators to the beginning and ending thereof.
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_;  // ignore rope_
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;  // special cases where searching to the next node is not
00415              // desireable -- used only by skiprope<> to jam in iterators
00416              // that aren't normally valid
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>; // testing tool
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   // The begin and end methods provide a way of finding out the range
00502   // of data quickly addressable by this node.  In other words, an iterator
00503   // has fast access to the data in the node specified during the iterator's
00504   // creation.  If you wish to make use of this faster access, you can use the
00505   // begin and end methods to get iterators to the beginning and ending thereof.
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++();    // pre-increment
00535   self operator++(int);  // post-increment
00536   self &operator--();    // pre-decrement
00537   self operator--(int);  // post-decrement
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_;    // first element at this level
00585   ptrdiff_t   offset_;  // to element at head_ from beginning of skiprope
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>; // testing tool
00642   friend class skiprope_iterator<T>; // needed for implementations below
00643   friend class skiprope_const_iterator<T>; // needed for implementations below
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); // adjusts size_
00726 
00727   void split_node(node *n, ptrdiff_t offset);  // cuts node into 2 pieces
00728                                                // and adjusts
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 { // find
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     // found a row containing the desired offset
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_;  // statistics for tests, etc.
00896     }
00897 
00898 
00899   }
00900 
00901   return end();
00902 
00903 } // find
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 { // find_node_before
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     // found a row containing the desired offset
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 } // find_node_before
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;  // cast away const
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 { // push_back
00968 
00969   ptrdiff_t insert_count = last - first;
00970 
00971   if(last_)
00972   { // use empty space in extant last node
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   } // use empty space in extant last node
00991 
00992   // if we get here, insert_count and first will have been
00993   // adjusted so that we must attend to only that which remains
00994   // to be done
00995 
00996   while(insert_count)
00997   { // append new nodes to end
00998 
00999     node *n = node::new_node(max_index_levels); // nodes_ is inc'd later
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       // inserting the first node
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   } // append new nodes to end
01040 
01041 } // push_back
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     //  copy the current node's info out
01055     //
01056     while( level < n->levels() )
01057     {
01058       pred[level].node_ = n;
01059       ++level;
01060     }
01061 
01062     // if all levels accounted for then quit
01063 
01064     if(level >= active_levels_)
01065       break;
01066 
01067     // otherwise scan backwards along the level of linkage
01068     // in node to find prev guy (this still maintains O(ln(N))
01069     // behavior because we are stepping to ever higher levels
01070     // as soon as one is found -- thus jumping over lower level
01071     // nodes.
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     // scan across then down the levels
01117 
01118     while(n->link_[level].next_ && n != pred[level].node_ )
01119     {
01120       // scan across this level until we find the pred[] entry
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   // first, get the node pointers
01158 
01159   int level=prednodes(n, pred);
01160 
01161 
01162   // then get the offset_'s by scanning along the the horizontal links
01163   // and adding up the distance between jumps.  When there is no next
01164   // node at the level, drop down and scan at that level
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     // link after to its predecessors in those areas
01219     // common to the before and after node
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     // if the after node is higher than all its predecessors
01259     // link the after node into the chains of level_ array
01260     // Here is the kind of thing I'm talking about:
01261     //
01262     //    lvl Nodes
01263     //    ---+------------
01264     //     4|
01265     //     3|             P
01266     //     2|       X     P
01267     //     1|   N   X B   P
01268     //     0| M N O X B A P
01269     //              ^
01270     //  Here, X is inserted after O and it's levels are higher than those
01271     //  of any of its predecessors.  Thus, it must be linked into the
01272     //  level 2 horizontal chain prior to P.
01273     //
01274 
01275     if(after_location < level_[i].offset_)
01276     {
01277       // this guy becomes the first link in the level_ horizontal chain
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       //  In this case, after, has a higher number of levels than before and all of its
01292       //  predecessors.  We must link the new node into the level_[].  Note that this
01293       //  new node will be the first node at this level -- otherwise, predecessors nodes
01294       //  would have taken it into acount
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     // push everyone else out
01316     level_[i].offset_ += after_size;
01317     ++i;
01318   }
01319 
01320   while(active_levels_ < after_levels)
01321   {
01322     // add new levels as needed
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     // this assumes that no node will be 0 length and not be
01388     // erased.
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     // this assumes that no node will be 0 length and not be
01427     // erased.
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     // this assumes that no node will be 0 length and not be
01506     // erased.
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     // this assumes that no node will be 0 length and not be
01542     // erased.
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   // handle the simple case where the new data fits in the first node
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   // handle the case that a new node must be created
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; // should be zero before, but who knows....
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   // finally, handle the case where more data remains to be
01695   // inserted after the newly created node
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   //  handle the easy special cases
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     //  In this case, the inserted data will fit in the specifed node
01762     //  so all we have to do is stick it in and adjust the linkage info.
01763     //  Here is a worst case scenario:
01764     //
01765     //    lvl  Nodes
01766     //    ---+-------------
01767     //     3|             G
01768     //     2|       D     G
01769     //     1|   B   D   F G
01770     //     0| A B C D E F G
01771     //                ^
01772     //                insert into E
01773     //
01774     //  In this case, the link_ info for D must be adjusted for levels
01775     //  1 and 2, and the level_[] info for the skiprope must be adjusted
01776     //  for level 3.
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     // pred[].offset_ not set by this call
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   //  now handle the cases where one or more nodes have to be
01809   //  injected into the list:
01810   //
01811   //      * split where.node_
01812   //
01813   //      * tack as much of the inserted data onto the node as
01814   //        possible
01815   //
01816   //      * insert new nodes for data that overflows the start
01817   //        node
01818   //
01819   //  Update linkages as needed
01820   //
01821 
01822 
01823   // SPLIT WHERE.NODE_
01824 
01825   split_node(n, where.offset_);
01826 
01827   avail = chunk_size - n->size();
01828 
01829   if(avail > count)
01830     avail = count;  // unlikely, but who knows what split_node might do
01831                     // to n.
01832 
01833   // the following iterator construction uses a special skiprope_iterator()
01834   // invocation that lets us force the constructor not to search past the
01835   // empty node we are actually point to.
01836 
01837   insert(iterator(n,where.offset_, this, 0), first, first + avail);
01838 
01839   where = iterator(n, where.offset_ + avail, this);  // will auto wrap to the
01840                                                      // next node
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   // note:  this code doesn't work if n is the last node.  you should
01919   //        be calling push_back to handle that.
01920 
01921 
01922   node_info pred[max_index_levels];
01923 
01924   int pred_levels = prednodes(n, pred); // need nodes and offset info
01925 
01926   //
01927   //  create a new node to put the split off part in.  Copy the
01928   //  data to the new node and remove it from the old
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   //  adjust the tables to account for the loss
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   //  connect the split off part up after original owner
01959   //  in its own node
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   // this code assumes that location has been adjusted such that it does not
01975   // point to the end of a node, but has been adjusted to point to the beginning
01976   // of the next block (iff needed) as is the normal behavior of the iterator
01977   // constructor
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     // erasure resulted in a zero length node:  nuke it
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         // width in 'n' has already had n's size() subtracted out
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_; // n->size is 0, but width may not be
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       // handle the cases where n is shorter than its predecessors
02031       // specifically handle the levels above n
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     // erasure only removed part of the data
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 } // namespace cxxtls
02076 
02077 #endif
Generated on Wed Feb 29 22:50:04 2012 for CXXUtilities by  doxygen 1.6.3