#include "cubes.h"

/****************************************************************************

NAME
	retain_node, unretain_inferior_node

DESCRIPTION
	Once we arrived to a decision concerning the scanned_node, we can
	have it executed it by the proper function in the list above.

SYNOPSIS
	retain_node()

	unretain_inferior_node()

DESCRIPTION

    -retain_node, the scanned_node is essential to the cover of our boolean
	function and we decided to retain it. This function will set its status
	to decided retained, free the scanned_cube allocated for this decision
	and finally we will scan all the intersecting nodes in the graph that
	can be affected. The affected nodes will be placed on the stack to be
	processed later.

    -unretain_node, the scanned node can be covered by another node so it is
	inferior and we decided to unretain it. Its status will be set to
	decided inferior and we will scan all the nodes affected by this  
	to put them on the processing stack.

COORDINATES
	McGill University Electrical Engineering MONTREAL CANADA
	17 july 1984

AUTHOR
	Michel DAGENAIS

***********************************************************************/

retain_node()

{ 
  free_list_of_cubes(&scanned_cube);
  free_list_of_cubes(&(scanned_node->uncovered));
  scanned_node->status = DECIDED_RETAINED;
  current_node = scanned_node;
  increment_pass_count();
  scan_affected_retained_ancestors();
  current_node = scanned_node;
  scan_affected_retained_descendants();
}

/************************************************************************/

unretain_inferior_node()

{
  scanned_node->status = DECIDED_INFERIOR;
  current_node = scanned_node;
  increment_pass_count();
  scan_affected_unretain_ancestors();
  current_node = scanned_node;
  scan_affected_unretain_descendants();
}

/**************************************************************************

NAME
	place_nodes_in_vector

PURPOSE
	This function puts the nodes in the vector in the following
	order : retained, undecided and unretained inferior, unretained.
	They arrive randomly placed.

SYNOPSIS
	place_nodes_in_vector()

DESCRIPTION
	We have taken many decisions to retain or unretain nodes, and we
	simply set their status word accordingly. Now we want to order them
	in the vector to remove from the active area the nodes which are
	decided and covered by the nodes retained up to date. The nodes retained
	are placed at the beginning of the vector, the nodes unretained and
	covered by the retained nodes are placed at the end and the nodes
	inferior or undecided are left in the middle. The nodes which are not
	covered (undecided and inferior unretained) are left in the middle
	because any decision may affect them so when we decide to branch,
	they must all be remembered.

COORDINATES
	McGill University Electrical Engineering VLSI lab MONTREAL CANADA
	25 july 1984

AUTHOR
	Michel DAGENAIS

***********************************************************************/

place_nodes_in_vector()

{
  int status;		/* temp space to put the status of the node processed */

  struct node
	**cursor,	/* pointer in the vector to nodes to place */
	*temp_node;	/* temp pointer to a node to place */	

  cursor = retained_nodes;

  for(; cursor < unretain_nodes ;)
   { status = (*cursor)->status;
     if(status & COVERED)
  
  /* The node is retained, it will be placed at the beginning of the vector
     the the pointer to retained nodes is incremented.			*/
 
      { if(status & RETAINED)
  	 { if(cursor == retained_nodes) cursor++;

	   else
	    { temp_node = *cursor;
	      *cursor = *retained_nodes;
	      *retained_nodes = temp_node;
	    }
           retained_nodes++;
	 }

/* The node is unretain covered it will be placed at the end of the vector.  */

	else
	 { unretain_nodes--;
	   temp_node = *cursor;
	   *cursor = *unretain_nodes;
	   *unretain_nodes = temp_node;
	 }
      }

/* The node is not covered, we leave it in the middle of the vector.	*/

     else cursor++;
   }

/* the retained and unretained covered nodes are now placed. Now we will
   count the undecided nodes. The count is placed in the external variable
   scan_count.								*/

  cursor = retained_nodes;
  scan_count = 0;

  for(; cursor < unretain_nodes ; cursor++)
   { if((*cursor)->status & DECIDED) continue;
     scan_count++;
   }
}

/*********************************************************************

NAME
	select_node

PURPOSE
	This function is called to select an undecided node using some
	heuristics. We want this node to break the cycle encountered
	efficiently. If we do not branch we simply hope that the node
	selected will give a good solution when retained.

SYNOPSIS
	select_node()

DESCRIPTION
	The function puts the node selected in scanned node. The heuristic
	used is the following; we take the node which if retained or
	unretained will affect the biggest number of direct undecided
	parents. This way we know that if we retain  or unretain it, most 
	probably, many nodes will be affected and get decided. We want
	this way to break in pieces the cycles, to reduce the branching depth
	necessary to solve completely the covering.

COORDINATES
	McGill University Electrical Engineering VLSI lab MONTREAL CANADA
	27 july 1984

AUTHOR
	Michel DAGENAIS

****************************************************************************/

#define AFFECTED_SCORE 1
#define COVERED_SCORE 4

select_node()

{
  struct parent *temp_parent;	/* pointer in the parent list of the node */

  struct node
	*temp_node,		/* pointer to the node examined */
	**cursor;		/* pointer in the vector of nodes */

  int
	value,			/* score of the temp_node */
	best_value;		/* score of scanned node, the best node */

  best_value = -1;
  cursor = retained_nodes;

  for(; cursor < unretain_nodes ; cursor++)
   { temp_node = *cursor;
     if(temp_node->status & DECIDED) continue;

/* the node is undecided, we will see how many of its parents have their
   uncovered part intersecting with it and so would be affected by any
   decision taken on it.					*/

     value = 0;
     temp_parent = temp_node->ancestors;
     for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
      { if(temp_parent->parent->status & DECIDED) continue;
	if(intersect_list(temp_node->cube,temp_parent->parent->uncovered))
         { if(covers_list(temp_node->cube,temp_parent->parent->uncovered))
	    { value += COVERED_SCORE;
	    }
	   else value += AFFECTED_SCORE;
	 }
      }

     temp_parent = temp_node->descendants;
     for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
      { if(temp_parent->parent->status & DECIDED) continue; 
	if(intersect_list(temp_node->cube,temp_parent->parent->uncovered))
         { if(covers_list(temp_node->cube,temp_parent->parent->uncovered))
	    { value += COVERED_SCORE;
	    }
	   else value += AFFECTED_SCORE;
	 }
      }

     if(value > best_value)
      { best_value = value;
	scanned_node = temp_node;
      }
   }

/* There should always be a node selected, but we might just check because
   the CPU cost is very small and it is very healty for software to check
   itself with assertions.						*/

  if(best_value == -1) fatal_program_error("partition with no undecided node"); 
}

/*********************************************************************

NAME
	increment_pass_count, init_pass_count

PURPOSE
	These function take care of all the operations needed by the 
	pass count, from the initialization of the count in the nodes
	to the increment of the pass counter.

SYNOPSIS
	increment_pass_count()

	init_pass_count()

DESCRIPTION
	When we initialize, all the nodes in the working lists get their count
	reset to 0, the pass_counter is then put to 2. At any time when we
	increment the pass_count, we want to insure that the count of all the
	nodes is inferior to the new pass_count so the count can never reach
	any of the values left in the nodes. There is a problem however, when
	the pass_count does overflow and comes back to 0; at that point, we
	simply reinitialize all the nodes and put the pass count to 2. Also
	the first node scanned, current_node, will have its count set to the
	pass counter.

    -increment_pass_count increments of 2 the pass counter and set to pass
	counter + 1 the odd_pass_counter. If the pass counter does overflow,
	we call the function init pass count.

COORDINATES
	McGill University Electrical Engineering VLSI lab MONTREAL CANADA
	20 july 1984

AUTHOR
	Michel DAGENAIS

*************************************************************************/

increment_pass_count()

{
  pass_counter += 2;

/* we have an overflow of the pass counter */

  if(pass_counter == NULL)
   { init_pass_count();
     pass_counter += 2;
   }

  odd_pass_counter = pass_counter | ONE;
  current_node->count = pass_counter;
  return;
}

/**************************************************************************/

init_pass_count()

{
  struct node **cursor;		/* temp pointer in the vector to reset */

  pass_counter = NULL;
  cursor = prime_nodes;
  for(; cursor <  end_prime ; cursor++)
   { (*cursor)->count = pass_counter;
   }
}

/***********************************************************************

NAME
	push, pop

PURPOSE
	push and pop node pointers from the stack of affected nodes.
	It is a standard stack implementation; When the stack is empty
	a null value is returned, when the stack is full a fatal error
	is signaled.

SYNOPSIS
	push(node)
	struct node *node;

	struct node *pop()

COORDINATES
	McGill University Electrical Engineering VLSI lab MONTREAL QUEBEC
	25 july 1984

AUTHOR
	Michel DAGENAIS

*****************************************************************************/

push(node)

struct node *node;
{
  if(current_in_stack == end_stack) 
			fatal_program_error("affected nodes stack is full");
  *current_in_stack = node;
  current_in_stack++;
}

/*************************************************************************/

struct node *pop()

{
  if(current_in_stack == start_stack) return(NULL);
  current_in_stack--;
  return(*current_in_stack);
}

*��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������