sharing.c

/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *                  STRUCTURE SHARING                     * */
/* *                                                        * */
/* *  $Module:   SHARING                                    * */ 
/* *                                                        * */
/* *  Copyright (C) 1996, 1997, 1998, 1999, 2000            * */
/* *  MPI fuer Informatik                                   * */
/* *                                                        * */
/* *  This program is free software; you can redistribute   * */
/* *  it and/or modify it under the terms of the GNU        * */
/* *  General Public License as published by the Free       * */
/* *  Software Foundation; either version 2 of the License, * */
/* *  or (at your option) any later version.                * */
/* *                                                        * */
/* *  This program 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 General Public * */
/* *  License for more details.                             * */
/* *                                                        * */
/* *  You should have received a copy of the GNU General    * */
/* *  Public License along with this program; if not, write * */
/* *  to the Free Software Foundation, Inc., 59 Temple      * */
/* *  Place, Suite 330, Boston, MA  02111-1307  USA         * */
/* *                                                        * */
/* *                                                        * */
/* $Revision$                                        * */
/* $State$                                            * */
/* $Date$                             * */
/* $Author$                                       * */
/* *                                                        * */
/* *             Contact:                                   * */
/* *             Christoph Weidenbach                       * */
/* *             MPI fuer Informatik                        * */
/* *             Stuhlsatzenhausweg 85                      * */
/* *             66123 Saarbruecken                         * */
/* *             Email: weidenb@mpi-sb.mpg.de               * */
/* *             Germany                                    * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/


/* $RCSfile$ */

#include "sharing.h"

/**************************************************************/
/* Static Variables                                           */
/**************************************************************/

#ifdef CHECK
static BOOL sharing_DATABLOCKED;
#endif

static LIST sharing_DATALIST = (LIST) NULL;

#define sharing_STACKSIZE      500
static LIST sharing_STACK[sharing_STACKSIZE];
static LIST* sharing_STACKPOINTER = sharing_STACK;

/**************************************************************/
/* Prototypes for static functions used only in this module   */
/**************************************************************/

static BOOL sharing_IsNoMoreUsed(TERM);
static LIST sharing_InternGetDataList(TERM);

static TERM sharing_InsertIntoSharing(TERM, SHARED_INDEX);
static void sharing_DeleteFromSharing(TERM, SHARED_INDEX);

static void sharing_ResetTermStamp(TERM);

static void sharing_PrintWithSuperterms(TERM);


/**************************************************************/
/* ********************************************************** */
/* *			                                    * */
/* *  PRIMITIVE SHARING FUNCTIONS                           * */
/* *							    * */
/* ********************************************************** */
/**************************************************************/


SHARED_INDEX sharing_IndexCreate(void)
/**********************************************************
  INPUT:   None.
  RETURNS: A shared index, consisting of an Index, a Consttable
           and a Vartable.
  EFFECTS: Initializes the shared Index for the sharing_Vartable and the
           sharing_Consttable with NULL-Pointers and an empty st_index.
**********************************************************/
{
  SHARED_INDEX Result;
  int          i;

  Result = (SHARED_INDEX)memory_Malloc(sizeof(SHARED_INDEX_NODE));
  sharing_SetIndex(Result, st_IndexCreate());

  for (i=0; (i < symbol_MaxVars()); i++)
    sharing_SetVartableEntry(Result, i, NULL);

  for (i=0; (i < symbol_MaxConsts()); i++)
    sharing_SetConsttableEntry(Result, i, NULL);

  sharing_SetStampID(Result, term_GetStampID());
  return Result;
}


void sharing_IndexDelete(SHARED_INDEX ShIndex)
/**********************************************************
  INPUT:   A shared Index.
  RETURNS: None.
  EFFECTS: Deletes the Index and frees the memory for the
           structure including the Const- and Vartable.
**********************************************************/
{
  st_IndexDelete(sharing_Index(ShIndex));

  memory_Free(ShIndex, sizeof(SHARED_INDEX_NODE));
}


void sharing_PushOnStack(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: None.
  EFFECTS: Creates a Stack of Pointers to the 
           term and all of its subterms in their order in
	   the arglist (thus ordered by depth).
	   top of the stack is bottom term
**********************************************************/
{
  LIST ArgList;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_PushOnStack: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  stack_Push(Term);

  ArgList = term_ArgumentList(Term);

  while (!list_Empty(ArgList)){
    sharing_PushOnStack(list_Car(ArgList));
    ArgList = list_Cdr(ArgList);
  }
}


void sharing_PushReverseOnStack(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: None.
  EFFECTS: Creates a Stack of Pointers to the 
           term and all of its subterms, except variables in their order in
	   the arglist (thus ordered by depth).
	   top of the stack is top term
**********************************************************/
{
  LIST ArgList;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_PushReverseOnStack: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  if (!term_IsVariable(Term)) {

    ArgList = term_ArgumentList(Term);

    while (!list_Empty(ArgList)){
      sharing_PushReverseOnStack(list_Car(ArgList));
      ArgList = list_Cdr(ArgList);
    }

    stack_Push(Term);
  }
}

void sharing_PushReverseOnStackExcept(TERM Term, LIST DontTermList)
/**********************************************************
  INPUT:   A term and an exception list.
  RETURNS: None.
  EFFECTS: Creates a Stack of Pointers to the 
           term and all of its subterms that are not contained
	   or below the terms in DontTermList in their order in
	   the arglist (thus ordered by depth).
	   top of the stack is top term
**********************************************************/
{
  LIST ArgList;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_PushReverseOnStack: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  if (!term_IsVariable(Term) && !term_ListContainsTerm(DontTermList, Term)) {
    ArgList = term_ArgumentList(Term);

    while (!list_Empty(ArgList)){
      sharing_PushReverseOnStackExcept(list_Car(ArgList), DontTermList);
      ArgList = list_Cdr(ArgList);
    }

    stack_Push(Term);
  }
}

void sharing_PushOnStackNoStamps(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: None.
  EFFECTS: Creates a Stack of Pointers to the 
           term and all of its subterms that are not stamped
	   or below stamped terms.
	   top of the stack is top term.
**********************************************************/
{
  LIST ArgList;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_PushReverseOnStackNoStamps: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  if (!term_IsVariable(Term) && !term_HasTermStamp(Term)) {

    stack_Push(Term);

    ArgList = term_ArgumentList(Term);

    while (!list_Empty(ArgList)){
      sharing_PushOnStackNoStamps(list_Car(ArgList));
      ArgList = list_Cdr(ArgList);
    }
  }
}


void sharing_PushListOnStack(LIST TermList)
/**********************************************************
  INPUT:   A list of terms.
  RETURNS: None.
  EFFECTS: Creates a Stack of Pointers to the 
           terms in <TermList>  and all of subterms in their order in
	   the arglist (thus ordered by depth).
**********************************************************/
{
  while (!list_Empty(TermList)) {
    sharing_PushOnStack(list_Car(TermList));
    TermList = list_Cdr(TermList);
  }
}


void sharing_PushListReverseOnStack(LIST TermList)
/**********************************************************
  INPUT:   A list of terms.
  RETURNS: None.
  EFFECTS: Puts all terms in Termlist and their superterms
           in their order in the arglist (thus ordered by depth)
	   on the stack.
	   On top of the stack are subterms.
**********************************************************/
{
  while (!list_Empty(TermList)) {
    sharing_PushReverseOnStack(list_Car(TermList));
    TermList = list_Cdr(TermList);
  }
}

void sharing_PushListReverseOnStackExcept(LIST TermList, LIST DontPushList)
/**********************************************************
  INPUT:   Two lists of terms.
  RETURNS: None.
  EFFECTS: Puts all terms in Termlist except those contained in
           DontPushList and their superterms
           in their order in the arglist (thus ordered by depth)
	   on the stack.
	   On top of the stack are subterms.
**********************************************************/
{
  while (!list_Empty(TermList)) {
    sharing_PushReverseOnStackExcept(list_Car(TermList), DontPushList);
    TermList = list_Cdr(TermList);
  }
}

void sharing_PushListOnStackNoStamps(LIST TermList)
/**********************************************************
  INPUT:   A list of terms.
  RETURNS: None.
  EFFECTS: Puts all terms in Termlist on the stack.
	   On top of the stack are subterms.
**********************************************************/
{
  while (!list_Empty(TermList)) {
    sharing_PushOnStackNoStamps(list_Car(TermList));
    TermList = list_Cdr(TermList);
  }
}


static BOOL sharing_IsNoMoreUsed(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: TRUE,  if the Term has no superterms,
           FALSE, else.
**********************************************************/
{
#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_IsNoMoreUsed: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  return (list_Empty(term_SupertermList(Term)));
}


/**************************************************************/
/* ********************************************************** */
/* *			                                    * */
/* *  FUNCTIONS FOR INSERTION AND DELETION                  * */
/* *							    * */
/* ********************************************************** */
/**************************************************************/

/**************************************************************/
/* ********************************************************** */
/* *			                                    * */
/* *  1) FUNCTIONS FOR INSERTION                            * */
/* *							    * */
/* ********************************************************** */
/**************************************************************/

TERM sharing_Insert(POINTER Data, TERM Atom, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A data element, it's unshared atom and a SharedIndex.
  RETURNS: The shared term inserted into the SharedIndex.
  CAUTION: The superterm slot of <Atom> is destructively used!
  MEMORY:  The term 'Atom' still exists, memory needed for
           the shared version is allocated. 
**********************************************************/
{
#ifdef CHECK
  if (!term_IsTerm(Atom) || (!sharing_IsNoMoreUsed(Atom))){
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_Insert: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  Atom = sharing_InsertIntoSharing(Atom, SharedIndex);

  term_RplacSupertermList(Atom, list_Cons(Data, term_SupertermList(Atom)));

  return(Atom);
}


static TERM sharing_InsertIntoSharing(TERM Term, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A term and a shared index.
  RETURNS: A copy of 'Term' which is inserted into the Sharing
           and the "SharedIndex".
  MEMORY:  The unshared version isn't freed, needed memory
           is allocated.
**********************************************************/
{
  int B_Stack;
  TERM InsTerm;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_InsertIntoSharing: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  B_Stack = stack_Bottom();
  sharing_PushOnStack(Term);
  InsTerm = stack_Top();      /* not necessary initialization ... */

  while (! stack_Empty(B_Stack)){
    InsTerm = stack_PopResult();

    if (term_IsVariable(InsTerm)){
      if (!sharing_IsSharedVar(InsTerm, SharedIndex)) {

	sharing_SetVartableEntry(SharedIndex, sharing_VariableIndex(InsTerm),
				 term_Create(term_TopSymbol(InsTerm),
					     list_Nil()));

	st_EntryCreate(sharing_Index(SharedIndex),
		       sharing_VartableEntry(SharedIndex,
					     sharing_VariableIndex(InsTerm)),
		       sharing_VartableEntry(SharedIndex,
					     sharing_VariableIndex(InsTerm)),
		       cont_LeftContext());
      }

	/* The NULL-Pointer in the Vartable is replaced by a copy of the */
	/* InsTerm, which is referenced by the InsTerms SharedTermCopy.  */
	/* A complex T still has to be insert. into its Args superlists. */
	/* The unshared Term isn't yet in the 'SharedIndex' and thus is  */
	/* inserted, too.                                                */
    

      sharing_RememberSharedTermCopy(InsTerm,
				     sharing_VartableEntry(SharedIndex, sharing_VariableIndex(InsTerm)));

    }else if (term_IsConstant(InsTerm)){ 
      if (!sharing_IsSharedConst(InsTerm, SharedIndex)) { 
	sharing_SetConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm),
				   term_Create(term_TopSymbol(InsTerm),
					       list_Nil()));

	st_EntryCreate(sharing_Index(SharedIndex),
		       sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm)),
		       sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm)),
		       cont_LeftContext());
      }

	/* The NULL-Pointer in the Consttable is replaced by a copy of the */
	/* InsTerm, which is referenced by the InsTerms SharedTermCopy.    */
	/* A complex T still has to be insert. into its Args superlists.   */
	/* The unshared Term isn't yet in the 'SharedIndex' and thus is    */
	/* inserted, too.                                                  */

      sharing_RememberSharedTermCopy(InsTerm,
				     sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm)));

    }else{  /* term_IsComplex(InsTerm) */
            /* -> owns subterms which now have copies in Sharing.  */

      TERM SharedDuplicate;
      LIST HelpList;
      BOOL DuplCandHasSameArgs;

      SharedDuplicate = (TERM)NULL;
      HelpList =
        term_SupertermList(sharing_SharedTermCopy(term_FirstArgument(InsTerm)));
      if (list_Empty(HelpList)){
	  SharedDuplicate = term_Create(term_TopSymbol(InsTerm), list_Nil());
	  DuplCandHasSameArgs = FALSE;
	}
      else{
	DuplCandHasSameArgs = FALSE;
	while (!DuplCandHasSameArgs && !list_Empty(HelpList)){
	  SharedDuplicate = (TERM) list_First(HelpList);

	  if (term_TopSymbol(SharedDuplicate) == term_TopSymbol(InsTerm)){
	    LIST OrigHelpArgList, DuplHelpArgList;

	    OrigHelpArgList = term_ArgumentList(InsTerm);
	    DuplHelpArgList = term_ArgumentList(SharedDuplicate);
	    while (!list_Empty(OrigHelpArgList) &&
		   (DuplCandHasSameArgs = 
                   (sharing_SharedTermCopy(list_First(OrigHelpArgList)) ==
		    list_First(DuplHelpArgList)))){
	      DuplHelpArgList = list_Cdr(DuplHelpArgList);
	      OrigHelpArgList = list_Cdr(OrigHelpArgList);
	    }
	  }
	  HelpList = list_Cdr(HelpList);
	}
	if (!DuplCandHasSameArgs)
	  SharedDuplicate = term_Create(term_TopSymbol(InsTerm), list_Nil());
      } /* end of else fuer Behandlung von InsTerm mit shared FirstArg. */

      if (!DuplCandHasSameArgs){
      /* Falls neue Kopie gemacht wurde, wird diese hier "eingeshared": */

	for (HelpList = term_ArgumentList(InsTerm); !list_Empty(HelpList);
	     HelpList = list_Cdr(HelpList)){
	  TERM SharedArg;
	
	  SharedArg = sharing_SharedTermCopy((TERM)list_First(HelpList));

	  term_RplacArgumentList(SharedDuplicate, 
				 list_Cons(SharedArg,
					   term_ArgumentList(SharedDuplicate)));

	  term_RplacSupertermList(SharedArg,
	    list_Cons(SharedDuplicate,
		      term_SupertermList(SharedArg)));
	}
	term_RplacArgumentList(SharedDuplicate, 
	  list_NReverse(term_ArgumentList(SharedDuplicate)));
	
	/* Now a newly generated term can be inserted into the 'SharedIndex' !  */
	
	st_EntryCreate(sharing_Index(SharedIndex),
		       SharedDuplicate,
		       SharedDuplicate,
		       cont_LeftContext());

      }
      sharing_RememberSharedTermCopy(InsTerm,
				      SharedDuplicate);
    } 
  } 

  return(sharing_SharedTermCopy(InsTerm));
}

/**************************************************************/
/* ********************************************************** */
/* *			                                    * */
/* *  2) FUNCTIONS FOR DELETION                             * */
/* *							    * */
/* ********************************************************** */
/**************************************************************/

void sharing_Delete(POINTER Data, TERM Atom, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A data element, its atom and an index.
  RETURNS: Nothing.
  MEMORY:  Destructive, deletes 'Atom' from Sharing and frees
           memory that's no more needed.
***********************************************************/
{
#ifdef CHECK
  if (!term_IsTerm(Atom)){
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_Delete: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  term_RplacSupertermList(Atom,
    list_PointerDeleteElement(term_SupertermList(Atom), Data));

  if (sharing_IsNoMoreUsed(Atom))
    sharing_DeleteFromSharing(Atom, SharedIndex);

}


static void sharing_DeleteFromSharing(TERM Term, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A term and a SharedIndex
  RETURNS: Nothing 
  MEMORY:  'Term' is removed from the Sharing, only correct
           if 'Term' is unshared in sharing (real subterms
	   may be shared, off course).
***********************************************************/
{
  BOOL IsIndexed;
#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_DeleteFromSharing: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  IsIndexed = st_EntryDelete(sharing_Index(SharedIndex), Term, Term, cont_LeftContext());

#ifdef CHECK
  if (!IsIndexed) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_DeleteFromSharing: Input not indexed.\n");
    misc_FinishErrorReport();
  }
#endif

  if (term_IsComplex(Term)){
    LIST Args;

    Args = term_ArgumentList(Term);

    while (!list_Empty(Args)){
      TERM NextArg;
      LIST Help;

      /* This block frees the terms arglists memory. */
      Help = Args;
      NextArg = (TERM) list_First(Args);
      Args = list_Cdr(Args);
      list_Free(Help);

      term_RplacSupertermList(NextArg, 
	list_PointerDeleteOneElement(term_SupertermList(NextArg), Term));
      if (sharing_IsNoMoreUsed(NextArg))
	sharing_DeleteFromSharing(NextArg, SharedIndex);
    }

  } else if (term_IsConstant(Term)) {
    sharing_SetConsttableEntry(SharedIndex, sharing_ConstantIndex(Term), NULL);
  } else {
    sharing_SetVartableEntry(SharedIndex, sharing_VariableIndex(Term), NULL);
  }
  list_Delete(term_SupertermList(Term));
  term_Free(Term);
}


/**************************************************************/
/* Functions to access unshared data via the shared term.     */
/**************************************************************/

LIST sharing_GetDataList(TERM Term, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared term and the shared index it belongs to.
  RETURNS: The list of data connected to all superterms of Term,
           e.g. the list of all literals containing Term.
  EFFECT:  Allocates memory for the returned list.
  CAUTION: Works recursive!
**********************************************************/
{
  LIST Result = list_Nil();
#ifdef CHECK
  if (!term_IsTerm(Term) || (SharedIndex == NULL)){
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_GetDataList: Illegal input.\n");
    misc_FinishErrorReport();
  }
  /* What if the term doesn't belong to this shared index ?????? */

#endif

  if (term_StampOverflow(sharing_StampID(SharedIndex)))
    sharing_ResetAllTermStamps(SharedIndex);
    
  term_StartStamp();

  Result = sharing_InternGetDataList(Term);

  term_StopStamp();

  return Result;
}


static LIST sharing_InternGetDataList(TERM Term)
/**********************************************************
  INPUT:   A shared term.
  RETURNS: The list of data connected to all superterms of Term
  EFFECT:  Allocates memory for the returned list.
********************************************************/
{
  if (term_IsAtom(Term))
    /* We are at top level of the superterm "tree",  */
    /* so the recursion stops here                   */ 
    return list_Copy(term_AtomsLiterals(Term));
  else{
    LIST SuperList;
    LIST DataList = list_Nil();

    for (SuperList = term_SupertermList(Term); !list_Empty(SuperList);
	 SuperList = list_Cdr(SuperList)) {
      TERM superterm = (TERM) list_Car(SuperList);
      if (!term_AlreadyVisited(superterm)) {
	DataList = list_Nconc(sharing_InternGetDataList(superterm), DataList);
	term_SetTermStamp(superterm);
      }
    }
    return DataList;
  }
}


void sharing_StartDataIterator(TERM Term, SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared term and the shared index it belongs to.
  RETURNS: Nothing.
  EFFECT:  Prepares the data iterator for Term.
           After this call you can access single data items
	   for Term with function sharing_GetNextData.
********************************************************/
{
#ifdef CHECK
  if (!term_IsTerm(Term) || (SharedIndex == NULL)){
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_StartDataIterator: Illegal input.\n");
    misc_FinishErrorReport();
  }
  if (sharing_DATABLOCKED) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_StartDataIterator: Data iterator already used.\n");
    misc_FinishErrorReport();
  }
  sharing_DATABLOCKED = TRUE;
#endif

  if (term_StampOverflow(sharing_StampID(SharedIndex)))
    sharing_ResetAllTermStamps(SharedIndex);
  term_StartStamp();

  /* Init stack */
  sharing_STACKPOINTER = sharing_STACK;  /* Pop all items */
  while (!term_IsAtom(Term)) {
    /* Push superterm list on stack */
    *(sharing_STACKPOINTER++) = term_SupertermList(Term);
    Term                      = list_Car(term_SupertermList(Term));
  }
    
  sharing_DATALIST = term_AtomsLiterals(Term);
}


POINTER sharing_GetNextData(void)
/**********************************************************
  INPUT:   None
  RETURNS: A single data item connected to the term specified
           in the previous call of sharing_StartDataIterator.
	   NULL is returned, if all data items were accessed before.
  EFFECT:  In contrast to function sharing_GetDataList
           no memory is allocated.
********************************************************/
{
  POINTER Result = NULL;
  LIST superlist;

#ifdef CHECK
  if (!sharing_DATABLOCKED) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_GetNextData: Iterator wasn't started.\n");
    misc_FinishErrorReport();
  }
#endif

  if (!list_Empty(sharing_DATALIST)) {
    Result = list_Car(sharing_DATALIST);
    sharing_DATALIST = list_Cdr(sharing_DATALIST);
  } else {
    superlist = NULL;
    while ((sharing_STACKPOINTER > sharing_STACK) && /* stack not empty */
	   list_Empty(superlist)) {
      /* change between backtracking and expansion */
      do { /* Backtracking */
	superlist = *(--sharing_STACKPOINTER); /* PopResult */
	term_SetTermStamp(list_Car(superlist));
	do
	  superlist = list_Cdr(superlist);
	while (!list_Empty(superlist) &&
	       term_AlreadyVisited(list_Car(superlist)));
      } while ((sharing_STACKPOINTER>sharing_STACK) && list_Empty(superlist));
      while (!list_Empty(superlist) &&
	     !term_IsAtom(list_Car(superlist))) { /* Expansion */
	*(sharing_STACKPOINTER++) = superlist;
	superlist = term_SupertermList(list_Car(superlist));
	/* Search next unvisited term */
	while (!list_Empty(superlist) &&
	       term_AlreadyVisited(list_Car(superlist)))
	  superlist = list_Cdr(superlist);
      }
    }
    if (!list_Empty(superlist)) {
      *(sharing_STACKPOINTER++) = superlist;
      sharing_DATALIST          = term_AtomsLiterals(list_Car(superlist));
      Result                    = list_Car(sharing_DATALIST);
      sharing_DATALIST          = list_Cdr(sharing_DATALIST);
    }
  } /* else */
  return Result;
}


void sharing_StopDataIterator(void)
/**********************************************************
  INPUT:   None.
  RETURNS: Nothing.
  EFFECT:  The data iterator is stopped for the term you specified
           in the corresponding call of sharing_StartDataIterator.
********************************************************/
{
#ifdef CHECK
  if (!sharing_DATABLOCKED) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_StopDataIterator: Iterator wasn't started.\n");
    misc_FinishErrorReport();
  }
  sharing_DATABLOCKED = FALSE;
#endif
  sharing_DATALIST = list_Nil();
  term_StopStamp();
}


LIST sharing_NAtomDataList(TERM Atom)
/**********************************************************
  INPUT:   A shared term.
  RETURNS: A List of data connected with 'Term' or superterms.
  EFFECT:  No memory Allocation
  CAUTION: THE RETURNED LIST MUST NOT CHANGE
**********************************************************/
{
#ifdef CHECK
  if (!term_IsTerm(Atom) || !term_IsAtom(Atom)){
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_NAtomDataList: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif
  
  return(term_AtomsLiterals(Atom));
}


LIST sharing_GetAllSuperTerms(SHARED_INDEX Index)
/**********************************************************
  INPUT:   A shared Index.
  RETURNS: A List of all Data in the shared Index.
  EFFECT:  The term stamp is used.
**********************************************************/
{
  int  i;
  LIST Result = list_Nil();
  TERM term;

  if (term_StampOverflow(sharing_StampID(Index)))
    sharing_ResetAllTermStamps(Index);
  term_StartStamp();
  
  for (i = 0; i < symbol_MaxVars(); i++) {
    term = sharing_VartableEntry(Index,i);
    if (term != NULL)
      Result = list_Nconc(sharing_InternGetDataList(term), Result);
  }

  for (i = 0; i < symbol_MaxConsts(); i++) {
    term = sharing_ConsttableEntry(Index,i);
    if (term != NULL)
      Result = list_Nconc(sharing_InternGetDataList(term), Result);
  }
  
  term_StopStamp();

  return Result;
}


void sharing_ResetAllTermStamps(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared index.
  RETURNS: Nothing.
  EFFECT:  The stamps of all terms in the shared index are reset.
**********************************************************/
{
  TERM term;
  int i;
     
  /* Reset stamp for all variables and their superterms */
  for (i = 0; i < symbol_MaxVars(); i++) {
    term = sharing_VartableEntry(SharedIndex, i);
    if (term != NULL)
      sharing_ResetTermStamp(term);
  }

  /* Reset stamp for all constants and their superterms */
  for (i = 0; i < symbol_MaxConsts(); i++){
    term = sharing_ConsttableEntry(SharedIndex, i);
    if (term != NULL)
      sharing_ResetTermStamp(term);
  }
}


static void sharing_ResetTermStamp(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: Nothing.
  EFFECT:  The stamps of Term and all its superterms are reset.
**********************************************************/
{
  LIST SuperList;
  TERM SuperTerm;

  if (!term_IsAtom(Term)) {
    for (SuperList = term_SupertermList(Term); !list_Empty(SuperList);
	 SuperList = list_Cdr(SuperList)) {
      SuperTerm = (TERM) list_Car(SuperList);
      if (!term_StampAlreadyReset(SuperTerm)) {
	sharing_ResetTermStamp(SuperTerm);
	term_ResetTermStamp(SuperTerm);
      }
    }
  }
}


NAT sharing_GetNumberOfOccurances(TERM Term)
/**************************************************************
  INPUT:   A shared (!) term.
  RETURNS: How many literals contain <Term>.
           Note that literals containing <Term> <n> times are counted
	   <n> times.
***************************************************************/
{
  if (term_IsAtom(Term))
    /* Stop recursion */
    return list_Length(term_AtomsLiterals(Term));
  else {
    LIST Scan;
    NAT  Result;

    Result = 0;
    for (Scan = term_SupertermList(Term); !list_Empty(Scan); Scan = list_Cdr(Scan))
      Result += sharing_GetNumberOfOccurances(list_Car(Scan));

    return Result;
  }
}


NAT sharing_GetNumberOfInstances(TERM Term, SHARED_INDEX Index)
/**************************************************************
  INPUT:   A (!) shared term and a shared index. The term has to be
           part of the index.
  RETURNS: How many literals within the index contain an instance of <Term>.
           Note that literals containing <n> instances of <Term>
	   are counted <n> times.
***************************************************************/
{
  NAT  Result;
  TERM Instance;

  Result   = 0;
  Instance = st_ExistInstance(cont_LeftContext(), sharing_Index(Index), Term);
  while (Instance != NULL) {
    Result += sharing_GetNumberOfOccurances(Instance);
    Instance = st_NextCandidate();
  }
  return Result;
}


/**************************************************************/
/* Output functions for the sharing structure.                  */
/**************************************************************/

void sharing_PrintVartable(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared index.
  RETURNS: Nothing.
  EFFECT:  Prints the Vartable entries to stdout
**********************************************************/
{
  int i;
     
  for (i = 0; i < symbol_MaxVars(); i++){
    if (sharing_VartableEntry(SharedIndex, i) != NULL){
      printf("\n X%d   :  ", i);
      
      term_Print(sharing_VartableEntry(SharedIndex, i));
    }
  }
}


void sharing_PrintConsttable(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT: A shared index.  
  RETURNS: Nothing.
  EFFECT:  Prints the Consttable entries to stdout
**********************************************************/
{
  int i;
     
  for (i = 0; i < symbol_MaxConsts(); i++){
    if (sharing_ConsttableEntry(SharedIndex, i) != NULL){
      printf("\n c%d   :  ", i);
      
      term_Print(sharing_ConsttableEntry(SharedIndex, i));
    }
  }
}


void sharing_PrintSharingConstterms1(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared index.
  RETURNS: Nothing.
  EFFECT:  Prints all terms from the Consttable and their
           direct superterms to stdout
**********************************************************/
{
  TERM term;
  int i;
     
  for (i = 0; i < symbol_MaxConsts(); i++) {
    term = sharing_ConsttableEntry(SharedIndex, i);
    if (term != NULL){
      printf("\n c%d   :  ", i);
      term_Print(term);
      puts("   has the direct superterms : ");
      term_TermListPrint(term_SupertermList(term));
    }
  }
}


void sharing_PrintSharingVarterms1(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared index.
  RETURNS: Nothing.
  EFFECT:  Prints all terms from the Vartable and their
           superterms to stdout
**********************************************************/
{
  TERM term;
  int i;
     
  for (i = 0; i < symbol_MaxVars(); i++) {
    term = sharing_VartableEntry(SharedIndex, i);
    if (term != NULL){
      printf("\n x%d   :  ", i);
      term_Print(term);
      puts("   has the direct superterms : ");
      term_TermListPrint(term_SupertermList(term));
    }
  }
}


static void sharing_PrintWithSuperterms(TERM Term)
/**********************************************************
  INPUT:   A Term
  RETURNS: Nothing.
  EFFECT:  Prints all Superterms of 'Term' from the sharing
           to stdout.
**********************************************************/
{

  LIST HelpList;

#ifdef CHECK
  if (!term_IsTerm(Term)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In sharing_PrintWithSuperterms: Illegal input.\n");
    misc_FinishErrorReport();
  }
#endif

  if (term_IsAtom(Term)) {
    term_Print(Term);
    putchar('\n');
  }
  else{
    term_Print(Term);
    HelpList = term_SupertermList(Term);
    if (!list_Empty(HelpList)){
      putchar('[');
      term_TermListPrint(HelpList);
      puts("]");
      while (!list_Empty(HelpList)){
	sharing_PrintWithSuperterms(list_Car(HelpList));
	HelpList = list_Cdr(HelpList);
      }
    }
  }
}


void sharing_PrintSharing(SHARED_INDEX SharedIndex)
/**********************************************************
  INPUT:   A shared Index.
  EFFECT:  Prints the sharing to standard.out.
**********************************************************/
{
  int i;
     
  for (i = 0; i < symbol_MaxConsts(); i++){
    if (sharing_ConsttableEntry(SharedIndex, i) != NULL){
      sharing_PrintWithSuperterms(sharing_ConsttableEntry(SharedIndex, i));
      puts("\n");
    }
  }
  puts("------------------------");
  for (i = 0; i < symbol_MaxVars(); i++){
    if (sharing_VartableEntry(SharedIndex, i) != NULL){
      sharing_PrintWithSuperterms(sharing_VartableEntry(SharedIndex, i));
      puts("\n");
    }
  }
}


void sharing_PrintSameLevelTerms(TERM Term)
/**********************************************************
  INPUT:   A term.
  RETURNS: Nothing.
  EFFECT:  Prints all terms, that share any of 'Term's args to 
           standard.out.
**********************************************************/
{
  LIST HelpList;

  HelpList = term_ArgumentList(Term);

  while (!list_Empty(HelpList)){
    if (!list_Empty(term_SupertermList(list_First(HelpList))))
      term_TermListPrint(term_SupertermList(list_First(HelpList)));

    HelpList = list_Cdr(HelpList);
  }
}

void sharing_PrintStack(void)
/**********************************************************
  INPUT:   None.
  RETURNS: Nothing.
  EFFECT:  Prints the internal sharing stack for iterative
           queries. Only for debugging purposes.
**********************************************************/
{
  TERM term;
  LIST* ptr = sharing_STACKPOINTER;

  while (ptr > sharing_STACK) {
    ptr--;
    term = list_Car(*ptr);
    term_Print(term);
    putchar('\n');
  }
}