/***********************************************
 (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   EPS General Public License (see file LICENSE)
 ***********************************************
 $Log: clrIT.c,v $
 * Revision 2.6  1994/10/10  19:19:59  eps
 * portability
 *
 * Revision 2.5  1993/07/21  12:42:42  eps
 * new functions: INTIsIn INTpos INTnth ITcmp IAT_IL_add
 *
 * Revision 2.4  1993/01/12  16:34:37  eps
 * portability issues
 *
 * Revision 2.3  1992/11/17  11:47:55  eps
 * fix definition of *alloc for PC portability
 *
 * Revision 2.2  1992/01/14  15:43:13  eps
 * distribution issues
 *
 * Revision 2.1  90/10/30  08:32:41  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/06/21  15:26:21  eps
 * calloc (N, s) => malloc (N * s)
 * allocate in incements of 256
 * 
 * Revision 1.5  90/05/10  17:12:39  eps
 * change colour delimiters from !...! into {...}
 * 
 * Revision 1.4  90/03/16  15:59:04  eps
 * get, put, fIT, cIT completely recoded
 * 
 * Revision 1.3  90/02/16  17:55:45  eps
 * miscellaneous cleanup
 * 
 * Revision 1.2  90/01/29  14:52:11  eps
 * fixing license details
 * 
 * Revision 1.1  90/01/25  18:00:40  eps
 * Initial revision
 * 
 **********************************************/

#ifndef lint
static char rcsid[]= "$Id: clrIT.c,v 2.6 1994/10/10 19:19:59 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 integers
 **********************************************************************/

/* LINTLIBRARY */

# define cast_IMP
# include "cast.hh"

# include <stdio.h>
# include <string.h>

PUBLIC IT*
ITcreate (size, incr, class)
  int size, incr;
  short class;
{
  IT* tbl;
  int s;

  tbl= (IT*) malloc (sizeof (IT));
  if (tbl == NULL)
    fatal ("ITcreate: 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->data= (int*) malloc (s * sizeof (int));
  if (tbl->data == NULL)
    fatal ("ITcreate: run out of memory for data");
  return tbl;
}

PUBLIC IT*
ITdup (tbl)
  IT* tbl;
{
  IT* new;
  int i;

  new= ITcreate (tbl->size, tbl->incr, tbl->class);
  for (i= 0; i < tbl->size; i++)
    new->data[i]= tbl->data[i];
  new->size= tbl->size;
  return new;
}

PRIVATE void
expand (tbl)
  IT* tbl;
{
  int s;

  if (tbl->incr < 0) {
    (void) fprintf (stderr, "IT 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 IT cannot get memory for expansion");
  tbl->max= s;
}

PUBLIC int
ITadd (n, tbl)
  int n;
  IT* tbl;
{
  int i, m, j;

  switch (tbl->class) {
  case 1:			/* no dup */
    for (i= 0; i < tbl->size; i++)
      if (tbl->data[i] == n)
	return i;
  case 0:			/* as is */
    if (tbl->size+1 > tbl->max)
      expand (tbl);
    tbl->data[tbl->size++]= 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  */
      if (tbl->data[m] == n)    /* tbl[j+1] > n  */
	return m;
      if (tbl->data[m] > n)
	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->data[i]= n;
    tbl->size++;
    return i;
  default:
     (void) fprintf (stderr, "IT colour: unkown class (%d)\n", tbl->class);
    exit (1);
  }
  return -2;			/* should never happen! */
}

PUBLIC void
ITrm (i, tbl)
  int i;
  IT* tbl;
{
  int m;

  if (i < 0 || i >= tbl->size)
    return;
  tbl->size--;
  for (m= i; m < tbl->size; m++)
    tbl->data[m]= tbl->data[m+1];
}

PUBLIC int
ITfind (n, tbl)
  int n;
  IT* tbl;
{
  int i, m, j;

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

PUBLIC void
ITnodup (tbl)
  IT* tbl;
{
  int i, j;

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

PUBLIC void
ITsort (tbl)
  IT* 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 (tbl->data[j] < tbl->data[m])
	m= j;
    if (m != i) {
      t= tbl->data[i];
      tbl->data[i]= tbl->data[m];
      tbl->data[m]= t;
    }
  }
  tbl->class= 2;
}

PUBLIC int
ITcmp (it1, it2)
  IT *it1, *it2;
{
  int *n1, *n2;

  if (it1 == it2)
    return 0;
  if (it1 == NULL)
    return -1;
  if (it2 == NULL)
    return 1;
  if (it1->size < it2->size)
    return -1;
  if (it1->size > it2->size)
    return 1;
  n1 = it1->data;
  n2 = it2->data;
  while (*n1 == *n2) {
    if (*n1 == '\0')
      return 0;
    n1++;
    n2++;
  }
  if (*n1 < *n2)
    return -1;
  return 1;
}

PUBLIC CLR_TYPE
getIT (fp)
    FILE* fp;
{
  int size, incr;
  short class;
  IT* tbl;
  int i, c;

  size= 4;			/* anyone would fit! */
  incr= 4;
  class= 0;			/* as is */

  tbl= ITcreate (size, incr, class);
  for (c= getc (fp); c != '}'; c= getc (fp)) {
    while (c == ',' || c == '\n' || c == ' ')
      c= getc (fp);
    (void) ungetc (c, fp);
    if (c != '}') {
      (void) fscanf (fp, "%d", &i);
      (void) ITadd (i, tbl);
    }
  }
  (void) ungetc (c, fp);
  tbl->incr= -1;		/* freeze it! */
  return (CLR_TYPE) tbl;
}

PUBLIC void
putIT (fp, val)
    FILE* fp;
    CLR_TYPE val;
{
  IT* tbl;
  int i;

  tbl= (IT*) val;
  if (tbl->size == 0)
    return;
  for (i= 0; i < tbl->size-1; i++) {
    if ((i+1)%16 == 0)
      (void) fprintf (fp, "%d,\n", tbl->data[i]);
    else
      (void) fprintf (fp, "%d,", tbl->data[i]);
  }
  (void) fprintf (fp, "%d", tbl->data[tbl->size-1]);
}

PUBLIC void
fIT (val)
    CLR_TYPE val;
{
  IT* tbl;

  tbl= (IT*) val;
  (void) free ((char*)tbl->data);
  (void) free ((char*)tbl);
}

PUBLIC CLR_TYPE
cIT (val)
    CLR_TYPE val;
{
  return (CLR_TYPE) ITdup ((IT*) val);
}
