/***********************************************
 (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   EPS General Public License (see file LICENSE)
 ***********************************************
 $Log: auxIAT.c,v $
 * Revision 2.6  1994/10/10  19:20:13  eps
 * portability
 *
 * Revision 2.5  1993/01/12  16:35:02  eps
 * portability issues
 *
 * Revision 2.4  1992/11/17  11:48:15  eps
 * fix definition of *alloc for PC portability
 *
 * Revision 2.3  1992/01/14  15:43:28  eps
 * distribution issues
 *
 * Revision 2.2  91/04/10  09:57:01  eps
 * private version of intcmp included
 * 
 * Revision 2.1  90/10/30  08:35:38  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: auxIAT.c,v 2.6 1994/10/10 19:20:13 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: Auxiliary functions
 **********************************************************************/

/* LINTLIBRARY */

# define cast_IMP
# include "cast.hh"

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

PRIVATE int
hash (id, size)			/* computes a hash index for an array */
     int* id;
     int size;
{
  int h;

  h= 0;
  while (*id != 0)
    h= 4*h + *(id++);
  h%= size;
  if (h < 0)
    h+= size;
  return h+1;
}

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;
}

PUBLIC HT
IATHinit (tbl, size)
     IAT* tbl;
     int size;
{
  HT htbl;
  int h;
  hentry* n;
  int i;
  
  assert (tbl->class ==1);	/* no dup */
  htbl= (hentry**) calloc (size+1, sizeof (hentry*));
  if (htbl == NULL)
    fatal ("IATHinit run out of memory");
  htbl[0]= (hentry*) size;
  for (i= 1; i <= size; i++)
    htbl[i]= NULL;
  for (i= 0; i < tbl->size; i++) {
    n= (hentry*) malloc (sizeof (hentry));
    if (n == NULL)
      fatal ("IATHinit run out of memory");
    n->idx= i;
    h= hash (tbl->data[i], size);
    n->next= htbl[h];
    htbl[h]= n;
  }
  return htbl;
}

PUBLIC int
IATHfind (id, tbl, htbl)
     int* id;
     IAT* tbl;
     HT htbl;
{
  int h;
  hentry* n;
  
  h= hash (id, (int) htbl[0]);
  for (n= htbl[h]; n != NULL; n= n->next)
    if (intcmp (id, tbl->data[n->idx]) == 0)
      return n->idx;
  return -1;
}

PUBLIC int
IATHadd (id, tbl, htbl, shared)
     int* id;
     IAT* tbl;
     HT htbl;
     int shared;
{
  int h;
  hentry* n;
  int i;
  
  h= hash (id, (int) htbl[0]);
  for (n= htbl[h]; n != NULL; n= n->next)
    if (intcmp (id, tbl->data[n->idx]) == 0)
      return n->idx;
  tbl->class= 0;		/* as is, to avoid search */
  i= IATadd (id, tbl, shared);
  tbl->class= 1;		/* reset to no dup */
  n= (hentry*) malloc (sizeof (hentry));
  if (n == NULL)
    fatal ("IATHinit run out of memory");
  n->idx= i;
  n->next= htbl[h];
  htbl[h]= n;
  return i;
}

PUBLIC IT*
IATsortP (tbl)
  IAT* tbl;
{
  int i, j, m;
  int* t;
  IT* perm;

  perm= ITcreate (tbl->size, -1, 0);
  for (i= 0; i < tbl->size; i++)
    perm->data[i]= i;
  perm->size= tbl->size;

  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;
      j= perm->data[i];
      perm->data[i]= perm->data[m];
      perm->data[m]= j;
    }
  }
  tbl->class= 2;
  return perm;
}
