tree_msvc.hh

一个德国人Kasper Peeters用C++ template写的tree的STL实现

            orig_last=orig_last->next_sibling;
         tree_node *new_last=new_first;
         while(sibling_iterator(++new_begin)!=new_end)
            new_last=new_last->next_sibling;

         // insert all siblings in new_first..new_last before orig_first
         bool first=true;
         pre_order_iterator ret;
         while(1==1) {
            pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
            if(first) {
               ret=tt;
               first=false;
               }
            if(new_first==new_last)
               break;
            new_first=new_first->next_sibling;
            }

         // erase old range of siblings
         bool last=false;
         tree_node *next=orig_first;
         while(1==1) {
            if(next==orig_last) 
               last=true;
            next=next->next_sibling;
            erase((pre_order_iterator)orig_first);
            if(last) 
               break;
            orig_first=next;
            }
         return ret;
         }

      // move all children of node at 'position' to be siblings, returns position
      template<typename iter> iter flatten(iter position)
         {
         if(position.node->first_child==0)
            return position;

         tree_node *tmp=position.node->first_child;
         while(tmp) {
            tmp->parent=position.node->parent;
            tmp=tmp->next_sibling;
            } 
         if(position.node->next_sibling) {
            position.node->last_child->next_sibling=position.node->next_sibling;
            position.node->next_sibling->prev_sibling=position.node->last_child;
            }
         else {
            position.node->parent->last_child=position.node->last_child;
            }
         position.node->next_sibling=position.node->first_child;
         position.node->next_sibling->prev_sibling=position.node;
         position.node->first_child=0;
         position.node->last_child=0;

         return position;
         }


      // move nodes in range to be children of 'position'
      template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end)
         {
         tree_node *first=begin.node;
         tree_node *last=first;
         if(begin==end) return begin;
         // determine last node
         while(sibling_iterator(++begin)!=end) { 
            last=last->next_sibling;
            }
         // move subtree
         if(first->prev_sibling==0) {
            first->parent->first_child=last->next_sibling;
            }
         else {
            first->prev_sibling->next_sibling=last->next_sibling;
            }
         if(last->next_sibling==0) {
            last->parent->last_child=first->prev_sibling;
            }
         else {
            last->next_sibling->prev_sibling=first->prev_sibling;
            }
         if(position.node->first_child==0) {
            position.node->first_child=first;
            position.node->last_child=last;
            first->prev_sibling=0;
            }
         else {
            position.node->last_child->next_sibling=first;
            first->prev_sibling=position.node->last_child;
            position.node->last_child=last;
            }
         last->next_sibling=0;

         tree_node *pos=first;
         while(1==1) {
            pos->parent=position.node;
            if(pos==last) break;
            pos=pos->next_sibling;
            }

         return first;
         }

      // ditto, the range being all children of the 'from' node
      template<typename iter> iter reparent(iter position, iter from)
         {
         if(from.node->first_child==0) return position;
         return reparent(position, from.node->first_child, from.node->last_child);
         }

      // merge with other tree, creating new branches and leaves only if they are not already present
      void     merge(sibling_iterator to1,   sibling_iterator to2,
                     sibling_iterator from1, sibling_iterator from2,
                     bool duplicate_leaves=false)
         {
         sibling_iterator fnd;
         while(from1!=from2) {
            if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
               if(from1.begin()==from1.end()) { // full depth reached
                  if(duplicate_leaves)
                     append_child(parent(to1), (*from1));
                  }
               else { // descend further
                  merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
                  }
               }
            else { // element missing
               insert_subtree(to2, from1);
               }
            ++from1;
            }
         }

      // sort (std::sort only moves values of nodes, this one moves children as well)
      void     sort(sibling_iterator from, sibling_iterator to, bool deep=false)
         {
         std::less<T> comp;
         sort(from, to, comp, deep);
         }

      template<class StrictWeakOrdering>
      void     sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep)
         {
         if(from==to) return;
         // make list of sorted nodes
         // CHECK: if multiset stores equivalent nodes in the order in which they
         // are inserted, then this routine should be called 'stable_sort'.
         std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
         sibling_iterator it=from, it2=to;
         while(it != to) {
            nodes.insert(it.node);
            ++it;
            }
         // reassemble
         --it2;

         // prev and next are the nodes before and after the sorted range
         tree_node *prev=from.node->prev_sibling;
         tree_node *next=it2.node->next_sibling;
         typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
         if(prev==0) {
            (*nit)->parent->first_child=(*nit);
            }
         --eit;
         while(nit!=eit) {
            (*nit)->prev_sibling=prev;
            if(prev)
               prev->next_sibling=(*nit);
            prev=(*nit);
            ++nit;
            }
         // prev now points to the last-but-one node in the sorted range
         if(prev)
            prev->next_sibling=(*eit);

         // eit points to the last node in the sorted range.
         (*eit)->next_sibling=next;
         (*eit)->prev_sibling=prev; // missed in the loop above
         if(next==0) {
            (*eit)->parent->last_child=(*eit);
            }

         if(deep) {  // sort the children of each node too
            sibling_iterator bcs(*nodes.begin());
            sibling_iterator ecs(*eit);
            ++ecs;
            while(bcs!=ecs) {
               sort(begin(bcs), end(bcs), comp, deep);
               ++bcs;
               }
            }
         }

      // compare two ranges of nodes (compares nodes as well as tree structure)
      template <typename iter>
      bool     equal(const iter& one_, const iter& two, const iter& three_) const
         {
         std::equal_to<T> comp; 
         return equal(one_, two, three_, comp); 
         }

      template<typename iter, class BinaryPredicate>
      bool     equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
         {
         pre_order_iterator one(one_), three(three_);

         while(one!=two && is_valid(three)) {
            if(!fun(*one,*three))
               return false;
            if(one.number_of_children()!=three.number_of_children()) 
               return false;
            ++one;
            ++three;
            }
         return true;
         }


      // extract a new tree formed by the range of siblings plus all their children
      tree     subtree(sibling_iterator from, sibling_iterator to) const
         {
         tree tmp;
         tmp.set_head(value_type());
         tmp.replace(tmp.begin(), tmp.end(), from, to);
         return tmp;
         }

      void     subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
         {
         tmp.set_head(value_type());
         tmp.replace(tmp.begin(), tmp.end(), from, to);
         }

      // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)
      void     swap(sibling_iterator it)
         {
         tree_node *nxt=it.node->next_sibling;
         if(nxt) {
            if(it.node->prev_sibling)
               it.node->prev_sibling->next_sibling=nxt;
            else
               it.node->parent->first_child=nxt;
            nxt->prev_sibling=it.node->prev_sibling;
            tree_node *nxtnxt=nxt->next_sibling;
            if(nxtnxt)
               nxtnxt->prev_sibling=it.node;
            else
               it.node->parent->last_child=it.node;
            nxt->next_sibling=it.node;
            it.node->prev_sibling=nxt;
            it.node->next_sibling=nxtnxt;
            }
         }
      
      // count the total number of nodes
      int      size() const
         {
         int i=0;
         pre_order_iterator it=begin(), eit=end();
         while(it!=eit) {
            ++i;
            ++it;
            }
         return i;
         }

      // compute the depth to the root
      int      depth(const iterator_base& it) const
         {
         tree_node* pos=it.node;
         assert(pos!=0);
         int ret=0;
         while(pos->parent!=0) {
            pos=pos->parent;
            ++ret;
            }
         return ret;
         }

      // count the number of children of node at position
      unsigned int number_of_children(const iterator_base& it) const
         {
         tree_node *pos=it.node->first_child;
         if(pos==0) return 0;
         
         unsigned int ret=1;
    //   while(pos!=it.node->last_child) {  
    //      ++ret;  
    //      pos=pos->next_sibling;  
    //      }  
         while((pos=pos->next_sibling))  
            ++ret;
         return ret;
         }

      // count the number of 'next' siblings of node at iterator
      unsigned int number_of_siblings(const iterator_base& it) const
         {
         tree_node *pos=it.node;
         unsigned int ret=1;
         while(pos->next_sibling && pos->next_sibling!=head) {
            ++ret;
            pos=pos->next_sibling;
            }
         return ret;
         }

      // determine whether node at position is in the subtrees with root in the range
      bool     is_in_subtree(const iterator_base& it, const iterator_base& begin, 
                                                 const iterator_base& end) const
         {
         // FIXME: this should be optimised.
         pre_order_iterator tmp=begin;
         while(tmp!=end) {
            if(tmp==it) return true;
            ++tmp;
            }
         return false;
         }

      // determine whether the iterator is an 'end' iterator and thus not actually
      // pointing to a node
      // DEPRECATE: this causes more trouble than it's worth.
      bool     is_valid(const iterator_base& it) const
         {
         if(it.node==0) return false;
         else return true;
         }

      // determine the index of a node in the range of siblings to which it belongs.
      unsigned int index(sibling_iterator it) const
         {
         unsigned int ind=0;
         if(it.node->parent==0) { 
            while(it.node->prev_sibling!=head) { 
               it.node=it.node->prev_sibling; 
               ++ind; 
               } 
            } 
         else { 
            while(it.node->prev_sibling!=0) {
               it.node=it.node->prev_sibling;
               ++ind;
               }
            }
         return ind;
         }

      // inverse of 'index': return the n-th child of the node at position
      sibling_iterator     child(const iterator_base& it, unsigned int num) const
         {
         tree_node *tmp=it.node->first_child;
         while(num--) {
            assert(tmp!=0);
            tmp=tmp->next_sibling;
            }
         return tmp;
         }

   private:
      tree_node_allocator alloc_;
      tree_node *head;    // head is always a dummy; if an iterator points to head it is invalid
      void head_initialise_() 
         { 
         head = alloc_.allocate(1,0); // MSVC does not have default second argument 

         head->parent=0;
         head->first_child=0;
         head->last_child=0;
         head->prev_sibling=head;
         head->next_sibling=head;
         }

      void 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 StrictWeakOrdering>
      class compare_nodes {
         public:
            bool operator()(const tree_node *a, const tree_node *b)
               {
               static StrictWeakOrdering comp;

               return comp(a->data, b->data);
               }

      };
};

#endif

// Local variables:
// default-tab-width: 3
// End: