CSCompositeSkipList.h

Go to the documentation of this file.

#include <algorithm>
#include <functional>
#include <utility>
#include <iterator>
#include "CSSkipListTools.h"


// Forward declarations of iterators.
template<unsigned int X, class container_type>
class XIterator0;

template<unsigned int X, class container_type>
class XIterator1;

template<unsigned int X, class container_type>
class YIterator0;

template<unsigned int X, class container_type>
class YIterator1;

// Some prototypes for sorting.
template<unsigned int X, class container_type, class Pr>
void sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last, const Pr pred);

template<unsigned int X, class container_type, class Pr>
void stable_sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last, const Pr pred);

template<unsigned int X, class container_type>
void sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last);

template<unsigned int X, class container_type>
void stable_sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last);


template <class T, class NT>
class XList
{
public:

  virtual void insert(NT *node)=0;


  virtual void insert(NT *ref, NT *node)=0;


  virtual void erase(NT *node)=0;



  virtual void setData(void *data)=0;

  virtual void clear()=0;
  // Return value is a custom iterator, so cannot make it virtual.
  // virtual void insert(const T &val)=0;
};


template<class size_type, class node_type>
class XTmpContainer
{
private:
  XTmpContainer() {} // Cannot create default list.
public:
  unsigned int maxLevel; 
  unsigned int level;    
  node_type *head;  
  node_type *tail; 
  double probability; 
  size_type items; 


  node_type* Alloc(unsigned int level) {}


  void Free(node_type *item) {}


  XTmpContainer(double probability, unsigned int maxLevel) {}


  ~XTmpContainer() {}


  size_type size() const{}


  bool empty() const{}

};


template<class size_type, class difference_type, class node_type, class value_type, unsigned int N, unsigned int S, class R>
class XData
{
public:
  R rng; 

  unsigned int maxLevel; 
  unsigned int level;    
  node_type *head;  
  node_type *tail; 
  double probability; 
  size_type items; 

  mutable size_type scan_index[N]; 
  mutable std::pair<size_type,node_type*> *update[N]; 

  XList<value_type,node_type>* Containers[N];

  typedef XTmpContainer<size_type, node_type> tmp_container_type;
  tmp_container_type *tmp_container; 

  void InitData() {}

  unsigned int getListCount() const { return N; }  
  unsigned int getIndexCount() const { return S; } 


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


  node_type* Alloc(unsigned int level) {}


  void Free(node_type *item) {}


  unsigned int GenerateRandomLevel() const {}

  void adjust_levels() {}


  void scan(node_type *nodex, unsigned int x) const {}


  void erase(node_type *node) {}

  XData() {}


  ~XData() {}
};


template <class T, unsigned int N=1, unsigned int S=0>
class XBidiNode
{
public:
  typedef size_t size_type;
  struct Pointers
  {
    size_type skip[S];  
    XBidiNode<T,N,S> *forward[N]; 
    XBidiNode<T,N,S> *backward[N]; 
  };
  typedef Pointers ptr_type; 

  T object; 
  unsigned int level; 
  ptr_type pointers[1]; 


  XBidiNode<T,N,S>*& forward(unsigned int ptr_type, unsigned int level) {return pointers[level].forward[ptr_type];}


  XBidiNode<T,N,S>*& backward(unsigned int ptr_type, unsigned int level) {return pointers[level].backward[ptr_type];}


  size_type& skip(unsigned int ptr_type, unsigned int level) {return pointers[level].skip[ptr_type];}


  XBidiNode<T,N,S>* forward(unsigned int ptr_type, unsigned int level) const {return pointers[level].forward[ptr_type];}


  XBidiNode<T,N,S>* backward(unsigned int ptr_type, unsigned int level) const {return pointers[level].backward[ptr_type];}


  size_type skip(unsigned int ptr_type, unsigned int level) const {return pointers[level].skip[ptr_type];}


  XBidiNode(unsigned int level, const T obj) {}


  XBidiNode(unsigned int level) {}

  unsigned int getListCount() const { return N; }  
  unsigned int getIndexCount() const { return S; } 
};


template <class T, unsigned int N, unsigned int S=0, class R = RNG>
class XBidiCompositeSkipList
{
public:
  typedef XBidiCompositeSkipList<T,N,S,R> container_type;
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;

  typedef T value_type;
  typedef XBidiNode<value_type,N,S> node_type;
  typedef XData<size_type,difference_type,node_type,value_type,N,S,R> data_type;
  friend XList<T,node_type>;
protected:
  data_type data;  


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

public:

  XBidiCompositeSkipList() {}


  XBidiCompositeSkipList(double probability, unsigned int maxLevel) {}


  XBidiCompositeSkipList(size_type maxNodes) {}


  XBidiCompositeSkipList(const container_type &source) {}


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


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


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


  virtual ~XBidiCompositeSkipList() {}


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


  void swap(container_type& right) {}

  void clear(){}

  void destroy(){}


  size_type size() const{}


  bool empty() const{}

  XList<T,node_type>** getContainers() { return data.Containers; }

  typedef XList<T,node_type>** XListArray;

  XListArray Containers;
};


template<unsigned int X, class container_type>
class XIterator0 : public std::iterator<std::random_access_iterator_tag, typename container_type::value_type >
{
public:
  typedef std::iterator<std::random_access_iterator_tag, typename container_type::value_type > baseclass;
  typedef typename baseclass::iterator_category iterator_category;
  typedef typename baseclass::value_type value_type;
  typedef typename baseclass::difference_type difference_type;
  typedef typename baseclass::pointer pointer;
  typedef typename baseclass::reference reference;

  typedef typename container_type::data_type data_type;
  typedef typename container_type::node_type node_type;
  typedef typename container_type::size_type size_type;
  typedef typename container_type::mapped_type mapped_type;
  typedef typename container_type::const_mapped_type const_mapped_type;
  typedef typename container_type::mapped_type_reference mapped_type_reference;
  typedef typename container_type::const_mapped_type_reference const_mapped_type_reference;

  typedef typename container_type::T0 T0;
  typedef typename container_type::T1 T1;

  typedef XIterator0<X,container_type> self_type;

private:
  data_type *data; 
  mutable size_type Findex; 
  node_type *FNode; 

public:
  size_type index;

  XIterator0() {}


  XIterator0(const T0 &t0) {}


  XIterator0(const T1 &t1) {}


  XIterator0(data_type *data, node_type* p) {}


  XIterator0(data_type *data, node_type* p, size_type index) {}


  template<unsigned int nX, class ncontainer_type>
  XIterator0(const XIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator0(const XIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(const_cast<node_type*>(t1.FNode)) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator0(const YIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator0(const YIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(const_cast<node_type*>(t1.FNode)) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  T0& operator=(const XIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T0& operator=(const XIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = const_cast<node_type*>(t1.FNode);
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T0& operator=(const YIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T0& operator=(const YIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = const_cast<node_type*>(t1.FNode);
    refresh();
    return *this;
  }

  node_type* getNode() const { return FNode; }

  void setNode(node_type *n) { FNode = n; }

  container_type* getContainer() 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{}


  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{}


  T0 operator+(difference_type off) const{}


  T0 operator-(difference_type off) const{}


  T0& operator+=(difference_type off){}


  T0& operator-=(difference_type off){}


  difference_type operator-(const T0 &other) const{}


  difference_type operator-(const T1 &other) const{}


  size_type refresh(){}


  value_type& operator[](difference_type off) const{}


  size_type getIndex() const{}
};


template<unsigned int X, class container_type>
class XIterator1 : public std::iterator<std::random_access_iterator_tag, typename container_type::value_type, typename container_type::difference_type, const typename container_type::pointer, typename container_type::const_reference >
{
public:
  typedef std::iterator<std::random_access_iterator_tag, typename container_type::value_type, typename container_type::difference_type, const typename container_type::pointer, typename container_type::const_reference > baseclass;
  typedef typename baseclass::iterator_category iterator_category;
  typedef typename baseclass::value_type value_type;
  typedef typename baseclass::difference_type difference_type;
  typedef typename baseclass::pointer pointer;
  typedef typename baseclass::reference reference;

  typedef typename container_type::data_type data_type;
  typedef typename container_type::node_type node_type;
  typedef typename container_type::size_type size_type;
  typedef typename container_type::mapped_type mapped_type;
  typedef typename container_type::const_mapped_type const_mapped_type;
  typedef typename container_type::mapped_type_reference mapped_type_reference;
  typedef typename container_type::const_mapped_type_reference const_mapped_type_reference;

  typedef typename container_type::T0 T0;
  typedef typename container_type::T1 T1;

  typedef XIterator1<X,container_type> self_type;

private:
  data_type *data; 
  mutable size_type Findex; 
  node_type *FNode; 
public:
  size_type index;

  XIterator1() {}


  XIterator1(const T1 &t1) {}


  XIterator1(const T0 &t0) {}


  XIterator1(data_type *data, node_type* p) {}


  XIterator1(data_type *data, node_type* p, size_type index) {}


  template<unsigned int nX, class ncontainer_type>
  XIterator1(const XIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator1(const XIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(t1.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator1(const YIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  XIterator1(const YIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(t1.FNode) { refresh(); }


  template<unsigned int nX, class ncontainer_type>
  T1& operator=(const XIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T1& operator=(const XIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = t1.FNode;
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T1& operator=(const YIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    refresh();
    return *this;
  }


  template<unsigned int nX, class ncontainer_type>
  T1& operator=(const YIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = t1.FNode;
    refresh();
    return *this;
  }


  node_type* getNode() const { return FNode; }

  void setNode(node_type *n) { FNode = n; }

  container_type* getContainer() 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{}


  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{}


  T1 operator+(difference_type off) const{}


  T1 operator-(difference_type off) const{}


  T1& operator+=(difference_type off){}


  T1& operator-=(difference_type off){}


  difference_type operator-(const T0 &other) const{}


  difference_type operator-(const T1 &other) const{}


  size_type refresh(){}


  value_type& operator[](difference_type off) const{}


  size_type getIndex() const{}
};


template <unsigned int X, class CT>
class XIndexedSkipList : public XList<typename CT::value_type, typename CT::node_type>
{
public:
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef XIndexedSkipList<X,CT> container_type;

  typedef XIterator0<X,container_type> T0;
  typedef XIterator1<X,container_type> T1;

  friend class XIterator0<X,container_type>;
  friend class XIterator1<X,container_type>;


  typedef T0 iterator;
  typedef T1 const_iterator;


  typedef typename CT::value_type value_type;
  typedef value_type T;
  typedef value_type mapped_type;
  typedef value_type& mapped_type_reference;
  typedef const value_type const_mapped_type;
  typedef const value_type& const_mapped_type_reference;
  typedef typename CT::node_type node_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef typename CT::data_type data_type;

  typedef XTmpContainer<size_type, node_type> tmp_container_type;

private:
  data_type *data; 


  void scan(size_type index) const {}


  void scanAll(size_type index) const {}


  void scan(const iterator &where) const {}


  void scanAll(const iterator &where) const {}


  void scan(node_type *nodex) {}


  void scanAll(node_type *nodex) {}


  size_type& getItems() {}

  void setItems(const size_type sz) {}

  std::pair<size_type,node_type*>* getUpdate() {}

  size_type getScanIndex() const {}


  void setScanIndex(const size_type sz) {}

  typedef std::pair<size_type,node_type*>* pair_t;

public:

  XIndexedSkipList() { }

  ~XIndexedSkipList() {}


  void setData(void *data) {}

  data_type* getData() { return this->data; }


  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 push_front(const value_type &val){}

  void pop_front(){}

  void destroy_front(){}


  void push_back(const value_type &val){}

  void pop_back(){}

  void destroy_back(){}


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


  void assign(size_type count, const T& val) {}


  void insert(node_type *node) {}


  void erase(node_type *node) {}


  iterator insert(const T &val) {}



  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){}


  iterator erase_index(size_type index);


  iterator destroy_index(size_type index);

  void clear(){}

  void destroy(){}


  void swap(container_type& right) {}


  mapped_type_reference value(reference value) const {}


  const_mapped_type_reference value(const_reference value) const {return value;}


  mapped_type_reference operator[](size_type index){}


  const_mapped_type_reference operator[](size_type index) const{}


  mapped_type_reference at(size_type off){}


  const_mapped_type_reference at(size_type off) const{}

  size_type max_size() const{}

  void resize(size_type newsize){}

  void resize(size_type newsize, const value_type &val){}


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


  void insert(const iterator &where, size_type count, const T& val){}


  template<class InIt> void insert(const iterator &where, InIt first, InIt last){}


  void reverse(){}


  void unique(){}


  template<class Pr2> void unique(Pr2 pred){}


  void sort(){}


  template<class Pr3> void sort(Pr3 pred){}


  void stable_sort(){}


  template<class Pr3> void stable_sort(Pr3 pred){}


  void erase_value(const value_type& val){}


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


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


  void move(const iterator &dest, const iterator &source) {}


  void move(const iterator &dest, const iterator &first, const iterator &last) {}


  void swap(const iterator &left, const iterator &right) {}


  void swap(const iterator &first1, const iterator &last1, const iterator &first2, const iterator &last2) {}


  void cut(const iterator &first, const iterator &last, tmp_container_type& right) {}


  void cut(const iterator &where, tmp_container_type& right) {}


  void splice(const iterator &where, tmp_container_type& right) {}

};


template <int X, class CT>
bool operator==(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));

}


template <int X, class CT>
bool operator!=(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return !(left==right);
}


template <int X, class CT>
bool operator<(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <int X, class CT>
bool operator<=(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return !(right < left);
}


template <int X, class CT>
bool operator>(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return (right < left);
}


template <int X, class CT>
bool operator>=(const XIndexedSkipList<X,CT> &left, const XIndexedSkipList<X,CT> &right)
{
  return !(left < right);
}



template<int X, class container_type, class Pr>
CS::XIterator0<X,container_type> scan(const CS::XIterator0<X,container_type> &first, const CS::XIterator0<X,container_type> &last, typename container_type::const_reference value, const Pr &pred) {}


template <int X, class CT, class Pr = std::less<typename CT::value_type> >
class XMultiAutoSkipList : public XList<typename CT::value_type, typename CT::node_type>
{
public:
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef XMultiAutoSkipList<X,CT,Pr> container_type;

  typedef XIterator0<X,container_type> T0;
  typedef XIterator1<X,container_type> T1;

  friend class XIterator0<X,container_type>;
  friend class XIterator1<X,container_type>;


  typedef T0 iterator;
  typedef T1 const_iterator;


  typedef typename CT::value_type value_type;
  typedef value_type T;
  typedef value_type key_type;
  typedef T mapped_type;
  typedef T& mapped_type_reference;
  typedef const value_type const_mapped_type;
  typedef const value_type& const_mapped_type_reference;
  typedef typename CT::node_type node_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

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

private:
  data_type *data; 

  Pr Compare; 


  void scan(size_type index) const {}


  void scanAll(size_type index) const {}


  void scan(const iterator &where) const {}


  void scanAll(const iterator &where) const {}


  void scan(node_type *nodex) {}


  void scanAll(node_type *nodex) {}


  void scan_val(const value_type &val) const {}


  void scanAll_val(const value_type &val) const {}


  void scan_val(const key_type &val) const {}


  void scanAll_val(const key_type &val) const {}

  size_type& getItems() {}

  void setItems(const size_type sz) {}

  std::pair<size_type,node_type*>* getUpdate() {}

  size_type getScanIndex() const {}


  void setScanIndex(const size_type sz) {}

  typedef std::pair<size_type,node_type*>* pair_t;

public:
  XMultiAutoSkipList() { }


  explicit XMultiAutoSkipList(const key_compare& comp) : Compare(comp) { }

  ~XMultiAutoSkipList() {}


  void setData(void *data) {}

  data_type* getData() {}


  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) {}


  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){}


  iterator erase_index(size_type index);


  iterator destroy_index(size_type index);

  void clear(){}

  void destroy(){}


  void swap(container_type& right) {}


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


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


  void unique(){}


  template<class Pr2> void unique(Pr2 pred){}


  mapped_type_reference operator[](size_type index){}


  const_mapped_type_reference operator[](size_type index) const{}


  mapped_type_reference at(size_type off){}


  const_mapped_type_reference at(size_type off) 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_reference value(reference value) const {}


  const_mapped_type_reference value(const_reference value) const {}


  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 <int X, class CT, class Pr>
bool operator==(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));
}


template <int X, class CT, class Pr>
bool operator!=(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return !(left==right);
}


template <int X, class CT, class Pr>
bool operator<(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <int X, class CT, class Pr>
bool operator<=(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return !(right < left);
}


template <int X, class CT, class Pr>
bool operator>(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return (right < left);
}


template <int X, class CT, class Pr>
bool operator>=(const XMultiAutoSkipList<X,CT,Pr> &left, const XMultiAutoSkipList<X,CT,Pr> &right)
{
  return !(left < right);
}


template <unsigned int X, class K, class CT, class A=XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K> >
class XMultiAutoAccessSkipList : public XList<typename CT::value_type, typename CT::node_type>
{
public:
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef XMultiAutoAccessSkipList<X,K,CT,A,Pr> container_type;

  typedef XIterator0<X,container_type> T0;
  typedef XIterator1<X,container_type> T1;

  friend class XIterator0<X,container_type>;
  friend class XIterator1<X,container_type>;


  typedef T0 iterator;
  typedef T1 const_iterator;


  typedef typename CT::value_type value_type;
  typedef value_type T;
  typedef K key_type;
  typedef T mapped_type;
  typedef T& mapped_type_reference;
  typedef const value_type const_mapped_type;
  typedef const value_type& const_mapped_type_reference;
  typedef typename CT::node_type node_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef typename CT::data_type data_type;
  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:
  data_type *data; 
  A a;  
  key_compare KeyCompare; 
  value_compare ValueCompare; 


  void scan(size_type index) const {}


  void scanAll(size_type index) const {}


  void scan(const iterator &where) const {}


  void scanAll(const iterator &where) const {}


  void scan(node_type *nodex) {}


  void scanAll(node_type *nodex) {}


  void scan_val(const value_type &val) const {}


  void scanAll_val(const value_type &val) const {}


  void scan_val(const key_type &val) const {}


  void scanAll_val(const key_type &val) const {}

  size_type& getItems() {}

  void setItems(const size_type sz) {}

  std::pair<size_type,node_type*>* getUpdate() {}

  size_type getScanIndex() const {}


  void setScanIndex(const size_type sz) {}

  typedef std::pair<size_type,node_type*>* pair_t;

public:
  XMultiAutoAcessSkipList() { }


  explicit XMultiAutoAcessSkipList(const key_compare& comp) : Compare(comp) { }

  ~XMultiAutoAcessSkipList() {}


  void setData(void *data) {}

  data_type* getData() {}


  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) {}


  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){}


  iterator erase_index(size_type index);


  iterator destroy_index(size_type index);

  void clear(){}

  void destroy(){}


  void swap(container_type& right) {}


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


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


  void unique(){}


  template<class Pr2> void unique(Pr2 pred){}


  mapped_type_reference operator[](size_type index){}


  const_mapped_type_reference operator[](size_type index) const{}


  mapped_type_reference at(size_type off){}


  const_mapped_type_reference at(size_type off) 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_reference value(reference value) const {}


  const_mapped_type_reference value(const_reference value) const {}


  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 <unsigned int X, class K, class CT, class A, class Pr>
bool operator==(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator!=(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(left==right);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator<(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator<=(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(right < left);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator>(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return (right < left);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator>=(const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAutoAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(left < right);
}


template<unsigned int X, class container_type>
class YIterator0 : public std::iterator<std::bidirectional_iterator_tag, typename container_type::value_type>
{
public:
  typedef std::iterator<std::bidirectional_iterator_tag, typename container_type::value_type> baseclass;
  typedef typename baseclass::iterator_category iterator_category;
  typedef typename baseclass::value_type value_type;
  typedef typename baseclass::difference_type difference_type;
  typedef typename baseclass::pointer pointer;
  typedef typename baseclass::reference reference;

  typedef typename container_type::data_type data_type;
  typedef typename container_type::node_type node_type;
  typedef typename container_type::size_type size_type;
  typedef typename container_type::mapped_type mapped_type;
  typedef typename container_type::const_mapped_type const_mapped_type;
  typedef typename container_type::mapped_type_reference mapped_type_reference;
  typedef typename container_type::const_mapped_type_reference const_mapped_type_reference;

  typedef typename container_type::T0 T0;
  typedef typename container_type::T1 T1;

private:
  data_type *data; 
  node_type *FNode; 
public:
  node_type *node;

  YIterator0() {}


  YIterator0(const T0 &t0) {}


  YIterator0(const T1 &t1) {}


  YIterator0(data_type *data, node_type* p) {}


  template<int nX, class ncontainer_type>
  YIterator0(const XIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) {}


  template<int nX, class ncontainer_type>
  YIterator0(const XIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(const_cast<node_type*>(t1.FNode)) {}


  template<int nX, class ncontainer_type>
  YIterator0(const YIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) {}


  template<int nX, class ncontainer_type>
  YIterator0(const YIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(const_cast<node_type*>(t1.FNode)) {}


  template<int nX, class ncontainer_type>
  T0& operator=(const XIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    return *this;
  }


  template<int nX, class ncontainer_type>
  T0& operator=(const XIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = const_cast<node_type*>(t1.FNode);
    return *this;
  }


  template<int nX, class ncontainer_type>
  T0& operator=(const YIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    return *this;
  }


  template<int nX, class ncontainer_type>
  T0& operator=(const YIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = const_cast<node_type*>(t1.FNode);
    return *this;
  }

  node_type* getNode() const { return FNode; }

  void setNode(node_type *n) { FNode = n; }

  container_type* getContainer() 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{}


  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{}

};


template<unsigned int X, class container_type>
class YIterator1 : public std::iterator<std::bidirectional_iterator_tag, typename container_type::value_type, typename container_type::difference_type, const typename container_type::pointer, typename container_type::const_reference >
{
public:
  typedef std::iterator<std::bidirectional_iterator_tag, typename container_type::value_type, typename container_type::difference_type, const typename container_type::pointer, typename container_type::const_reference> baseclass;
  typedef typename baseclass::iterator_category iterator_category;
  typedef typename baseclass::value_type value_type;
  typedef typename baseclass::difference_type difference_type;
  typedef typename baseclass::pointer pointer;
  typedef typename baseclass::reference reference;

  typedef typename container_type::data_type data_type;
  typedef typename container_type::node_type node_type;
  typedef typename container_type::size_type size_type;
  typedef typename container_type::mapped_type mapped_type;
  typedef typename container_type::const_mapped_type const_mapped_type;
  typedef typename container_type::mapped_type_reference mapped_type_reference;
  typedef typename container_type::const_mapped_type_reference const_mapped_type_reference;

  typedef typename container_type::T0 T0;
  typedef typename container_type::T1 T1;

private:
  data_type *data; 
  node_type *FNode; 
public:
  YIterator1() {}


  YIterator1(const T1 &t1) {}


  YIterator1(const T0 &t0) {}


  YIterator1(const data_type *data, node_type* p) {}


  template<int nX, class ncontainer_type>
  YIterator1(const XIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) {}


  template<int nX, class ncontainer_type>
  YIterator1(const XIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(t1.FNode) {}

  template<int nX, class ncontainer_type>
  YIterator1(const YIterator0<nX,ncontainer_type> &t0) : data(t0.data), FNode(t0.FNode) {}


  template<int nX, class ncontainer_type>
  YIterator1(const YIterator1<nX,ncontainer_type> &t1) : data(t1.data), FNode(t1.FNode) {}


  template<int nX, class ncontainer_type>
  T1& operator=(const XIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    return *this;
  }


  template<int nX, class ncontainer_type>
  T1& operator=(const XIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = t1.FNode;
    return *this;
  }


  template<int nX, class ncontainer_type>
  T1& operator=(const YIterator0<nX,ncontainer_type> &t0)
  {
    this->data = t0->data;
    this->FNode = t0->FNode;
    return *this;
  }


  template<int nX, class ncontainer_type>
  T1& operator=(const YIterator1<nX,ncontainer_type> &t1)
  {
    this->data = t1->data;
    this->FNode = t1.FNode;
    return *this;
  }

  node_type* getNode() const { return FNode; }

  void setNode(node_type *n) { FNode = n; }

  container_type* getContainer() 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{}


  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{}

};



template <unsigned int X, class CT, class Pr = std::less<typename CT::value_type> >
class XMultiSkipList : public XList<typename CT::value_type, typename CT::node_type>
{
public:
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef XMultiSkipList<X,CT,Pr> container_type;

  typedef YIterator0<X,container_type> T0;
  typedef YIterator1<X,container_type> T1;

  friend class YIterator0<X,container_type>;
  friend class YIterator1<X,container_type>;


  typedef T0 iterator;
  typedef T1 const_iterator;


  typedef typename CT::value_type value_type;
  typedef value_type T;
  typedef value_type key_type;
  typedef value_type mapped_type;
  typedef value_type& mapped_type_reference;
  typedef const value_type const_mapped_type;
  typedef const value_type& const_mapped_type_reference;
  typedef typename CT::node_type node_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef typename CT::data_type data_type;

  typedef std::pair<iterator, iterator> ipair;
  typedef std::pair<const_iterator, const_iterator> const_ipair;

  typedef Pr key_compare;
  typedef Pr value_compare;

private:
  data_type *data; 

  Pr Compare; 


  void scan(const iterator &where) const {}


  void scanAll(const iterator &where) const {}


  void scan(node_type *nodex) {}


  void scanAll(node_type *nodex) {}


  void scan_val(const value_type &val) const {}


  void scanAll_val(const value_type &val) const {}


  void scan_val(const key_type &val) const {}


  void scanAll_key(const key_type &val) const {}

  size_type& getItems() {}

  void setItems(const size_type sz) {}

  std::pair<size_type,node_type*>* getUpdate() {}

  size_type getScanIndex() const {}


  void setScanIndex(const size_type sz) {}

  typedef std::pair<size_type,node_type*>* pair_t;

public:
  XMultiSkipList() {}

  ~XMultiSkipList() {}


  void setData(void *data) {}

  data_type* getData() {}


  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) {}


  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 clear(){}

  void destroy(){}


  void swap(container_type& right) {}


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


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


  void unique(){}


  template<class Pr2> void unique(Pr2 pred){}

  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_reference value(reference value) const {}


  const_mapped_type_reference value(const_reference value) const {return 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 <int X, class CT, class Pr>
bool operator==(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));
}


template <int X, class CT, class Pr>
bool operator!=(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return !(left==right);
}


template <int X, class CT, class Pr>
bool operator<(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <int X, class CT, class Pr>
bool operator<=(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return !(right < left);
}


template <int X, class CT, class Pr>
bool operator>(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return (right < left);
}


template <int X, class CT, class Pr>
bool operator>=(const XMultiSkipList<X,CT,Pr> &left, const XMultiSkipList<X,CT,Pr> &right)
{
  return !(left < right);
}


template <unsigned int X, class K, class CT, class A=XAccessSelf<K,typename CT::value_type>, class Pr = std::less<K> >
class XMultiAccessSkipList : public XList<typename CT::value_type, typename CT::node_type>
{
public:
  typedef size_t size_type;

  typedef ptrdiff_t difference_type;
  typedef XMultiAccessSkipList<X,K,CT,A,Pr> container_type;

  typedef YIterator0<X,container_type> T0;
  typedef YIterator1<X,container_type> T1;

  friend class YIterator0<X,container_type>;
  friend class YIterator1<X,container_type>;


  typedef T0 iterator;
  typedef T1 const_iterator;


  typedef typename CT::value_type value_type;
  typedef value_type T;
  typedef value_type key_type;
  typedef value_type mapped_type;
  typedef value_type& mapped_type_reference;
  typedef const value_type const_mapped_type;
  typedef const value_type& const_mapped_type_reference;
  typedef typename CT::node_type node_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;

  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef typename CT::data_type data_type;

  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 class MultiAccessSkipList<K,T,A,Pr,R>;
  public:
    bool operator()(const value_type& left, const value_type& right) const
      {return (comp(a(left), a(right))); }
  protected:
    value_compare(const key_compare &pr) : comp(pr) {}
    key_compare comp;
    A a;
  };

private:
  data_type *data; 
  A a;  
  key_compare KeyCompare; 
  value_compare ValueCompare; 


  void scan(const iterator &where) const {}


  void scanAll(const iterator &where) const {}


  void scan(node_type *nodex) {}


  void scanAll(node_type *nodex) {}


  void scan_val(const value_type &val) const {}


  void scanAll_val(const value_type &val) const {}


  void scan_val(const key_type &val) const {}


  void scanAll_key(const key_type &val) const {}

  size_type& getItems() {}

  void setItems(const size_type sz) {}

  std::pair<size_type,node_type*>* getUpdate() {}

  size_type getScanIndex() const {}


  void setScanIndex(const size_type sz) {}

  typedef std::pair<size_type,node_type*>* pair_t;

public:
  XMultiAccessSkipList() {}

  ~XMultiAccessSkipList() {}


  void setData(void *data) {}

  data_type* getData() {}


  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) {}


  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 clear(){}

  void destroy(){}


  void swap(container_type& right) {}


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


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


  void unique(){}


  template<class Pr2> void unique(Pr2 pred){}

  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_reference value(reference value) const {}


  const_mapped_type_reference value(const_reference value) const {return 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 <unsigned int X, class K, class CT, class A, class Pr>
bool operator==(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return ((left.size() == right.size()) &&
          (std::equal(left.begin(), left.end(), right.begin())));
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator!=(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(left==right);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator<(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return lexicographical_compare(left.begin(),left.end(),right.begin(),right.end(),left.value_comp());
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator<=(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(right < left);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator>(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return (right < left);
}


template <unsigned int X, class K, class CT, class A, class Pr>
bool operator>=(const XMultiAcessSkipList<X,K,CT,A,Pr> &left, const XMultiAcessSkipList<X,K,CT,A,Pr> &right)
{
  return !(left < right);
}

//namespace std
//{

template<unsigned int X, class container_type>
void iter_swap(CS::XIterator0<X,container_type> left, CS::XIterator0<X,container_type> right) {}


template<unsigned int X, class container_type>
void reverse(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last) {}


template<unsigned int X, class container_type>
void quick_sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last) {}


template <class T, class Pr>
class XDerefT : std::binary_function<T, T, bool>
{
private:
  Pr pred; 
  XDerefT() {} 
public:

  XDerefT(const Pr &pred) : pred(pred) {}


  bool operator()(const T &a, const T &b) const { return pred(a->object,b->object); }
};


template<unsigned int X, class container_type, class Pr>
void insert_sort_N(const CS::XIterator0<X,container_type> &first, const CS::XIterator0<X,container_type> &last, const Pr &pred) {}



template<unsigned int X, class container_type, class Pr>
void insert_sort(const CS::XIterator0<X,container_type> &first, const CS::XIterator0<X,container_type> &last, const Pr &pred) {}


template<unsigned int X, class container_type>
void insert_sort(const CS::XIterator0<X,container_type> &first, const CS::XIterator0<X,container_type> &last) {}


template <class T, class Pr>
class LessEqualT : std::binary_function<T, T, bool>
{
private:
  Pr pred; 
  LessEqualT() {} 
public:

  LessEqualT(const Pr &pred) : pred(pred) {}

  bool operator()(const T &a, const T &b) const { return (!pred(b,a)); }
};


template<unsigned int X, class container_type, class Pr>
void merge_sort(CS::XIterator0<X,container_type> &first, CS::XIterator0<X,container_type> &last, const Pr &pred) {}


template<unsigned int X, class container_type>
void merge_sort(CS::XIterator0<X,container_type> &first, CS::XIterator0<X,container_type> &last) {}


template<unsigned int X, class container_type, class Pr>
void sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last, const Pr pred) {}


template<unsigned int X, class container_type, class Pr>
void stable_sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last, const Pr pred) {}


template<unsigned int X, class container_type>
void sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last) {}


template<unsigned int X, class container_type>
void stable_sort(CS::XIterator0<X,container_type> first, CS::XIterator0<X,container_type> last) {}


//}