template<class StrictWeakOrdering>      class compare_nodes {         public:            compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};                        bool operator()(const tree_node *a, const tree_node *b)                {               static StrictWeakOrdering comp;               return comp(a->data, b->data);               }         private:            StrictWeakOrdering comp_;      };};//template <class T, class tree_node_allocator>//class iterator_base_less {// public://    bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,//                  const typename tree<T, tree_node_allocator>::iterator_base& two) const//       {//       txtout << "operatorclass<" << one.node < two.node << std::endl;//       return one.node < two.node;//       }//};// template <class T, class tree_node_allocator>// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,//                const typename tree<T, tree_node_allocator>::iterator& two)//    {//    txtout << "operator< " << one.node < two.node << std::endl;//    if(one.node < two.node) return true;//    return false;//    }// // template <class T, class tree_node_allocator>// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,//                const typename tree<T, tree_node_allocator>::iterator& two)//    {//    txtout << "operator== " << one.node == two.node << std::endl;//    if(one.node == two.node) return true;//    return false;//    }// // template <class T, class tree_node_allocator>// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,//                const typename tree<T, tree_node_allocator>::iterator_base& two)//    {//    txtout << "operator> " << one.node < two.node << std::endl;//    if(one.node > two.node) return true;//    return false;//    }// Treetemplate <class T, class tree_node_allocator>tree<T, tree_node_allocator>::tree()    {   head_initialise_();   }template <class T, class tree_node_allocator>tree<T, tree_node_allocator>::tree(const T& x)    {   head_initialise_();   set_head(x);   }template <class T, class tree_node_allocator>tree<T, tree_node_allocator>::tree(const iterator_base& other)   {   head_initialise_();   set_head((*other));   replace(begin(), other);   }template <class T, class tree_node_allocator>tree<T, tree_node_allocator>::~tree()   {   clear();   alloc_.deallocate(head,1);   alloc_.deallocate(feet,1);   }template <class T, class tree_node_allocator>void tree<T, tree_node_allocator>::head_initialise_()    {    head = alloc_.allocate(1,0); // MSVC does not have default second argument    feet = alloc_.allocate(1,0);   head->parent=0;   head->first_child=0;   head->last_child=0;   head->prev_sibling=0; //head;   head->next_sibling=feet; //head;   feet->parent=0;   feet->first_child=0;   feet->last_child=0;   feet->prev_sibling=head;   feet->next_sibling=0;   }template <class T, class tree_node_allocator>void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)   {   copy_(other);   }template <class T, class tree_node_allocator>tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)   {   head_initialise_();   copy_(other);   }template <class T, class tree_node_allocator>void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)    {   clear();   pre_order_iterator it=other.begin(), to=begin();   while(it!=other.end()) {      to=insert(to, (*it));      it.skip_children();      ++it;      }   to=begin();   it=other.begin();   while(it!=other.end()) {      to=replace(to, it);      to.skip_children();      it.skip_children();      ++to;      ++it;      }   }template <class T, class tree_node_allocator>void tree<T, tree_node_allocator>::clear()   {   if(head)      while(head->next_sibling!=feet)         erase(pre_order_iterator(head->next_sibling));   }template<class T, class tree_node_allocator> void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)   {   tree_node *cur=it.node->first_child;   tree_node *prev=0;   while(cur!=0) {      prev=cur;      cur=cur->next_sibling;      erase_children(pre_order_iterator(prev));      kp::destructor(&prev->data);      alloc_.deallocate(prev,1);      }   it.node->first_child=0;   it.node->last_child=0;   }template<class T, class tree_node_allocator> template<class iter>iter tree<T, tree_node_allocator>::erase(iter it)   {   tree_node *cur=it.node;   assert(cur!=head);   iter ret=it;   ret.skip_children();   ++ret;   erase_children(it);   if(cur->prev_sibling==0) {      cur->parent->first_child=cur->next_sibling;      }   else {      cur->prev_sibling->next_sibling=cur->next_sibling;      }   if(cur->next_sibling==0) {      cur->parent->last_child=cur->prev_sibling;      }   else {      cur->next_sibling->prev_sibling=cur->prev_sibling;      }   kp::destructor(&cur->data);   alloc_.deallocate(cur,1);   return ret;   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const   {   return pre_order_iterator(head->next_sibling);   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const   {   return pre_order_iterator(feet);   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const   {   return breadth_first_queued_iterator(head->next_sibling);   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const   {   return breadth_first_queued_iterator();   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const   {   tree_node *tmp=head->next_sibling;   if(tmp!=feet) {      while(tmp->first_child)         tmp=tmp->first_child;      }   return post_order_iterator(tmp);   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const   {   return post_order_iterator(feet);   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const   {   tree_node *tmp=pos.node;   unsigned int curdepth=0;   while(curdepth<dp) { // go down one level      while(tmp->first_child==0) {         tmp=tmp->next_sibling;         if(tmp==0)            throw std::range_error("tree: begin_fixed out of range");         }      tmp=tmp->first_child;      ++curdepth;      }   return tmp;   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const   {   assert(1==0); // FIXME: not correct yet   tree_node *tmp=pos.node;   unsigned int curdepth=1;   while(curdepth<dp) { // go down one level      while(tmp->first_child==0) {         tmp=tmp->next_sibling;         if(tmp==0)            throw std::range_error("tree: end_fixed out of range");         }      tmp=tmp->first_child;      ++curdepth;      }   return tmp;   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const   {   assert(pos.node!=0);   if(pos.node->first_child==0) {      return end(pos);      }   return pos.node->first_child;   }template <class T, class tree_node_allocator>typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const   {   sibling_iterator ret(0);   ret.parent_=pos.node;   return ret;   }template <class T, class tree_node_allocator>template <typename iter>iter tree<T, tree_node_allocator>::parent(iter position) const   {   assert(position.node!=0);   return iter(position.node->parent);   }template <class T, class tree_node_allocator>template <typename iter>iter tree<T, tree_node_allocator>::previous_sibling(iter position) const   {   assert(position.node!=0);   iter ret(position);   ret.node=position.node->prev_sibling;   return ret;   }template <class T, class tree_node_allocator>template <typename iter>iter tree<T, tree_node_allocator>::next_sibling(iter position) const   {   assert(position.node!=0);   iter ret(position);   ret.node=position.node->next_sibling;   return ret;   }template <class T, class tree_node_allocator>template <typename iter>iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const   {   assert(position.node!=0);   iter ret(position);   if(position.node->next_sibling) {      ret.node=position.node->next_sibling;      }   else {       int relative_depth=0;      upper:      do {         ret.node=ret.node->parent;         if(ret.node==0) return ret;         --relative_depth;         } while(ret.node->next_sibling==0);      lower:      ret.node=ret.node->next_sibling;      while(ret.node->first_child==0) {         if(ret.node->next_sibling==0)            goto upper;         ret.node=ret.node->next_sibling;         if(ret.node==0) return ret;         }      while(relative_depth<0 && ret.node->first_child!=0) {         ret.node=ret.node->first_child;         ++relative_depth;         }      if(relative_depth<0) {         if(ret.node->next_sibling==0) goto upper;         else                          goto lower;         }      }   return ret;   }template <class T, class tree_node_allocator>template <typename iter>iter tree<T, tree_node_allocator>::append_child(iter position)   {   assert(position.node!=head);   assert(position.node);   tree_node* tmp = alloc_.allocate(1,0);   kp::constructor(&tmp->data);   tmp->first_child=0;   tmp->last_child=0;   tmp->parent=position.node;   if(position.node->last_child!=0) {      position.node->last_child->next_sibling=tmp;      }   else {      position.node->first_child=tmp;      }   tmp->prev_sibling=position.node->last_child;   position.node->last_child=tmp;   tmp->next_sibling=0;   return tmp;   }template <class T, class tree_node_allocator>template <class iter>iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)   {   // If your program fails here you probably used 'append_child' to add the top   // node to an empty tree. From version 1.45 the top element should be added   // using 'insert'. See the documentation for further information, and sorry about   // the API change.   assert(position.node!=head);   assert(position.node);   tree_node* tmp = alloc_.allocate(1,0);   kp::constructor(&tmp->data, x);   tmp->first_child=0;   tmp->last_child=0;   tmp->parent=position.node;   if(position.node->last_child!=0) {      position.node->last_child->next_sibling=tmp;      }   else {      position.node->first_child=tmp;      }   tmp->prev_sibling=position.node->last_child;   position.node->last_child=tmp;