gatreebase.cpp

遗传算法工具箱C++

    if(bchild){
      bchild->parent = a;
      for(GANodeBASE * n=bchild->next; n && n != bchild; n=n->next)
	n->parent = a;
    }

    if(anext == b && bnext != a){         // same as b->prev = a
      a->prev = b;
      a->next = bnext;
      b->prev = aprev;
      b->next = a;
      aprev->next = b;
      bnext->prev = a;
    }
    else if(bnext == a && anext != b){    // same as a->prev = b
      a->prev = bprev;
      a->next = b;
      b->prev = a;
      b->next = anext;
      anext->prev = b;
      bprev->next = a;
    }
  }
  else{				    // a & b are not adjacent
    if(bprev == b || bnext == b){
      a->prev = a;
      a->next = a;
    }
    else{
      a->prev = bprev;
      a->next = bnext;
      bprev->next = a;
      bnext->prev = a;
    }
    if(aprev == a || anext == a){
      b->prev = b;
      b->next = b;
    }
    else{
      b->prev = aprev;
      b->next = anext;
      aprev->next = b;
      anext->prev = b;
    }

    if(achild == b){		// same as b->parent = a
      a->parent = b;
      a->child = bchild;
      b->parent = aparent;
      b->child = a;
      if(aparent && aparent->child == a) aparent->child = b;
      for(GANodeBASE * n=a->next; n && n != a; n=n->next)
	n->parent = b;
      if(bchild){
	bchild->parent = a;
	for(GANodeBASE * n=bchild->next; n && n != bchild; n=n->next)
	  n->parent = a;
      }
    }
    else if(bchild == a){	// same as a->parent = b
      a->parent = bparent;
      a->child = b;
      b->parent = a;
      b->child = achild;
      if(bparent && bparent->child == b) bparent->child = a;
      if(achild){
	achild->parent = b;
	for(GANodeBASE * n=achild->next; n && n != achild; n=n->next)
	  n->parent = b;
      }
      for(GANodeBASE * n=b->next; n && n != b; n=n->next)
	n->parent = a;
    }
    else{			// a and b are not adjacent nor parent-child
      a->parent = bparent;
      a->child = bchild;
      b->parent = aparent;
      b->child = achild;
      if(aparent == bparent){
	if(aparent && aparent->child == a) aparent->child = b;
	else if(bparent && bparent->child == b) bparent->child = a;
      }
      else{
	if(aparent && aparent->child == a) aparent->child = b;
	if(bparent && bparent->child == b) bparent->child = a;
      }
      if(achild){
	achild->parent = b;
	for(GANodeBASE * n=achild->next; n && n != achild; n=n->next)
	  n->parent = b;
      }
      if(bchild){
	bchild->parent = a;
	for(GANodeBASE * n=bchild->next; n && n != bchild; n=n->next)
	  n->parent = a;
      }
    }
  }

  if(rt == a) rt = b;		// this only works if they're in the same tree!
  else if(rt == b) rt = a;

  return NO_ERR;
}


// Return the number of nodes in the tree.  We do a complete traversal of the
// tree and count the number of nodes that we encounter.  Could do this breadth
// first or depth first - doesn't really matter.  We have to traverse the 
// entire tree to do the count.
//   We have to do a little work-around here to get through the const-ness of
// the size method.  Its ok to call size on a const object because it does not
// modify the logical state of the object.  It does, however, modify the
// physical state of the object.  So to work around the strictness of the 
// const specifier, we do a little pointer magic and cast this to be non-const.
int
GATreeBASE::size() const
{
  if(!csz) return sz;
  GATreeBASE * This = CON_CAST(GATreeBASE *, this);
  This->csz = 0;
  return(This->sz = _GATreeSize(rt));
}


// Return the number of levels in the tree.  We do a complete traversal of the
// tree and keep a count of the number of times we go down and come up a level.
// I should be able to combine _size and _depth so we don't have to do two
// traversals...
int
GATreeBASE::depth() const
{
  if(!cdpth) return dpth;
  GATreeBASE * This = CON_CAST(GATreeBASE *, this);
  This->cdpth = 0;
  return(This->dpth = _GATreeDepth(rt));
}


// Is node i an ancestor of node j or vice versa?  If so, we return 1.  Other-
// wise we return a 0.
int 
GATreeBASE::ancestral(unsigned int i, unsigned int j) const {
  GATreeIterBASE aiter(*this);
  GATreeIterBASE biter(*this);
  GANodeBASE * aparent, *a;
  GANodeBASE * bparent, *b;
  aparent = a = aiter.warp(i); 
  bparent = b = biter.warp(j);

  while(aparent && aparent != b)
    aparent = aparent->parent;
  if(aparent == b) return 1;
  while(bparent && bparent != a)
    bparent = bparent->parent;
  if(bparent == a) return 1;

  return 0;
}


/* ----------------------------------------------------------------------------
Recursive routines for the TreeBASE objects
---------------------------------------------------------------------------- */
static int
_GATreeSize(GANodeBASE * node)
{
  if(!node) return 0;
  int count = 1 + _GATreeSize(node->child);
  for(GANodeBASE * tmp=node->next; tmp && tmp != node; tmp=tmp->next){
    count++;
    count += _GATreeSize(tmp->child);
  }
  return count;
}


static int
_GATreeDepth(GANodeBASE * node)
{
  if(!node) return 0;
  int depth;
  int maxdepth = 1 + _GATreeDepth(node->child);
  for(GANodeBASE * tmp=node->next; tmp != node; tmp=tmp->next){
    depth = 1 + _GATreeDepth(tmp->child);
    maxdepth = maxdepth > depth ? maxdepth : depth;
  }
  return maxdepth;
}





/* ----------------------------------------------------------------------------
TreeIterBASE
---------------------------------------------------------------------------- */
// Return the root of the specified node.
GANodeBASE * 
GATreeIterBASE::root(GANodeBASE * c)
{
  if(!c) return (GANodeBASE *)0;
  while(c->parent != (GANodeBASE *)0)
    c = c->parent;
  return(node = c);
}


// Return the eldest child in a row of siblings.  The eldest is the one that 
// the parent of that row points to.
//   This could get into an infinite loop if the tree structure were ever 
// corrupted, so be sure that it doesn't!  Also, it will break if the parent
// member is not set in any child, so be sure that never happens either.
//   Remember to set the current node to the one we found.
GANodeBASE * 
GATreeIterBASE::eldest(GANodeBASE * c)
{
  if(!c) return (GANodeBASE *)0;
  if(!c->parent) return(node=c);

  GANodeBASE * tmp = c;

  while(tmp->parent->child != tmp)
    tmp = tmp->next;
  return(node = tmp);
}


// Return the youngest child in a row of siblings.  The youngest is the last
// one in the row (ie the prev for the eldest since we're using circular lists)
// Basically we just find the eldest then take the one previous to that one.
//   Remember to set the current node to the one we found.
GANodeBASE * 
GATreeIterBASE::youngest(GANodeBASE * c)
{
  if(!c) return (GANodeBASE *)0;
  if(!c->parent) return(node=c);

  GANodeBASE * tmp = c;

  while(tmp->parent->child != tmp)
    tmp = tmp->next;
  return(node = tmp->prev);
}


// Return the number of siblings for the specified node.  Notice that this 
// function returns the number of siblings INCLUDING the specified node.
int
GATreeIterBASE::nsiblings(GANodeBASE * c)
{
  GANodeBASE * tmp = c;
  int n=1;
  while(tmp->next && ((tmp=tmp->next) != c)) n++;
  return n;
}


// Return the number of children for the specified node.  This is basically the
// same code as the nsiblings routine, but we look at the child of the node, 
// not the node itself.
int
GATreeIterBASE::nchildren(GANodeBASE * c)
{
  if(!c->child) return 0;
  GANodeBASE * tmp = c->child;
  int n=1;
  while(tmp->next && ((tmp=tmp->next) != c->child)) n++;
  return n;
}


// Set the current node to the node indexed by the integer x.  If x is out of
// bounds, we return NULL and don't change the state of the iterator.  This 
// method uses a depth-first traversal to find the node.  Root node is 0, then
// we go up from there.
GANodeBASE *
GATreeIterBASE::warp(unsigned int x)
{
  unsigned int w=0;
  GANodeBASE * tmp = _GATreeTraverse(x, w, root());
  if(tmp) node = tmp;
  return(tmp);
}


// Return the number of nodes in the tree from the specified node on down.  
// Similar to the TreeBASE size method, but we don't set the sz member and 
// we can't cache the size since this could be called on any node.
int
GATreeIterBASE::size(GANodeBASE * n)
{
  return(_GATreeSize(n));
}


// Return the depth of the tree from the specified node on down.
int
GATreeIterBASE::depth(GANodeBASE * n)
{
  return(_GATreeDepth(n));
}



// Traverse the tree (depth-first) until we come to the node with the index
// specified by 'index'.  Return NULL if cur != index.
GANodeBASE *
_GATreeTraverse(unsigned int index, unsigned int & cur, GANodeBASE * node)
{
  if(!node) return (GANodeBASE *)0;
  if(cur == index) return node;
  cur++;

  GANodeBASE * n;
  if((n = _GATreeTraverse(index, cur, node->child)) != (GANodeBASE *)0)
    return n;

  for(GANodeBASE * tmp=node->next; tmp && tmp != node; tmp=tmp->next){
    if(cur == index) return tmp;
    cur++;
    if((n = _GATreeTraverse(index, cur, tmp->child)) != (GANodeBASE *)0)
      return n;
  }
  return (GANodeBASE *)0;
}


// Comparison operators for a a tree check for identical tree structure
// only (no check for same contents of nodes).  These check for
// similar tree structure - we traverse one tree and expect the second to be
// just like it (depth-first traversal).  If there is any difference along the
// way, then we return a not equal.
//   Neither of these operators affects the internal iterator of either
// tree genome in any way.

//   Recursively traverse two trees at the same time.  Return 1 if they are 
// different, return a 0 if they are identical.  This checks only the tree
// structure, not the node contents.
int
_GATreeCompare(GANodeBASE * anode, GANodeBASE * bnode)
{
  if(anode==0 && bnode==0) return 0;
  if(anode==0 || bnode==0) return 1;
  int count = _GATreeCompare(anode->child, bnode->child);
  for(GANodeBASE * atmp=anode->next, * btmp=bnode->next;
      atmp && atmp != anode;
      atmp=atmp->next, btmp=btmp->next){
    count += _GATreeCompare(atmp->child, btmp->child);
  }
  return count;
}