CSIndexedSkipList.h

Go to the documentation of this file.
00001 
00009 // Changes
00010 // Random Access Container
00011 // - return value for operator[] is mapped_type with Pair Associative Containers.
00012 
00013 // DOCS for mainpage etc.
00155 
08514 
08515 
13747 
13748 
13795 template <class T, class R = RNG>
13796 class IndexedSkipList
13797 {
13798 public:
13799   class T0;
13800   class T1;
13801   friend class T0;
13802   friend class T1;
13804   typedef size_t size_type;
13806 
13809   typedef ptrdiff_t difference_type;
13811   typedef IndexedSkipList<T,R> container_type;
13813 
13816   typedef T value_type;
13818   typedef value_type mapped_type;
13820   typedef value_type& mapped_type_reference;
13822   typedef const value_type const_mapped_type;
13824   typedef const value_type& const_mapped_type_reference;
13826   typedef BidiIdxNode<value_type> node_type;
13828 
13833   typedef T0 iterator;
13835   typedef value_type* pointer;
13837   typedef value_type& reference;
13839   typedef const T& const_reference;
13841   typedef T1 const_iterator;
13843 
13846   typedef std::reverse_iterator<iterator> reverse_iterator;
13848   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
13849 
13850 private:
13851   R rng; 
13852   unsigned int maxLevel; 
13853   unsigned int level;    
13854   node_type *head;  
13855   node_type *tail; 
13856   double probability; 
13857   size_type items; 
13858   mutable size_type scan_index; 
13859   mutable std::pair<size_type,node_type*> *update; 
13860 
13862 
13866   void Init(double probability,unsigned int maxLevel) {}
13867 
13869 
13874   node_type* Alloc(unsigned int level, const T &obj) {}
13875 
13877 
13881   node_type* Alloc(unsigned int level) {}
13882 
13884 
13887   void Free(node_type *item) {}
13888 
13890 
13893   unsigned int GenerateRandomLevel() const {}
13894 
13896   void adjust_levels() {}
13897 
13899 
13905   void scan(size_type index) const{}
13906 
13908 
13915   void scan(const iterator &where) const{}
13916 
13917 
13918 public:
13920   struct Prob
13921   {
13922     double probability; 
13923     unsigned int maxLevel; 
13924 
13925     explicit Prob(size_type maxNodes)  {}
13927     Prob(double probability, unsigned int maxLevel) {}
13928   };
13929 
13931 
13934   class T0 : public std::iterator<std::random_access_iterator_tag, value_type>
13935   {
13936   public:
13937     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
13938     typedef std::random_acces_iterator_tag iterator_category;
13939     typedef typename baseclass::value_type value_type;
13940     typedef typename baseclass::value_type* pointer;
13941     typedef typename baseclass::value_type& reference;
13942     typedef ptrdiff_t difference_type;
13943 
13944     friend T1;
13945     friend container_type;
13946   private:
13947     container_type *container; 
13948     mutable size_type Findex; 
13949     node_type* node; 
13950   public:
13952     T0() {}
13954 
13957     T0(const T0 &t0){}
13958 
13960 
13963     T0(const T1 &t1){}
13964 
13966 
13972     T0(container_type *container, node_type* p){}
13973 
13975 
13980     T0(container_type *container, node_type* p, size_type index){}
13981 
13983 
13986     bool operator==(const T0& other) const{}
13987 
13989 
13992     bool operator!=(const T0& other) const{}
13993 
13995 
13998     bool operator==(const T1& other) const{}
13999 
14001 
14004     bool operator!=(const T1& other) const{}
14005 
14007 
14012     T0& operator++(){}
14013 
14015 
14020     T0 operator++(int){}
14021 
14023 
14028     T0& operator--(){}
14029 
14031 
14036     T0 operator--(int){}
14037 
14039 
14044     reference operator*() const{}
14045 
14047 
14052     pointer operator->() const{}
14053 
14055 
14058     bool operator<(const T0 &other) const{}
14059 
14061 
14064     bool operator<=(const T0 &other) const{}
14065 
14067 
14070     bool operator>(const T0 &other) const{}
14071 
14073 
14076     bool operator>=(const T0 &other) const{}
14077 
14079 
14082     bool operator<(const T1 &other) const{}
14083 
14085 
14088     bool operator<=(const T1 &other) const{}
14089 
14091 
14094     bool operator>(const T1 &other) const{}
14095 
14097 
14100     bool operator>=(const T1 &other) const{}
14101 
14103 
14107     T0 operator+(difference_type off) const{}
14108 
14110 
14114     T0 operator-(difference_type off) const{}
14115 
14117 
14121     T0& operator+=(difference_type off){}
14122 
14124 
14128     T0& operator-=(difference_type off){}
14129 
14131 
14135     difference_type operator-(const T0 &other) const{}
14136 
14138 
14142     difference_type operator-(const T1 &other) const{}
14143 
14145 
14151     size_type refresh(){}
14152 
14154 
14158     value_type& operator[](difference_type off) const{}
14159 
14161 
14164     size_type getIndex() const{}
14165   };
14166 
14168 
14171   class T1 : public std::iterator<std::random_access_iterator_tag, value_type, ptrdiff_t, const value_type*, const value_type&>
14172   {
14173   public:
14174     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
14175     typedef std::random_acces_iterator_tag iterator_category;
14176     typedef typename baseclass::value_type value_type;
14177     typedef typename const baseclass::value_type* pointer;
14178     typedef typename const baseclass::value_type& reference;
14179     typedef ptrdiff_t difference_type;
14180 
14181     friend T0;
14182     friend container_type;
14183   private:
14184     const container_type *container; 
14185     mutable size_type Findex; 
14186     const node_type* node; 
14187   public:
14188 
14190     T1() {}
14191 
14193 
14196     T1(const T1 &t1){}
14197 
14199 
14202     T1(const T0 &t0){}
14203 
14205 
14211     T1(container_type *container, node_type* p){}
14212 
14214 
14219     T1(container_type *container, node_type* p, size_type index){}
14220 
14222 
14225     bool operator==(const T0& other) const{}
14226 
14228 
14231     bool operator!=(const T0& other) const{}
14232 
14234 
14237     bool operator==(const T1& other) const{}
14238 
14240 
14243     bool operator!=(const T1& other) const{}
14244 
14246 
14251     T1& operator++(){}
14252 
14254 
14259     T1 operator++(int){}
14260 
14262 
14267     T1& operator--(){}
14268 
14270 
14275     T1 operator--(int){}
14276 
14278 
14283     reference operator*() const{}
14284 
14286 
14291     pointer operator->() const{}
14292 
14294 
14297     bool operator<(const T0 &other) const{}
14298 
14300 
14303     bool operator<=(const T0 &other) const{}
14304 
14306 
14309     bool operator>(const T0 &other) const{}
14310 
14312 
14315     bool operator>=(const T0 &other) const{}
14316 
14318 
14321     bool operator<(const T1 &other) const{}
14322 
14324 
14327     bool operator<=(const T1 &other) const{}
14328 
14330 
14333     bool operator>(const T1 &other) const{}
14334 
14336 
14339     bool operator>=(const T1 &other) const{}
14340 
14342 
14346     T1 operator+(difference_type off) const{}
14347 
14349 
14353     T1 operator-(difference_type off) const{}
14354 
14356 
14360     T1& operator+=(difference_type off){}
14361 
14363 
14367     T1& operator-=(difference_type off){}
14368 
14370 
14374     difference_type operator-(const T0 &other) const{}
14375 
14377 
14381     difference_type operator-(const T1 &other) const{}
14382 
14384 
14390     size_type refresh(){}
14391 
14393 
14397     value_type& operator[](difference_type off) const{}
14398 
14400 
14403     size_type getIndex() const{}
14404 
14405   };
14406 
14407 
14409 
14413   IndexedSkipList(){}
14414 
14416 
14420   IndexedSkipList(double probability, unsigned int maxLevel){}
14421 
14423 
14428   IndexedSkipList(const container_type &source){}
14429 
14431 
14438   template<class InIt> IndexedSkipList(InIt first, InIt last){}
14439 
14441 
14447   template<class InIt> IndexedSkipList(InIt first, InIt last, double probability, unsigned int maxLevel){}
14448 
14450 
14458   template<class InIt> IndexedSkipList(InIt first, InIt last, size_type maxNodes){}
14459 
14461 
14467   explicit IndexedSkipList(size_type count) {}
14468 
14469 
14471 
14478   IndexedSkipList(size_type count, const T& val) {}
14479 
14481 
14490   IndexedSkipList(size_type count, const T& val, double probability, unsigned int maxLevel) {}
14491 
14493 
14501   IndexedSkipList(size_type count, const T& val, size_type maxNodes) {}
14502 
14504 
14507   IndexedSkipList(const Prob &prob) {}
14508 
14510 
14514   IndexedSkipList(size_type count, const Prob &prob) {}
14515 
14517 
14522   IndexedSkipList(size_type count, const T& val, const Prob &prob) {}
14523 
14525 
14530   template<class InIt> IndexedSkipList(InIt first, InIt last, const Prob &prob) {}
14531 
14533 
14536   ~IndexedSkipList(){}
14537 
14538 
14540 
14546   container_type& operator=(const container_type &source){}
14547 
14549 
14552   iterator begin(){}
14553 
14555 
14558   iterator end(){}
14559 
14561 
14564   const_iterator begin() const{}
14565 
14567 
14570   const_iterator end() const{}
14571 
14573 
14576   reverse_iterator rbegin(){}
14577 
14579 
14582   reverse_iterator rend(){}
14583 
14585 
14588   const_reverse_iterator rbegin() const{}
14589 
14591 
14594   const_reverse_iterator rend() const{}
14595 
14597 
14600   size_type size() const{}
14601 
14603 
14606   bool empty() const{}
14607 
14609 
14612   reference front(){}
14613 
14615 
14618   const_reference front() const{}
14619 
14621 
14624   reference back(){}
14625 
14627 
14630   const_reference back() const{}
14631 
14633 
14636   void push_front(const value_type &val){}
14637 
14639   void pop_front(){}
14640 
14642   void destroy_front(){}
14643 
14645 
14648   void push_back(const value_type &val){}
14649 
14651   void pop_back(){}
14652 
14654   void destroy_back(){}
14655 
14657 
14661   template<class InIt> void assign(InIt first, InIt last){}
14662 
14663 
14665 
14669   void assign(size_type count, const T& val) {}
14670 
14672 
14677   iterator insert(const iterator &where, const value_type& val){}
14678 
14680 
14685   void insert(const iterator &where, size_type count, const T& val){}
14686 
14688 
14693   template<class InIt> void insert(const iterator &where, InIt first, InIt last){}
14694 
14696   void clear(){}
14697 
14699   void destroy(){}
14700 
14702 
14706   iterator erase(const iterator &where){}
14707 
14709 
14713   iterator destroy(const iterator &where){}
14714 
14716 
14723   iterator erase(const iterator &first, const iterator &last){}
14724 
14726 
14733   iterator destroy(const iterator &first, const iterator &last){}
14734 
14736 
14740   iterator erase_index(size_type index);
14741 
14743 
14747   iterator destroy_index(size_type index);
14748 
14750   void resize(size_type newsize){}
14751 
14753   void resize(size_type newsize, const value_type &val){}
14754 
14756 
14759   void swap(container_type& right) {}
14760 
14762 
14765   template<class Pr1> void erase_if(Pr1 pred);
14766 
14768 
14771   template<class Pr4> void destroy_if(Pr4 pred);
14772 
14774 
14785   void cut(const iterator &first, const iterator &last, container_type& right);
14786 
14788 
14794   mapped_type_reference operator[](size_type index){}
14795 
14797 
14803   const_mapped_type_reference operator[](size_type index) const{}
14804 
14806 
14812   mapped_type_reference at(size_type off){}
14813 
14815 
14821   const_mapped_type_reference at(size_type off) const{}
14822 
14824   size_type max_size() const{}
14825 
14827 
14834   mapped_type& value(value_type& value) {}
14835 
14837 
14840   void reverse(){}
14841 
14843 
14849   void unique(){}
14850 
14852 
14860   template<class Pr2> void unique(Pr2 pred){}
14861 
14863 
14870   void sort(){}
14871 
14873 
14882   template<class Pr3> void sort(Pr3 pred){}
14883 
14885 
14892   void stable_sort(){}
14893 
14895 
14902   template<class Pr3> void stable_sort(Pr3 pred){}
14903 
14905 
14912   void erase_value(const value_type& val){}
14913 
14915 
14923   void splice(const iterator &where, container_type& right){}
14924 
14926 
14935   void splice(const iterator &where, container_type& right, iterator first){}
14936 
14938 
14947   void splice(const iterator &where, container_type& right, iterator first, iterator last){}
14948 };
14949 
14951 
14956 template <class T, class R>
14957 bool operator==(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
14958 {
14959   return ((left.size() == right.size()) &&
14960           (std::equal(left.begin(), left.end(), right.begin())));
14961 
14962 }
14963 
14965 
14970 template <class T, class R>
14971 bool operator!=(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
14972 {
14973   return !(left==right);
14974 }
14975 
14977 
14982 template <class T, class R>
14983 bool operator<(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
14984 {
14985   return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
14986 }
14987 
14989 
14994 template <class T, class R>
14995 bool operator<=(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
14996 {
14997   return !(right < left);
14998 }
14999 
15001 
15006 template <class T, class R>
15007 bool operator>(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
15008 {
15009   return (right < left);
15010 }
15011 
15013 
15018 template <class T, class R>
15019 bool operator>=(const IndexedSkipList<T,R> &left, const IndexedSkipList<T,R> &right)
15020 {
15021   return !(left < right);
15022 }
15023 
15025 
15072 template <class T, class R = RNG>
15073 class IndexedSSkipList
15074 {
15075 public:
15076   class T0;
15077   class T1;
15078   friend class T0;
15079   friend class T1;
15080 
15082   typedef size_t size_type;
15084 
15087   typedef ptrdiff_t difference_type;
15089   typedef IndexedSSkipList<T,R> container_type;
15091 
15094   typedef T value_type;
15096   typedef value_type mapped_type;
15098   typedef value_type& mapped_type_reference;
15100   typedef const value_type const_mapped_type;
15102   typedef const value_type& const_mapped_type_reference;
15104   typedef ForwardIdxNode<value_type> node_type;
15106 
15111   typedef T0 iterator;
15113   typedef value_type* pointer;
15115   typedef value_type& reference;
15117   typedef const T& const_reference;
15119   typedef T1 const_iterator;
15121 
15124   typedef std::reverse_iterator<iterator> reverse_iterator;
15126   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
15127 
15128 private:
15129   R rng; 
15130   unsigned int maxLevel; 
15131   unsigned int level;    
15132   node_type *head;  
15133   node_type *tail; 
15134   double probability; 
15135   size_type items; 
15136   mutable size_type scan_index; 
15137   mutable std::pair<size_type,node_type*> *update; 
15138 
15140 
15144   void Init(double probability,unsigned int maxLevel) {}
15145 
15147 
15152   node_type* Alloc(unsigned int level, const T &obj) {}
15153 
15155 
15159   node_type* Alloc(unsigned int level) {}
15160 
15162 
15165   void Free(node_type *item) {}
15166 
15168 
15171   unsigned int GenerateRandomLevel() const {}
15172 
15174   void adjust_levels() {}
15175 
15177 
15183   void scan(size_type index) const{}
15184 
15186 
15193   void scan(const iterator &where) const{}
15194 
15195 
15196 
15197 public:
15198 
15200   struct Prob
15201   {
15202     double probability; 
15203     unsigned int maxLevel; 
15204 
15205     explicit Prob(size_type maxNodes)  {}
15207     Prob(double probability, unsigned int maxLevel) {}
15208   };
15209 
15211 
15214   class T0 : public std::iterator<std::random_access_iterator_tag, value_type>
15215   {
15216   public:
15217     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
15218     typedef std::random_acces_iterator_tag iterator_category;
15219     typedef typename baseclass::value_type value_type;
15220     typedef typename baseclass::value_type* pointer;
15221     typedef typename baseclass::value_type& reference;
15222     typedef ptrdiff_t difference_type;
15223 
15224     friend T1;
15225     friend container_type;
15226   private:
15227     container_type *container; 
15228     mutable size_type Findex; 
15229     node_type* node; 
15230   public:
15232     T0() {}
15233 
15235 
15238     T0(const T0 &t0){}
15239 
15241 
15244     T0(const T1 &t1){}
15245 
15247 
15253     T0(container_type *container, node_type* p){}
15254 
15256 
15261     T0(container_type *container, node_type* p, size_type index){}
15262 
15264 
15267     bool operator==(const T0& other) const{}
15268 
15270 
15273     bool operator!=(const T0& other) const{}
15274 
15276 
15279     bool operator==(const T1& other) const{}
15280 
15282 
15285     bool operator!=(const T1& other) const{}
15286 
15288 
15293     T0& operator++(){}
15294 
15296 
15301     T0 operator++(int){}
15302 
15304 
15309     T0& operator--(){}
15310 
15312 
15317     T0 operator--(int){}
15318 
15320 
15325     value_type& operator*() const{}
15326 
15328 
15333     value_type* operator->() const{}
15334 
15336 
15339     bool operator<(const T0 &other) const{}
15340 
15342 
15345     bool operator<=(const T0 &other) const{}
15346 
15348 
15351     bool operator>(const T0 &other) const{}
15352 
15354 
15357     bool operator>=(const T0 &other) const{}
15358 
15360 
15363     bool operator<(const T1 &other) const{}
15364 
15366 
15369     bool operator<=(const T1 &other) const{}
15370 
15372 
15375     bool operator>(const T1 &other) const{}
15376 
15378 
15381     bool operator>=(const T1 &other) const{}
15382 
15384 
15388     T0 operator+(difference_type off) const{}
15389 
15391 
15395     T0 operator-(difference_type off) const{}
15396 
15398 
15402     T0& operator+=(difference_type off){}
15403 
15405 
15409     T0& operator-=(difference_type off){}
15410 
15412 
15416     difference_type operator-(const T0 &other) const{}
15417 
15419 
15423     difference_type operator-(const T1 &other) const{}
15424 
15426 
15432     size_type refresh(){}
15433 
15435 
15439     value_type& operator[](difference_type off) const{}
15440 
15442 
15445     size_type getIndex() const{}
15446   };
15447 
15449 
15452   class T1 : public std::iterator<std::random_access_iterator_tag, value_type>
15453   {
15454   public:
15455     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
15456     typedef std::random_acces_iterator_tag iterator_category;
15457     typedef typename baseclass::value_type value_type;
15458     typedef typename const baseclass::value_type* pointer;
15459     typedef typename const baseclass::value_type& reference;
15460     typedef ptrdiff_t difference_type;
15461 
15462     friend T0;
15463     friend container_type;
15464   private:
15465     const container_type *container; 
15466     mutable size_type Findex; 
15467     const node_type* node; 
15468   public:
15470     T1() {}
15471 
15473 
15476     T1(const T1 &t1){}
15477 
15479 
15482     T1(const T0 &t0){}
15483 
15485 
15491     T1(container_type *container, node_type* p){}
15492 
15494 
15499     T1(container_type *container, node_type* p, size_type index){}
15500 
15502 
15505     bool operator==(const T0& other) const{}
15506 
15508 
15511     bool operator!=(const T0& other) const{}
15512 
15514 
15517     bool operator==(const T1& other) const{}
15518 
15520 
15523     bool operator!=(const T1& other) const{}
15524 
15526 
15531     T1& operator++(){}
15532 
15534 
15539     T1 operator++(int){}
15540 
15542 
15547     T1& operator--(){}
15548 
15550 
15555     T1 operator--(int){}
15556 
15558 
15563     value_type& operator*() const{}
15564 
15566 
15571     value_type* operator->() const{}
15572 
15574 
15577     bool operator<(const T0 &other) const{}
15578 
15580 
15583     bool operator<=(const T0 &other) const{}
15584 
15586 
15589     bool operator>(const T0 &other) const{}
15590 
15592 
15595     bool operator>=(const T0 &other) const{}
15596 
15598 
15601     bool operator<(const T1 &other) const{}
15602 
15604 
15607     bool operator<=(const T1 &other) const{}
15608 
15610 
15613     bool operator>(const T1 &other) const{}
15614 
15616 
15619     bool operator>=(const T1 &other) const{}
15620 
15622 
15626     T1 operator+(difference_type off) const{}
15627 
15629 
15633     T1 operator-(difference_type off) const{}
15634 
15636 
15640     T1& operator+=(difference_type off){}
15641 
15643 
15647     T1& operator-=(difference_type off){}
15648 
15650 
15654     difference_type operator-(const T0 &other) const{}
15655 
15657 
15661     difference_type operator-(const T1 &other) const{}
15662 
15664 
15670     size_type refresh(){}
15671 
15673 
15677     value_type& operator[](difference_type off) const{}
15678 
15680 
15683     size_type getIndex() const{}
15684 
15685   };
15686 
15688 
15692   IndexedSSkipList(){}
15693 
15695 
15699   IndexedSSkipList(double probability, unsigned int maxLevel){}
15700 
15702 
15707   IndexedSSkipList(const container_type &source){}
15708 
15710 
15717   template<class InIt> IndexedSSkipList(InIt first, InIt last){}
15718 
15720 
15726   template<class InIt> IndexedSSkipList(InIt first, InIt last, double probability, unsigned int maxLevel){}
15727 
15729 
15737   template<class InIt> IndexedSSkipList(InIt first, InIt last, size_type maxNodes){}
15738 
15740 
15746   explicit IndexedSSkipList(size_type count) {}
15747 
15748 
15750 
15757   IndexedSSkipList(size_type count, const T& val) {}
15758 
15760 
15769   IndexedSSkipList(size_type count, const T& val, double probability, unsigned int maxLevel) {}
15770 
15772 
15780   IndexedSSkipList(size_type count, const T& val, size_type maxNodes) {}
15781 
15783 
15786   IndexedSSkipList(const Prob &prob) {}
15787 
15789 
15793   IndexedSSkipList(size_type count, const Prob &prob) {}
15794 
15796 
15801   IndexedSSkipList(size_type count, const T& val, const Prob &prob) {}
15802 
15804 
15809   template<class InIt> IndexedSSkipList(InIt first, InIt last, const Prob &prob) {}
15810 
15812 
15815   ~IndexedSSkipList(){}
15816 
15818 
15824   container_type& operator=(const container_type &source){}
15825 
15827 
15830   iterator begin(){}
15831 
15833 
15836   iterator end(){}
15837 
15839 
15842   const_iterator begin() const{}
15843 
15845 
15848   const_iterator end() const{}
15849 
15851 
15854   reverse_iterator rbegin(){}
15855 
15857 
15860   reverse_iterator rend(){}
15861 
15863 
15866   const_reverse_iterator rbegin() const{}
15867 
15869 
15872   const_reverse_iterator rend() const{}
15873 
15875 
15878   size_type size() const{}
15879 
15881 
15884   bool empty() const{}
15885 
15887 
15890   reference front(){}
15891 
15893 
15896   const_reference front() const{}
15897 
15899 
15902   reference back(){}
15903 
15905 
15908   const_reference back() const{}
15909 
15911 
15914   void push_front(const value_type &val){}
15915 
15917   void pop_front(){}
15918 
15920   void destroy_front(){}
15921 
15923 
15926   void push_back(const value_type &val){}
15927 
15929   void pop_back(){}
15930 
15932   void destroy_back(){}
15933 
15935 
15939   template<class InIt> void assign(InIt first, InIt last){}
15940 
15941 
15943 
15947   void assign(size_type count, const T& val) {}
15948 
15950 
15955   iterator insert(const iterator &where, const value_type& val){}
15956 
15958 
15963   void insert(const iterator &where, size_type count, const T& val){}
15964 
15966 
15971   template<class InIt> void insert(const iterator &where, InIt first, InIt last){}
15972 
15974   void clear(){}
15975 
15977   void destroy(){}
15978 
15980   iterator erase(const iterator &where){}
15981 
15983   iterator destroy(const iterator &where){}
15984 
15986 
15993   iterator erase(const iterator &first, const iterator &last){}
15994 
15996 
16003   iterator destroy(const iterator &first, const iterator &last){}
16004 
16006 
16010   iterator erase_index(size_type index);
16011 
16013 
16017   iterator destroy_index(size_type index);
16018 
16020   void resize(size_type newsize){}
16021 
16023   void resize(size_type newsize, const value_type &val){}
16024 
16026 
16029   void swap(container_type& right) {}
16030 
16032 
16035   template<class Pr1> void erase_if(Pr1 pred);
16036 
16038 
16041   template<class Pr4> void destroy_if(Pr4 pred);
16042 
16044 
16055   void cut(const iterator &first, const iterator &last, container_type& right);
16056 
16058 
16064   mapped_type_reference operator[](size_type index){}
16065 
16067 
16073   const_mapped_type_reference operator[](size_type index) const{}
16074 
16076 
16082   mapped_type_reference at(size_type off){}
16083 
16085 
16091   const_mapped_type_reference at(size_type off) const{}
16092 
16094   size_type max_size() const{}
16095 
16097 
16104   mapped_type& value(value_type& value) {}
16105 
16107 
16115   void reverse(){}
16116 
16118 
16127   void unique(){}
16128 
16130 
16142   template<class Pr2> void unique(Pr2 pred){}
16143 
16145 
16152   void sort(){}
16154 
16163   template<class Pr3> void sort(Pr3 pred){}
16164 
16166 
16173   void stable_sort(){}
16174 
16176 
16185   template<class Pr3> void stable_sort(Pr3 pred){}
16186 //***
16187 
16189 
16198   void erase_value(const value_type& val){}
16199 
16201 
16209   void splice(const iterator &where, container_type& right){}
16210 
16212 
16221   void splice(const iterator &where, container_type& right, iterator first){}
16222 
16224 
16233   void splice(const iterator &where, container_type& right, iterator first, iterator last){}
16234 
16235 };
16236 
16238 
16243 template <class T, class R>
16244 bool operator==(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16245 {
16246   return ((left.size() == right.size()) &&
16247           (std::equal(left.begin(), left.end(), right.begin())));
16248 
16249 }
16250 
16252 
16257 template <class T, class R>
16258 bool operator!=(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16259 {
16260   return !(left==right);
16261 }
16262 
16264 
16269 template <class T, class R>
16270 bool operator<(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16271 {
16272   return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
16273 }
16274 
16276 
16281 template <class T, class R>
16282 bool operator<=(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16283 {
16284   return !(right < left);
16285 }
16286 
16288 
16293 template <class T, class R>
16294 bool operator>(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16295 {
16296   return (right < left);
16297 }
16298 
16300 
16305 template <class T, class R>
16306 bool operator>=(const IndexedSSkipList<T,R> &left, const IndexedSSkipList<T,R> &right)
16307 {
16308   return !(left < right);
16309 }
16310 
16311 
16313 
16362 template <class T, class R = RNG>
16363 class IndexedTinySkipList
16364 {
16365 public:
16366   class T0;
16367   class T1;
16368   friend class T0;
16369   friend class T1;
16370 
16372   typedef size_t size_type;
16374 
16377   typedef ptrdiff_t difference_type;
16379   typedef IndexedTinySkipList<T,R> container_type;
16381 
16384   typedef T value_type;
16386   typedef value_type mapped_type;
16388   typedef value_type& mapped_type_reference;
16390   typedef const value_type const_mapped_type;
16392   typedef const value_type& const_mapped_type_reference;
16394   typedef ForwardTinyNode<value_type> node_type;
16396 
16401   typedef T0 iterator;
16403   typedef value_type* pointer;
16405   typedef value_type& reference;
16407   typedef const T& const_reference;
16409   typedef T1 const_iterator;
16411 
16414   typedef std::reverse_iterator<iterator> reverse_iterator;
16416   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
16417 
16418 private:
16419   R rng; 
16420   unsigned int maxLevel; 
16421   unsigned int level;    
16422   node_type *head;  
16423   node_type *tail; 
16424   double probability; 
16425   size_type items; 
16426   mutable size_type scan_index; 
16427   mutable std::pair<size_type,node_type*> *update; 
16428 
16430 
16434   void Init(double probability,unsigned int maxLevel) {}
16435 
16437 
16442   node_type* Alloc(unsigned int level, const T &obj) {}
16443 
16445 
16449   node_type* Alloc(unsigned int level) {}
16450 
16452 
16455   void Free(node_type *item) {}
16456 
16458 
16461   unsigned int GenerateRandomLevel() const {}
16462 
16464   void adjust_levels() {}
16465 
16467 
16473   void scan(size_type index) const{}
16474 
16476 
16483   void scan(const iterator &where) const{}
16484 
16486   struct Prob
16487   {
16488     double probability; 
16489     unsigned int maxLevel; 
16490 
16491     explicit Prob(size_type maxNodes)  {}
16493     Prob(double probability, unsigned int maxLevel) {}
16494   };
16495 
16496 
16497 public:
16498 
16500 
16503   class T0 : public std::iterator<std::random_access_iterator_tag, value_type>
16504   {
16505   public:
16506     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
16507     typedef std::random_acces_iterator_tag iterator_category;
16508     typedef typename baseclass::value_type value_type;
16509     typedef typename baseclass::value_type* pointer;
16510     typedef typename baseclass::value_type& reference;
16511     typedef ptrdiff_t difference_type;
16512 
16513     friend T1;
16514     friend container_type;
16515   private:
16516     container_type *container; 
16517     mutable size_type Findex; 
16518     node_type* node; 
16519   public:
16521     T0() {}
16522 
16524 
16527     T0(const T0 &t0){}
16528 
16530 
16533     T0(const T1 &t1){}
16534 
16536 
16542     T0(container_type *container, node_type* p){}
16543 
16545 
16550     T0(container_type *container, node_type* p, size_type index){}
16551 
16553 
16556     bool operator==(const T0& other) const{}
16557 
16559 
16562     bool operator!=(const T0& other) const{}
16563 
16565 
16568     bool operator==(const T1& other) const{}
16569 
16571 
16574     bool operator!=(const T1& other) const{}
16575 
16577 
16582     T0& operator++(){}
16583 
16585 
16590     T0 operator++(int){}
16591 
16593 
16598     T0& operator--(){}
16599 
16601 
16606     T0 operator--(int){}
16607 
16609 
16614     value_type& operator*() const{}
16615 
16617 
16622     value_type* operator->() const{}
16623 
16625 
16628     bool operator<(const T0 &other) const{}
16629 
16631 
16634     bool operator<=(const T0 &other) const{}
16635 
16637 
16640     bool operator>(const T0 &other) const{}
16641 
16643 
16646     bool operator>=(const T0 &other) const{}
16647 
16649 
16652     bool operator<(const T1 &other) const{}
16653 
16655 
16658     bool operator<=(const T1 &other) const{}
16659 
16661 
16664     bool operator>(const T1 &other) const{}
16665 
16667 
16670     bool operator>=(const T1 &other) const{}
16671 
16673 
16677     T0 operator+(difference_type off) const{}
16678 
16680 
16684     T0 operator-(difference_type off) const{}
16685 
16687 
16691     T0& operator+=(difference_type off){}
16692 
16694 
16698     T0& operator-=(difference_type off){}
16699 
16701 
16705     difference_type operator-(const T0 &other) const{}
16706 
16708 
16712     difference_type operator-(const T1 &other) const{}
16713 
16715 
16721     size_type refresh(){}
16722 
16724 
16728     value_type& operator[](difference_type off) const{}
16729 
16731 
16734     size_type getIndex() const{}
16735   };
16736 
16738 
16741   class T1 : public std::iterator<std::random_access_iterator_tag, value_type>
16742   {
16743   public:
16744     typedef std::iterator<std::random_access_iterator_tag, value_type> baseclass;
16745     typedef std::random_acces_iterator_tag iterator_category;
16746     typedef typename baseclass::value_type value_type;
16747     typedef typename const baseclass::value_type* pointer;
16748     typedef typename const baseclass::value_type& reference;
16749     typedef ptrdiff_t difference_type;
16750 
16751     friend T0;
16752     friend container_type;
16753   private:
16754     const container_type *container; 
16755     mutable size_type Findex; 
16756     const node_type* node; 
16757   public:
16759     T1() {}
16760 
16762 
16765     T1(const T1 &t1){}
16766 
16768 
16771     T1(const T0 &t0){}
16772 
16774 
16780     T1(container_type *container, node_type* p){}
16781 
16783 
16788     T1(container_type *container, node_type* p, size_type index){}
16789 
16791 
16794     bool operator==(const T0& other) const{}
16795 
16797 
16800     bool operator!=(const T0& other) const{}
16801 
16803 
16806     bool operator==(const T1& other) const{}
16807 
16809 
16812     bool operator!=(const T1& other) const{}
16813 
16815 
16820     T1& operator++(){}
16821 
16823 
16828     T1 operator++(int){}
16829 
16831 
16836     T1& operator--(){}
16837 
16839 
16844     T1 operator--(int){}
16845 
16847 
16852     value_type& operator*() const{}
16853 
16855 
16860     value_type* operator->() const{}
16861 
16863 
16866     bool operator<(const T0 &other) const{}
16867 
16869 
16872     bool operator<=(const T0 &other) const{}
16873 
16875 
16878     bool operator>(const T0 &other) const{}
16879 
16881 
16884     bool operator>=(const T0 &other) const{}
16885 
16887 
16890     bool operator<(const T1 &other) const{}
16891 
16893 
16896     bool operator<=(const T1 &other) const{}
16897 
16899 
16902     bool operator>(const T1 &other) const{}
16903 
16905 
16908     bool operator>=(const T1 &other) const{}
16909 
16911 
16915     T1 operator+(difference_type off) const{}
16916 
16918 
16922     T1 operator-(difference_type off) const{}
16923 
16925 
16929     T1& operator+=(difference_type off){}
16930 
16932 
16936     T1& operator-=(difference_type off){}
16937 
16939 
16943     difference_type operator-(const T0 &other) const{}
16944 
16946 
16950     difference_type operator-(const T1 &other) const{}
16951 
16953 
16959     size_type refresh(){}
16960 
16962 
16966     value_type& operator[](difference_type off) const{}
16967 
16969 
16972     size_type getIndex() const{}
16973 
16974   };
16975 
16977 
16981   IndexedTinySkipList(){}
16982 
16984 
16988   IndexedTinySkipList(double probability, unsigned int maxLevel){}
16989 
16991 
16996   IndexedTinySkipList(const container_type &source){}
16997 
16999 
17006   template<class InIt> IndexedTinySkipList(InIt first, InIt last){}
17007 
17009 
17015   template<class InIt> IndexedTinySkipList(InIt first, InIt last, double probability, unsigned int maxLevel){}
17016 
17018 
17026   template<class InIt> IndexedTinySkipList(InIt first, InIt last, size_type maxNodes){}
17027 
17029 
17035   explicit IndexedTinySkipList(size_type count) {}
17036 
17037 
17039 
17046   IndexedTinySkipList(size_type count, const T& val) {}
17047 
17049 
17058   IndexedTinySkipList(size_type count, const T& val, double probability, unsigned int maxLevel) {}
17059 
17061 
17069   IndexedTinySkipList(size_type count, const T& val, size_type maxNodes) {}
17070 
17072 
17075   IndexedTinySkipList(const Prob &prob) {}
17076 
17078 
17082   IndexedTinySkipList(size_type count, const Prob &prob) {}
17083 
17085 
17090   IndexedTinySkipList(size_type count, const T& val, const Prob &prob) {}
17091 
17093 
17098   template<class InIt> IndexedTinySkipList(InIt first, InIt last, const Prob &prob) {}
17099 
17101 
17104   ~IndexedTinySkipList(){}
17105 
17107 
17113   container_type& operator=(const container_type &source){}
17114 
17116 
17119   iterator begin(){}
17120 
17122 
17125   iterator end(){}
17126 
17128 
17131   const_iterator begin() const{}
17132 
17134 
17137   const_iterator end() const{}
17138 
17140 
17143   reverse_iterator rbegin(){}
17144 
17146 
17149   reverse_iterator rend(){}
17150 
17152 
17155   const_reverse_iterator rbegin() const{}
17156 
17158 
17161   const_reverse_iterator rend() const{}
17162 
17164 
17167   size_type size() const{}
17168 
17170 
17173   bool empty() const{}
17174 
17176 
17179   reference front(){}
17180 
17182 
17185   const_reference front() const{}
17186 
17188 
17191   reference back(){}
17192 
17194 
17197   const_reference back() const{}
17198 
17200 
17203   void push_front(const value_type &val){}
17204 
17206   void pop_front(){}
17207 
17209   void destroy_front(){}
17210 
17212 
17215   void push_back(const value_type &val){}
17216 
17218   void pop_back(){}
17219 
17221   void destroy_back(){}
17222 
17224 
17228   template<class InIt> void assign(InIt first, InIt last){}
17229 
17230 
17232 
17236   void assign(size_type count, const T& val) {}
17237 
17239 
17244   iterator insert(const iterator &where, const value_type& val){}
17245 
17247 
17252   void insert(const iterator &where, size_type count, const T& val){}
17253 
17255 
17260   template<class InIt> void insert(const iterator &where, InIt first, InIt last){}
17261 
17263   void clear(){}
17264 
17266   void destroy(){}
17267 
17269   iterator erase(const iterator &where){}
17270 
17272   iterator destroy(const iterator &where){}
17273 
17275 
17282   iterator erase(const iterator &first, const iterator &last){}
17283 
17285 
17292   iterator destroy(const iterator &first, const iterator &last){}
17293 
17295 
17299   iterator erase_index(size_type index);
17300 
17302 
17306   iterator destroy_index(size_type index);
17307 
17309   void resize(size_type newsize){}
17310 
17312   void resize(size_type newsize, const value_type &val){}
17313 
17315 
17318   void swap(container_type& right) {}
17319 
17321 
17324   template<class Pr1> void erase_if(Pr1 pred);
17325 
17327 
17330   template<class Pr4> void destroy_if(Pr4 pred);
17331 
17333 
17344   void cut(const iterator &first, const iterator &last, container_type& right);
17345 
17347 
17353   mapped_type_reference operator[](size_type index){}
17354 
17356 
17362   const_mapped_type_reference operator[](size_type index) const{}
17363 
17365 
17371   mapped_type_reference at(size_type off){}
17372 
17374 
17380   const_mapped_type_reference at(size_type off) const{}
17381 
17383   size_type max_size() const{}
17384 
17386 
17393   mapped_type& value(value_type& value) {}
17394 
17396 
17404   void reverse(){}
17405 
17407 
17416   void unique(){}
17417 
17419 
17431   template<class Pr2> void unique(Pr2 pred){}
17432 
17434 
17441   void sort(){}
17443 
17452   template<class Pr3> void sort(Pr3 pred){}
17453 
17455 
17462   void stable_sort(){}
17463 
17465 
17474   template<class Pr3> void stable_sort(Pr3 pred){}
17475 
17477 
17486   void erase_value(const value_type& val){}
17487 
17489 
17497   void splice(const iterator &where, container_type& right){}
17498 
17500 
17509   void splice(const iterator &where, container_type& right, iterator first){}
17510 
17512 
17521   void splice(const iterator &where, container_type& right, iterator first, iterator last){}
17522 
17523 };
17524 
17526 
17531 template <class T, class R>
17532 bool operator==(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17533 {
17534   return ((left.size() == right.size()) &&
17535           (std::equal(left.begin(), left.end(), right.begin())));
17536 
17537 }
17538 
17540 
17545 template <class T, class R>
17546 bool operator!=(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17547 {
17548   return !(left==right);
17549 }
17550 
17552 
17557 template <class T, class R>
17558 bool operator<(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17559 {
17560   return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
17561 }
17562 
17564 
17569 template <class T, class R>
17570 bool operator<=(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17571 {
17572   return !(right < left);
17573 }
17574 
17576 
17581 template <class T, class R>
17582 bool operator>(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17583 {
17584   return (right < left);
17585 }
17586 
17588 
17593 template <class T, class R>
17594 bool operator>=(const IndexedTinySkipList<T,R> &left, const IndexedTinySkipList<T,R> &right)
17595 {
17596   return !(left < right);
17597 }
17598 
 All Classes Files Functions Variables Typedefs