tree.h

著名的标准C＋＋的html解析器

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

   if(tmp->next_sibling==0) {
      if(tmp->parent) // when adding nodes at the head, there is no parent
         tmp->parent->last_child=tmp;
      }
   else {
      tmp->next_sibling->prev_sibling=tmp;
      }
   return tmp;
   }

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
   {
   // insert dummy
   iter it=insert(position, value_type());
   // replace dummy with subtree
   return replace(it, subtree);
   }

// template <class T, class tree_node_allocator>
// template <class iter>
// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
//    {
//    // insert dummy
//    iter it(insert(position, value_type()));
//    // replace dummy with subtree
//    return replace(it, subtree);
//    }

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
   {
   kp::destructor(&position.node->data);
   kp::constructor(&position.node->data, x);
   return position;
   }

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>::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 *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);
   kp::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;
   kp::destructor(&current_to->data);
   alloc_.deallocate(current_to,1);
   current_to=tmp;
   
   // only at this stage can we fix 'last'
   tree_node *last=from.node->next_sibling;

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::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((++orig_begin)!=orig_end)
      orig_last=orig_last->next_sibling;
   tree_node *new_last=new_first;
   while((++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;
   }

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>::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;
   }


template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>::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((++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;
   }

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
   {
   if(from.node->first_child==0) return position;
   return reparent(position, from.node->first_child, end(from));
   }

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
   else                     dst->parent->first_child=src;
   src->prev_sibling=dst->prev_sibling;
   dst->prev_sibling=src;
   src->next_sibling=dst;
   src->parent=dst->parent;
   return src;
   }

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;

   // remember connection points
   tree_node *b_prev_sibling=dst->prev_sibling;
   tree_node *b_next_sibling=dst->next_sibling;
   tree_node *b_parent=dst->parent;

   // remove target
   erase(target);

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
   else                  b_parent->first_child=src;
   if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
   else                  b_parent->last_child=src;
   src->prev_sibling=b_prev_sibling;
   src->next_sibling=b_next_sibling;
   src->parent=b_parent;
   return src;
   }

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::merge(sibling_iterator to1,   sibling_iterator to2,
                                          sibling_iterator from1, sibling_iterator from2,
                                          bool duplicate_leaves)
   {
   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;
      }
   }


template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
   {
   std::less<T> comp;
   sort(from, to, comp, deep);
   }

template <class T, class tree_node_allocator>
template <class StrictWeakOrdering>
void tree<T, tree_node_allocator>::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) {
      if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*nit)->parent->first_child=(*nit);
      }
   else prev->next_sibling=(*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) {
      if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*eit)->parent->last_child=(*eit);
      }
   else next->prev_sibling=(*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;
         }
      }
   }

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
   {
   std::equal_to<T> comp;
   return equal(one_, two, three_, comp);
   }

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
   {
   std::equal_to<T> comp;
   return equal_subtree(one_, two_, comp);
   }

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

// if(one==two && is_valid(three) && three.number_of_children()!=0)
//    return false;
   while(one!=two && is_valid(three)) {