mw_matching.t

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

    // create new root f with key cur->key in case h1 == h2
    if (f == nil) {      
      GenPtr new_key = cur->key;
      copy_key(new_key);
      f = new_conc_pq_node(new_key, nil);
      f->child = cur;
      f->height = cur->height + 1;	
      f->leaves = cur->leaves;
      f->children = 1;
      cur->parent = f;
    }

    // INVARIANT: f is the parent of cur
    f->child->left = r2;
    r2->right = f->child;
    r2->left  = cur;
    cur->right = r2;
    r2->parent = f;
    
    add_leaves(f, r2->leaves);
    f->children += 1;
    
    if (cmp(f->key, r2->key) > 0)
      decrease_prio(f, r2->key);

    if (f->children > b) f = split_node(f);

    return (f->height > r1->height ? f : r1);
  }
  else { 
    // seek leftmost node cur in tree rooted at r2 
    // with height h1 and let f be the father of cur
    cur = r2;
    // next line mod. 12/01, was before: 
    // while (cur->height != h1) cur = cur->child->left;
    while (cur->height != h1) cur = cur->child;
    f = cur->parent;
    
    // INVARIANT: f is the parent of cur
    r1->left = f->child->left;
    r1->right  = cur;
    r1->parent = f;
    f->child->left->right = r1;
    f->child = r1;
    cur->left = r1;

    add_leaves(f, r1->leaves);
    f->children += 1;

    if (cmp(f->key, r1->key) > 0)
      decrease_prio(f, r1->key);

    if (f->children > b) f = split_node(f);

    return (f->height > r2->height ? f : r2);
  }
}



void conc_pq_tree::conc(conc_pq_tree &pq, int dir) {

  if (a != pq.a || b != pq.b) 
    error_handler(1, "void conc_pq_tree::conc(...): incompatible tree types");
  if (&pq == this) 
    error_handler(1, "void conc_pq_tree::conc(...): argument is identical with object"); 

  conc_pq_tree *T1 = (dir == leda::after ? this : &pq );
  conc_pq_tree *T2 = (dir == leda::after ? &pq  : this);

  // set root
  root = conc(T1->root, T2->root);
  root->tree = this;

  // determine new minptr
  if (T1->minptr == nil)
    minptr = T2->minptr;
  else if (T2->minptr == nil)
    minptr = T1->minptr;
  else {
    conc_pq_node* aux = T2->minptr;
    // CAREFUL: minptr might overwrite T2->minptr in the
    // next step, but using aux. variable is save
    minptr = T1->minptr;
    if (cmp(minptr->key, aux->key) > 0)
      minptr = aux;
  }

  // concatenate leave lists (with special cases
  // T1 or T2 empty)

  if (T1->tail_leaf == nil)
    T1->head_leaf = T2->head_leaf;
  else if (T2->tail_leaf == nil)
    T2->tail_leaf = T1->tail_leaf;
  else {
    T1->tail_leaf->succ = T2->head_leaf;
    T2->head_leaf->pred = T1->tail_leaf;
  }

  head_leaf = T1->head_leaf;
  tail_leaf = T2->tail_leaf;

  // destroy object different form *this
  if (T1 != this) {
    T1->head_leaf = T1->tail_leaf = nil;
    T1->root = T1->minptr = nil;
  }
  if (T2 != this) {
    T2->head_leaf = T2->tail_leaf = nil;
    T2->root = T2->minptr = nil;
  }
}



void conc_pq_tree::delete_node(conc_pq_node *p) {
  // deletes the node p
  
  clear_key(p->key);
  clear_inf(p->inf);  
  std_memory.deallocate_bytes(p, sizeof(conc_pq_node));

}


void conc_pq_tree::print_tree(conc_pq_node *cur, int blancs) const { 

  if (cur == 0) { 
    for(int j = 1; j <= blancs; j++) 
      cout << " ";
    cout << "NIL" << endl;
    return;
  }  
  if (cur->height == 0) { 
    for(int j = 1; j <= blancs; j++) 
      cout << " ";
    if (cmp(cur->key, infinity) == 0) 
      cout << "infty";
    else 
      print_key(cur->key); 
    cout << endl;
  }
  else {         
    conc_pq_node *it = cur->child;

    print_tree(it, blancs + 10);
    it = it->right;
    while (it != cur->child) {
      print_tree(it, blancs + 10);
      it = it->right;
    }
    for(int j = 1; j <= blancs; j++) 
      cout << " ";
    if (cmp(cur->key, infinity) == 0) 
      cout << "infty";
    else 
      print_key(cur->key); 
    cout << endl;
  }
}


void conc_pq_tree::split_at_item(conc_pq_node *p, conc_pq_tree &pq1, conc_pq_tree &pq2) {
  // splits *this at p into pq1 and pq2. pq1 contains thereafter all elements
  // of *this that preceede p (inclusive).
  // NOTICE: relevant for the split operation is the linear precedence relation
  // on the leaves and NOT the key of the elements  
  // case p == nil:         pq1 gets empty and pq2 equals *this
  // case p == last_item(): pq2 gets empty and pq1 equals *this

  if (root == nil) 
    error_handler(1, "void conc_pq_tree::split(...): pq is empty.");
  if (&pq1 == &pq2)
    error_handler(1, "void conc_pq_tree::split(...): identical arguments.");
  if (a != pq1.a || a != pq2.a || b != pq1.b || b != pq2.b) 
    error_handler(1, "void conc_pq_tree::split(...): incompatible priority queues."); 
  
  if (&pq1 != this) pq1.clear();
  if (&pq2 != this) pq2.clear();

  if (p == nil || p == last_item()) {
    // make either pq1 or pq2 a copy of *this
    conc_pq_tree *pq = (p == nil ? &pq2 : &pq1);

    // make pq equal to *this
    pq->head_leaf = head_leaf;
    pq->tail_leaf = tail_leaf;
    pq->root = root;
    // mod. 05/01
    pq->root->tree = pq;

    pq->minptr = minptr;
    
    // destroy *this
    if (pq != this) {
      head_leaf = tail_leaf = nil;
      root = minptr = nil;
    }
    return;
  }

  // store pointers to roots of left/right forest in array
  conc_pq_node **left_trees  = new conc_pq_node*[root->leaves];  
  conc_pq_node **right_trees = new conc_pq_node*[root->leaves]; 

  int left_cnt  = 0;  
  int right_cnt = 0;

  conc_pq_node *cur = p, *f, *l, *r;
  conc_pq_node *l_stop, *r_stop;

  while (cur->parent) {
    f = cur->parent;
    l = cur->left;  l_stop = f->child->left; 
    r = cur->right; r_stop = f->child;
     
    // take cur to the left forest, when cur == p (leaf) 
    if (p == cur) left_trees[left_cnt++] = cur;
    
    // collect trees to the left of cur
    while (l != l_stop) {
      left_trees[left_cnt++] = l;
      l = l->left;
    }

    // collect trees to the right of cur
    while (r != r_stop) {
      right_trees[right_cnt++] = r;
      r = r->right;
    }

    if (cur != p) delete_node(cur);
    cur = f;    
  }

  // delete root
  if (cur != p) delete_node(cur);
  
  // destroy *this
  root = nil;

  // concatenate all trees from the left forest
  // -- mod. 12/09/00: for (int i = left_cnt-1 ; i >= 0; i--) 
  int i;
  for (i = 0; i < left_cnt; i++) {
    conc_pq_node *cur = left_trees[i];
    cur->parent = nil;
    cur->left = cur->right = cur;
    // -- mod. 12/09/00: pq1.root = conc(pq1.root, cur);
    pq1.root = conc(cur, pq1.root);
  }

  // concatenate all trees from the right forest
  for (i = 0 ; i < right_cnt; i++) {
    conc_pq_node *cur = right_trees[i];
    cur->parent = nil;
    cur->left = cur->right = cur;
    pq2.root = conc(pq2.root, cur);
  }

  // determine new min: determine the min of the smaller group.
  // if this is equal to the current minptr (hard luck) the 
  // min of the larger group must be determined as well; otherwise,
  // we're done

  conc_pq_node *aux = minptr;
  
  conc_pq_tree *small_pq = (pq1.root->leaves > pq2.root->leaves ? &pq2 : &pq1);
  conc_pq_tree *large_pq = (pq1.root->leaves > pq2.root->leaves ? &pq1 : &pq2);
  
  small_pq->minptr = locate_min(small_pq->root);

  // mod. 13/01
  // CAREFULL: aux might point to an element different from the minptr of small_pq,
  // _although_ the priority of aux->key and minptr->key are equal. 
  // Eg:  this = (pq1 = 2 1 3 4 | pq2 = 7 8 2 0 0)    (pq1 large, pq2 small)
  //                                            ^aux
  // locate_min in small pq (pq2) yields:     ^
  // Hence, next line does not work
  // -- if (small_pq->minptr == aux) 
  if (cmp(small_pq->minptr->key, aux->key) == 0)
    large_pq->minptr = locate_min(large_pq->root);
  else
    large_pq->minptr = aux;

  // split leaf list
  pq1.head_leaf = head_leaf;
  pq2.tail_leaf = tail_leaf;
  pq1.tail_leaf = p;
  pq2.head_leaf = p->succ;
  pq1.tail_leaf->succ = nil;
  pq2.head_leaf->pred = nil;

  // adjust the tree pointers of the root nodes
  pq1.root->tree = &pq1;
  pq2.root->tree = &pq2;

  // destroy *this
  if ((&pq1 != this) && (&pq2 != this)) {
    minptr    = nil; 
    head_leaf = tail_leaf = nil;
  }

  delete[] left_trees;
  delete[] right_trees;
}




conc_pq_node* conc_pq_tree::locate_min(conc_pq_node *p) const {
  // determines the minimal leaf in tree rooted at p

#define _LOCATE_MIN_MACRO(ktype)\
ktype cur_key, it_key;\
while(cur->child) {\
  it = cur->child;\
  cur_key = LEDA_ACCESS(ktype, cur->key);\
  it_key  = LEDA_ACCESS(ktype, it->key);\
  while (it_key != cur_key) {\
    it = it->right;\
    it_key = LEDA_ACCESS(ktype, it->key);\
  }\
  cur = it;\
}

  conc_pq_node *cur = p, *it = nil;

  switch( key_type_id() ) {

  case CHAR_TYPE_ID:   { _LOCATE_MIN_MACRO(char);   } break;
  case INT_TYPE_ID:    { _LOCATE_MIN_MACRO(int);    } break;
  case LONG_TYPE_ID:   { _LOCATE_MIN_MACRO(long);   } break;
  case FLOAT_TYPE_ID:  { _LOCATE_MIN_MACRO(float);  } break;
  case DOUBLE_TYPE_ID: { _LOCATE_MIN_MACRO(double); } break;

  default: {
    while (cur->child) {
      it = cur->child;
      while (cmp(it->key, cur->key) != 0)
	it = it->right;
      cur = it;
    }
  } 
  break;
  }

  return cur;
}



void conc_pq_tree::decrease_prio(conc_pq_node *p, GenPtr k) {
  // starts at p and follows the path to the root of p.
  // at each node: if current key is larger than k
  // replace with k, and exit otherwise.

  conc_pq_node *cur = p;
  
  while (cur && (cmp(cur->key, k) > 0)) {
    copy_key(k);
    cur->key = k;
    cur = cur->parent;
  }         
}



conc_pq_node* conc_pq_tree::increase_prio(conc_pq_node *p, GenPtr k) {
  // starts at p and follows the path to the root of p.
  // at each node: if current key is not the min. of all children
  // replace, otherwise exit.
  // the function returns a conc_pq_node* to the node having minimal 
  // key that has been inspected during the search

#define _INCREASE_PRIO_MACRO(ktype) \
ktype old_key; \
ktype cur_key = LEDA_ACCESS(ktype, cur->key); \
ktype min_key = LEDA_ACCESS(ktype, k); \
while (cur && (cur_key != min_key)) { \
  old_key = cur_key; \
  cur->key = leda_cast(min_key); \
  if (cur->parent && (LEDA_ACCESS(ktype, cur->parent->key) == old_key)) { \
    cur_stop = cur; \
    cur = cur->right; \
    while(cur != cur_stop) { \
      cur_key = LEDA_ACCESS(ktype, cur->key); \
      if (min_key > cur_key) { min = cur; min_key = cur_key; } \
      cur = cur->right; \
    } \
    cur = cur->parent; \
  } \
  if (cur) cur_key = LEDA_ACCESS(ktype, cur->key); \
}

  conc_pq_node *cur = p, *cur_stop;
  conc_pq_node *min = cur;

  switch( key_type_id() ) {

  case CHAR_TYPE_ID:   { _INCREASE_PRIO_MACRO(char);   } break;
  case INT_TYPE_ID:    { _INCREASE_PRIO_MACRO(int);    } break;
  case LONG_TYPE_ID:   { _INCREASE_PRIO_MACRO(long);   } break;
  case FLOAT_TYPE_ID:  { _INCREASE_PRIO_MACRO(float);  } break;
  case DOUBLE_TYPE_ID: { _INCREASE_PRIO_MACRO(double); } break;

  default: {
    GenPtr old_key;
    GenPtr min_key = k;

    while (cur && (cmp(cur->key, min_key) != 0)) {
      old_key = cur->key;
      copy_key(min_key);
      cur->key = min_key;      
      if (cur->parent && (cmp(cur->parent->key, old_key) == 0)) {
	cur_stop = cur;
	cur = cur->right;	
	while(cur != cur_stop) {
	  if (cmp(min_key, cur->key) > 0) { 
	    min = cur; 
	    min_key = cur->key; 
	  }
	  cur = cur->right;
	}
        cur = cur->parent;
      }      
    }
  }
  break;
  }

  return min;

}


void conc_pq_tree::del_item(conc_pq_node *p) {
  // we do not really delete an item, but instead set the
  // key to infinity

  if (p == nil) return;

  bool was_min = (p == minptr);

  if (cmp(p->key, infinity) == 0) return;
  else {
    conc_pq_node *start = increase_prio(p, infinity);
    if (was_min) minptr = locate_min(start);
  }
}


bool conc_pq_tree::decrease_key(conc_pq_node *p, GenPtr k) {
  // the key of p is decreased to k. in case k >= p->key 
  // we return false, else true to signalize, if the operation
  // was succesfull, or not

  int r = cmp(k, p->key);

  if (r >= 0) return false;
  else {
    if (cmp(k, minptr->key) < 0)
      minptr = p;
    decrease_prio(p, k);
    return true;
  }
}




bool conc_pq_tree::increase_key(conc_pq_node *p, GenPtr k) {
  // increases the key of p to k. if p->key >= k false is returned,
  // and true otherwise

  if (p == nil) return false;
  
  bool was_min = (p == minptr);
  
  if (cmp(p->key, k) >= 0) return false;
  else {
    conc_pq_node *start = increase_prio(p, k);
    if (was_min) minptr = locate_min(start);
    return true;
  }
}





inline void conc_pq_tree::traverse_tree(conc_pq_node* cur, GenPtr k) {
  // traverses the tree. for each node v: sets the key of v to k 
  // (case k != nil), or deletes v (case k == nil)

  if (cur == nil) return; 

  register conc_pq_node* it = cur->child;