heap.cc

模拟器提供了一个简单易用的平台

static char rcsid [] = "$Id: heap.cc,v 1.2 2001/08/08 13:24:07 suman Exp suman $";

/*
 * $Log: heap.cc,v $
 * Revision 1.2  2001/08/08 13:24:07  suman
 * enforcing insert order on objects inserted with same key values
 *
 * Revision 1.1  2001/08/07 22:09:38  suman
 * Initial revision
 *
 */

/*
 * File: heap.cc
 * Author: Suman Banerjee <[e-mail]>
 * Date: July 31, 2001
 * Terms: GPL
 *
 * myns simulator
 */


#include <stdio.h>
#include <assert.h>
#include "heap.h"

static long int static_unique_gen = 0;

Heap *init_heap (void)
{
 Heap *h = new Heap;
 h->root = NULL;
 h->num_elements = 0;
 h->completed_levels = 0;
 return h;
}

void delete_heap (Heap *h)
{
 delete_tree(h->root);
 delete h;
 return;
}

void delete_tree (HeapElement *he)
{
 if (he == NULL)
   return;
 delete_tree(he->left);
 delete_tree(he->right);
 delete he;
 return;
}

bool is_empty (Heap *h)
{
  return (h->num_elements == 0);
}

// Returns the direction (left or right) where the next insert should be.
// The parent is returned in the reference parameter.
TreeDirection locate_parent_for_next_insert (Heap *h, HeapElement*& p)
{
  int split_point;

  if (h->num_elements == 0)
    return INVALID;

  p = h->root;

  // dir_vector is the number of elements in the first incomplete level
  // would be between 0 and 2^completed_levels - 1.
  int dir_vector = h->num_elements - (1 << h->completed_levels) + 1;
  for (split_point = 1 << (h->completed_levels - 1); split_point > 1; split_point >>= 1)
    {
      if ((dir_vector / split_point) == 0)
	p = p->left;
      else
	{
	  p = p->right;
	  dir_vector -= split_point;
	}
    }

  if (dir_vector == 0)
    return LEFT;
  else
    return RIGHT;
}

void exchange_node_with_parent (Heap *h, HeapElement *he)
{
  HeapElement *he_parent = he->parent;
  assert (he_parent != NULL);
  HeapElement *he_grand_parent = he_parent->parent;

  TreeDirection child_dir = ((he_parent->left == he) ? LEFT : RIGHT);

  HeapElement *he_leftchild = he->left;
  HeapElement *he_rightchild = he->right;
  HeapElement *he_other_child;

  if (child_dir == LEFT)
    {
      he->left = he_parent;
      he_other_child = he->right = he_parent->right;
    }
  else
    {
      he->right = he_parent;
      he_other_child = he->left = he_parent->left;
    }
  he->parent = he_grand_parent;

  he_parent->left = he_leftchild;
  he_parent->right = he_rightchild;
  he_parent->parent = he;

  // Now we set the grandparent pointers.
  if (he_grand_parent != NULL)
    {
      if (he_grand_parent->left == he_parent)
	he_grand_parent->left = he;
      else
	he_grand_parent->right = he;
    }
  else
    h->root = he;

  // Next we set the pointer of the other child of the original parent
  if (he_other_child != NULL)
    he_other_child->parent = he;

  // Finally we set the pointer of the children of the original node.
  if (he_leftchild != NULL)
    he_leftchild->parent = he_parent;
  if (he_rightchild != NULL)
    he_rightchild->parent = he_parent;

  return;
}

void exchange_nodes (Heap *h, HeapElement *h1, HeapElement *h2)
{
  assert ((h1 != NULL) && (h2 != NULL));
  if (h1 == h2)
    return;

  if (h1->parent == h2)
    {
      exchange_node_with_parent(h,h1);
      return;
    }

  if (h2->parent == h1)
    {
      exchange_node_with_parent(h,h2);
      return;
    }

  HeapElement *h1_leftchild = h1->left;
  HeapElement *h1_rightchild = h1->right;
  HeapElement *h1_parent = h1->parent;
  HeapElement *h2_parent = h2->parent;

  // First exchange the fields in the node structures.
  h1->left = h2->left;
  h1->right = h2->right;
  h1->parent = h2->parent;

  h2->left = h1_leftchild;
  h2->right = h1_rightchild;
  h2->parent = h1_parent;

  // Next adjust the pointers in the parents of the se nodes.
  if (h1_parent == h2_parent) {
      assert (h1_parent != NULL);
      if (h1_parent->left == h1) {
        h1_parent->left = h2;
        h1_parent->right = h1;
      }
      else {
        assert (h1_parent->right == h1) ;
        h1_parent->left = h1;
        h1_parent->right = h2;
      }
  }
  else {
   if (h1_parent != NULL)
     if (h1_parent->left == h1)
       h1_parent->left = h2;
     else // (h1_parent->right == h1)
       h1_parent->right = h2;

   if (h2_parent != NULL)
     if (h2_parent->left == h2)
       h2_parent->left = h1;
     else // (h2_parent->right == h2)
       h2_parent->right = h1;
  }

  // Update the pointers in the children
  if (h1->left != NULL)
    h1->left->parent = h1;
  if (h1->right != NULL)
    h1->right->parent = h1;

  if (h2->left != NULL)
    h2->left->parent = h2;
  if (h2->right != NULL)
    h2->right->parent = h2;
  
  // Finally, update the heap root if needed.
  if (h->root == h1)
    h->root = h2;
  else if (h->root == h2)
    h->root = h1;
  
  return;
}

// Insert an element into the heap
void* heap_insert (Heap *h, void *key, void *value, int (*compare_fn)(void*,void*))
{
  HeapElement *new_he;
  HeapElement *parent_he;

  new_he = new HeapElement;
  new_he->left = NULL;
  new_he->right = NULL;
  new_he->parent = NULL;
  new_he->key = key;
  new_he->unique = static_unique_gen ++;
  new_he->value = value;

  if (h->num_elements == 0)
    {
      h->root = new_he;
      h->num_elements = 1;
      h->completed_levels = 1;
      return new_he;
    }

  if (locate_parent_for_next_insert(h,parent_he) == LEFT)
    {
      assert(parent_he->left == NULL);
      parent_he->left = new_he;
    }
  else
    {
      assert(parent_he->right == NULL);
      parent_he->right = new_he;
    }
  new_he->parent = parent_he;

  heapify_upwards(h,new_he,compare_fn);

  // Update the size of the heap and completed levels
  h->num_elements ++;
  if ( h->num_elements == (((1 << h->completed_levels + 1)) - 1) )
    h->completed_levels ++;
  return new_he;
}

void heapify_upwards (Heap *h, HeapElement *he, int (*compare_fn)(void*,void*))
{
  assert (he != NULL);
  while (he->parent != NULL)
    {
      if (compare_function_wrapper(he->unique,he->key,he->parent->unique,he->parent->key,compare_fn) < 0)
	  exchange_node_with_parent(h,he);
      else
	break;
      // Since the node actually moves up, we do not have to update he.
    }
  return;
}

void heapify_downwards (Heap *h, HeapElement *he, int (*compare_fn)(void*,void*))
{
  HeapElement *smallest;

  while (1)
    {
      if ((he->left != NULL) && (compare_function_wrapper(he->left->unique,he->left->key,he->unique,he->key,compare_fn) < 0))
	smallest = he->left;
      else
	smallest = he;

      if ((he->right != NULL) && (compare_function_wrapper(he->right->unique,he->right->key,smallest->unique,smallest->key,compare_fn) < 0))
	smallest = he->right;

      if (smallest != he)
	{
	  exchange_node_with_parent(h,smallest);
	  // he = smallest; This need not be done since the node moves up.
	}
      else
	break;
    }
  return;
}

void output_heap (Heap *h, void (*output_fn)(void*))
{
  fprintf (stdout,"Display of heap\n");
  traverse_heap(h->root,0,output_fn);
  return;
}

void traverse_heap (HeapElement *he, int levels, void (*output_fn)(void*))
{
  if (he == NULL)
    return;
  for (int i = 0; i < levels; i++)
    fprintf (stdout, "\t");
  (*output_fn)(he->value);

  traverse_heap(he->left,levels+1,output_fn);
  traverse_heap(he->right,levels+1,output_fn);
  return;
}

int cmp (void *n1, void *n2)
{
  return (*(int*)n1 - *(int*)n2);
}

void output_data (void *data)
{
  fprintf (stdout, "%d\n",*(int*)data);
  return;
}

void heap_lookup_data (void *pos, void*& key, void* & value)
{
  HeapElement *he = (HeapElement*)pos;
  key = he->key;
  value = he->value;
  return;
}

void heap_lookup_min (Heap *h, void*& key, void* & value)
{
  key = h->root->key;
  value = h->root->value;
  return;
}

int heap_extract_data (Heap *h, void* pos, void*& key, void*& value, int (*compare_fn)(void*,void*))
{
  assert (pos != NULL);

  HeapElement *last_node_parent;
  HeapElement *last_node;
  HeapElement *data_node = (HeapElement *)pos;

  if (h->num_elements == 0)
    return -1;

  key = data_node->key;
  value = data_node->value;

  if (h->num_elements == ((1 << h->completed_levels) - 1))
    h->completed_levels --;
  h->num_elements --;

  if (h->num_elements == 0)
    {
      // If only one node in tree, must be the root.
      assert (h->root == data_node);
      delete h->root;
      h->root = NULL;
      return 1;
    }

  // Find the last inserted node in the heap. Need to have decremented the
  // num_elements before this.
  TreeDirection tree_dir = locate_parent_for_next_insert(h,last_node_parent);
  assert (tree_dir != INVALID);

  if (tree_dir == LEFT)
    {
      assert (last_node_parent->left != NULL);
      last_node = last_node_parent->left;
    }
  else
    {
      assert (last_node_parent->right != NULL);
      last_node = last_node_parent->right;
    }

  // Exchange the last node with the node to be deleted and then adjust heap.
  if (data_node != last_node)
    {
      exchange_nodes (h,data_node,last_node);
      if (data_node != last_node_parent)
	{
	  if (tree_dir == LEFT)
	    last_node_parent->left = NULL;
	  else
	    last_node_parent->right = NULL;
	}
      else
	{
	  if (tree_dir == LEFT)
	    last_node->left = NULL;
	  else
	    last_node->right = NULL;
	}

      if ((last_node->parent != NULL) && (compare_function_wrapper(last_node->unique,last_node->key,last_node->parent->unique,last_node->parent->key,compare_fn) < 0))
	heapify_upwards(h,last_node,compare_fn);
      else
	heapify_downwards(h,last_node,compare_fn);
    }

  if (data_node->parent != NULL)
    {
      if (data_node->parent->right == data_node)
	data_node->parent->right = NULL;
      else if (data_node->parent->left == data_node)
	data_node->parent->left = NULL;
    }

  delete data_node;

  return 1;
}

// Returns and deletes the min element. The min key and value is returned by
// the reference pointers.
int heap_extract_min (Heap *h, void*& key, void*& value, int (*compare_fn)(void*,void*))
{
  if (h->num_elements == 0)
    return -1;
  return heap_extract_data(h,(void*)(h->root),key,value,compare_fn);
}

// Locates the specific value in the tree
void* locate_data (Heap *h, void *value)
{
  return locate_data_in_subtree(h,h->root,value);
};

// Locates specific value in a subtree
void* locate_data_in_subtree (Heap *h, HeapElement *he, void *value)
{
  if (he == NULL)
    return NULL;
  if (he->value == value)
    return (void *)he;

  void *left_found = locate_data_in_subtree(h,he->left,value);
  if (left_found != NULL)
    return left_found;

  void *right_found = locate_data_in_subtree(h,he->right,value);
  if (right_found != NULL)
    return right_found;

  return NULL;
}

int compare_function_wrapper (long int u1, void * k1, long int u2, void * k2, int (*compare_fn)(void*,void*)) {

  int res = ((*compare_fn)(k1,k2));
  if (res == 0) {
    if (u1 > u2)
      res = 1;
    else if (u2 > u1)
      res = -1;
    else
      assert(0);
  }
  return res;
}

int heap_menu (void)
{
  int ch;

  fprintf (stdout, "Welcome to heap V1.0\n");
  fprintf (stdout, "0) Exit heap\n");
  fprintf (stdout, "1) Insert to heap\n");
  fprintf (stdout, "2) Delete min\n");
  fprintf (stdout, "3) Delete data\n");
  fprintf (stdout, "4) Display heap\n");
  fprintf (stdout, "Choose : ");
  fscanf (stdin, "%d", &ch);
  return ch;
}

/*
int main (void)
{
  Heap *h = init_heap();
  int ch;
  
  do
    {
      ch = heap_menu();
      switch (ch)
	{
	case 0 :
	  break;

	case 1 :
	  {
	    fprintf (stdout, "Enter value : ");
	    int *data = new int;
	    fscanf (stdin, "%d", data);
	    void *data_pos = heap_insert(h,(void*)data,(void*)data,cmp);
	    fprintf (stdout, "Data pos : %x\n",data_pos);
	    break;
	  }

	case 2 :
	  {
	    void *data;
	    heap_extract_min(h,data,data,cmp);
	    fprintf (stdout, "Deleted data : %d\n",*(int*)data);
	    delete data;
	    break;
	  }

	case 3 :
	  {
	    int data_pos;
	    void *data;
	    fprintf (stdout, "Enter data pos : ");
	    fscanf (stdin,"%x",&data_pos);
	    heap_extract_data(h,(void*)data_pos,data,data,cmp);
	    fprintf (stdout, "Data : %d\n",*(int*)data);
	    break;
	  }

	case 4 :
	  output_heap(h,output_data);
	  break;

	default :
	  fprintf (stderr, "No such choice\n");
	}
    }
  while (ch != 0);

 delete_heap(h);
 return 1;
}
*/