#include "cubes.h"

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

NAME
	scan_affected_retained_ancestors, scan_affected_retained_descendants
	scan_affected_unretain_ancestors, scan_affected_unretain_descendants

PURPOSE
	This recursive function scans all the path in the graph that may
	contain some nodes that may be affected by the decision taken on
	a node. If a node is retained, all the undecided nodes that intersect
	with this node might get completely covered or simply inferior; their
	uncovered part is updated in the process to take into account the fact
	that a new node was retained and covers part of it. If a node is
	unretained, some node might become essential because they would be
	the only remaining undecided node to cover a yet uncovered part of
	the function.

SYNOPSIS
	scan_affected_retained_ancestors()

	scan_affected_retained_descendants()

	scan_affected_unretain_ancestors()

	scan_affected_unretain_descendants()

DESCRIPTION
    -scan_affected_retained_ancestors will look at all the ancestors of the
	current_node. For each of them, if their uncovered part intersects with
	the scanned_node, it is updated to take into account the fact that
	the scanned node is being retained. The undecided nodes affected are
	put on the stack with the status affected_retained. Also when we have
	intersection, all the ancestors and descendants of the node affected
	will be recursively scanned.

    -scan_affected_retained_descendants does the samething but on the
	descendants of the current node. Also the intersecting descendants
	only have their descendants recursively scannned.

    -scan_affected_unretain_ancestors will look to all the ancestors of
	the current node. For each of them, if their uncovered part intersects
	with the scanned node they have their ancestors and descendants
	recursively checked. Also the nodes undecided affected are put on the
	affected stack to be processed in case we can now get a decision on 
	them.

    -scan_affected_unretain_descendants does the same but on the descendants
	of the current node. Also the intersecting descendants only have
	their intersecting descendants recursively scanned.

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

AUTHOR
	Michel DAGENAIS

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

scan_affected_retained_descendants()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if((current_node->count | ONE) == odd_pass_counter)continue;

/* if the node is covered there is nothing to do on this side */

     if(current_node->status & COVERED)
      { current_node->count = pass_counter;
	continue;
      }

/* if the uncovered part of the node intersects with the node retained
   we will sharp it.						*/

     if(intersect_list(scanned_node->cube,current_node->uncovered))
      { current_node->count = odd_pass_counter;
	if(disjoint_sharp(&(current_node->uncovered),scanned_node->cube))
	 { current_node->status |= COVERED;
	 }
	if(current_node->status & DECIDED)scan_affected_retained_descendants();
	else

/* the node is undecided so if it is not already in the affected stack, we
   will put it in it.						*/

	 { if((current_node->status & AFFECTED) == 0) push(current_node);
	   current_node->status |= AFFECTED_RETAINED;
	   scan_affected_retained_descendants();
	 }
      }
     else current_node->count = pass_counter;
   }
}

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

scan_affected_retained_ancestors()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if(current_node->count == pass_counter)continue;

/* If the node was already scanned for descendants, we will also at this point
   scan its ancestors.						*/

     if(current_node->count == odd_pass_counter)
      { current_node->count = pass_counter;
	scan_affected_retained_ancestors();
        continue;
      }

/* if the node is covered there is nothing to do on this side */

     current_node->count = pass_counter;

     if(current_node->status & COVERED) continue;

/* if the uncovered part of the node intersects with the node retained
   we will sharp it.						*/

     if(intersect_list(scanned_node->cube,current_node->uncovered))
      { if(disjoint_sharp(&(current_node->uncovered),scanned_node->cube))
	 { current_node->status |= COVERED;
	 }
	if(current_node->status & DECIDED)
	 { scan_affected_retained_ancestors();
	   current_node = temp_parent->parent;
	   scan_affected_retained_descendants();
 	 }
	else

/* the node is undecided so if it is not already in the affected stack, we
   will put it in it.						*/

	 { if((current_node->status & AFFECTED) == 0) push(current_node);
	   current_node->status |= AFFECTED_RETAINED;
	   scan_affected_retained_ancestors();
	   current_node = temp_parent->parent;
	   scan_affected_retained_descendants();
	 }
      }
   }
}

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

scan_affected_unretain_descendants()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if((current_node->count | ONE) == odd_pass_counter)continue;

/* if the node is covered there is nothing to do on this side */

     if(current_node->status & COVERED)
      { current_node->count = pass_counter;
	continue;
      }

/* if the uncovered part of the node intersects with the node unretained
   this part may become essential if this node is the only one not
   unretained to cover it.				*/

     if(intersect_list(scanned_node->cube,current_node->uncovered))
      { current_node->count = odd_pass_counter;
	if(current_node->status & DECIDED)scan_affected_unretain_descendants();
	else

/* the node is undecided so if it is not already in the affected stack, we
   will put it in it.						*/

	 { if((current_node->status & AFFECTED) == 0) push(current_node);
	   current_node->status |= AFFECTED_UNRETAIN;
	   scan_affected_unretain_descendants();
	 }
      }
     else current_node->count = pass_counter;
   }
}

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

scan_affected_unretain_ancestors()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if(current_node->count == pass_counter)continue;

/* if the node was already scanned for descendants we will now at this
   point scan it for ancestors.					*/

     if(current_node->count == odd_pass_counter)
      { current_node->count = pass_counter;
        scan_affected_unretain_ancestors();
	continue;
      }

     current_node->count = pass_counter;

/* if the node is covered there is nothing to do on this side */

     if(current_node->status & COVERED)continue;

/* if the uncovered part of the node intersects with the node unretained
   this part may become essential if this node is the only one not
   unretained to cover it.				*/

     if(intersect_list(scanned_node->cube,current_node->uncovered))
      { if(current_node->status & DECIDED)
	 { scan_affected_unretain_ancestors();
	   current_node = temp_parent->parent;
	   scan_affected_unretain_descendants();
	 }
	else

/* the node is undecided so if it is not already in the affected stack, we
   will put it in it.						*/

	 { if((current_node->status & AFFECTED) == 0) push(current_node);
	   current_node->status |= AFFECTED_UNRETAIN;
	   scan_affected_unretain_ancestors();
	   current_node = temp_parent->parent;
	   scan_affected_unretain_descendants();
	 }
      }
   }
}

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

NAME
	scan_inferior_descendants, scan_inferior_ancestors

PURPOSE
	Determine if the uncovered part of a cube by retained cubes can
	be covered by a single unretained cube of lower or equal cost,
	in which case, the scanned cube is inferior.

SYNOPSIS
	int scan_inferior_descendants()

	int scan_inferior_ancestors()

DESCRIPTION

    -scan_inferior_descendants, for each descendants of the current node,
	we look if they are undecided and can cover the uncovered part of
	the scanned node. If the cube is of lower or equal cost then the
	scanned node, we unretain inferior the scanned node. If the node
	is of greater cost and covers, if we dont ask for minimum number 
	of literals, we will unretain inferior the scanned node just as well.
	If the descendants examined is undecided inferior or if it is
	undecided but of greater cost, we will scan its descendants 
	recursively.

    -scan_inferior_ancestors does the same but on the ancestors. Also the
	recursive scanning is on both the ancestors and descendants.

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

AUTHOR
	Michel DAGENAIS

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

int scan_inferior_descendants()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or the scanned node to avoid passing many times on some node on the 
   graph. 							*/

     if((current_node->count | ONE) == odd_pass_counter)continue;

/* If the node is covered by retained cubes, we can ignore it since it was
   sharped from the scanned cube in the scan covering pass	*/

     if(current_node->status & COVERED) 
      { current_node->count = pass_counter;
        continue;
      }

     if(intersect_list(current_node->cube,scanned_node->uncovered))
      { current_node->count = odd_pass_counter;
        if(current_node->status & DECIDED)

/* the node is unretained but covers the uncovered part of the scanned_node
   so maybe one of its parents is undecided and also covers it and we must
   scan them.								*/

	 { if(scan_inferior_descendants()) return(1);
	 }

/* if the node is undecided and covers the scanned cube and has a lower cost
   then the scanned cube is unretained inferior.			*/

	else if(covers_list(current_node->cube,scanned_node->uncovered))
	 { if(current_node->cost <= scanned_node->cost || DONT_MIN_LITERAL)
	    {
#ifdef CHECK
	      unretain_inferior_check_node();
#else
	      unretain_inferior_node();
#endif
              return(1);
	    }
	   else if(scan_inferior_descendants()) return(1);
	 }
	else
	 { if(scan_inferior_descendants()) return(1);
	 }
      }
     else current_node->count = pass_counter;
   }
  return(0);
}

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

int scan_inferior_ancestors()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or the scanned node to avoid passing many times on some node on the 
   graph. 							*/

     if(current_node->count == pass_counter)continue;

     if(current_node->count == odd_pass_counter)
      { current_node->count = pass_counter;
	if(scan_inferior_ancestors()) return(1);
	continue;
      }

     current_node->count = pass_counter;

/* If the node is covered by retained cubes, we can ignore it since it was
   sharped from the scanned cube in the scan covering pass	*/

     if(current_node->status & COVERED) continue;

     if(intersect_list(current_node->cube,scanned_node->uncovered))
      { if(current_node->status & DECIDED)

/* the node is unretained but covers the uncovered part of the scanned_node
   so maybe one of its parents is undecided and also covers it and we must
   scan them.								*/

	 { if(scan_inferior_ancestors()) return(1);
	   current_node = temp_parent->parent;
	   if(scan_inferior_descendants()) return(1);
	 }

/* if the node is undecided and covers the scanned cube and has a lower cost
   then the scanned cube is unretained inferior.			*/

	else if(covers_list(current_node->cube,scanned_node->uncovered))
	 { if(current_node->cost <= scanned_node->cost || DONT_MIN_LITERAL)
	    {
#ifdef CHECK
	      unretain_inferior_check_node();
#else
	      unretain_inferior_node();
#endif
	      return(1);
	    }
	   else
	    { if(scan_inferior_ancestors()) return(1);
	      current_node = temp_parent->parent;
	      if(scan_inferior_descendants()) return(1);
	    }
	 }
	else
	 { if(scan_inferior_ancestors()) return(1);
	   current_node = temp_parent->parent;
	   if(scan_inferior_descendants()) return(1);
	 }
      }
   }
  return(0);
}

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

NAME
	scan_essential_descendants, scan_essential_ancestors

PURPOSE
	Determine if the uncovered part of the scanned node can be 
	covered by an undecided node, if not the scanned node must
	be retained.

SYNOPSIS
	int scan_essential_descendants()

	int scan_essential_ancestors()

DESCRIPTION
	The parent nodes are scanned to see if the uncovered part can be
	covered by the undecided cubes. Scanned_cube contains the part
	of scanned_node not covered by any retained or undecided node.
	The parents of the current node which are undecided are sharped
	from the scanned_cube; The parents unretained inferior intersecting
	with the scanned cube are scanned recursively in case one of their
	parent would intersect with scanned cube and be undecided.

    -scan_essential_descendants examines the descendants of the current node
	and scans recursively the intersecting inferior nodes.

    -scan_essential_ancestors does the same on the ancestors of the current
	node. Also the ancestors and descendants are scanned recursively.

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

AUTHOR
	Michel DAGENAIS

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

int scan_essential_descendants()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or the scanned node to avoid passing many times on some node on the 
   graph. 							*/

     if((current_node->count | ONE) == odd_pass_counter)continue;

/* If the node is covered by retained cubes, we can ignore it since it was
   sharped from the scanned cube in the scan covering pass	*/

     if(current_node->status & COVERED) 
      { current_node->count = pass_counter;
	continue;
      }

     if(intersect_list(current_node->cube,scanned_cube))
      { if(current_node->status & DECIDED)

/* the node is unretained but covers a part of the scanned_node
   so maybe one of its parents is undecided and also covers it and we must
   scan them.								*/

	 { current_node->count = odd_pass_counter;
	   if(scan_essential_descendants())return(1);
	 }

/* if the node is undecided and covers a part of the scanned cube we sharp it
   and see if any uncovered part remains.				*/

	else
	 { current_node->count = pass_counter;
 	   if(disjoint_sharp(&scanned_cube,current_node->cube)) return(1);
	 }
      }
     else current_node->count = pass_counter;
   }
  return(0);
}

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

int scan_essential_ancestors()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or the scanned node to avoid passing many times on some node on the 
   graph. 							*/

     if(current_node->count == pass_counter)continue;

     if(current_node->count == odd_pass_counter)
      { current_node->count = pass_counter;
	if(scan_essential_ancestors()) return(1);
	continue;
      }

     current_node->count = pass_counter;

/* If the node is covered by retained cubes, we can ignore it since it was
   sharped from the scanned cube in the scan covering pass	*/

     if(current_node->status & COVERED) continue;

     if(intersect_list(current_node->cube,scanned_cube))
      { if(current_node->status & DECIDED)

/* the node is unretained but covers a part of the scanned_node
   so maybe one of its parents is undecided and also covers it and we must
   scan them.								*/

	 { if(scan_essential_ancestors())return(1);
	   current_node = temp_parent->parent;
	   if(scan_essential_descendants()) return(1);
	 }

/* if the node is undecided and covers a part of the scanned cube we sharp it
   and see if any uncovered part remains.				*/

	else
	 { if(disjoint_sharp(&scanned_cube,current_node->cube)) return(1);
	 }
      }
   }
  return(0);
}

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

NAME
	scan_partition

PURPOSE
	When we have a cycle we want to put in a partition only the nodes that
	can interact with each other. Two nodes can interact with each other 
	when their respective uncovered part do intersect. So in a partition
	we put together all the nodes undecided or inferior such that each node
	is related directly or indirectly to the starting node.

SYNOPSIS
	scan_partition()

DESCRIPTION
	All the nodes which can affect the current node have their pass count
	set to the pass counter and they are recursively scanned. Also, each
	node put this way in the partition is counted in scan_count. 

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

AUTHOR
	Michel DAGENAIS

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

scan_partition()

{
  struct parent *temp_parent;	/* parent to inspect */

  struct node *save_current_node;	/* current node saved during scanning */

/* we will now scan its ancestors to find uncovered nodes to scan */

  save_current_node = current_node;
  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

     if(current_node->count == pass_counter)continue;

/* If the node is covered by retained cubes, we can ignore it since it 
   does cut the interactions with the other cubes related to it. */

     if(current_node->status & COVERED) 
      { current_node->count = pass_counter;
        continue;
      }

/* it is a undecided or inferior node it will be scanned for partition */

     if(intersect_list(current_node->cube,save_current_node->uncovered))
      { current_node->count = pass_counter;
	scan_count++;
	scan_partition();
      }
   }
	
/* we will now scan its descendants to find uncovered nodes to scan */

  temp_parent = save_current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

     if(current_node->count == pass_counter)continue;

/* If the node is covered by retained cubes, we can ignore it since it 
   does cut the interactions with the other cubes related to it. */

     if(current_node->status & COVERED) 
      { current_node->count = pass_counter;
        continue;
      }

/* it is a undecided or inferior node it will be scanned for partition */

     if(intersect_list(current_node->cube,save_current_node->uncovered))
      { current_node->count = pass_counter;
	scan_count++;
        scan_partition();
      }
   }
}

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

NAME
	scan_sparse_ancestors, scan_sparse_descendants

PURPOSE
	Find all the other retained cubes intersecting with a retained cube,
	to sharp them and determine which part is uniquely covered by each
	retained cube.

SYNOPSIS
	scan_sparse_ancestors()

	scan_sparse_descendants()

DESCRIPTION

    -scan_sparse_ancestors, the ancestors of the current node are examined,
	the retained nodes are sharped from the scanned cube. The other
	nodes intersecting with the scanned cube have their ancestors and
	descendants recursively scanned.

    -scan_sparse_descendants does the same but for the descendants of the
	current node. Also the recursive scan is done only on the descendants.

COORDINATES
	McGill University Electrical Engineering VLSI lab MONTREAL CANADA
	14 august 1984

AUTHOR
	Michel DAGENAIS

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

scan_sparse_descendants()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->descendants;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if((current_node->count | ONE) == odd_pass_counter)continue;

/* The node is retained, we will sharp it from the scanned cube */ 

     if(current_node->status & RETAINED)
      { (void)disjoint_sharp(&scanned_cube,current_node->cube);
	current_node->count = pass_counter;
	continue;
      }

     if(intersect_list(current_node->cube,scanned_cube))
      { current_node->count = odd_pass_counter;
	scan_sparse_descendants();
      }
     else current_node->count = pass_counter;
   }
}

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

scan_sparse_ancestors()

{
  struct parent *temp_parent;	/* parent to inspect */

  temp_parent = current_node->ancestors;

  for(; temp_parent != NULL ; temp_parent = temp_parent->next_parent)
   { current_node = temp_parent->parent;

/* we must check that we do not come back to either the calling node 
   or a node already scanned to avoid passing many times on some node on the 
   graph. 							*/

     if(current_node->count == pass_counter)continue;

/* If the node was already scanned for descendants, we will also at this point
   scan its ancestors.						*/

     if(current_node->count == odd_pass_counter)
      { current_node->count = pass_counter;
	scan_sparse_ancestors();
        continue;
      }

     current_node->count = pass_counter;

     if(current_node->status & RETAINED) 
      { (void)disjoint_sharp(&scanned_cube,current_node->cube);
	continue;
      }

     if(intersect_list(scanned_node->cube,current_node->uncovered))
      { scan_sparse_ancestors();
	current_node = temp_parent->parent;
	scan_sparse_descendants();
      }
   }
}