avltree.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

    if (node->right) return avltree_node_lookup(node->right, key);
    }
  else
    {	/* key == node->key */
    return node->data;
    }

  return NULL;
  }
#endif


/*
 * Iterative version -- much more efficient than the recursive version.
 */
static vpointer avltree_node_lookup(AVLNode *node, AVLKey key)
  {
  while (node!=NULL && key!=node->key)
    {
    if (key < node->key)
      node = node->left;
    else
      node = node->right;
    }
/* 
if (node) printf("Found key %p >", node->data); else printf("Not found key >");
*/

  return node;
  }


/*
 * Recursive node counting routine.
 * Need an iterative version.
 */
static int avltree_node_count(AVLNode *node)
  {
  int count=1;

  if (node->left!=NULL) count += avltree_node_count(node->left);
  if (node->right!=NULL) count += avltree_node_count(node->right);

  return count;
  }


/*
 * Stops when an AVLTraverseFunc() callback returns TRUE.
 */
static boolean avltree_node_traverse(AVLNode *node,
                     AVLTraverseFunc traverse_func, vpointer userdata)
  {
  if (node->left!=NULL)
    {
    if (avltree_node_traverse(node->left, traverse_func, userdata)) return TRUE;
    }

  if ((*traverse_func)(node->key, node->data, userdata)) return TRUE;

  if (node->right!=NULL)
    {
    if (avltree_node_traverse(node->right, traverse_func, userdata)) return TRUE;
    }

  return FALSE;
  }


static int avltree_node_height(AVLNode *node)
  {
  int left_height;
  int right_height;

  if (!node) return 0;

  if (node->left!=NULL)
    left_height = avltree_node_height(node->left);
  else
    left_height = 0;

  if (node->right!=NULL)
    right_height = avltree_node_height(node->right);
  else
    right_height = 0;

  return MAX(left_height, right_height) + 1;
  }


static AVLNode *avltree_node_rotate_left(AVLNode *node)
  {
  AVLNode *right;
  int a_bal;
  int b_bal;

  right = node->right;

  node->right = right->left;
  right->left = node;

  a_bal = node->balance;
  b_bal = right->balance;

  if (b_bal <= 0)
    {
    if (a_bal >= 1) right->balance = b_bal - 1;
    else right->balance = a_bal + b_bal - 2;

    node->balance = a_bal - 1;
    }
  else
    {
    if (a_bal <= b_bal) right->balance = a_bal - 2;
    else right->balance = b_bal - 1;

    node->balance = a_bal - b_bal - 1;
    }

  return right;
  }


static AVLNode *avltree_node_rotate_right(AVLNode *node)
  {
  AVLNode *left;
  int a_bal;
  int b_bal;

  left = node->left;

  node->left = left->right;
  left->right = node;

  a_bal = node->balance;
  b_bal = left->balance;

  if (b_bal <= 0)
    {
    if (b_bal > a_bal) left->balance = b_bal + 1;
    else left->balance = a_bal + 2;

    node->balance = a_bal - b_bal + 1;
    }
  else
    {
    if (a_bal <= -1) left->balance = b_bal + 1;
    else left->balance = a_bal + b_bal + 2;

    node->balance = a_bal + 1;
    }

  return left;
  }


static void avltree_node_check(AVLNode *node)
  {
  int left_height;
  int right_height;
  int balance;
  
  if (node!=NULL)
    {
    if (node->left!=NULL)
      left_height = avltree_node_height(node->left);
    else
      left_height = 0;

    if (node->right!=NULL)
      right_height = avltree_node_height(node->right);
    else
      right_height = 0;
      
    balance = right_height - left_height;
    if (balance != node->balance)
      dief("avltree_node_check: failed: %d ( %d )", balance, node->balance);
      
    if (node->left!=NULL)
      avltree_node_check(node->left);
    if (node->right!=NULL)
      avltree_node_check(node->right);
    }

  return;
  }


/*
 * Public Interface:
 */

/*
 * This function must be called before any other functions is OpenMP
 * code is to be used.  Can be safely called when OpenMP code is not
 * being used, and can be safely called more than once.
 */
void avltree_init_openmp(void)
  {

#if USE_OPENMP == 1
  if (avltree_openmp_initialised == FALSE)
    {
    omp_init_lock(&avltree_node_buffer_lock);
    avltree_openmp_initialised = TRUE;
    }
#endif

  return;
  }


AVLTree *avltree_new(AVLKeyFunc key_generate_func)
  {
  AVLTree *tree;

  if (!key_generate_func) return NULL;

  AVLnum_trees++;

  tree = s_malloc(sizeof(AVLTree));
  if (!tree) die("Unable to allocate memory.");

  tree->root = NULL;
  tree->key_generate_func = key_generate_func;

  return tree;
  }


void avltree_delete(AVLTree *tree)
  {
  if (!tree) return;

  avltree_node_delete(tree->root);

  s_free(tree);

  AVLnum_trees--;

  THREAD_LOCK(avltree_node_buffer_lock);
  if (AVLnum_trees == 0)
    _destroy_buffers();
  THREAD_UNLOCK(avltree_node_buffer_lock);

  return;
  }


void avltree_destroy(AVLTree *tree, AVLDestructorFunc free_func)
  {
  if (!tree) return;

  if (free_func!=NULL)
    avltree_node_destroy(tree->root, free_func);
  else
    avltree_node_delete(tree->root);

  s_free(tree);

  AVLnum_trees--;

  THREAD_LOCK(avltree_node_buffer_lock);
  if (AVLnum_trees == 0)
    _destroy_buffers();
  THREAD_UNLOCK(avltree_node_buffer_lock);

  return;
  }


boolean avltree_insert(AVLTree *tree, vpointer data)
  {
  boolean	inserted=FALSE;

  if (!tree) return FALSE;
  if (!data) return FALSE;	/* ordered search would barf at this! */

  tree->root = avltree_node_insert(tree->root,
                    tree->key_generate_func(data), data, &inserted);

  return inserted;
  }


vpointer avltree_remove(AVLTree *tree, vpointer data)
  {
  vpointer removed=NULL;

  if (!tree || !tree->root) return NULL;

  tree->root = avltree_node_remove(tree->root, tree->key_generate_func(data), &removed);

  return removed;
  }


vpointer avltree_remove_key(AVLTree *tree, AVLKey key)
  {
  vpointer removed=NULL;

  if (!tree || !tree->root) return NULL;

  tree->root = avltree_node_remove(tree->root, key, &removed);

  return removed;
  }


vpointer avltree_lookup(AVLTree *tree, vpointer data)
  {
  AVLNode	*node;

  if (!tree || !tree->root) return NULL;

  node = avltree_node_lookup(tree->root, tree->key_generate_func(data));
  return node?node->data:NULL;
  }


vpointer avltree_lookup_key(AVLTree *tree, AVLKey key)
  {
  AVLNode	*node;

  if (!tree || !tree->root) return NULL;

  node = avltree_node_lookup(tree->root, key);
  return node?node->data:NULL;
  }


vpointer avltree_lookup_lowest(AVLTree *tree)
  {
  AVLNode	*node;

  if (!tree || !tree->root) return NULL;

  node = avltree_node_lookup_leftmost(tree->root);
  return node?node->data:NULL;
  }


vpointer avltree_lookup_highest(AVLTree *tree)
  {
  AVLNode	*node;

  if (!tree || !tree->root) return NULL;

  node = avltree_node_lookup_rightmost(tree->root);
  return node?node->data:NULL;
  }


vpointer avltree_ordered_search(AVLTree *tree,
                    AVLSearchFunc search_func, vpointer userdata)
  {
  if (!tree || !tree->root) return NULL;

  return avltree_node_ordered_search(tree->root, search_func, userdata);
  }


vpointer avltree_search(AVLTree *tree, AVLMatchFunc search_func, vpointer userdata)
  {
  vpointer	nodedata=NULL;

  if (!tree || !tree->root) return NULL;

  return avltree_node_search(tree->root, search_func, userdata, &nodedata)?nodedata:NULL;
  }


void avltree_traverse(AVLTree *tree, AVLTraverseFunc traverse_func, vpointer userdata)
  {
  if (!tree || !tree->root) return;

  avltree_node_traverse(tree->root, traverse_func, userdata);

  return;
  }


int avltree_height(AVLTree *tree)
  {
  return (tree!=NULL && tree->root!=NULL)?avltree_node_height(tree->root):0;
  }


int avltree_num_nodes(AVLTree *tree)
  {
  return (tree!=NULL && tree->root!=NULL)?avltree_node_count(tree->root):0;
  }


/*
 * Testing:
 */

void avltree_diagnostics(void)
  {
  printf("=== AVLTree diagnostics ======================================\n");
  printf("Version:                   %s\n", GA_VERSION_STRING);
  printf("Build date:                %s\n", GA_BUILD_DATE_STRING);
  printf("Compilation machine characteristics:\n%s\n", GA_UNAME_STRING);

  printf("--------------------------------------------------------------\n");
  printf("structure                  sizeof\n");
  printf("AVLTree                    %lu\n", (unsigned long) sizeof(AVLTree));
  printf("AVLNode                    %lu\n", (unsigned long) sizeof(AVLNode));
  printf("--------------------------------------------------------------\n");
  printf("Trees in use:              %d\n", AVLnum_trees);
  printf("==============================================================\n");

  return;
  }


static boolean failed = FALSE;

static AVLKey test_avltree_generate(constvpointer data)
  {
/*
 * Simple casting from char to AVLKey... should work ;)
 * (It works when AVLKey is the default unsigned long...)
 */
  return (AVLKey) *((char *)data);
/*
  return (AVLKey) (data);
*/
  }

static boolean test_avltree_traverse(AVLKey key, vpointer data, vpointer userdata)
  {
/* check. */
  if (key != test_avltree_generate(data))
    {
    printf("failure (%ld %ld) ", key, test_avltree_generate(data));
    failed=TRUE;
    }

/* output character. */
  printf("%c ", *((char *)data));
/*
  printf("%c=%ld ", *((char *)data), (long) test_avltree_generate(data));
*/

/* terminate traversal if userdata is non-NULL and character is 'S'. */
  if ((boolean *)userdata!=NULL && *((char *)data)=='S')
    {
    printf("%s ", (char *)userdata);
    return TRUE;
    }

  return FALSE;
  }

#ifdef AVLTREE_COMPILE_MAIN
int main(int argc, char **argv)
#else
boolean avltree_test(void)
#endif
  {
  int		i, j;
  AVLTree	*tree;
  char		chars[62];
  char		chx='x', chX='X', *ch;

  printf("Testing my dodgy AVL tree routines.\n");

  tree = avltree_new(test_avltree_generate);

  i = 0;
  for (j = 0; j < 26; j++, i++)
    {
    chars[i] = 'A' + (char) j;
    avltree_insert(tree, &chars[i]);
    }
  for (j = 0; j < 26; j++, i++)
    {
    chars[i] = 'a' + (char) j;
    avltree_insert(tree, &chars[i]);
    }
  for (j = 0; j < 10; j++, i++)
    {
    chars[i] = '0' + (char) j;
    avltree_insert(tree, &chars[i]);
    }

  printf("height: %d\n", avltree_height(tree));
  printf("num nodes: %d\n", avltree_num_nodes(tree));

  printf("tree: ");
  avltree_traverse(tree, test_avltree_traverse, NULL);
  printf("\n");

  printf("tree to 'S' then foo: ");
  avltree_traverse(tree, test_avltree_traverse, "foo");
  printf("\n");

  for (i = 0; i < 26; i++)
    if ( !avltree_remove(tree, &chars[i]) ) printf("%c not found.\n", chars[i]);

  printf("height: %d\n", avltree_height(tree));
  printf("num nodes: %d\n", avltree_num_nodes(tree));

  printf("tree: ");
  avltree_traverse(tree, test_avltree_traverse, NULL);
  printf("\n");

  printf("Lookup for 'x': ");
  ch = (char *) avltree_lookup(tree, (vpointer) &chx);
  if (ch) printf("Found '%c'\n", *ch); else printf("Not found.\n");

  printf("Lookup for 'X': ");
  ch = (char *) avltree_lookup(tree, (vpointer) &chX);
  if (ch) printf("Found '%c'\n", *ch); else printf("Not found.\n");

  printf("Tests:         %s\n", failed?"FAILED":"PASSED");

  avltree_delete(tree);

  return failed;
  }