/***********************************************
 (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   EPS General Public License (see file LICENSE)
 ***********************************************
 $Log: clrIAT.c,v $
 * Revision 2.7  1994/10/10  19:20:08  eps
 * portability
 *
 * Revision 2.6  1993/07/21  12:42:42  eps
 * new functions: INTIsIn INTpos INTnth ITcmp IAT_IL_add
 *
 * Revision 2.5  1993/01/12  16:34:44  eps
 * portability issues
 *
 * Revision 2.4  1992/11/17  11:48:02  eps
 * fix definition of *alloc for PC portability
 *
 * Revision 2.3  1992/02/29  13:29:31  eps
 * fix memory allocation
 *
 * Revision 2.2  92/01/14  15:43:18  eps
 * distribution issues
 * 
 * Revision 2.1  90/10/30  08:32:49  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
 * 
 **********************************************/

#ifndef lint
static char rcsid[]= "$Id: clrIAT.c,v 2.7 1994/10/10 19:20:08 eps Exp $";
#endif

/***********************************************************************
	Jose A. Manas
        dpt. Ingenieria Telematica
        E.T.S.I. Telecomunicacion
        Ciudad Universitaria
        E-28040  MADRID
        jmanas@dit.upm.es

        Tables of Integer Arrays
 **********************************************************************/

/* LINTLIBRARY */

# define cast_IMP
# include "cast.hh"

# include <stdio.h>
# include <assert.h>

PRIVATE int
intlen (n)
     int* n;
{
  register int i= 0;

  while (*(n++))
    i++;
  return i;
}

PRIVATE int
intcmp (n1, n2)
     int *n1, *n2;
{
  while (*n1 == *n2) {
    if (*n1 == 0)
      return 0;
    n1++;
    n2++;
  }
  if (*n1 == 0)
    return -1;
  if (*n2 == 0)
    return 1;
  if (*n1 < *n2)
    return -1;
  return 1;
}

PRIVATE int*
int_alloc (n)
     int* n;
{
  int* pool;
  register int i= 0;

  for (pool= n; *pool != 0; pool++)
    i++;

  pool= (int*) calloc (i+1, sizeof (int));
  if (pool == NULL)
    fatal ("int_alloc run out of memory");
  for (; *n != 0; n++)
    *(pool++)= *n;
  *pool= 0;
  return pool;
}

PUBLIC IAT*
IATcreate (size, incr, class)
  int size, incr;
  short class;
{
  IAT* tbl;
  int s;

  tbl= (IAT*) malloc (sizeof (IAT));
  if (tbl == NULL)
    fatal ("IATcreate run out of memory");
  tbl->size= 0;
  if (incr < 0)
    s= size;
  else if (incr == 0)
    for (s= 4; s < size; s*= 2)
      ;
  else
    for (s= incr; s < size; s+= incr)
      ;
  tbl->max= s;
  tbl->incr= incr;
  tbl->class= class;
  tbl->nint= 0;
  tbl->data= (int**) malloc (s * sizeof (int*));
  if (tbl->data == NULL)
    fatal ("IATcreate run out of memory for data");
  return tbl;
}

PUBLIC IAT*
IATdup (tbl, share)
  IAT* tbl;
  int share;
{
  IAT* new;
  int i;

  new= IATcreate (tbl->size, tbl->incr, tbl->class);
  for (i= 0; i < tbl->size; i++)
    if (share)
      new->data[i]= tbl->data[i];
    else
      new->data[i]= int_alloc (tbl->data[i]);
  new->size= tbl->size;
  new->nint= tbl->nint;
  return new;
}

PRIVATE void
expand (tbl)
  IAT* tbl;
{
  int s;
  
  if (tbl->incr < 0) {
    (void) fprintf (stderr, "IAT colour: cannot expand fixed table\n");
    exit (1);
  }
  else if (tbl->incr == 0)
    for (s= 4; s < tbl->max+1; s*= 2)
      ;
  else
    for (s= tbl->incr; s < tbl->max+1; s+= tbl->incr)
      ;
  tbl->data= (int**) realloc (tbl->data, s * sizeof (int*));
  if (tbl->data == NULL)
    fatal ("colour IAT cannot get memory for expansion");
  tbl->max= s;
}

PUBLIC int
IATadd (n, tbl, shared)
  int* n;
  IAT* tbl;
  int shared;
{
  int i, m, j;
  int cmp;
  
  switch (tbl->class) {
  case 1:			/* no dup */
    for (i= 0; i < tbl->size; i++)
      if (intcmp (tbl->data[i], n) == 0)
	return i;
  case 0:			/* as is */
    if (tbl->size+1 > tbl->max)
      expand (tbl);
    tbl->nint+= intlen (n);
    if (shared)
      tbl->data[tbl->size++]= n;
    else
      tbl->data[tbl->size++]= int_alloc (n);
    return tbl->size-1;
  case 2:			/* sorted */
    i= 0;
    j= tbl->size-1;
    while (i <= j) {		       /* invariant:    */
      m= (i+j)/2;                      /* tbl[i-1] < n  */
      cmp= intcmp (tbl->data[m], n);   /* tbl[j+1] > n  */
      if (cmp == 0)
	return m;
      if (cmp > 0)
	j= m-1;
      else
	i= m+1;
    }
    if (tbl->size+1 > tbl->max)
      expand (tbl);
    for (m= tbl->size; m > j; m--)
      tbl->data[m]= tbl->data[m-1];
    tbl->nint+= intlen (n);
    if (shared)
      tbl->data[i]= n;
    else
      tbl->data[i]= int_alloc (n);
    tbl->size++;
    return i;
  default:
    (void) fprintf (stderr, "IAT colour: unkown class (%d)\n", tbl->class);
    exit (1);
  }
  return -2;			/* should never happen! */
}

PUBLIC int
IAT_IT_add (itbl, tbl)
  IT* itbl;
  IAT* tbl;
{
  int i;
  int *n, *np;

  n= np= (int*) calloc (itbl->size+1, sizeof (int));
  if (n == NULL)
    fatal ("IAT_IT_add run out of memory");
  for (i= 0; i < itbl->size; i++)
    *(np++)= itbl->data[i];
  *np= 0;
  return IATadd (n, tbl, TRUE);
}

PUBLIC int
IAT_IL_add (il, tbl)
  INTlist il;
  IAT *tbl;
{
  int *n, *np;

  n= np= (int*) calloc ((unsigned) INTlength (il)+1, sizeof (int));
  if (n == NULL)
    fatal ("IAT_IL_add run out of memory");
  for ( ; il != NULL; il = INTtail (il))
    *(np++)= INThead (il);
  *np= 0;
  return IATadd (n, tbl, TRUE);
}

PUBLIC void
IATrm (i, tbl, shared)
  int i;
  IAT* tbl;
  int shared;
{
  int m;

  if (i < 0 || i >= tbl->size)
    return;
  tbl->size--;
  tbl->nint-= intlen (tbl->data[i]);
/* buggy: needs to fix getIAT
  if (!shared)
    free ((char*)tbl->data[i]);
*/
  for (m= i; m < tbl->size; m++)
    tbl->data[m]= tbl->data[m+1];
}

PUBLIC int
IATfind (n, tbl)
  int* n;
  IAT* tbl;
{
  int i, m, j;
  int cmp;

  switch (tbl->class) {
  case 0:			/* as is */
  case 1:			/* no dup */
    for (i= 0; i < tbl->size; i++)
      if (intcmp (tbl->data[i], n) == 0)
	return i;
    return -1;
  case 2:			/* sorted */
    i= 0;
    j= tbl->size-1;
    while (i <= j) {		       /* invariant:    */
      m= (i+j)/2;                      /* tbl[i-1] < n  */
      cmp= intcmp (tbl->data[m], n);   /* tbl[j+1] > n  */
      if (cmp == 0)
	return m;
      if (cmp > 0)
	j= m-1;
      else
	i= m+1;
    }
    return -1;
  default:
    (void) fprintf (stderr, "IAT colour: unkown class (%d)\n", tbl->class);
    exit (1);
  }
  return -2;			/* should never happen! */
}

PUBLIC void
IATnodup (tbl)
  IAT* tbl;
{
  int i, j;

  for (i= 0; i < tbl->size; i++)
    for (j= i+1; j < tbl->size; j++)
      if (intcmp (tbl->data[i], tbl->data[j]) == 0)
	IATrm (j, tbl, FALSE);
  tbl->class= 1;
}

PUBLIC void
IATsort (tbl)
  IAT* tbl;
{
  int i, j, m;
  int* t;

  for (i= 0; i < tbl->size; i++) {
    m= i;
    for (j= i+1; j < tbl->size; j++)
      if (intcmp (tbl->data[j], tbl->data[m]) < 0)
	m= j;
    if (m != i) {
      t= tbl->data[i];
      tbl->data[i]= tbl->data[m];
      tbl->data[m]= t;
    }
  }
  tbl->class= 2;
}

PUBLIC CLR_TYPE
getIAT (fp)
     FILE* fp;
{
  int size, incr, nint;
  short class;
  IAT* tbl;
  int i;
  int* pool;
  char c;
  int new_entry;

  (void) fscanf (fp, "%d %d", &size, &nint);
  c= getc (fp);

  incr= -1;
  class= 0;			/* as is */
  tbl= IATcreate (size, incr, class);
  tbl->nint= nint;
  pool= (int*) calloc (nint+size, sizeof (int));
  if (pool == NULL)
    fatal ("colour IAT cannot get memory for data");
  new_entry= TRUE;
  for (c= getc (fp); c != '}'; c= getc (fp)) {
    if (c == '\n') {
      *(pool++)= 0;
      new_entry= TRUE;
    }
    else {
      (void) fscanf (fp, "%d", &i);
      if (new_entry) {
	tbl->data[tbl->size++]= pool;
	new_entry= FALSE;
      }
      *(pool++)= i;
    }
  }
  (void) ungetc (c, fp);
  assert (tbl->size == size);
  return (CLR_TYPE) tbl;
}

PUBLIC void
putIAT (fp, val)
     FILE* fp;
     CLR_TYPE val;
{
  IAT* tbl;
  int i;
  int* p;

  tbl= (IAT*) val;
  fprintf (fp, "%d %d\n", tbl->size, tbl->nint);
  if (tbl->size == 0)
    return;
  for (i= 0; i < tbl->size; i++) {
    for (p= tbl->data[i]; *p != 0; p++)
      fprintf (fp, " %d", *p);
    (void) fputc ('\n', fp);
  }
}

PUBLIC void
fIAT (attrp)
     TATTR* attrp;
{
/* buggy: needs to fix getIAT
  IAT* tbl;
  int i;

  tbl= (IAT*)attrp->value;
  for (i= 0; i < tbl->size; i++)
    free ((char*)tbl->data[i]);
  (void) free ((char*)tbl->data);
  (void) free ((char*)tbl);
*/
  attrp->value= NULL;
}

PUBLIC void
fIATs (attrp)
     TATTR* attrp;
{
/* buggy: needs to fix getIAT
  IAT* tbl;

  tbl= (IAT*)attrp->value;
  (void) free ((char*)tbl->data);
  (void) free ((char*)tbl);
*/
  attrp->value= NULL;
}

PUBLIC CLR_TYPE
cIAT (val)
    CLR_TYPE val;
{
  return (CLR_TYPE) IATdup ((IAT*) val, FALSE);
}

PUBLIC CLR_TYPE
cIATs (val)
    CLR_TYPE val;
{
  return (CLR_TYPE) IATdup ((IAT*) val, TRUE);
}
