et-forest.c   [plain text]

/* ET-trees datastructure implementation.
   Contributed by Pavel Nejedly
   Copyright (C) 2002 Free Software Foundation, Inc.

This file is part of the libiberty library.
Libiberty is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.

Libiberty is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with libiberty; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  

  The ET-forest structure is described in:
    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
    J.  G'omput. System Sci., 26(3):362 381, 1983.
*/

#include "config.h"
#include "system.h"
#include "et-forest.h"

struct et_forest_occurrence;
typedef struct et_forest_occurrence* et_forest_occurrence_t;

/* The ET-forest type.  */
struct et_forest
{
  /* Linked list of nodes is used to destroy the structure.  */
  int nnodes;
};

/* Single occurrence of node in ET-forest.  
   A single node may have multiple occurrences.
 */
struct et_forest_occurrence
{
  /* Parent in the splay-tree.  */
  et_forest_occurrence_t parent;

  /* Children in the splay-tree.  */
  et_forest_occurrence_t left, right;

  /* Counts of vertices in the two splay-subtrees.  */
  int count_left, count_right;

  /* Next occurrence of this node in the sequence.  */
  et_forest_occurrence_t next;

  /* The node, which this occurrence is of.  */
  et_forest_node_t node;
};


/* ET-forest node.  */
struct et_forest_node
{
  et_forest_t forest;
  void *value;

  /* First and last occurrence of this node in the sequence.  */
  et_forest_occurrence_t first, last;
};


static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
static void remove_all_occurrences PARAMS ((et_forest_node_t));
static inline et_forest_occurrence_t find_leftmost_node 
                               PARAMS ((et_forest_occurrence_t));
static inline et_forest_occurrence_t find_rightmost_node 
                               PARAMS ((et_forest_occurrence_t));
static int calculate_value PARAMS ((et_forest_occurrence_t));

/* Return leftmost node present in the tree roted by OCC.  */
static inline et_forest_occurrence_t
find_leftmost_node (occ)
     et_forest_occurrence_t occ;
{
  while (occ->left)
    occ = occ->left;

  return occ;
}

/* Return rightmost node present in the tree roted by OCC.  */
static inline et_forest_occurrence_t
find_rightmost_node (occ)
     et_forest_occurrence_t occ;
{
  while (occ->right)
    occ = occ->right;
  return occ;
}


/* Operation splay for splay tree structure representing ocuurences.  */
static et_forest_occurrence_t
splay (node)
     et_forest_occurrence_t node;
{
  et_forest_occurrence_t parent;
  et_forest_occurrence_t grandparent;

  while (1)
    {
      parent = node->parent;

      if (! parent)
	return node;  /* node == root.  */

      grandparent = parent->parent;

      if (! grandparent)
	break;

      /* Now there are four possible combinations:  */

      if (node == parent->left)
	{
	  if (parent == grandparent->left)
	    {
	      et_forest_occurrence_t node1, node2;
	      int count1, count2;

	      node1 = node->right;
	      count1 = node->count_right;
	      node2 = parent->right;
	      count2 = parent->count_right;

	      grandparent->left = node2;
	      grandparent->count_left = count2;
	      if (node2)
		node2->parent = grandparent;
	      parent->left = node1;
	      parent->count_left = count1;
	      if (node1)
		node1->parent = parent;
	      parent->right = grandparent;
	      parent->count_right = count2 + grandparent->count_right + 1;
	      node->right = parent;
	      node->count_right = count1 + parent->count_right + 1;

	      node->parent = grandparent->parent;
	      parent->parent = node;
	      grandparent->parent = parent;

	      if (node->parent)
		{
		  if (node->parent->left == grandparent)
		    node->parent->left = node;
		  else
		    node->parent->right = node;
		}
	    }
	  else
	    {
	      /* parent == grandparent->right && node == parent->left*/
	      et_forest_occurrence_t node1, node2;
	      int count1, count2;

	      node1 = node->left;
	      count1 = node->count_left;
	      node2 = node->right;
	      count2 = node->count_right;

	      grandparent->right = node1;
	      grandparent->count_right = count1;
	      if (node1)
		node1->parent = grandparent;
	      parent->left = node2;
	      parent->count_left = count2;
	      if (node2)
		node2->parent = parent;
	      node->left = grandparent;
	      node->count_left = grandparent->count_left + count1 + 1;
	      node->right = parent;
	      node->count_right = parent->count_right + count2 + 1;

	      node->parent = grandparent->parent;
	      parent->parent = node;
	      grandparent->parent = node;

	      if (node->parent)
		{
		  if (node->parent->left == grandparent)
		    node->parent->left = node;
		  else
		    node->parent->right = node;
		}
	    }
	}
      else
	{
	  /* node == parent->right.  */
	  if (parent == grandparent->left)
	    {
	      et_forest_occurrence_t node1, node2;
	      int count1, count2;

	      node1 = node->left;
	      count1 = node->count_left;
	      node2 = node->right;
	      count2 = node->count_right;

	      parent->right = node1;
	      parent->count_right = count1;
	      if (node1)
		node1->parent = parent;
	      grandparent->left = node2;
	      grandparent->count_left = count2;
	      if (node2)
		node2->parent = grandparent;
	      node->left = parent;
	      node->count_left = parent->count_left + count1 + 1;
	      node->right = grandparent;
	      node->count_right = grandparent->count_right + count2 + 1;

	      node->parent = grandparent->parent;
	      parent->parent = node;
	      grandparent->parent = node;

	      if (node->parent)
		{
		  if (node->parent->left == grandparent)
		    node->parent->left = node;
		  else
		    node->parent->right = node;
		}
	    }
	  else
	    {
	      /* parent == grandparent->right && node == parent->right*/
	      et_forest_occurrence_t node1, node2;
	      int count1, count2;

	      node1 = node->left;
	      count1 = node->count_left;
	      node2 = parent->left;
	      count2 = parent->count_left;

	      grandparent->right = node2;
	      grandparent->count_right = count2;
	      if (node2)
		node2->parent = grandparent;
	      parent->right = node1;
	      parent->count_right = count1;
	      if (node1)
		node1->parent = parent;
	      parent->left = grandparent;
	      parent->count_left = count2 + grandparent->count_left + 1;
	      node->left = parent;
	      node->count_left = count1 + parent->count_left + 1;

	      node->parent = grandparent->parent;
	      parent->parent = node;
	      grandparent->parent = parent;

	      if (node->parent)
		{
		  if (node->parent->left == grandparent)
		    node->parent->left = node;
		  else
		    node->parent->right = node;
		}
	    }
	}
	  
    }

  /* parent == root.  */
  /* There are two possible combinations:  */

  if (node == parent->left)
    {
      et_forest_occurrence_t node1;
      int count1;
      
      node1 = node->right;
      count1 = node->count_right;

      parent->left = node1;
      parent->count_left = count1;
      if (node1)
	node1->parent = parent;
      node->right = parent;
      node->count_right = parent->count_right + 1 + count1;
      node->parent = parent->parent;  /* the same as = 0;  */
      parent->parent = node;

      if (node->parent)
	{
	  if (node->parent->left == parent)
	    node->parent->left = node;
	  else
	    node->parent->right = node;
	}
    } 
  else 
    {
      /* node == parent->right.  */
      et_forest_occurrence_t node1;
      int count1;
      
      node1 = node->left;
      count1 = node->count_left;

      parent->right = node1;
      parent->count_right = count1;
      if (node1)
	node1->parent = parent;
      node->left = parent;
      node->count_left = parent->count_left + 1 + count1;
      node->parent = parent->parent;  /* the same as = 0;  */
      parent->parent = node;

      if (node->parent)
	{
	  if (node->parent->left == parent)
	    node->parent->left = node;
	  else
	    node->parent->right = node;
	}
    }

  return node;
}

/* Remove all occurences of the given node before destroying the node.  */
static void
remove_all_occurrences (forest_node)
     et_forest_node_t forest_node;
{
  et_forest_occurrence_t first = forest_node->first;
  et_forest_occurrence_t last = forest_node->last;
  et_forest_occurrence_t node;

  splay (first);

  if (first->left)
    first->left->parent = 0;
  if (first->right)
    first->right->parent = 0;   

  if (last != first)
    {
      splay (last);

      if (last->left)
	last->left->parent = 0;
      if (last->right)
	last->right->parent = 0;
    }

  if (last->right && first->left) /* actually, first->left would suffice.  */
    {
      /* Need to join them.  */
      et_forest_occurrence_t prev_node, next_node;

      prev_node = splay (find_rightmost_node (first->left));
      next_node = splay (find_leftmost_node (last->right));
      /* prev_node and next_node are consecutive occurencies
	 of the same node.  */
      if (prev_node->next != next_node)
	abort ();

      prev_node->right = next_node->right;
      prev_node->count_right = next_node->count_right;
      prev_node->next = next_node->next;
      if (prev_node->right)
	prev_node->right->parent = prev_node;

      if (prev_node->node->last == next_node)
	prev_node->node->last = prev_node;

      free (next_node);
    }

  if (first != last)
    {
      node = first->next;

      while (node != last)
	{
	  et_forest_occurrence_t next_node;

	  splay (node);

	  if (node->left)
	    node->left->parent = 0;
	  if (node->right)
	    node->right->parent = 0;

	  next_node = node->next;
	  free (node);
	  node = next_node;
	}
    }

  free (first);
  if (first != last)
    free (last);
}

/* Calculate ET value of the given node.  */
static inline int
calculate_value (node)
     et_forest_occurrence_t node;
{
  int value = node->count_left;

  while (node->parent)
    {
      if (node == node->parent->right)
	value += node->parent->count_left + 1;

      node = node->parent;
    }

  return value;
}




/* Create ET-forest structure.  */
et_forest_t
et_forest_create ()
{

  et_forest_t forest = xmalloc (sizeof (struct et_forest));

  forest->nnodes = 0;
  return forest;
}



/* Deallocate the structure.  */
void 
et_forest_delete (forest)
     et_forest_t forest;
{
  if (forest->nnodes)
    abort ();

  free (forest);
}

/* Create new node with VALUE and return the edge.
   Return NULL when memory allocation failed.  */
et_forest_node_t
et_forest_add_node (forest, value)
     et_forest_t forest;
     void *value;
{
  /* Create node with one occurrence.  */
  et_forest_node_t node;
  et_forest_occurrence_t occ;

  node = xmalloc (sizeof (struct et_forest_node));
  occ = xmalloc (sizeof (struct et_forest_occurrence));

  node->first = node->last = occ;
  node->value = value;
  forest->nnodes++;

  occ->node = node;
  occ->left = occ->right = occ->parent = 0;
  occ->next = 0;
  occ->count_left = occ->count_right = 0;
  return node;
}

/* Add new edge to the tree, return 1 if succesfull.
   0 indicates that creation of the edge will close the cycle in graph.  */
int
et_forest_add_edge (forest, parent_node, child_node)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t parent_node;
     et_forest_node_t child_node;
{
  et_forest_occurrence_t new_occ, parent_occ, child_occ;

  if (! parent_node || ! child_node)
    abort ();

  parent_occ = parent_node->first;
  child_occ = child_node->first;

  splay (parent_occ);
  splay (child_occ);

  if (parent_occ->parent)
    return 0; /* Both child and parent are in the same tree.  */

  if (child_occ->left)
    abort ();  /* child must be root of its containing tree.  */
  
  new_occ = xmalloc (sizeof (struct et_forest_occurrence));

  new_occ->node = parent_node;
  new_occ->left = child_occ;
  new_occ->count_left = child_occ->count_right + 1; /* count_left is 0.  */
  new_occ->right = parent_occ->right;
  new_occ->count_right = parent_occ->count_right;
  new_occ->parent = parent_occ;
  new_occ->next = parent_occ->next;
  child_occ->parent = new_occ;
  parent_occ->right = new_occ;
  parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
  parent_occ->next = new_occ;
  if (new_occ->right)
    new_occ->right->parent = new_occ;

  if (parent_node->last == parent_occ)
    parent_node->last = new_occ;
  return 1;
}

/* Remove NODE from the tree and all connected edges.  */
void
et_forest_remove_node (forest, node)
     et_forest_t forest;
     et_forest_node_t node;
{
  remove_all_occurrences (node);
  forest->nnodes--;

  free (node);
}

/* Remove edge from the tree, return 1 if sucesfull,
   0 indicates nonexisting edge.  */
int
et_forest_remove_edge (forest, parent_node, child_node)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t parent_node;
     et_forest_node_t child_node;
{
  et_forest_occurrence_t parent_pre_occ, parent_post_occ;

  splay (child_node->first);

  if (! child_node->first->left)
    return 0;

  parent_pre_occ = find_rightmost_node (child_node->first->left);
  if (parent_pre_occ->node != parent_node)
    abort ();

  splay (parent_pre_occ);
  parent_pre_occ->right->parent = 0;
  
  parent_post_occ = parent_pre_occ->next;
  splay (parent_post_occ);

  parent_post_occ->left->parent = 0;

  parent_pre_occ->right = parent_post_occ->right;
  parent_pre_occ->count_right = parent_post_occ->count_right;
  if (parent_post_occ->right)
    parent_post_occ->right->parent = parent_pre_occ;

  parent_pre_occ->next = parent_post_occ->next;

  if (parent_post_occ == parent_node->last)
    parent_node->last = parent_pre_occ;

  free (parent_post_occ);
  return 1;
}

/* Return the parent of the NODE if any, NULL otherwise.  */
et_forest_node_t
et_forest_parent (forest, node)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t node;
{
  splay (node->first);

  if (node->first->left)
    return find_rightmost_node (node->first->left)->node;
  else
    return 0;
}


/* Return nearest common ancestor of NODE1 and NODE2.
   Return NULL of they are in different trees.  */
et_forest_node_t
et_forest_common_ancestor (forest, node1, node2)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t node1;
     et_forest_node_t node2;
{
  int value1, value2, max_value;
  et_forest_node_t ancestor;

  if (node1 == node2)
    return node1;
  
  if (! node1 || ! node2)
    abort ();

  splay (node1->first);
  splay (node2->first);

  if (! node1->first->parent)  /* The two vertices are in different trees.  */
    return 0;

  value2 = calculate_value (node2->first);
  value1 = calculate_value (node1->first);

  if (value1 < value2)
    {
      ancestor = node1;
      max_value = value2;
    }
  else
    {
      ancestor = node2;
      max_value = value1;
    }
  
  while (calculate_value (ancestor->last) < max_value)
    {
      /* Find parent node.  */
      splay (ancestor->first);
      ancestor = find_rightmost_node (ancestor->first->left) ->node;
    }

  return ancestor;
}

/* Return the value pointer of node set during it's creation.  */
void *
et_forest_node_value (forest, node)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t node;
{
  /* Alloc threading NULL as a special node of the forest.  */
  if (!node)
    return NULL;
  return node->value;
}

/* Find all sons of NODE and store them into ARRAY allocated by the caller.
   Return number of nodes found.  */
int
et_forest_enumerate_sons (forest, node, array)
     et_forest_t forest ATTRIBUTE_UNUSED;
     et_forest_node_t node;
     et_forest_node_t *array;
{
  int n = 0;
  et_forest_occurrence_t occ = node->first, stop = node->last, occ1;

  /* Parent is the rightmost node of the left successor.
     Look for all occurences having no right succesor
     and lookup the sons.  */
  while (occ != stop)
    {
      splay (occ);
      if (occ->right)
	{
          occ1 = find_leftmost_node (occ->right);
	  if (occ1->node->first == occ1)
	    array[n++] = occ1->node;
	}
      occ = occ->next;
    }
  return n;
}