/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_AVL_H
#define _POLYMAKE_AVL_H "$Project: polymake $$Id: AVL.h 7402 2006-07-27 23:44:14Z gawrilow $"

#include <memory>
#include <algorithm>
#ifdef POLY_DEBUG
#  include <iostream>
#  include <GenericIO.h>
#endif

#ifndef _POLYMAKE_PLAUSIBLE_CHECKS_H
#  include <plausible_checks.h>
#endif
#ifndef _POLYMAKE_ITERATORS_H
#  include <iterators.h>
#endif
#ifndef _POLYMAKE_COMPARATORS_H
#  include <comparators.h>
#endif

namespace pm {
namespace AVL {

enum link_index { L=-1, P=0, R=1 };

/** Bit fields in \\ptr\\
    The nodes are assumed to be allocated at addresses aligned to the word boundary.
    Thus the lowest two bits of the address are always zero and so can be used for storing
    of various flags.
*/
enum Ptr_flags {
   NONE=0,
   SKEW=1,		// the subtree under this link is taller than the opposite one
   LEAF=2,		// the node pointed to is not the child of this node; it is a thread pointer
   END=SKEW|LEAF,	// the node pointed to is an apparent node in the tree head
   LINK=(-1UL & ~END)	// the rest bits hold the address
};

template <typename Node>
class Ptr {
private:
   /// pointer
   unsigned long ptr;

public:
   explicit Ptr(Node *n=0) : ptr(reinterpret_cast<unsigned long>(n)) { }

   Ptr(Node *n, Ptr_flags flags) : ptr(reinterpret_cast<unsigned long>(n) | flags) { }

   Ptr& set(Node *n, Ptr_flags flags)
   {
      ptr = reinterpret_cast<unsigned long>(n) | flags;
      return *this;
   }

   Ptr& set(Ptr_flags flags)
   {
      (ptr &= LINK) |= flags;
      return *this;
   }

   Ptr& clear(Ptr_flags flags)
   {
      ptr &= ~flags;
      return *this;
   }

   Ptr& set(Node *n)
   {
      ptr = reinterpret_cast<unsigned long>(n) | (ptr & END);
      return *this;
   }

   operator Node* () const { return reinterpret_cast<Node*>(ptr & LINK); }
   Node* get_node() const { return reinterpret_cast<Node*>(ptr & LINK); }

   operator bool() const { return ptr; }
   bool operator! () const { return !ptr; }

   Ptr& operator= (Node *n)
   {
      ptr = reinterpret_cast<unsigned long>(n);
      return *this;
   }

   Ptr_flags leaf() const { return Ptr_flags(ptr & LEAF); }
   Ptr_flags skew() const { return Ptr_flags(ptr & SKEW); }
   bool skew_strict() const { return (ptr & END)==SKEW; }
   bool end() const { return (ptr & END)==END; }

   link_index direction() const
   {
      return link_index((signed long)(ptr << sizeof(ptr)*8-2) >> sizeof(ptr)*8-2);
   }

   Ptr& set_direction(Node *n, link_index X)
   {
      ptr = reinterpret_cast<unsigned long>(n) | (X & (SKEW|LEAF));
      return *this;
   }

   bool operator== (Node *n) const
   {
      return static_cast<Node*>(*this) == n;
   }

   bool operator== (const Ptr& p) const
   {
      return static_cast<Node*>(*this) == static_cast<Node*>(p);
   }

   bool operator!= (Node *n) const
   {
      return !(*this==n);
   }

   bool operator!= (const Ptr& p) const
   {
      return !(*this==p);
   }
};

template <typename Traits> class tree;

/// Move to the next ($dir==R$) or previous ($dir==L$) node.
template <typename Traits> inline
Ptr<typename Traits::Node>
traverse(const Traits& t, Ptr<typename Traits::Node> cur, link_index Dir)
{
   Ptr<typename Traits::Node> n=t.link(cur,Dir), n2;
   if (!n.leaf())
      while (! (n2=t.link(n,link_index(-Dir))).leaf())
	 n=n2;
   return n;
}

template <typename Traits, link_index Dir>
class tree_iterator : public deref<Traits>::type {
public:
   typedef typename deref<Traits>::type traits;
   typedef bidirectional_iterator_tag iterator_category;
   typedef typename traits::Node value_type;
   typedef typename inherit_const<value_type, Traits>::type& reference;
   typedef typename inherit_const<value_type, Traits>::type* pointer;
   typedef ptrdiff_t difference_type;
   typedef tree_iterator<traits,Dir> iterator;
   typedef tree_iterator<const traits,Dir> const_iterator;
protected:
   /// pointer to the current node
   Ptr<value_type> cur;

   static const link_index Oppos=link_index(-Dir);
   typedef const tree_iterator<Traits,Oppos> reverse_iterator;
   typedef typename inherit_const<tree_iterator<traits,Oppos>, Traits>::type alt_reverse_iterator;
public:
   tree_iterator() { }
   tree_iterator(const traits& arg, const Ptr<value_type>& cur_arg)
      : traits(arg), cur(cur_arg) { }

   tree_iterator(const traits& arg, pointer cur_arg)
      : traits(arg), cur(cur_arg) { }

   tree_iterator(const iterator& it)
      : traits(it), cur(it.cur) { }

   tree_iterator(reverse_iterator& it)
      : traits(it), cur(it.cur) { }

   tree_iterator(alt_reverse_iterator& it)
      : traits(it), cur(it.cur) { }

   tree_iterator& operator= (const iterator& it)
   {
      static_cast<traits&>(*this)=it;
      cur=it.cur;
      return *this;
   }

   tree_iterator& operator= (reverse_iterator& it)
   {
      static_cast<traits&>(*this)=it;
      cur=it.cur;
      return *this;
   }

   tree_iterator& operator= (alt_reverse_iterator& it)
   {
      static_cast<traits&>(*this)=it;
      cur=it.cur;
      return *this;
   }

   reference operator* () const { return *cur; }
   pointer operator-> () const { return cur; }

   tree_iterator& operator++ ()
   {
      cur=traverse(static_cast<traits&>(*this),cur,Dir);
      return *this;
   }

   tree_iterator& operator-- ()
   {
      cur=traverse(static_cast<traits&>(*this),cur,link_index(-Dir));
      return *this;
   }

   const tree_iterator operator++ (int) { tree_iterator copy=*this; operator++(); return copy; }
   const tree_iterator operator-- (int) { tree_iterator copy=*this; operator--(); return copy; }

   template <link_index Dir2>
   bool operator== (const tree_iterator<traits,Dir2>& it) const { return cur==it.cur; }
   template <link_index Dir2>
   bool operator== (const tree_iterator<const traits,Dir2>& it) const { return cur==it.cur; }
   template <link_index Dir2>
   bool operator!= (const tree_iterator<traits,Dir2>& it) const { return cur!=it.cur; }
   template <link_index Dir2>
   bool operator!= (const tree_iterator<const traits,Dir2>& it) const { return cur!=it.cur; }

   bool at_end() const { return cur.end(); }

   template <typename,link_index> friend class tree_iterator;
   template <typename> friend class tree;
};

template <typename Traits>
class tree : public Traits {
public:
   typedef Traits tree_traits;
   typedef tree tree_type;
   typedef typename Traits::Node Node;
   typedef typename Traits::key_type key_type;
   typedef typename Traits::node_allocator_type node_allocator_type;
protected:
   typedef Ptr<Node> Ptr;

private:
   /// @not_provided
   void operator= (const tree&);

   /** Recursive procedure making an exact copy of the tree.
       @param n        root node of the subtree to be cloned
       @param lthread  previous node in the new tree
       @param rthread  next node in the new tree
       @return         the root node of the subtree copy.
   */
   Node* clone_tree(Node *n, Ptr lthread, Ptr rthread)
   {
      Node *copy=this->clone_node(n);
      if (this->link(n,L).leaf()) {
	 if (!lthread) {
	    this->link(this->head_node(),R).set(copy,LEAF);
	    lthread=end_node();
	 }
	 this->link(copy,L)=lthread;
      } else {
	 Node *lc=clone_tree(this->link(n,L), lthread, Ptr(copy,LEAF));
	 this->link(copy,L).set(lc, this->link(n,L).skew());
	 this->link(lc,P).set_direction(copy,L);
      }
      if (this->link(n,R).leaf()) {
	 if (!rthread) {
	    this->link(this->head_node(),L).set(copy,LEAF);
	    rthread=end_node();
	 }
	 this->link(copy,R)=rthread;
      } else {
	 Node *rc=clone_tree(this->link(n,R), Ptr(copy,LEAF), rthread);
	 this->link(copy,R).set(rc, this->link(n,R).skew());
	 this->link(rc,P).set_direction(copy,R);
      }
      return copy;
   }

   /** Recursive procedure converting the list fragment to the AVL subtree.
       @param left left neighbour of the leftmost leaf of the subtree to be built
       @return pair(root, rightmost leaf) of the subtree
   */
   pair<Node*,Node*> treeify(Node *left, int n) const
   {
      if (n<=2) {
	 Node *cur=this->link(left,R);
	 if (n==2) {
	    left=cur;
	    cur=this->link(left,R);
	    this->link(cur,L).set(left,SKEW);
	    this->link(left,P).set_direction(cur,L);
	 }
	 return pair<Node*,Node*>(cur,cur);
      }
      pair<Node*, Node*> subtree=treeify(left, (n-1)/2);
      Node *root=this->link(subtree.second,R);
      this->link(root,L)=subtree.first;
      this->link(subtree.first,P).set_direction(root,L);
      subtree=treeify(root, n/2);
      this->link(root,R).set(subtree.first, Ptr_flags(!(n&(n-1))) /* SKEW if n is a power of 2 */);
      this->link(subtree.first,P).set_direction(root,R);
      return pair<Node*, Node*>(root,subtree.second);
   }

   /** Converts the list structure to the AVL tree.
       The conversion is performed by relinking some pointers,
       the nodes are neither copied nor moved around in the storage.
   */
   void treeify() const
   {
      Node *root=treeify(this->head_node(),n_elem).first;
      this->link(this->head_node(),P)=root;
      this->link(root,P).set_direction(this->head_node(),P);
   }

   Ptr root_node() const { return this->link(this->head_node(),P); }
   Ptr first()     const { return this->link(this->head_node(),R); }
   Ptr last()      const { return this->link(this->head_node(),L); }
   Ptr end_node()  const { return Ptr(this->head_node(), END); }

   friend class AVL::tree_iterator<typename Traits::traits_for_iterator, R>;
   friend class AVL::tree_iterator<const typename Traits::traits_for_iterator, R>;
   friend class AVL::tree_iterator<typename Traits::traits_for_iterator, L>;
   friend class AVL::tree_iterator<const typename Traits::traits_for_iterator, L>;

   typedef binary_op_builder<typename Traits::key_comparator_type, const key_type*, const key_type*> internal_cmpb;
   typedef typename internal_cmpb::operation internal_cmp_type;

public:
   bool tree_form() const { return root_node(); }

   typedef typename Traits::traits_for_iterator traits_for_iterator;
   typedef AVL::tree_iterator<traits_for_iterator, R> iterator;
   typedef AVL::tree_iterator<const traits_for_iterator, R> const_iterator;
   typedef AVL::tree_iterator<traits_for_iterator, L> reverse_iterator;
   typedef AVL::tree_iterator<const traits_for_iterator, L> const_reverse_iterator;

   typedef Node value_type;
   typedef Node& reference;
   typedef const Node& const_reference;

   iterator begin()
   {
      return iterator(this->get_it_traits(), first());
   }
   iterator end()
   {
      return iterator(this->get_it_traits(), end_node());
   }
   const_iterator begin() const
   {
      return const_iterator(this->get_it_traits(), first());
   }
   const_iterator end() const
   {
      return const_iterator(this->get_it_traits(), end_node());
   }
   reverse_iterator rbegin()
   {
      return reverse_iterator(this->get_it_traits(), last());
   }
   reverse_iterator rend()
   {
      return reverse_iterator(this->get_it_traits(), end_node());
   }
   const_reverse_iterator rbegin() const
   {
      return const_reverse_iterator(this->get_it_traits(), last());
   }
   const_reverse_iterator rend() const
   {
      return const_reverse_iterator(this->get_it_traits(), end_node());
   }

private:
   template <typename Key, typename Comparator>
   pair<Ptr,link_index> _do_find_descend(const Key& k, const Comparator& comparator) const
   {
      typedef binary_op_builder<Comparator, const key_type*, const key_type*> cmpb;
      const typename cmpb::operation& cmp_op=cmpb::create(comparator);
      Ptr cur;
      if (!tree_form()) {
	 // quick test whether one of the list ends matches
	 cur=last();
	 cmp_value c=cmp_op(k, this->key(*cur));
	 if (c>=0 ||
	     n_elem==1 ||
	     (cur=first(), c=cmp_op(k, this->key(*cur)))<=0)
	    return pair<Ptr,link_index>(cur,link_index(c));
	 treeify();
      }
      link_index Down;
      cur=root_node();
      typename prevent_lazy<Key>::result_type K=prevent_lazy<Key>::get(k);
      while (1) {
	 Down=link_index(cmp_op(K, this->key(*cur)));
	 if (Down==P ||
	     this->link(cur,Down).leaf()) break;
	 cur=this->link(cur,Down);
      }
      return pair<Ptr,link_index>(cur,Down);
   }

   template <typename Key, typename Comparator>
   pair<Ptr,link_index> find_descend(const Key& k, const Comparator& comparator) const
   {
      return _do_find_descend(k,comparator);
   }

   template <typename Key, typename Data, typename Comparator>
   pair<Ptr,link_index> find_descend(const pair<Key,Data>& p, const Comparator& comparator) const
   {
      return _do_find_descend(pair_init_first<key_type>(p),comparator);
   }

   Node* insert_first(Node *n)
   {
      this->link(this->head_node(),L)=this->link(this->head_node(),R).set(n,LEAF);
      this->link(n,R)=this->link(n,L)=end_node();
      n_elem=1;
      return n;
   }

   template <typename Key>
   void _assign_node(Node&, const Key&, False) { }

   template <typename Key, typename Data>
   void _assign_node(Node& n, const pair<Key, Data>& p, True)
   {
      Traits::data(n)=p.second;
   }

   struct assign_op {
      template <typename Dst, typename Src>
      void operator() (Dst& dst, const Src& src) const { dst=src; }
   };

   template <typename Key>
   Node* find_insert(const Key& k)
   {
      if (!n_elem) return insert_first(this->create_node(k));
      pair<Ptr,link_index> p=find_descend(k, this->key_comparator);
      if (p.second==P) {
	 _assign_node(*p.first, k, bool2type<isomorphic_to_first<key_type, Key>::value>());
	 return p.first;
      }
      ++n_elem;
      Node *n=this->create_node(k);
      insert_rebalance(n,p.first,p.second);
      return n;
   }

   template <typename Key, typename Data, typename Operation>
   Node* find_insert(const Key& k, const Data& d, const Operation& op)
   {
      if (!n_elem) return insert_first(this->create_node(k,d));
      pair<Ptr,link_index> p=find_descend(k, this->key_comparator);
      if (p.second==P) {
	 op(Traits::data(*p.first),d);
	 return p.first;
      }
      ++n_elem;
      Node *n=this->create_node(k,d);
      insert_rebalance(n,p.first,p.second);
      return n;
   }

   void insert_rebalance(Node *n, Node *parent, link_index Down);
   void remove_rebalance(Node *n);

   template <typename Key, typename Comparator>
   Ptr find_node(const Key& k, const Comparator& comparator) const
   {
      if (!n_elem) return end_node();
      pair<Ptr,link_index> p=find_descend(k, comparator);
      return p.second==P ? p.first : end_node();
   }

private:
   void find_last_equal(Ptr& cur, link_index Dir) const
   {
      Ptr next;
      const internal_cmp_type& cmp_op=internal_cmpb::create(this->key_comparator);
      while (!this->link(cur,Dir).end()) {
	 next=traverse(*this,cur,Dir);
	 if (cmp_op(this->key(*cur), this->key(*next)) == cmp_eq)
	    cur=next;
	 else
	    break;
      }
   }

public:
   template <typename Key, typename RelOp>
   Ptr find_nearest_node(const Key& k, const RelOp&) const
   {
      if (n_elem) {
	 if (is_instance_of<Key, maximal>::value) {
	    if (identical<RelOp, polymake::operations::le>::value ||
		identical<RelOp, polymake::operations::lt>::value)
	       return last();
	    else
	       return end_node();
	 }
	 if (is_instance_of<Key, minimal>::value) {
	    if (identical<RelOp, polymake::operations::ge>::value ||
		identical<RelOp, polymake::operations::gt>::value)
	       return first();
	    else
	       return end_node();
	 }

	 pair<Ptr,link_index> p=find_descend(k, this->key_comparator);
	 switch (p.second) {
	 case P:
	    if (Traits::allow_multiple) {
	       if (identical<RelOp, polymake::operations::ge>::value ||
		   identical<RelOp, polymake::operations::gt>::value) {
		  find_last_equal(p.first, R);
	       }
	       if (identical<RelOp, polymake::operations::le>::value ||
		   identical<RelOp, polymake::operations::lt>::value) {
		  find_last_equal(p.first, L);
	       }
	    }
	    if (identical<RelOp, polymake::operations::gt>::value)
	       return traverse(*this,p.first,R);
	    if (identical<RelOp, polymake::operations::lt>::value)
	       return traverse(*this,p.first,L);
	    return p.first;

	 case R:
	    if (identical<RelOp, polymake::operations::le>::value ||
		identical<RelOp, polymake::operations::lt>::value)
	       return p.first;
	    if (identical<RelOp, polymake::operations::ge>::value ||
		identical<RelOp, polymake::operations::gt>::value)
	       return traverse(*this,p.first,R);
	    break;

	 case L:
	    if (identical<RelOp, polymake::operations::ge>::value ||
		identical<RelOp, polymake::operations::gt>::value)
	       return p.first;
	    if (identical<RelOp, polymake::operations::le>::value ||
		identical<RelOp, polymake::operations::lt>::value)
	       return traverse(*this,p.first,L);
	    break;
	 }
      }
      return end_node();
   }

   template <typename Key, typename RelOp, typename Comparator>
   Ptr find_nearest_node(const Key& k, const RelOp&, const Comparator& comparator) const
   {
      typedef binary_op_builder<Comparator, const key_type*, const key_type*> cmpb;
      const typename cmpb::operation& cmp_op=cmpb::create(comparator);
      Ptr found=end_node();
      const link_index Left= identical<RelOp, polymake::operations::ge>::value ||
	                     identical<RelOp, polymake::operations::gt>::value ? L : R,
	               Right=link_index(-Left);
      link_index Down;
      if (n_elem) {
	 typename unary_op_builder< operations::fix2<cmp_value, RelOp>, const cmp_value*>::operation good(cmp_eq);

	 if (!tree_form()) {	// we have the list form - test the ends
	    if (good(cmp_op(this->key(*this->link(this->head_node(),Right)), k)))
	       // the first node satisfies
	       return this->link(this->head_node(),Right);
	    if (n_elem==1 || !good(cmp_op(this->key(*this->link(this->head_node(),Left)), k)))
	       // the last node does not satisfy
	       return found;
	    treeify();
	 }
	 typename prevent_lazy<Key>::result_type K=prevent_lazy<Key>::get(k);
	 Ptr cur=root_node();
	 do {
	    const cmp_value diff=cmp_op(this->key(*cur), K);
	    if (good(diff)) {
	       found=cur;
	       Down=Left;
	    } else {
	       Down=Right;
	    }
	 } while (!(cur=this->link(cur,Down)).leaf());
      }
      return found;
   }

   /// Insert a given node @c n before the node @c next.
   Node* insert_node(Ptr next, Node *n)
   {
#if AVL_CHECKS
      {
	 const internal_cmp_type& cmp_op=internal_cmpb::create(this->key_comparator);
	 Ptr prev=traverse(*this,next,L);
	 AVL_CHECK(((!prev.end() && cmp_op(this->key(*prev), this->key(*n)) > (Traits::allow_multiple ? cmp_eq : cmp_lt)) ||
		    (!next.end() && cmp_op(this->key(*n), this->key(*next)) > (Traits::allow_multiple ? cmp_eq : cmp_lt))),
		   "AVL::insert - order violation");
      }
#endif
      ++n_elem;
      if (!tree_form()) {
	 Ptr prev=this->link(next,L);
	 this->link(n,L)=prev;
	 this->link(n,R)=next;
	 this->link(prev,R)=this->link(next,L).set(n,LEAF);
      } else {
	 link_index Down=L;
	 if (next.end()) {
	    next=last();
	    Down=R;
	 } else if (! this->link(next,L).leaf()) {
	    next=traverse(*this,next,L);
	    Down=R;
	 }
	 insert_rebalance(n,next,Down);
      }
      return n;
   }

   template <typename Key>
   iterator _insert(const Key& k, int2type<0>)
   {
      return iterator(this->get_it_traits(), find_insert(k));
   }

   template <typename Key, typename Data>
   iterator _insert(const Key& k, const Data& d, int2type<0>)
   {
      return iterator(this->get_it_traits(), find_insert(k,d,assign_op()));
   }

   template <typename Key, typename Data, typename Operation>
   iterator _insert(const Key& k, const Data& d, const Operation& op, int2type<0>)
   {
      return iterator(this->get_it_traits(), find_insert(k,d,op));
   }

   template <typename Key, typename Data>
   iterator _insert(const pair<Key,Data>& p, int2type<1>)
   {
      return iterator(this->get_it_traits(), find_insert(p.first,p.second,assign_op()));
   }

   template <typename Key, typename Data, typename Operation>
   iterator _insert(const pair<Key,Data>& p, const Operation& op, int2type<1>)
   {
      return iterator(this->get_it_traits(), find_insert(p.first,p.second,op));
   }

   template <typename Key>
   iterator _insert(const iterator& pos, const Key& k, int2type<2>)
   {
      return iterator(this->get_it_traits(), insert_node(pos.cur, this->create_node(k)));
   }

   template <typename Key, typename Data>
   iterator _insert(const iterator& pos, const Key& k, const Data& data, int2type<2>)
   {
      return iterator(this->get_it_traits(), insert_node(pos.cur, this->create_node(k,data)));
   }

   template <typename Key>
   iterator _insert(const reverse_iterator& pos, const Key& k, int2type<2>)
   {
      return iterator(this->get_it_traits(), insert_node(traverse(*this,pos.cur,R), this->create_node(k)));
   }

   template <typename Key, typename Data>
   iterator _insert(const reverse_iterator& pos, const Key& k, const Data& data, int2type<2>)
   {
      return iterator(this->get_it_traits(), insert_node(traverse(*this,pos.cur,R), this->create_node(k,data)));
   }

   template <typename Key>
   void _erase(const Key& k, int2type<0>)
   {
      if (empty()) return;
      pair<Ptr,link_index> p=find_descend(k, this->key_comparator);
      if (p.second!=P) return;
      remove_node(p.first);
      this->destroy_node(p.first);
   }

   void _erase(const iterator& pos, int2type<2>)
   {
      this->destroy_node(remove_node(pos.cur));
   }

   void _erase(const reverse_iterator& pos, int2type<2>)
   {
      this->destroy_node(remove_node(pos.cur));
   }

   void swap_nodes_list_form(Node *l, Node *r)
   {
      Ptr pl=this->link(l,L), pr=this->link(r,L);
      std::swap(this->link(pl,R), this->link(pr,R));
      this->link(l,L)=pr;  this->link(r,L)=pl;
      pl=this->link(l,R);  pr=this->link(r,R);
      std::swap(this->link(pl,L), this->link(pr,L));
      this->link(l,R)=pr;  this->link(r,R)=pl;
   }

public:
   template <typename Key>
   iterator find(const Key& k)
   {
      return iterator(this->get_it_traits(), find_node(k,this->key_comparator));
   }

   template <typename Key>
   const_iterator find(const Key& k) const
   {
      return const_iterator(this->get_it_traits(), find_node(k,this->key_comparator));
   }

   template <typename Key, typename Comparator>
   iterator find(const Key& k, const Comparator& comparator)
   {
      return iterator(this->get_it_traits(), find_node(k,comparator));
   }

   template <typename Key, typename Comparator>
   const_iterator find(const Key& k, const Comparator& comparator) const
   {
      return const_iterator(this->get_it_traits(), find_node(k,comparator));
   }

   template <typename Key, typename RelOp>
   iterator find_nearest(const Key& k, const RelOp& relop)
   {
      return iterator(this->get_it_traits(), find_nearest_node(k,relop));
   }

   template <typename Key, typename RelOp>
   const_iterator find_nearest(const Key& k, const RelOp& relop) const
   {
      return const_iterator(this->get_it_traits(), find_nearest_node(k,relop));
   }

   template <typename Key, typename RelOp, typename Comparator>
   iterator find_nearest(const Key& k, const RelOp& relop, const Comparator& comparator)
   {
      return iterator(this->get_it_traits(), find_nearest_node(k,relop,comparator));
   }

   template <typename Key, typename RelOp, typename Comparator>
   const_iterator find_nearest(const Key& k, const RelOp& relop, const Comparator& comparator) const
   {
      return const_iterator(this->get_it_traits(), find_nearest_node(k,relop,comparator));
   }

   template <typename Key>
   bool exists(const Key& k) const
   {
      return ! find_node(k,this->key_comparator).end();
   }

   template <typename Arg>
   struct insert_arg_helper {
      static const bool is_iterator=derived_from<Arg, iterator>::value ||
	                            derived_from<Arg, reverse_iterator>::value;
      static const bool is_pair=isomorphic_to_first<key_type, Arg>::value;
      static const int d=is_iterator*2+is_pair;
      typedef int2type<d> discr;
   };

   template <typename First>
   iterator insert(const First& first_arg)
   {
      return _insert(first_arg, typename insert_arg_helper<First>::discr());
   }

   template <typename First, typename Second>
   iterator insert(const First& first_arg, const Second& second_arg)
   {
      return _insert(first_arg, second_arg, typename insert_arg_helper<First>::discr());
   }

   template <typename First, typename Second, typename Third>
   iterator insert(const First& first_arg, const Second& second_arg, const Third& third_arg)
   {
      return _insert(first_arg, second_arg, third_arg, typename insert_arg_helper<First>::discr());
   }

   /** Insert a given node in the tree corresponding to the value of its key field.
       The tree should not already contain a node with the equal key.
   */
   Node* insert_node(Node *n)
   {
      if (n_elem) {
	 pair<Ptr,link_index> p=find_descend(this->key(*n), this->key_comparator);
	 if (Traits::allow_multiple) {
	    if (p.second==P) {
	       if (tree_form()) {
		  if (this->link(p.first, L).leaf()) {
		     p.second=L;
		  } else if (this->link(p.first, R).leaf()) {
		     p.second=R;
		  } else if (this->link(p.first, L).skew()) {
		     p.first=traverse(*this,p.first,R);
		     p.second=L;
		  } else {
		     p.first=traverse(*this,p.first,L);
		     p.second=R;
		  }
	       } else {
		  p.second=R;
	       }
	    }
	 } else {
	    AVL_CHECK(p.second==P, "multiple nodes with same key");
	 }
	 ++n_elem;
	 insert_rebalance(n,p.first,p.second);
      } else {
	 insert_first(n);
      }
      return n;
   }

   /** Delete an element if it exists.
       Delete the element the iterator points to. */
   template <typename Key_or_Iterator>
   void erase(const Key_or_Iterator& k_or_it)
   {
      _erase(k_or_it, typename insert_arg_helper<Key_or_Iterator>::discr());
   }

   /** Remove the node with a given address.
       The \\Node\\ object is not destroyed.
       @return address of the removed node
   */
   Node* remove_node(Node *n)
   {
      --n_elem;
      if (!tree_form()) {
	 Ptr next=this->link(n,R),
	     prev=this->link(n,L);
	 this->link(next,L)=prev;
	 this->link(prev,R)=next;
      } else {
	 remove_rebalance(n);
      }
      return n;
   }

   void update_node(Node *n);

   template <typename Key>
   iterator toggle(const Key& k)
   {
      if (!n_elem) {
	 return iterator(this->get_it_traits(), insert_first(this->create_node(k)));
      }
      pair<Ptr,link_index> p=find_descend(k, this->key_comparator);
      if (p.second==P) {
	 this->destroy_node(remove_node(p.first));
	 return end();
      }
      ++n_elem;
      Node *n=this->create_node(k);
      insert_rebalance(n,p.first,p.second);
      return iterator(this->get_it_traits(), Ptr(n));
   }

   /// Return the current number of nodes.
   int size() const { return n_elem; }
   bool empty() const { return n_elem==0; }

   template <typename Key>
   void push_front(const Key& k)
   {
      insert_node(first(), this->create_node(k));
   }

   template <typename Key, typename Data>
   void push_front(const Key& k, const Data& data)
   {
      insert_node(first(), this->create_node(k,data));
   }

   void push_front_node(Node *n)
   {
      insert_node(first(), n);
   }

   template <typename Key>
   void push_back(const Key& k)
   {
      insert_node(end_node(), this->create_node(k));
   }

   template <typename Key, typename Data>
   void push_back(const Key& k, const Data& data)
   {
      insert_node(end_node(), this->create_node(k,data));
   }

   void push_back_node(Node *n)
   {
      insert_node(end_node(), n);
   }

   reference front() { return *first(); }
   const_reference front() const { return *first(); }
   reference back() { return *last(); }
   const_reference back() const { return *last(); }

   void pop_front()
   {
      this->destroy_node(remove_node(first()));
   }

   void pop_back()
   {
      this->destroy_node(remove_node(last()));
   }

   /** Makes the tree look like empty.
       Nodes are not destroyed.
   */
   void init()
   {
      this->link(this->head_node(),L)=this->link(this->head_node(),R)=end_node();
      this->link(this->head_node(),P)=0;
      n_elem=0;
   }

private:
   void destroy_nodes(bool force=false)
   {
      Ptr n=last();
      while (!n.end() && (force || this->own_node(n))) {
	 Node *to_delete=n;
	 n=traverse(*this,n,L);
	 this->destroy_node(to_delete);
      }
   }

public:
   /// Make the tree empty, destroy the nodes.
   void clear()
   {
      if (n_elem) {
	 destroy_nodes(true);
	 init();
      }
   }

   /// Creates an empty tree.
   tree() { init(); }

   tree(typename Traits::arg_type traits_arg) : Traits(traits_arg) { init(); }

   /** Create a copy of another tree.
       The current form (list or tree) is also inherited.
   */
   tree(const tree& t) : Traits(t)
   {
      if (t.tree_form()) {
	 n_elem=t.n_elem;
	 Node *root=clone_tree(t.root_node(), Ptr(), Ptr());
	 this->link(this->head_node(),P)=root;
	 this->link(root,P).set_direction(this->head_node(),P);
      } else {		// list form
	 init();
	 for (Ptr n=t.first(); !n.end(); n=t.link(n,R))
	    insert_node(end_node(),this->clone_node(n));
      }
   }

private:
   template <typename Iterator>
   void _fill(Iterator& src, True)
   {
      for (; !src.at_end(); ++src)
	 push_back(src.index(), *src);
   }

   template <typename Iterator>
   void _fill(Iterator& src, False)
   {
      for (; !src.at_end(); ++src)
	 push_back(*src);
   }

   template <typename Iterator>
   void _fill(Iterator& src)
   {
      _fill(src, bool2type< check_iterator_feature<Iterator,indexed>::value &&
		            isomorphic_types<typename iterator_traits<Iterator>::value_type,
	                                     typename Node::data_type>::value >());
   }
public:
   template <typename Iterator>
   tree(Iterator src, Iterator end)
   {
      init();
      for (; src != end; ++src)
	 push_back(*src);
   }

   template <typename Iterator>
   explicit tree(Iterator src, typename enable_if_iterator<Iterator,end_sensitive>::type=0)
   {
      init(); _fill(src);
   }

   ~tree() { destroy_nodes(); }

   void swap(tree& t)
   {
      if (this==&t) return;
      std::swap(static_cast<Traits&>(*this), static_cast<Traits&>(t));
      std::swap(n_elem, t.n_elem);
   }

   friend void relocate(tree* from, tree* to)
   {
      pm::relocate(static_cast<Traits*>(from), static_cast<Traits*>(to));
      if (from->n_elem) {
	 to->n_elem=from->n_elem;
	 to->link(to->first(),L)=to->link(to->last(),R)=to->end_node();
	 if (to->tree_form())
	    to->link(to->root_node(),P).set_direction(to->head_node(), P);
      } else {
	 to->init();
      }
   }

   template <typename Iterator>
   void assign(Iterator src) { clear(); _fill(src); }

#ifdef POLY_DEBUG
private:
   struct check_ret {
      /// height and weight of the visited subtree
      int h, w;
   };

   check_ret
   check_tree(Ptr n, const char *prefix, bool is_leftmost, bool is_rightmost, const internal_cmp_type& cmp_op) const
   {
      check_ret l={ 0, 0 }, r={ 0, 0 };
      Ptr left=this->link(n,L),
	  right=this->link(n,R);
      if (left.end()) {
	 if (!is_leftmost) cerr << prefix << "bad END <-- " << this->key(*n) << endl;
	 else if (this->link(left,R) != n) cerr << prefix << "bad LEFTMOST" << endl;
      } else {
	 if (cmp_op(this->key(*left),this->key(*n)) > (Traits::allow_multiple ? cmp_eq : cmp_lt))
	    cerr << prefix << "order violation: " << this->key(*left) << " <-- " << this->key(*n) << endl;
	 if (!left.leaf()) {
	    if (this->link(left,P) != n || this->link(left,P).direction() != L)
	       cerr << prefix << this->key(*left) << " : P broken" << endl;
	    l=check_tree(left,prefix,is_leftmost,false,cmp_op);
	 }
      }
      if (right.end()) {
	 if (!is_rightmost) cerr << prefix << this->key(*n) << " --> bad END" << endl;
	 else if (this->link(right,L) != n) cerr << prefix << "bad RIGHTMOST" << endl;
      } else {
	 if (cmp_op(this->key(*n),this->key(*right)) > (Traits::allow_multiple ? cmp_eq : cmp_lt))
	    cerr << prefix << "order violation: " << this->key(*n) << " --> " << this->key(*right) << endl;
	 if (!right.leaf()) {
	    if (this->link(right,P) != n || this->link(right,P).direction() != R)
	       cerr << prefix << this->key(*right) << " : P broken" << endl;
	    r=check_tree(right,prefix,false,is_rightmost,cmp_op);
	 }
      }
      if (l.h-r.h<-1 || l.h-r.h>1) {
	 cerr << prefix << "disbalance: (" << l.h << ") <-- " << this->key(*n) << " --> (" << r.h << ")" << endl;
      }
      if (left.skew_strict()) {
	 if (l.h<=r.h) cerr << prefix << "SKEW <-- " << this->key(*n) << endl;
      } else {
	 if (l.h>r.h) cerr << prefix << "!SKEW <-- " << this->key(*n) << endl;
      }
      if (right.skew_strict()) {
	 if (r.h<=l.h) cerr << prefix << this->key(*n) << "--> SKEW" << endl;
      } else {
	 if (r.h>l.h) cerr << prefix << this->key(*n) << "--> !SKEW" << endl;
      }
      r.h=std::max(r.h,l.h)+1;
      r.w=r.w+l.w+1;
      return r;
   }

   /// Dump the subtree.
   void dump_tree(Ptr n, int depth) const
   {
      if (! this->link(n,R).leaf())
	 dump_tree(this->link(n,R), depth+3);
      cerr << std::setw(depth) << (n.skew() ? "*" : " ") << std::setw(0) << this->key(*n) << endl;
      if (! this->link(n,L).leaf())
	 dump_tree(this->link(n,L), depth+3);
   }
public:
   /** Check the integrity of the tree.
       @param prefix a string to be prepended to each error message
   */
   void check(const char *prefix) const
   {
      int n=0;
      if (this->link(this->head_node(),P).direction() != P)
	 cerr << prefix << "root pointer - wrong direction" << endl;
      const internal_cmp_type& cmp_op=internal_cmpb::create(this->key_comparator);
      if (Ptr root=root_node()) {
	 if (this->link(root,P) != this->head_node() || this->link(root,P).direction() != P)
	    cerr << prefix << "root node " << this->key(*root_node()) << " : P broken" << endl;
	 n=(check_tree(root,prefix,true,true,cmp_op)).w;
      } else {
	 Ptr cur=first(), prev=end_node();
	 while (!cur.end()) {
	    if (!this->link(cur,L).leaf())
	       cerr << prefix << this->key(*cur) << " L !leaf" << endl;
	    if (this->link(cur,L) != prev)
	       cerr << prefix << this->key(*cur) << " L broken" << endl;
	    if (!prev.end() && cmp_op(this->key(*prev),this->key(*cur)) > (Traits::allow_multiple ? cmp_eq : cmp_lt))
	       cerr << prefix << "order violation: " << this->key(*prev) << " --> " << this->key(*cur) << endl;
	    prev=cur;
	    if (!this->link(cur,R).leaf())
	       cerr << prefix << this->key(*cur) << " R !leaf" << endl;
	    cur=this->link(cur,R);
	    ++n;
	 }
	 if (prev != last()) cerr << prefix << "RIGHTMOST broken" << endl;
      }
      if (n != n_elem)
      cerr << prefix << "element count=" << n_elem << " != " << n << endl;
   }

   void dump() const
   {
      if (tree_form()) {
	 dump_tree(root_node(),1);
      } else {
	 for (Ptr cur=first(); !cur.end(); cur=traverse(*this,cur,R))
	    cerr << this->key(*cur) << ", ";
      }
      cerr << endl;
   }
#endif // POLY_DEBUG

private:
   /// current number of nodes
   int n_elem;
};


template <typename Traits>
void tree<Traits>::insert_rebalance(Node *n, Node *parent, link_index Tonew)
{
   link_index Oppos=link_index(-Tonew);
   this->link(n,Oppos).set(parent,LEAF);

   if (!tree_form()) {
      this->link((this->link(n,Tonew)=this->link(parent,Tonew)), Oppos).set(n,LEAF);
      this->link(parent,Tonew).set(n,LEAF);
      return;
   }

   if ((this->link(n,Tonew)=this->link(parent,Tonew)).end())
      this->link(this->head_node(),Oppos).set(n,LEAF);
   this->link(n,P).set_direction(parent,Tonew);
   if (this->link(parent,Oppos).skew_strict()) {
      this->link(parent,Oppos).clear(SKEW);
      this->link(parent,Tonew)=n;
      return;
   }

   this->link(parent,Tonew).set(n,SKEW);
   Node *root=root_node();
   while (parent != root) {
      n=parent;
      parent=this->link(n,P);
      Tonew=this->link(n,P).direction();
      Oppos=link_index(-Tonew);

      if (this->link(parent,Tonew).skew()) {
	 Node *grandparent=this->link(parent,P);
	 link_index Down=this->link(parent,P).direction();

	 if (this->link(n,Tonew).skew_strict()) {	// single rotation
	    if (this->link(n,Oppos).leaf())
	       this->link(parent,Tonew).set(n,LEAF);
	    else
	       this->link((this->link(parent,Tonew)=(Node*)this->link(n,Oppos)),P).set_direction(parent,Tonew);

	    this->link(grandparent,Down).set(n);
	    this->link(n,P).set_direction(grandparent,Down);
	    this->link(parent,P).set_direction(n,Oppos);
	    this->link(n,Tonew).clear(SKEW);
	    this->link(n,Oppos)=parent;
	 } else {				// double rotation
	    Node *n2=this->link(n,Oppos);
	    if (this->link(n2,Tonew).leaf()) {
	       this->link(n,Oppos).set(n2,LEAF);
	    } else {
	       this->link((this->link(n,Oppos)=(Node*)this->link(n2,Tonew)),P).set_direction(n,Oppos);
	       this->link(parent,Oppos).set( this->link(n2,Tonew).skew() );
	    }
	    if (this->link(n2,Oppos).leaf()) {
	       this->link(parent,Tonew).set(n2,LEAF);
	    } else {
	       this->link((this->link(parent,Tonew)=(Node*)this->link(n2,Oppos)),P).set_direction(parent,Tonew);
	       this->link(n,Tonew).set( this->link(n2,Oppos).skew() );
	    }

	    this->link(grandparent,Down).set(n2);
	    this->link(n2,P).set_direction(grandparent,Down);
	    this->link(n2,Tonew)=n;
	    this->link(n,P).set_direction(n2,Tonew);
	    this->link(n2,Oppos)=parent;
	    this->link(parent,P).set_direction(n2,Oppos);
	 }
	 break;
      }

      if (this->link(parent,Oppos).skew()) {
	 this->link(parent,Oppos).clear(SKEW);
	 break;
      }

      this->link(parent,Tonew).set(SKEW);
   }
}

template <typename Traits>
void tree<Traits>::remove_rebalance(Node *n)
{
   if (!n_elem) {		// the last element removed - tree got empty
      this->link(this->head_node(),L)=this->link(this->head_node(),R)=end_node();
      this->link(this->head_node(),P)=0;
      return;
   }

   Node *lf=n;
   Node *parent=this->link(n,P);
   link_index Down=this->link(n,P).direction();
   if (! this->link(n,L).leaf() && ! this->link(n,R).leaf()) {
      link_index Descend;			// the node to be removed has both subtrees, find the
      Node *neighbor_leaf;			// lexicographically adjacent as replacement
      if (this->link(n,L).skew()) {
	 neighbor_leaf=traverse(*this, Ptr(n), R);
	 Descend=L;
      } else {
	 neighbor_leaf=traverse(*this, Ptr(n), L);
	 Descend=R;
      }
      link_index Oppos=link_index(-Descend), lf_Down=Descend;
      while (1) {
	 lf=this->link(lf,lf_Down);
	 if (this->link(lf,Oppos).leaf()) break;
	 lf_Down=Oppos;
      }
      this->link(neighbor_leaf,Descend).set(lf,LEAF);

      this->link(parent,Down).set(lf);
      this->link((this->link(lf,Oppos)=this->link(n,Oppos)), P).set_direction(lf,Oppos);

      if (lf_Down==Descend) {
	 if (!this->link(n,Descend).skew() && this->link(lf,Descend).skew_strict())
	    this->link(lf,Descend).clear(SKEW);
	 this->link(lf,P).set_direction(parent,Down);
	 parent=lf;
      } else {
	 Node *lf_parent=this->link(lf,P);
	 if (this->link(lf,Descend).leaf()) {
	    this->link(lf_parent,lf_Down).set(lf,LEAF);
	 } else {
	    Node *n2=this->link(lf,Descend);
	    this->link(lf_parent,lf_Down).set(n2);
	    this->link(n2,P).set_direction(lf_parent,lf_Down);
	 }
	 this->link((this->link(lf,Descend)=this->link(n,Descend)), P).set_direction(lf,Descend);
	 this->link(lf,P).set_direction(parent,Down);
	 parent=lf_parent;
      }
      Down=lf_Down;
   } else {
      link_index Toleaf= this->link(n,L).leaf() ? L : R;
      link_index Oppos=link_index(-Toleaf);
      if (this->link(n,Oppos).leaf()) {
	 if ((this->link(parent,Down)=this->link(n,Down)).end())
	    this->link(this->head_node(),link_index(-Down)).set(parent,LEAF);
      } else {
	 Node *n2=this->link(n,Oppos);
	 this->link(parent,Down).set(n2);
	 this->link(n2,P).set_direction(parent,Down);
	 if ((this->link(n2,Toleaf)=this->link(n,Toleaf)).end())
	    this->link(this->head_node(),Oppos).set(n2,LEAF);
      }
   }

   // rebalance the tree
   while (parent != this->head_node()) {
      Node *cur=parent;
      link_index Todel=Down, Oppos=link_index(-Todel);
      parent=this->link(cur,P);
      Down=this->link(cur,P).direction();
      if (this->link(cur,Todel).skew_strict()) {
	 this->link(cur,Todel).clear(SKEW);
      } else if (this->link(cur,Oppos).skew_strict()) {
	 Node *n1=this->link(cur,Oppos);
	 if (this->link(n1,Todel).skew()) {        // double rotation
	    Node *n2=this->link(n1,Todel);
	    if (this->link(n2,Todel).leaf()) {
	       this->link(cur,Oppos).set(n2,LEAF);
	    } else {
	       this->link((this->link(cur,Oppos)=(Node*)this->link(n2,Todel)),P).set_direction(cur,Oppos);
	       this->link(n1,Oppos).set( this->link(n2,Todel).skew() );
	    }
	    if (this->link(n2,Oppos).leaf()) {
	       this->link(n1,Todel).set(n2,LEAF);
	    } else {
	       this->link((this->link(n1,Todel)=(Node*)this->link(n2,Oppos)),P).set_direction(n1,Todel);
	       this->link(cur,Todel).set( this->link(n2,Oppos).skew() );
	    }

	    this->link(parent,Down).set(n2);
	    this->link(n2,P).set_direction(parent,Down);
	    this->link(n2,Todel)=cur;
	    this->link(cur,P).set_direction(n2,Todel);
	    this->link(n2,Oppos)=n1;
	    this->link(n1,P).set_direction(n2,Oppos);
	 } else {					// single rotation
	    if (this->link(n1,Todel).leaf())
	       this->link(cur,Oppos).set(n1,LEAF);
	    else
	       this->link((this->link(cur,Oppos)=this->link(n1,Todel)),P).set_direction(cur,Oppos);

	    this->link(parent,Down).set(n1);
	    this->link(n1,P).set_direction(parent,Down);
	    this->link(n1,Todel)=cur;
	    this->link(cur,P).set_direction(n1,Todel);
	    if (this->link(n1,Oppos).skew_strict()) {
	       this->link(n1,Oppos).clear(SKEW);
	    } else {
	       this->link(n1,Todel).set(SKEW);
	       this->link(cur,Oppos).set(SKEW);
	       break;
	    }
	 }
      } else if (! this->link(cur,Oppos).leaf()) {
	 this->link(cur,Oppos).set(SKEW);
	 break;
      }
   }
}

template <typename Traits>
void tree<Traits>::update_node(Node *n)
{
   if (n_elem<=1) return;
   const internal_cmp_type& cmp_op=internal_cmpb::create(this->key_comparator);

   if (tree_form()) {
      Ptr l=traverse(*this,Ptr(n),L), r=traverse(*this,Ptr(n),R);
      if ((!l.end() && cmp_op(this->key(*l), this->key(*n))==cmp_gt) ||
	  (!r.end() && cmp_op(this->key(*r), this->key(*n))==cmp_lt)) {
	 --n_elem;
	 remove_rebalance(n);
	 insert_node(n);
      }

   } else {
      Ptr next(n);
      do
	 next=this->link(next,L);
      while (!next.end() && cmp_op(this->key(*next), this->key(*n)) == cmp_gt);
      next=this->link(next,R);
      if (next != n) {
	 swap_nodes_list_form(next,n);
	 return;
      }

      do
	 next=this->link(next,R);
      while (!next.end() && cmp_op(this->key(*n), this->key(*next)) == cmp_gt);
      next=this->link(next,L);
      if (next != n) {
	 swap_nodes_list_form(n,next);
      }
   }
}

/** Standard node of an AVL tree
    @tmplparam K type of the key field
    @tmplparam D type of the data field
*/
template <typename K, typename D>
struct node {
   typedef D data_type;
   typedef pair<const K, D> value_type;

   /// links in the tree
   Ptr<node> links[3];
   /// key and data fields
   value_type key_and_data;

   template <typename Key>
   explicit node(const Key& key_arg)
      : key_and_data(key_arg,D()) { }

   template <typename Key, typename Data>
   explicit node(const pair<Key,Data>& p)
      : key_and_data(p) { }

   template <typename Key, typename Data>
   node(const Key& key_arg, const Data& data_arg)
      : key_and_data(key_arg,data_arg) { }

   template <typename Key>
   node(const Key& key_arg, const nothing&)
      : key_and_data(key_arg,D()) { }

   /// doesn't copy the tree links
   node(const node& o) : key_and_data(o.key_and_data) { }
};

/** Key-data pair access filter for @c node.
    Key field is referred to as @c first, data field as @c second.
*/
template <typename NodeRef, bool _no_data=identical<typename deref<NodeRef>::type::data_type, nothing>::value>
struct node_accessor_impl {
   typedef NodeRef argument_type;
   typedef typename inherit_ref<typename deref<NodeRef>::type::value_type, NodeRef>::type result_type;
   result_type operator() (argument_type n) const { return n.key_and_data; }
};

template <typename NodeRef>
struct node_accessor_impl<NodeRef, true> {
   typedef NodeRef argument_type;
   typedef typename inherit_ref<typename deref<NodeRef>::type::value_type::first_type, NodeRef>::type result_type;
   result_type operator() (argument_type n) const { return n.key_and_data.first; }
};

template <typename NodeRef>
struct node_accessor : node_accessor_impl<NodeRef> { };

template <typename K, typename D, typename Comparator>
struct it_traits {
   typedef node<K,D> Node;

   static Ptr<Node>& link(Node *n, link_index X) { return n->links[X-L]; }

   const it_traits& get_it_traits() const { return *this; }
};

template <typename K, typename D, typename Comparator>
class traits : public it_traits<K,D,Comparator> {
public:
   typedef it_traits<K,D,Comparator> traits_for_iterator;
   typedef typename traits_for_iterator::Node Node;
   typedef K key_type;
   typedef Comparator key_comparator_type;
   static const bool allow_multiple=false;
   typedef std::allocator<Node> node_allocator_type;

protected:
   mutable Ptr<Node> root_links[3];
   key_comparator_type key_comparator;
   node_allocator_type node_allocator;

   Node* head_node() const { return reinterpret_cast<Node*>(&root_links[0]); }

   static const K& key(const Node& n) { return n.key_and_data.first; }

   static D& data(Node& n) { return n.key_and_data.second; }

   template <typename Key, typename Data>
   Node* _create_from_pair(const pair<Key,Data>& arg, False)
   {
      return new(node_allocator.allocate(1)) Node(arg.first, arg.second);
   }

   template <typename Key1, typename Key2>
   Node* _create_from_pair(const pair<Key1,Key2>& arg, True)
   {
      return new(node_allocator.allocate(1)) Node(arg, nothing());
   }

   template <typename Key1, typename Key2>
   Node* create_node(const pair<Key1,Key2>& arg)
   {
      return _create_from_pair(arg, bool2type<isomorphic_types<pair<Key1,Key2>, key_type>::value>());
   }

   template <typename Key>
   Node* create_node(const Key& key_arg)
   {
      return new(node_allocator.allocate(1)) Node(key_arg);
   }

   template <typename Key, typename Data>
   Node* create_node(const Key& key_arg, const Data& data_arg)
   {
      return new(node_allocator.allocate(1)) Node(key_arg, data_arg);
   }

   Node* clone_node(Node *n)
   {
      return new(node_allocator.allocate(1)) Node(*n);
   }

   void destroy_node(Node *n)
   {
      node_allocator.destroy(n);
      node_allocator.deallocate(n,1);
   }

   static bool own_node(Node*) { return true; }

public:
   typedef const key_comparator_type& arg_type;

   traits() { }
   explicit traits(arg_type cmp_arg) : key_comparator(cmp_arg) { }

   static int max_size()
   {
      return (unsigned int)-1/sizeof(Node);
   }

   const key_comparator_type& get_comparator_object() const { return key_comparator; }
};

} // end namespace AVL

template <typename Traits, AVL::link_index Dir>
struct check_iterator_feature<AVL::tree_iterator<Traits,Dir>, end_sensitive> : True { };

template <typename Traits, AVL::link_index Dir>
struct iterator_reversed< AVL::tree_iterator<Traits,Dir> > {
   typedef AVL::tree_iterator<Traits, AVL::link_index(-Dir)> type;

   static
   const AVL::tree_iterator<Traits,Dir>& revert(const type& it)
   {
      return reinterpret_cast<const AVL::tree_iterator<Traits,Dir>&>(it);
   }
};

} // end namespace pm

namespace std {
   template <typename Traits>
   inline void swap(pm::AVL::tree<Traits>& t1, pm::AVL::tree<Traits>& t2) { t1.swap(t2); }
}

#endif // _POLYMAKE_AVL_H

// Local Variables:
// mode:C++
// End:
