#ifndef cast_HH
#define cast_HH

#define PUBLIC
#define PRIVATE static

/***********************************************
 (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   EPS General Public License (see file LICENSE)
 ***********************************************
 $Log: cast.desc,v $
 * Revision 2.13  1994/06/02  17:18:36  eps
 * documentation error
 *
 * Revision 2.12  1993/11/08  16:40:12  eps
 * add new colour: table of integer pairs
 *
 * Revision 2.11  1993/09/20  14:16:40  eps
 * new functions: cut_rb cut_lb cutsons cutbrothers
 * new functions: ln_rb ln_lb
 * new function: ILshare
 * new function: SLshare
 * new function: ATcp
 *
 * Revision 2.10  1993/07/21  12:42:42  eps
 * new functions: INTIsIn INTpos INTnth ITcmp IAT_IL_add
 *
 * Revision 2.9  1993/06/15  10:58:17  eps
 * is NOT a LINTLIBRARY
 *
 * Revision 2.8  1993/01/12  16:35:13  eps
 * portability issues
 *
 * Revision 2.7  1992/11/17  11:48:28  eps
 * fix definition of *alloc for PC portability
 *
 * Revision 2.6  1992/05/06  17:26:33  eps
 * shut up lint complaints about exit()
 *
 * Revision 2.5  92/01/14  15:43:37  eps
 * distribution issues
 * 
 * Revision 2.4  92/01/14  15:26:46  eps
 * speed up case independent hashing
 * 
 * Revision 2.3  92/01/07  11:31:17  eps
 * better explanation of argument "shr" in cp_* functions
 * 
 * Revision 2.2  91/04/10  09:58:40  eps
 * table driven rag phases
 * 
 * Revision 2.1  90/10/30  08:36:40  eps
 * hardwired colours added
 * new colours I2, IAT, AT
 * ! is no longer used as colour delimiter
 * still some bugs are known w.r.t. colour deallocation
 * 
 * Revision 1.6  90/05/10  17:10:33  eps
 * new global variable befussy
 * that complaints for non explicitly declared colours in TIOCOLOURS
 * 
 * Revision 1.5  90/03/16  16:01:38  eps
 * new field cpy in TIOcolours
 * new function fadd_attr
 * colour I/O is done directly on the files by get/put functions
 * IO_xxx are defined for most frequently used colours
 * new functions STRrev, STRcmp, cSL, cSLs
 * new functions INTrev, INTcmp, cIT
 * 
 * Revision 1.4  90/02/19  19:07:03  eps
 * new function set_attr
 * 
 * Revision 1.3  90/02/16  17:52:49  eps
 * miscellaneous cleanup
 * INTlists, STRlists, IT, ST are made compatible
 * and interface is optimized and clarified
 * 
 * Revision 1.2  90/01/29  14:52:20  eps
 * fixing license details
 * 
 * Revision 1.1  90/01/25  20:07:41  eps
 * Initial revision
 * 
 **********************************************
 $Id: cast.desc,v 2.13 1994/06/02 17:18:36 eps Exp $
 **********************************************/

/***********************************************************************
        Tomas P. de Miguel Moro
        Jose A. Manas
        dpt. Ingenieria Telematica
        E.T.S.I. Telecomunicacion
        Ciudad Universitaria
        E-28040  MADRID

        tmiguel@dit.upm.es
        jmanas@dit.upm.es
*************************************************************/

#include <stdlib.h>
#include <stdio.h>

#ifndef TRUE
# define FALSE 0
# define TRUE  1
#endif

# define CLR_TYPE void*
# define others    0	/* for unexpected colours */
typedef enum {PREORDER, POSTORDER} trav_mode;

/*

 * basic AST node
 */

typedef struct Node {
	int         	type;
	struct	Node*	father;
	struct	Node*	brothers;
	struct	Node*	sons;
	struct	Attr*	attrs;
	CLR_TYPE	value0;	/* application dependent */
	CLR_TYPE	value1;	/* application dependent */
	} TNODE;

/* Most colours (or attributes) go to the linked list in attrs,
 * but some that are used very often
 * may be hardwired into value{0,1}.
 * Applications must be aware of the use of value{0,1}
 * and use table HWclr
 * instead of castinit(), key2clr(), and type2clr()
 */

/* basic colour node: a linked list */

typedef struct Attr {
	int		atype;
	struct Attr*	next;
	CLR_TYPE	value;	/* application dependent */
	} TATTR;

/* colour i/o
 * + deallocation,
 * and non-shared copies
 */

typedef struct {
	char		*keyword;
	int		atype;
	CLR_TYPE	(*get)();	/* read */
	void		(*put)();	/* write */
	void		(*free)();	/* deallocate */
	CLR_TYPE	(*cpy)();	/* get a fresh copy */
	} TIOCOLOURS;

/* for hardwired colours ... */
extern TIOCOLOURS HWclr [] /* = {
  "clr0",      0, IO_int,
  "clr1",      1, IO_int
  } */;

/*

 * clrbsc.c: basic functions
 */

/* draws one node on stdout */

void	dr_node ();

/* debugging: draws a tree on stdout */

void	dr_tree ();

/* draws a tree on stdout, down to <depth> levels */

void	drn_tree ();

/*

 * asttrav.c: ast traversal
 */

/* looks for predecesor in the specified traversing mode */

TNODE*	pred    ();

/* looks for successor in the specified traversing mode */

TNODE*	succ    ();

/* looks for predecesor in the specified traversing mode
 * of the specified type
 */

TNODE*	lkpred  ();

/* looks for successor in the specified traversing mode
 * of the specified type
 */

TNODE*	lksucc  ();

/* looks for predecesor in the specified traversing mode
 * that makes true the predicate
 */

TNODE*	lppred  ();

/* looks for successor in the specified traversing mode
 * that makes true the precicate
 */

TNODE*	lpsucc  ();

/*

 * astgoto.c: navigating functions
 */

/* goto father */

# define gt_ft(nodep) ((nodep) == NULL ? NULL : (nodep)->father)

/* goto first son */

# define gt_fs(nodep) ((nodep) == NULL ? NULL : (nodep)->sons)

/* goto last son */

TNODE*	gt_ls   ();

/* goto right brother */

# define gt_rb(nodep) ((nodep) == NULL ? NULL : (nodep)->brothers)

/* goto left brother
 * warning: fails if no father!
 */

TNODE*	gt_lb   ();

/* goto root */

TNODE*	gt_rt ();

/*

 * astmmg.c: memory management
 */

/* get a fresh AST node
 * of then specified type
 */

TNODE*	new_node        ();

/* release an AST node */

void	free_node       ();

/* copy node: get a fresh one,
 * shr == FALSE => the new node has no colouring
 * shr == TRUE  => colours are copied into the new node
 */

TNODE*	cp_node ();

/* copy tree: get a fresh subtree,
 * nodep is used as the root of a subtree,
 * and this subtree is replicated
 * (notice that brothers of nodep are not replicated).
 * shr == FALSE => the new tree has no colouring
 * shr == TRUE  => colours are copied into the new tree
 */

TNODE*	cp_tree ();

/*      cuts off from father and brothers */

void	cut_tree        ();

/* cuts off right brother and returns it */

TNODE*	cut_rb ();

/* cuts off left brother and returns it */

TNODE*	cut_lb ();

/* cuts off sons and returns them */

TNODE*	cutsons ();

/* cuts off brothers and returns them */

TNODE*	cutbrothers ();

/*	kills a branch of a tree
 *      cuts off from father and brothers
 *      frees memory
 */

void	kill_tree       ();

/*

 * astlink.c: tree building functions
 */

/*      adds new sons to a father
 *      They become the youngest brothers of old sons
 *	returns TRUE if successfully completed
 *	returns FALSE if the operation was not possible
 */

int	lnsons  ();

/*      inserts a new son as the n-th one of a father
 *      or last one if there are not so many
 *      sons are numbered 1, 2, ...
 */

TNODE*	lnnson  ();

/*      a new brother is added as the youngest one
 *      the father of the old brothers
 *      becomes the father of the new one
 */

void	lnrnode ();

/*      a new node becomes the oldest brother
 *      the father of the old brothers
 *      becomes the father of the new one
 */

void	lnlnode ();

/*      puts a list of brothers to nodep
 *      the father of nodep
 *      becomes the father of all the brothers
 */

void	lnbrothers      ();

/* adds a new brother to the right */

void	ln_rb ();

/* adds a new brother to the left */

void	ln_lb ();

/*

 * asttest.c: testing node properties
 */

/* test whether it is the root node */

# define t_root(nodep) ((nodep) == NULL ? FALSE : (nodep)->father == NULL)

/* test whether it is a leaf node */

# define t_leaf(nodep) ((nodep) == NULL ? FALSE : (nodep)->sons == NULL)

/* test whether it is the first brother */

int	t_fbrother      ();

/* test whether there are brothers to the right */

# define t_brother(nodep) ((nodep) == NULL ? FALSE : (nodep)->brothers == NULL)

/*

 * astio.c: internal/external conversions
 */

/* save tree onto a file */

void	save_tree       ();

/* load tree from a file */

TNODE*	restore ();

/*

 **********************************************************************
        COLOURS
 **********************************************************************/

/*
 * clrbsc: basic functions
 */

/* initializes the colour i/o tables */
/* as well as the rag phases information */

void	cast_init ();

/* table holding information for rag phases */
extern int* ragphase	/* = 0 */;

/* get the colour i/o table entry by external name */

TIOCOLOURS*	name2clr ();

/* get the colour i/o table entry by internal code */

TIOCOLOURS*	type2clr ();

/* if (befussy & unknown-colour)
 *   then name2clr() and type2clr() will complain
 *   else name2clr() and type2clr() will return OTHERS
 */

extern int befussy /* = FALSE */;

/*
 * clrlib.c: colouring library
 */

/* add a new attribute to a node.
 * duplicates are rejected,
 * except for colour OTHERS (0)
 */

TATTR*	add_attr ();

/* add a new attribute to a node, and set its value.
 * duplicates are rejected,
 * except for colour OTHERS (0)
 */

void	set_attr ();

/* find an attribute in a node */

TATTR*	find_attr ();

/* try to find an attribute in a node
 * if it exists, return it,
 * otherwise, create it, with value NULL
 */

TATTR*	fadd_attr ();

/* extract an attribute from a node,
 * actually eliminating it from the tree
 */

TATTR*	take_attr ();

/*

 * clrio.c: input/output of ast colouring
 */

/* get attributes from external into internal representation */

void	getattrs        ();

/* puts attributes from internal to external representation */

void	putattrs ();

/* releases memory allocated to an attribute */

void	free_attr       ();

/* copy attributes between nodes */

void	copyattrs       ();

/* gets room for a new attribute */

TATTR*	new_attr        ();

/* release attributes */

void	freeattrs       ();

/*

 **********************************************************
 *	Predefined colours
 **********************************************************
 type           get         put         free        cpy
 -------------------------------------------------------------
 int            getint      putint      -           -
 I2             getI2       putI2       -           -
 string         getstring   putstring   freestring  copystring
 hashed str     getlexv     putlexv     -           -
 lists of int   getINTlist  putINTlist  fIL         cIL
 lists of str   getSTRlist  putSTRlist  fSL         cSL
   (shared)                             fSLs        cSLs
 tables of int  getIT       putIT       fIT         cIT
 tables of str  getST       putST       fST         cST
   (shared)                             fSTs        cSTs
 IAT            getIAT      putIAT      fIAT        cIAT
 IAT (shared)   getIAT      putIAT      fIATs       cIATs
 tables of attr	getAT       putAT       -           -
 **********************************************************

 PUBLIC CLR_TYPE
 getXXX (fp)
     FILE* fp;

 PUBLIC void
 putXXX (fp, val)
     FILE* fp;
     CLR_TYPE val;

 PUBLIC void
 freeXXX (val)
     CLR_TYPE val;

 PUBLIC CLR_TYPE
 copyXXX (val)
     CLR_TYPE val;

 **********************************************************/
/**********************************************************
 * the following defines should help in writing TIOCOLOURS entries
 **********************************************************/

# define IO_int getint,     putint,     NULL,       NULL
# define IO_I2  getI2 ,     putI2 ,     NULL,       NULL
# define IO_str getstring,  putstring,  freestring, copystring
# define IO_lxv getlexv,    putlexv,    NULL,       NULL
# define IO_IL  getINTlist, putINTlist, fIL,        cIL
# define IO_SL  getSTRlist, putSTRlist, fSL,        cSL
# define IO_IT  getIT,      putIT,      fIT,        cIT
# define IO_ST  getST,      putST,      fST,        cST
# define IO_IAT getIAT,     putIAT,     fIAT,       cIAT
# define IO_AT  getAT,      putAT,      NULL,       NULL
# define IO_ign NULL,       NULL,       NULL,       NULL

# define OTHERS NULL, others, IO_str

/*

 * clrint.c: integer valued colours
 */

CLR_TYPE	getint ();

void	putint ();

/** integers are not using extra memory to be freed **/

/*

 * clrI2.c: pairs of integers, stored in a pool
 */

int*	newI2 ();

CLR_TYPE	getI2 ();

void	putI2 ();

/** int pairs are stored in a pool of int's,
 ** and cannot be freed
 */

/*

 * clrstr.c: string valued colours
 */

CLR_TYPE	getstring ();

void	putstring ();

void	freestring ();

CLR_TYPE	copystring ();

/*

 * clrids.c: lexical values stored in hash tables
 */

char*	newid ();

CLR_TYPE	getlexv ();

void	putlexv ();

/** strings are shared and cannot be freed **/

/*

 * INTlists.c: lists of integers
 */

/* these are LISP-like data structures */

typedef struct IL {
	int		elt;
	struct IL*	next;
	int		cnt;	/* reference count, for garbage collection */
	}* INTlist;

/* returns value of first element in the list */
/*
 * PUBLIC int
 * INThead (L)
 *     INTlist L;
 */

# define INThead(L) ((L)->elt)

/* returns rest of list, dropping first item */
/*
 * PUBLIC INTlist
 * INTtail (L)
 *     INTlist L;
 */

# define INTtail(L) ((L)->next)

/* adds a new element to the list, at the very beginning */

INTlist	INTcons ();

/* concatenates two lists
 * by means of duplicating the first one,
 * while sharing the second
 */

INTlist	INTappend ();

/* reverses a list
 * by means of duplicating every item
 */

INTlist	INTrev ();

/* compares two lists */

int	INTcmp ();

/* checks for empty list */
/*
 * PUBLIC int
 * INTempty (L)
 *     INTlist L;
 */

# define INTempty(L) ((L) == NULL)

/* returns number of items in the list */

int	INTlength ();

/* returns value of last element in the list */

int	INTlast ();

/* checks if "e" is in "L"
 */

int	INTIsIn ();

/* returns the position of
 * the element "e" in "L"
 * returns 0 (FALSE) if not found
 */

int	INTpos ();

/* returns the "n"th element of "L"
 * fails if list is NULL or if there are not 'n' elements
 */

int	INTnth ();

/* These are functions for loading/dumping lists
 * from/to external representation.

 * putINTlist dumps the same format as putIT
 * it just dumps the items in the table.

 * getINTlist loads the same format as getIT
 */

CLR_TYPE	getINTlist ();

void	putINTlist ();

/* frees a list */

void	fIL ();

/* get a fresh copy */

CLR_TYPE	cIL ();

/* shares an Integer List */

CLR_TYPE	ILshare ();

/*

 * STRlists.c: lists of strings
 */

/* these are LISP-like data structures */

typedef struct SL {
	char*		elt;
	struct SL*	next;
	int		cnt;	/* reference count, for garbage collection */
	}* STRlist;

/* returns value of first element in the list */
/*
 * PUBLIC char*
 * STRhead (L)
 *     STRlist L;
 */

# define STRhead(L) ((L)->elt)

/* returns rest of list, dropping first item */
/*
 * PUBLIC STRlist
 * STRtail (L)
 *     STRlist L;
 */

# define STRtail(L) ((L)->next)

/* adds a new element to the list, at the very beginning
 * shared is boolean valued:
 * TRUE => do not allocate fresh memory for the string
 */

STRlist	STRcons ();

/* concatenates two lists
 * by means of duplicating the first one,
 * while sharing the second.
 * shared affects to the duplication of L1, it is boolean valued:
 * TRUE => do not allocate fresh memory for the string
 */

STRlist	STRappend ();

/* reverses a list
 * by means of duplicating every item
 * shared affects to the duplication of L, it is boolean valued:
 * TRUE => do not allocate fresh memory for the string
 */

STRlist	STRrev ();

/* compares two lists */

int	STRcmp ();

/* checks for empty list */
/*
 * PUBLIC int
 * STRempty (L)
 *     STRlist L;
 */

# define STRempty(L) ((L) == NULL)

/* returns number of items in the list */

int	STRlength ();

/* returns value of last element in the list */

char*	STRlast ();

/* These are functions for loading/dumping lists
 * from/to external representation.

 * putSTRlist dumps the same format as putST
 * it just dumps the items in the table.

 * getSTRlist loads the same format as getST
 */

CLR_TYPE	getSTRlist ();

void	putSTRlist ();

/* frees a list
 * assuming strings are not shared
 * and, therefore, must be freed too
 */

void	fSL ();

/* frees a list
 * assuming that strings are shared
 * and, therefore, must NOT be freed
 */

void	fSLs ();

/* copies a list
 * assuming strings are not shared
 * and, therefore, must be copied too
 */

CLR_TYPE	cSL ();

/* copies a list
 * assuming that strings are shared
 * and, therefore, must NOT be copied
 */

CLR_TYPE	cSLs ();

/* shares an String List */

CLR_TYPE	SLshare ();

/*

 * clrIT.c: tables of integers
 */

/* This set of functions permits the manipulation
 * of variable size tables of integers.
 */

/* size  is the current number of items in the table
 * max   is the maximum number allowed with current allocation
 *       (if more items try to get in, it will expanded,
 *        according to incr)
 * incr  is the expansion criterion:
 *         < 0 => no expansion, size is fixed
 *       0     => expansion by duplication: 4, 8, 16, 32, 64, ...
 *       N > 0 => linear expansion: N, 2N, 3N, 4N, 5N, ...
 * class identifies the allocation criterion:
 *       0: items are hold as they come in
 *       1: items are not duplicated in the table
 *       2: items are sorted in ascending order
 * data  holds the items themselves
 */

typedef struct {
  int size, max, incr;
  short class;
  int* data;
  } IT;

/* creates a new table able to hold <size> items */

IT*	ITcreate ();

/* duplicates a table: fresh memmory is allocated for it */

IT*	ITdup ();

/* adds a new item to an existing table.
 * takes care of non-duplicating or sorting.
 * returns the item index in the table,
 * i.e. tbl->data [ITadd (n, tbl)] = n
 */

int	ITadd ();

/* removes an item.
 * the other items are moved down.
 * warning: previous indexes are no longer correct!
 */

void	ITrm ();

/* locates an item in the table.
 * it returns its index or
 * -1 if it does not exist.
 */

int	ITfind ();

/* takes an existing table
 * and deletes duplicates from it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 */

void	ITnodup ();

/* takes an existing table
 * and sorts it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 */

void	ITsort ();

/* compares two tables, it1 and it2.
 * Return -1 if it1 < it2, 0 if equal, 1 if >.
 * It does not matter the class of the tables.
 */

int	ITcmp ();

/* These are functions for loading/dumping tables
 * from/to external representation.

 * Warning: class and incr are fixed,
 * that means that programs cannot communicate this information
 * [unless the user creates his/her own get/put functions].
 
 * The rational behind this drastic restriction is twofold:
 * 1- to permit exchanging between INTlists and ITs
 * 2- usually an IT is of variable size in one generating tool,
 *    but it is frozen from them on.

 * putIT dumps the same format as putINTlist
 * it just dumps the items in the table.

 * getIT loads the same format as getINTlist
 * it assumes class 0 (as is) and incr -1 (fixed size).
 * size is taken from the number of read items.
 */

CLR_TYPE	getIT ();

void	putIT ();

/* to kill an attribute: memory is freed */

void	fIT ();

/* get a fresh copy */

CLR_TYPE	cIT ();

/*

 * clrST.c: tables of strings
 */

/* This set of functions permits the manipulation
 * of variable size tables of strings.
 */

/* size  is the current number of items in the table
 * max   is the maximum number allowed with current allocation
 *       (if more items try to get in, it will expanded,
 *        according to incr)
 * incr  is the expansion criterion:
 *         < 0 => no expansion, size is fixed
 *       0     => expansion by duplication: 4, 8, 16, 32, 64, ...
 *       N > 0 => linear expansion: N, 2N, 3N, 4N, 5N, ...
 * class identifies the allocation criterion:
 *       0: items are hold as they come in
 *       1: items are not duplicated in the table
 *       2: items are sorted in ascending order (lexicographic)
 * ecase is a boolean flag to denote case sensitivity in comparisions
 *       FALSE => case independent
 *       TRUE  => case sensitive
 * data  holds the items themselves
 */

typedef struct {
  int size, max, incr;
  short class;
  short ecase;
  char** data;
  } ST;

/* case independent version of strcmp () */

int	cstrcmp ();

/* creates a new table able to hold <size> items */

ST*	STcreate ();

/* duplicates a table:
 * fresh memmory is allocated for the table
 * if (share) then strings are shared between old and new table
 *            else new space is allocated, and strings copied into it
 */

ST*	STdup ();

/* adds a new item to an existing table.
 * takes care of non-duplicating or sorting.
 * returns the item index in the table,
 * i.e. tbl->data [STadd (n, tbl)] = n
 * shared is boolean valued:
 * TRUE => do not allocate fresh memory for the string
 */

int	STadd ();

/* removes an item.
 * the other items are moved down.
 * warning: previous indexes are no longer correct!
 * if strings are NOT SHARED, then space is freed
 */

void	STrm ();

/* locates an item in the table.
 * it returns its index or
 * -1 if it does not exist.
 */

int	STfind ();

/* takes an existing table
 * and deletes duplicates from it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 * strings are supposed to be NOT SHARED,
 * and therefore, space is freed
 */

void	STnodup ();

/* takes an existing table
 * and sorts it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 */

void	STsort ();

/* These are functions for loading/dumping tables
 * from/to external representation.

 * Warning: class and incr are fixed,
 * that means that programs cannot communicate this information
 * [unless the user creates his/her own get/put functions].
 
 * The rational behind this drastic restriction is twofold:
 * 1- to permit exchanging between STRlists and STs
 * 2- usually an ST is of variable size in one generating tool,
 *    but it is frozen from them on.

 * getST it assumes class 0 (as is) and incr -1 (fixed size).
 * size is taken from the number of read items.

 * putST dumps the same format as putSTRlist
 * it just dumps the items in the table.

 * getST loads the same format as getSTRlist
 */

CLR_TYPE	getST ();

void	putST ();

/* frees a table
 * assuming strings are not shared
 * and, therefore, must be freed too
 */

void	fST ();

/* frees a table
 * assuming that strings are shared
 * and, therefore, must NOT be freed
 */

void	fSTs ();

/* copies a table
 * assuming strings are not shared
 * and, therefore, must be copied too
 */

CLR_TYPE	cST ();

/* copies a table
 * assuming that strings are shared
 * and, therefore, must NOT be copied
 */

CLR_TYPE	cSTs ();

/*

 * clrIAT.c: tables of integer arrays
 */

/* This set of functions permits the manipulation
 * of variable size tables of integer arrays.
 */

/* size  is the current number of items in the table
 * max   is the maximum number allowed with current allocation
 *       (if more items try to get in, it will expanded,
 *        according to incr)
 * incr  is the expansion criterion:
 *         < 0 => no expansion, size is fixed
 *       0     => expansion by duplication: 4, 8, 16, 32, 64, ...
 *       N > 0 => linear expansion: N, 2N, 3N, 4N, 5N, ...
 * class identifies the allocation criterion:
 *       0: items are hold as they come in
 *       1: items are not duplicated in the table
 *       2: items are sorted in ascending order (lexicographic)
 * nint  logs the total number of integers in the data
 * data  holds the items themselves
 *       WARNING: integer value 0 is used as array terminator,
 *                therefore it cannot be used as a legal value.
 */

typedef struct {
  int size, max, incr, nint;
  short class;
  int** data;
  } IAT;

/* creates a new table able to hold <size> items */

IAT*	IATcreate ();

/* duplicates a table:
 * fresh memmory is allocated for the table
 * if (share) then arrays are shared between old and new table
 *            else new space is allocated, and arrays copied into it
 */

IAT*	IATdup ();

/* adds a new item to an existing table.
 * takes care of non-duplicating or sorting.
 * returns the item index in the table,
 * i.e. tbl->data [IATadd (n, tbl)] = n
 * shared is boolean valued:
 * TRUE => do not allocate fresh memory for the array
 */

int	IATadd ();

/* similar to IATadd,
 * taking the data from an IT.
 * last (terminating) 0 is automatically added.
 * fresh space is allocated, since nothing can be shared!
 */

int	IAT_IT_add ();

/* similar to IAT_IT_add,
 * taking the data from an INTlist.
 * last (terminating) 0 is automatically added.
 * fresh space is allocated, since nothing can be shared!
 */

int	IAT_IL_add ();

/* removes an item.
 * the other items are moved down.
 * warning: previous indexes are no longer correct!
 * if arrays are NOT SHARED, then space is freed
 */

void	IATrm ();

/* locates an item in the table.
 * it returns its index or
 * -1 if it does not exist.
 */

int	IATfind ();

/* takes an existing table
 * and deletes duplicates from it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 * arrays are supposed to be NOT SHARED,
 * and therefore, space is freed
 */

void	IATnodup ();

/* takes an existing table
 * and sorts it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 */

void	IATsort ();

/* These are functions for loading/dumping tables
 * from/to external representation.

 * getIAT it assumes class 0 (as is) and incr -1 (fixed size).
 * size and nint are read taken from the colour.
 */

CLR_TYPE	getIAT ();

void	putIAT ();

/* frees a table
 * assuming arrays are not shared
 * and, therefore, must be freed too
 */

void	fIAT ();

/* frees a table
 * assuming that strings are shared
 * and, therefore, must NOT be freed
 */

void	fIATs ();

/* copies a table
 * assuming arrays are not shared
 * and, therefore, must be copied too
 */

CLR_TYPE	cIAT ();

/* copies a table
 * assuming that arrays are shared
 * and, therefore, must NOT be copied
 */

CLR_TYPE	cIATs ();

/*

 * auxuliary functions
 */

/** hash tables **
 * Suggestion for size: 1. odd number
 *                      2. aprox 3 times the expected size
 */

typedef struct Hentry {
        int             idx;
        struct Hentry*  next;
        } hentry;

typedef hentry** HT;

/*
 * auxIT.c: for IT
 */

/* Provided an IT, is is sorted as by ITsort(tbl)
 * furthermore, a permutation table is generated
 * LET perm= ITsortP (tbl)
 * such that  if   tbl->data[i] = N               on new tbl
 *            then tbl->data[perm->data[i]] = N   on old tbl
 */

IT*	ITsortP ();

/*
 * auxST.c: hash entries for ST
 */

/* Prepares a new table for hash-directed entry on the ST
 * ST must already exist (may be empty).
 * After initializing the HT,
 * STHfind must replace STfind
 * STHadd  must replace STadd
 * NOTE: the original table ST is kept untouched.
 *       ST must be of class 1 (no dup)
 */

HT	STHinit ();

int	STHfind ();

int	STHadd ();

/* Provided an ST, is is sorted as by STsort(tbl)
 * furthermore, a permutation table is generated
 * LET perm= STsortP (tbl)
 * such that  if   tbl->data[i] = S               on new tbl
 *            then tbl->data[perm->data[i]] = S   on old tbl
 */

IT*	STsortP ();

/*
 * auxIAT.c: hash entries for IAT
 */

/* prepares a new table for hash-directed entry on the IAT
 * IAT must already exist (may be empty)
 * after initializing the HT,
 * IATHfind must replace IATfind
 * IATHadd  must replace IATadd
 * NOTE: the original table IAT is kept untouched.
 *       IAT must be of class 1 (no dup)
 */

HT	IATHinit ();

int	IATHfind ();

int	IATHadd ();

/* Provided an IAT, is is sorted as by IATsort(tbl)
 * furthermore, a permutation table is generated
 * LET perm= IATsortP (tbl)
 * such that  if   tbl->data[i] = N               on new tbl
 *            then tbl->data[perm->data[i]] = N   on old tbl
 */

IT*	IATsortP ();

/*

 * clrAT.c: tables of attributes (= colours)
 */

/* This set of functions permits the manipulation
 * of variable size tables of attributes.
 */

/* size  is the current number of items in the table
 * max   is the maximum number allowed with current allocation
 *       (if more items try to get in, it will expanded,
 *        according to incr)
 * incr  is the expansion criterion:
 *         < 0 => no expansion, size is fixed
 *       0     => expansion by duplication: 4, 8, 16, 32, 64, ...
 *       N > 0 => linear expansion: N, 2N, 3N, 4N, 5N, ...
 * data  holds the items themselves
 */

typedef struct {
	struct	Attr*	attrs;
	CLR_TYPE	value0;	/* application dependent */
	CLR_TYPE	value1;	/* application dependent */
	} ATdata;
  
typedef struct {
  int size, max, incr;
  ATdata* data;
  } AT;

/* creates a new table able to hold <size> items */

AT*	ATcreate ();

/*
 * Looks for ONE more slot in the table,
 * incrementing the table max size if necessary
 * (according to incr paremeter at creation).
 * Returns next available index.
 */

int	ATinc ();

/* similar to cp_node () */

int	ATcp ();

/* loads from external file */

CLR_TYPE	getAT ();

/*
 * puts onto external file
 * size, max, and incr are preserved on future loads (via getAT)
 */

void	putAT ();

/* similar to add_attr () */

TATTR*	ATadd ();

/* similar to set_attr () */

void	ATset ();

/* similar to find_attr () */

TATTR*	ATfind ();

/* similar to fadd_attr () */

TATTR*	ATfadd ();

/* similar to take_attr () */

TATTR*	ATtake ();

/*

 * stack operations
 */

/*
 * Initializes the stack.
 * if size == 0 it clears the old one and builds another with previous size
 * if size > 0 builds a new one with the given size.
 * Exceptions: nothing should be wrong
 */

void	stinit ();

/*
 * Insert a new item on the top of the stack.
 * Exceptions: the stack cannot grow large enough to build the item.
 */

void	stpush ();

/*
 * Remove an item from the top of the stack
 * Exceptions: the stack is already empty
 */

void	stpop ();

/*
 * Remove the item of the top of stack and
 * free its memory
 * Exceptions: the stack is already empty
 */

void	stkpop ();

/*
 * Returns the current number of items on the stack.
 * Exceptions: nothing should be wrong.
 */

int	stdepth ();

/*
 * Returns TRUE if there is no items on the stack.
 * Exceptions: nothing should be wrong.
 */

int	stisempty ();

/*
 * Returns TRUE if the stack cannot include more items.
 * Exceptions: nothing should be wrong.
 */

int	stisfull ();

/*
 * Returns the item on the top of the stack without retrieve it.
 * Exceptions: the stack has not any item.
 */

TNODE*	sttop ();

/*
 * Returns the n'th item of the stack.
 * Equal to pop n-1 item, return the top and push all items again.
 * Exceptions: the stack has less then n items.
 */

TNODE*	stpick ();

# define sttype()	(sttop()->type)
# define stgtft()	(sttop()->father)
# define stgtfs()	(sttop()->sons)
# define stgtrb()	(sttop()->brothers)

/*
 * Link a new father to the item on the top of stack
 * Exception: the stack is empty
 */

void	stpft ();

/*
 * Link new sons to the item on the top of stack
 * Exception: the stack is empty
 */

void	stpfs ();

/*
 * Link a new right brother to the item on the top of stack
 * Exception: the stack is empty
 */

void	stprb ();

/*
 * Exchange the items on the top of the stack.
 * Exceptions: there is less than 2 items on the stack
 */

void	stswap ();

/*
 * Builds a new item and push it on the stack
 * Exception: the stack cannot grow
 */

void	stput ();

/*
 * Increase the size of stack in n positions.
 * Exceptions: the stack cannot grow.
 */

void	stincr ();

/*
 * Decrease the size of stack in n positions.
 * Equal to pop n items of the stack.
 * Exceptions: there is less than n items in the stack.
 */

void	stdecr ();

/*
 * Pops the top of the stack and
 * puts it as a right brother of pick(1) item
 * Exceptions: there is less than 2 items on the stack.
 */

void	stlrlink ();

/*
 * Do an stlrlink and as father of r the father of l.
 * Exceptions: there is less than 2 items on the stack.
 */

void	staddrb ();

/*
 * Pops the top of the stack and
 * puts it as a father of pick(1) item.
 * Exceptions: there is less than 2 items on the stack.
 */

void	stsflink ();

/*
 * Adds a new colout to the node on the top of the stack.
 * Exceptions: The stack is empty.
 *             The top value is NULL
 *             There is a colour with the same code.
 */

void	staclr (int clr, CLR_TYPE value);

/*
 * Returns the value of the colour clr of the top of the stack
 * Exceptions: The stack is empty
 *             The top value is NULL
 *             there is not a colour with clr code
 */

CLR_TYPE	stfclr ();

/*
 * Returns TRUE if the top has clr colour
 * Exceptions: The stack is empty
 *             The top value is NULL
 */

int	stchclr ();

/*
 * Sustitute the value of colour clr of the top of stack
 * if colour does not exist, builds a new one.
 * Exceptions: The stack is empty
 *             The top value is NULL
 *             there is not a colour with clr code
 */

void	stsclr ();

/*
 * Prints out all items stored in the stack.
 * Exceptions : nothing should be wrong
 */

void	stdraw ();

/*

 * miscellaneous
 */

/*
 * allocates space for an string,
 * and copies it into the fresh room
 */

char*	str_alloc ();

/*
 * prints and error message,
 * and exits
 */

void	fatal ();


/*

 * clrI2T.c: tables of pairs of integers
 */

/* This set of functions permits the manipulation
 * of tables of pairs of integers.
 */

/* size  is the current number of pairs in the table
 * max   is the maximum number allowed with current allocation
 *       (if more pairs try to get in, it will expanded,
 *        according to incr)
 * incr  is the expansion criterion:
 *         < 0 => no expansion, size is fixed
 *       0     => expansion by duplication: 4, 8, 16, 32, 64, ...
 *       N > 0 => linear expansion: N, 2N, 3N, 4N, 5N, ...
 * class identifies the allocation criterion:
 *       0: pairs are hold as they come in
 *       1: pairs are not duplicated in the table
 * data  holds the pairs themselves
 */

typedef struct {
  int size, max, incr;
  short class;
  int* data;
} I2T;


/* creates a new table able to hold <size> pairs */

I2T*	I2Tcreate ();

/* duplicates a table:
 * fresh memmory is allocated for the table
 */

I2T*	I2Tdup ();

/* adds a new pair to an existing table.
 * takes care of non-duplicating.
 * returns the pair index in the table,
 * i.e. tbl->data [I2Tadd (n, tbl)] = n
 */

int	I2Tadd ();

/* removes a pair.
 * the other pairs are moved down.
 * warning: previous indexes are no longer correct!
 */

void	I2Trm ();

/* locates a pair in the table.
 * it returns its index or
 * -1 if it does not exist.
 */

int	I2Tfind ();

/* takes an existing table
 * and deletes duplicates from it.
 * class is changed accordingly.
 * warning: previous indexes are no longer correct!
 */

void	I2Tnodup ();

/* These are functions for loading/dumping tables
 * from/to external representation.

 * getI2T it assumes class 0 (as is) and incr -1 (fixed size).
 * size and nint are read taken from the colour.
 */

CLR_TYPE	getI2T ();

void	putI2T ();

/* frees a table
 */

void	fI2T ();

/* copies a table
 */

CLR_TYPE	cI2T ();

/***** END of cast.desc *****/
#endif
