CSKeyedSkipList.h

Go to the documentation of this file.

template <class K, class T, class Pr = std::less<K>, class R = RNG >
class KeyedSkipList
{
public:
  class T0;
  class T1;
  friend class T0;
  friend class T1;
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef KeyedSkipList<K,T,Pr,R> container_type;
  typedef K key_type;
  typedef std::pair<const K, T> value_type;
  typedef BidiNode<value_type> node_type;

  typedef T0 iterator;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef T data_type;
  typedef T mapped_type;
  typedef T& mapped_type_reference;
  typedef const T const_mapped_type;
  typedef const T& const_mapped_type_reference;
  typedef const T& const_reference;
  typedef T1 const_iterator;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::pair<iterator, bool> slpair;
  typedef std::pair<iterator, iterator> ipair;
  typedef std::pair<const_iterator, const_iterator> const_ipair;
  typedef Pr key_compare;

  class value_compare
    : public std::binary_function<value_type, value_type, bool>
  {
  friend container_type;
  public:
    bool operator()(const value_type& left, const value_type& right) const
      {return (comp(left.first, right.first)); }
  protected:
    value_compare(const key_compare &pr) : comp(pr) {}
    key_compare comp;
  };

private:
  R rng; 
  key_compare KeyCompare; 
  value_compare ValueCompare; 
  unsigned int maxLevel; 
  unsigned int level;    
  node_type *head;  
  node_type *tail; 
  double probability; 
  size_type items; 
  mutable std::pair<size_type,node_type*> *update; 


  void Init(double probability, unsigned int maxLevel) {}


  node_type* Alloc(unsigned int level, const T &obj) {}


  node_type* Alloc(unsigned int level) {}


  void Free(node_type *item) {}


  unsigned int GenerateRandomLevel() const {}

  void adjust_levels() {}


  void scan(const key_type &val) const{}


  void scan(const value_type &val) const{}


  void scan(const node_type *nodex) const{}


  void scan(const iterator &where) const{}
public:


  class T0 : public std::iterator<std::bidirectional_iterator_tag, value_type>
  {
  public:
    typedef std::iterator<std::bidirectional_iterator_tag, value_type> baseclass;
    typedef std::random_acces_iterator_tag iterator_category;
    typedef typename baseclass::value_type value_type;
    typedef typename baseclass::value_type* pointer;
    typedef typename baseclass::value_type& reference;
    typedef ptrdiff_t difference_type;

    friend T1;
    friend container_type;
  private:
    container_type *container; 
    node_type* node; 
  public:
    T0() {}


    T0(const T0 &t0){}


    T0(const T1 &t1){}


    T0(container_type *container, node_type* p){}


    bool operator==(const T0& other) const{}


    bool operator!=(const T0& other) const{}


    bool operator==(const T1& other) const{}


    bool operator!=(const T1& other) const{}


    T0& operator++(){}


    T0 operator++(int){}


    T0& operator--(){}


    T0 operator--(int){}


    reference operator*() const{}


    pointer operator->() const{}


    bool operator<(const T0 &other) const{}


    bool operator<=(const T0 &other) const{}


    bool operator>(const T0 &other) const{}


    bool operator>=(const T0 &other) const{}


    bool operator<(const T1 &other) const{}


    bool operator<=(const T1 &other) const{}


    bool operator>(const T1 &other) const{}


    bool operator>=(const T1 &other) const{}
  };


  class T1 : public std::iterator<std::bidirectional_iterator_tag, value_type, ptrdiff_t, const value_type*, const value_type&>
  {
  public:
    typedef std::iterator<std::bidirectional_iterator_tag, value_type> baseclass;
    typedef std::random_acces_iterator_tag iterator_category;
    typedef typename baseclass::value_type value_type;
    typedef typename const baseclass::value_type* pointer;
    typedef typename const baseclass::value_type& reference;
    typedef ptrdiff_t difference_type;

    friend T0;
    friend container_type;
  private:
    const container_type *container; 
    const node_type* node; 
  public:
    T1() {}


    T1(const T1 &t1){}


    T1(const T0 &t0){}


    T1(container_type *container, node_type* p){}


    bool operator==(const T0& other) const{}


    bool operator!=(const T0& other) const{}


    bool operator==(const T1& other) const{}


    bool operator!=(const T1& other) const{}


    T1& operator++(){}


    T1 operator++(int){}


    T1& operator--(){}


    T1 operator--(int){}


    reference operator*() const{}


    pointer operator->() const{}


    bool operator<(const T0 &other) const{}


    bool operator<=(const T0 &other) const{}


    bool operator>(const T0 &other) const{}


    bool operator>=(const T0 &other) const{}


    bool operator<(const T1 &other) const{}


    bool operator<=(const T1 &other) const{}


    bool operator>(const T1 &other) const{}


    bool operator>=(const T1 &other) const{}
  };


  KeyedSkipList(){}


  explicit KeyedSkipList(size_type maxNodes){}


  KeyedSkipList(double probability, unsigned int maxLevel){}


  KeyedSkipList(const container_type &source){}


  template<class InIt> KeyedSkipList(InIt first, InIt last){}


  template<class InIt> KeyedSkipList(InIt first, InIt last, double probability, unsigned int maxLevel){}


  template<class InIt> KeyedSkipList(InIt first, InIt last, size_type maxNodes){}


  explicit KeyedSkipList(const key_compare& comp){}


  template<class InIt> KeyedSkipList(InIt first, InIt last, const key_compare& comp){}


  template<class InIt> KeyedSkipList(InIt first, InIt last, const key_compare& comp, double probability, unsigned int maxLevel){}


  template<class InIt> KeyedSkipList(InIt first, InIt last, const key_compare& comp, size_type maxNodes) : Compare(comp){}


  ~KeyedSkipList(){}



  container_type& operator=(const container_type &source){}


  iterator begin(){}


  iterator end(){}


  const_iterator begin() const{}


  const_iterator end() const{}


  reverse_iterator rbegin(){}


  reverse_iterator rend(){}


  const_reverse_iterator rbegin() const{}


  const_reverse_iterator rend() const{}


  size_type size() const{}


  bool empty() const{}


  reference front(){}


  const_reference front() const{}


  reference back(){}


  const_reference back() const{}

  void pop_front(){}

  void destroy_front(){}

  void pop_back(){}

  void destroy_back(){}


  template<class InIt> void assign(InIt first, InIt last){}


  slpair insert(const value_type& val){}


  iterator insert(const iterator &where, const value_type& val) {}


  template<class InIt> void insert(InIt first, InIt last) {}

  void clear(){}

  void destroy(){}

  iterator erase(const iterator &where){}

  iterator destroy(const iterator &where){}


  iterator erase(const iterator &first, const iterator &last){}


  iterator destroy(const iterator &first, const iterator &last){}


  size_type erase(const key_type &keyval){}


  size_type destroy(const key_type &keyval){}


  void swap(container_type& right) {}


  template<class Pr1> void erase_if(Pr1 pred);


  template<class Pr4> void destroy_if(Pr4 pred);


  void cut(const iterator &first, const iterator &last, container_type& right);


  mapped_type_reference operator[](const key_type& key){}


  const_mapped_type_reference operator[](const key_type& key) const{}


  mapped_type_reference operator()(const key_type& key){}


  const_mapped_type_reference operator()(const key_type& key) const{}

  key_compare key_comp() const { }

  value_compare value_comp() const { }

  size_type max_size() const{}


  const key_type& key(const value_type& value) const {}


  mapped_type& value(value_type& value) {}


  iterator find(const key_type& keyval) {}


  const_iterator find(const key_type& keyval) const {}


  size_type count(const key_type& keyval) const {}



  iterator lower_bound(const key_type& keyval) {}


  const_iterator lower_bound(const key_type& keyval) const {}


  iterator upper_bound(const key_type& keyval) {}


  const_iterator upper_bound(const key_type& keyval) const {}


  ipair equal_range(const key_type& keyval) {}


  const_ipair equal_range(const key_type& keyval) const {}
};


template <class K, class T, class Pr, class R>
bool operator==(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));

}


template <class K, class T, class Pr, class R>
bool operator!=(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return !(left==right);
}


template <class K, class T, class Pr, class R>
bool operator<(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <class K, class T, class Pr, class R>
bool operator<=(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return !(right < left);
}


template <class K, class T, class Pr, class R>
bool operator>(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return (right < left);
}


template <class K, class T, class Pr, class R>
bool operator>=(const KeyedSkipList<K,T,Pr,R> &left, const KeyedSkipList<K,T,Pr,R> &right)
{
  return !(left < right);
}

/*#define csarg1 template <class T, class Pr, class R>
#define csarg2 KeyedSkipList<K,T,Pr,R>
CSDefineCompOps(csarg1, csarg2)
#undef csarg1
#undef csarg2

#undef CSUNIQUE
#define CSUNIQUE(a,b) b
*/


template <class K, class T, class Pr = std::less<K>, class R = RNG >
class MultiKeyedSkipList
{
public:
  class T0;
  class T1;
  friend class T0;
  friend class T1;
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef MultiKeyedSkipList<K,T,Pr> container_type;
  typedef K key_type;
  typedef std::pair<const K, T> value_type;
  typedef BidiNode<value_type> node_type;

  typedef T0 iterator;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef T data_type;
  typedef T mapped_type;
  typedef T& mapped_type_reference;
  typedef const T const_mapped_type;
  typedef const T& const_mapped_type_reference;
  typedef const T& const_reference;
  typedef T1 const_iterator;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef std::pair<iterator, iterator> ipair;
  typedef std::pair<const_iterator, const_iterator> const_ipair;
  typedef Pr key_compare;

  class value_compare
    : public std::binary_function<value_type, value_type, bool>
  {
  friend container_type;
  public:
    bool operator()(const value_type& left, const value_type& right) const
      {return (comp(left.first, right.first)); }
  protected:
    value_compare(const key_compare &pr) : comp(pr) {}
    key_compare comp;
  };

private:
  R rng; 
  key_compare KeyCompare; 
  value_compare ValueCompare; 
  unsigned int maxLevel; 
  unsigned int level;    
  node_type *head;  
  node_type *tail; 
  double probability; 
  size_type items; 
  mutable std::pair<size_type,node_type*> *update; 


  void Init(double probability,unsigned int maxLevel) {}


  node_type* Alloc(unsigned int level, const T &obj) {}


  node_type* Alloc(unsigned int level) {}


  void Free(node_type *item) {}


  unsigned int GenerateRandomLevel() const {}

  void adjust_levels() {}


  void scan(const key_type &val) const{}


  void scan(const value_type &val) const{}


  void scan(const node_type *nodex) const{}


  void scan(const iterator &where) const{}

public:

  class T0 : public std::iterator<std::bidirectional_iterator_tag, value_type>
  {
  public:
    typedef std::iterator<std::bidirectional_iterator_tag, value_type> baseclass;
    typedef std::random_acces_iterator_tag iterator_category;
    typedef typename baseclass::value_type value_type;
    typedef typename baseclass::value_type* pointer;
    typedef typename baseclass::value_type& reference;
    typedef ptrdiff_t difference_type;

    friend T1;
    friend container_type;
  private:
    container_type *container; 
    node_type* node; 
  public:
    T0() {}


    T0(const T0 &t0){}


    T0(const T1 &t1){}


    T0(container_type *container, node_type* p){}


    bool operator==(const T0& other) const{}


    bool operator!=(const T0& other) const{}


    bool operator==(const T1& other) const{}


    bool operator!=(const T1& other) const{}


    T0& operator++(){}


    T0 operator++(int){}


    T0& operator--(){}


    T0 operator--(int){}


    reference operator*() const{}


    pointer operator->() const{}


    bool operator<(const T0 &other) const{}


    bool operator<=(const T0 &other) const{}


    bool operator>(const T0 &other) const{}


    bool operator>=(const T0 &other) const{}


    bool operator<(const T1 &other) const{}


    bool operator<=(const T1 &other) const{}


    bool operator>(const T1 &other) const{}


    bool operator>=(const T1 &other) const{}
  };


  class T1 : public std::iterator<std::bidirectional_iterator_tag, value_type, ptrdiff_t, const value_type*, const value_type&>
  {
  public:
    typedef std::iterator<std::bidirectional_iterator_tag, value_type> baseclass;
    typedef std::random_acces_iterator_tag iterator_category;
    typedef typename baseclass::value_type value_type;
    typedef typename const baseclass::value_type* pointer;
    typedef typename const baseclass::value_type& reference;
    typedef ptrdiff_t difference_type;

    friend T0;
    friend container_type;
  private:
    const container_type *container; 
    const node_type* node; 
  public:
    T1() {}


    T1(const T1 &t1){}


    T1(const T0 &t0){}


    T1(container_type *container, node_type* p){}


    bool operator==(const T0& other) const{}


    bool operator!=(const T0& other) const{}


    bool operator==(const T1& other) const{}


    bool operator!=(const T1& other) const{}


    T1& operator++(){}


    T1 operator++(int){}


    T1& operator--(){}


    T1 operator--(int){}


    reference operator*() const{}


    pointer operator->() const{}


    bool operator<(const T0 &other) const{}


    bool operator<=(const T0 &other) const{}


    bool operator>(const T0 &other) const{}


    bool operator>=(const T0 &other) const{}


    bool operator<(const T1 &other) const{}


    bool operator<=(const T1 &other) const{}


    bool operator>(const T1 &other) const{}


    bool operator>=(const T1 &other) const{}
  };



  MultiKeyedSkipList(){}


  explicit MultiKeyedSkipList(size_type maxNodes){}


  MultiKeyedSkipList(double probability, unsigned int maxLevel){}


  MultiKeyedSkipList(const container_type &source){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last, double probability, unsigned int maxLevel){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last, size_type maxNodes){}


  explicit MultiKeyedSkipList(const key_compare& comp){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last, const key_compare& comp){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last, const key_compare& comp, double probability, unsigned int maxLevel){}


  template<class InIt> MultiKeyedSkipList(InIt first, InIt last, const key_compare& comp, size_type maxNodes) : Compare(comp){}


  ~MultiKeyedSkipList(){}



  container_type& operator=(const container_type &source){}


  iterator begin(){}


  iterator end(){}


  const_iterator begin() const{}


  const_iterator end() const{}


  reverse_iterator rbegin(){}


  reverse_iterator rend(){}


  const_reverse_iterator rbegin() const{}


  const_reverse_iterator rend() const{}


  size_type size() const{}


  bool empty() const{}


  reference front(){}


  const_reference front() const{}


  reference back(){}


  const_reference back() const{}

  void pop_front(){}

  void destroy_front(){}

  void pop_back(){}

  void destroy_back(){}


  template<class InIt> void assign(InIt first, InIt last){}


  iterator insert(const value_type& val){}


  iterator insert(const iterator &where, const value_type& val) {}


  template<class InIt> void insert(InIt first, InIt last) {}

  void clear(){}

  void destroy(){}

  iterator erase(const iterator &where){}

  iterator destroy(const iterator &where){}


  iterator erase(const iterator &first, const iterator &last){}


  iterator destroy(const iterator &first, const iterator &last){}


  size_type erase(const key_type &keyval){}


  size_type destroy(const key_type &keyval){}


  void swap(container_type& right) {}


  template<class Pr1> void erase_if(Pr1 pred);


  template<class Pr4> void destroy_if(Pr4 pred);


  void cut(const iterator &first, const iterator &last, container_type& right);

  key_compare key_comp() const { }

  value_compare value_comp() const { }

  size_type max_size() const{}


  const key_type& key(const value_type& value) const {}


  mapped_type& value(value_type& value) {}


  iterator find(const key_type& keyval) {}


  const_iterator find(const key_type& keyval) const {}


  size_type count(const key_type& keyval) const {}



  iterator lower_bound(const key_type& keyval) {}


  const_iterator lower_bound(const key_type& keyval) const {}


  iterator upper_bound(const key_type& keyval) {}


  const_iterator upper_bound(const key_type& keyval) const {}


  ipair equal_range(const key_type& keyval) {}


  const_ipair equal_range(const key_type& keyval) const {}
};


template <class K, class T, class Pr, class R>
bool operator==(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));
}


template <class K, class T, class Pr, class R>
bool operator!=(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return !(left==right);
}


template <class K, class T, class Pr, class R>
bool operator<(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <class K, class T, class Pr, class R>
bool operator<=(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return !(right < left);
}


template <class K, class T, class Pr, class R>
bool operator>(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return (right < left);
}


template <class K, class T, class Pr, class R>
bool operator>=(const MultiKeyedSkipList<K,T,Pr,R> &left, const MultiKeyedSkipList<K,T,Pr,R> &right)
{
  return !(left < right);
}


/*#define csarg1 template <class T, class Pr, class R>
#define csarg2 MultiKeyedSkipList<K,T,Pr,R>
CSDefineCompOps(csarg1, csarg2)
#undef csarg1
#undef csarg2
*/