tree_msvc.hh

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

            bool operator!=(const sibling_iterator& other) const
               {
               if(other.node!=node) return true;
               else return false;
               }

            virtual iterator_base&  operator++()
               {
               if(node)
                  node=node->next_sibling;
               return *this;
               }

            virtual iterator_base&  operator--()
               {
               if(node) node=node->prev_sibling;
               else {
                  assert(parent_);
                  node=parent_->last_child;
                  }
               return *this;
               }

            virtual iterator_base&  operator+=(unsigned int num)
               {
               while(num>0) {
                  ++(*this);
                  --num;
                  }
               return (*this);
               }

            virtual iterator_base&  operator-=(unsigned int num)
               {
               while(num>0) {
                  --(*this);
                  --num;
                  }
               return (*this);
               }

            tree_node *range_first() const
               {
               tree_node *tmp=parent_->first_child;
               return tmp;
               }

            tree_node *range_last() const
               {
               return parent_->last_child;
               }

            tree_node *parent_;

         private:

            void set_parent_()
               {
               parent_=0;
               if(node==0) return;
               if(node->parent!=0)
                  parent_=node->parent;
               }
      };

      // begin/end of tree
      pre_order_iterator  begin() const
         {
         return pre_order_iterator(head->next_sibling);
         }

      pre_order_iterator  end() const
         {
         return pre_order_iterator(head);
         }

      post_order_iterator begin_post() const
         {
         tree_node *tmp=head->next_sibling;
         if(tmp!=head) {
            while(tmp->first_child)
               tmp=tmp->first_child;
            }
         return post_order_iterator(tmp);
         }

      post_order_iterator end_post() const
         {
         return post_order_iterator(head);
         }

      // begin/end of children of node
      sibling_iterator begin(const iterator_base& pos) const
         {
         if(pos.node->first_child==0) {
            return end(pos);
            }
         return pos.node->first_child;
         }

      sibling_iterator end(const iterator_base& pos) const
         {
         sibling_iterator ret(0);
         ret.parent_=pos.node;
         return ret;
         }

      template<typename iter> iter parent(iter position) const
         {
         assert(position.node!=0);
         return iter(position.node->parent);
         }

      sibling_iterator previous_sibling(const iterator_base& position) const
         {
         assert(position.node!=0);
         return sibling_iterator(position.node->prev_sibling);
         }

      sibling_iterator next_sibling(const iterator_base& position) const
         {
         assert(position.node!=0);
         if(position.node->next_sibling==0)
            return end(pre_order_iterator(position.node->parent));
         else
            return sibling_iterator(position.node->next_sibling);
         }

      void     clear()
         {
         if(head)
            while(head->next_sibling!=head)
               erase(pre_order_iterator(head->next_sibling));
         }

      // erase element at position pointed to by iterator, increment iterator
      template<typename iter> iter 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;
            }

         destructor(&cur->data);
         alloc_.deallocate(cur,1);
         return ret;
         }


      // erase all children of the node pointed to by iterator
      void     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));
            destructor(&prev->data);
            alloc_.deallocate(prev,1);
            }
         it.node->first_child=0;
         it.node->last_child=0;
         }

      // insert node as last child of node pointed to by position (first one inserts empty node)
      template<typename iter> iter append_child(iter position)
         {
         assert(position.node!=head);

         tree_node* tmp = alloc_.allocate(1,0);
         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<typename iter> iter 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);

         tree_node* tmp = alloc_.allocate(1,0);
         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;
         tmp->next_sibling=0;
         return tmp;
         }


      // the following two append nodes plus their children
      template<typename iter> iter append_child(iter position, iter other)
         {
         assert(position.node!=head);

         sibling_iterator aargh=append_child(position, value_type());
      // FIXME: really weird things happen when this is written in the shorthand  
      // form, with ++sibling_iterator(other). Shows up only with gcc 3.2.x.  
         sibling_iterator ap1=aargh; ++ap1;  
         sibling_iterator ot1=other; ++ot1;  
         return replace(aargh, ap1, other, ot1);  
         }

      template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to)
         {
         iter ret=from;

         while(from!=to) {
            insert_subtree(position.end(), from);
            ++from;
            }
         return ret;
         }

      // short-hand to insert topmost node in otherwise empty tree
      pre_order_iterator set_head(const T& x)
         {
         assert(begin()==end());
         return insert(begin(), x);
         }

      // insert node as previous sibling of node pointed to by position
      template<typename iter> iter insert(iter position, const T& x)
         {
         tree_node* tmp = alloc_.allocate(1,0);
         constructor(&tmp->data, x);
         tmp->first_child=0;
         tmp->last_child=0;

         tmp->parent=position.node->parent;
         tmp->next_sibling=position.node;
         tmp->prev_sibling=position.node->prev_sibling;
         position.node->prev_sibling=tmp;

         if(tmp->prev_sibling==0)
            tmp->parent->first_child=tmp;
         else
            tmp->prev_sibling->next_sibling=tmp;
         return tmp;
         }

      // insert node as previous sibling of node pointed to by position
      sibling_iterator insert(sibling_iterator position, const T& x)
         {
         tree_node* tmp = alloc_.allocate(1,0);
         constructor(&tmp->data, x);
         tmp->first_child=0;
         tmp->last_child=0;

         tmp->next_sibling=position.node;
         if(position.node==0) { // iterator points to end of a subtree
            tmp->parent=position.parent_;
            tmp->prev_sibling=position.range_last();
            }
         else {
            tmp->parent=position.node->parent;
            tmp->prev_sibling=position.node->prev_sibling;
            position.node->prev_sibling=tmp;
            }

         if(tmp->prev_sibling==0)
            tmp->parent->first_child=tmp;
         else
            tmp->prev_sibling->next_sibling=tmp;
         return tmp;
         }

      // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
      template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree)
         {
         // insert dummy
         iter it=insert(position, value_type());
         // replace dummy with subtree
         return replace(it, subtree);
         }

      // insert node as next sibling of node pointed to by position
      template<typename iter> iter insert_after(iter position, const T& x)
         {
         tree_node* tmp = alloc_.allocate(1,0);
         constructor(&tmp->data, x);
         tmp->first_child=0;
         tmp->last_child=0;

         tmp->parent=position.node->parent;
         tmp->prev_sibling=position.node;
         tmp->next_sibling=position.node->next_sibling;
         position.node->next_sibling=tmp;

         if(tmp->next_sibling==0) {
            tmp->parent->last_child=tmp;
            }
         else {
            tmp->next_sibling->prev_sibling=tmp;
            }
         return tmp;
         }

      // replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
      template<typename iter> iter replace(iter position, const T& x)
         {
         destructor(&position.node->data);
         constructor(&position.node->data, x);
         return position;
         }

      // replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
      template<typename iter> iter replace(iter position, const iterator_base& from)
         {
         assert(position.node!=head);

         tree_node *current_from=from.node;
         tree_node *start_from=from.node;
         tree_node *last=from.node->next_sibling;
         tree_node *current_to  =position.node;

         // replace the node at position with head of the replacement tree at from
         erase_children(position);  
         tree_node* tmp = alloc_.allocate(1,0);
         constructor(&tmp->data, (*from));
         tmp->first_child=0;
         tmp->last_child=0;
         if(current_to->prev_sibling==0) {
            current_to->parent->first_child=tmp;
            }
         else {
            current_to->prev_sibling->next_sibling=tmp;
            }
         tmp->prev_sibling=current_to->prev_sibling;
         if(current_to->next_sibling==0) {
            current_to->parent->last_child=tmp;
            }
         else {
            current_to->next_sibling->prev_sibling=tmp;
            }
         tmp->next_sibling=current_to->next_sibling;
         tmp->parent=current_to->parent;
         destructor(&current_to->data);
         alloc_.deallocate(current_to,1);
         current_to=tmp;

         pre_order_iterator toit=tmp;

         // copy all children
         do {
            assert(current_from!=0);
            if(current_from->first_child != 0) {
               current_from=current_from->first_child;
               toit=append_child(toit, current_from->data);
               }
            else {
               while(current_from->next_sibling==0 && current_from!=start_from) {
                  current_from=current_from->parent;
                  toit=parent(toit);
                  assert(current_from!=0);
                  }
               current_from=current_from->next_sibling;
               if(current_from!=last) {
                  toit=append_child(parent(toit), current_from->data);
                  }
               }
            } while(current_from!=last);

         return current_to;
         }

      // replace string of siblings (plus their children) with copy of a new string (with children); see above
      sibling_iterator replace(
         sibling_iterator orig_begin, 
         sibling_iterator orig_end, 
         sibling_iterator new_begin, 
         sibling_iterator new_end)
         {
         tree_node *orig_first=orig_begin.node;
         tree_node *new_first=new_begin.node;
         tree_node *orig_last=orig_first;
         while(sibling_iterator(++orig_begin)!=orig_end)