/***********************************************
 (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   EPS General Public License (see file LICENSE)
 ***********************************************
 $Log: auxST.c,v $
 * Revision 2.5  1993/01/12  16:34:57  eps
 * portability issues
 *
 * Revision 2.4  1992/11/17  11:48:12  eps
 * fix definition of *alloc for PC portability
 *
 * Revision 2.3  1992/01/14  15:43:26  eps
 * distribution issues
 *
 * Revision 2.2  92/01/14  15:26:38  eps
 * speed up case independent hashing
 * 
 * Revision 2.1  90/10/30  08:35:19  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: auxST.c,v 2.5 1993/01/12 16:34:57 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 Strings: Auxiliary functions
 **********************************************************************/

/* LINTLIBRARY */

# define cast_IMP
# include "cast.hh"

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

PRIVATE int
hash (id, size)			/* computes a hash index for an id */
     char *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
chash (id, size)		/* idem, case independent */
     char *id;
     int size;
{
  int h;

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

PUBLIC HT
STHinit (tbl, size)
     ST* 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 ("STHinit 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 ("STHinit run out of memory");
    n->idx= i;
    if (tbl->ecase)
      h= hash (tbl->data[i], size);
    else
      h= chash (tbl->data[i], size);
    n->next= htbl[h];
    htbl[h]= n;
  }
  return htbl;
}

PUBLIC int
STHfind (id, tbl, htbl)
     char* id;
     ST* tbl;
     HT htbl;
{
  int h;
  hentry* n;
  
  if (tbl->ecase)
    h= hash (id, (int) htbl[0]);
  else
    h= chash (id, (int) htbl[0]);
  for (n= htbl[h]; n != NULL; n= n->next) {
    if (tbl->ecase) {
      if (strcmp (id, tbl->data[n->idx]) == 0)
	return n->idx;
    }
    else {
      if (cstrcmp (id, tbl->data[n->idx]) == 0)
	return n->idx;
    }
  }
  return -1;
}

PUBLIC int
STHadd (id, tbl, htbl, shared)
     char* id;
     ST* tbl;
     HT htbl;
     int shared;
{
  int h;
  hentry* n;
  int i;
  
  if (tbl->ecase)
    h= hash (id, (int) htbl[0]);
  else
    h= chash (id, (int) htbl[0]);
  for (n= htbl[h]; n != NULL; n= n->next) {
    if (tbl->ecase) {
      if (strcmp (id, tbl->data[n->idx]) == 0)
	return n->idx;
    }
    else {
      if (cstrcmp (id, tbl->data[n->idx]) == 0)
	return n->idx;
    }
  }
  tbl->class= 0;		/* as is, to avoid search */
  i= STadd (id, tbl, shared);
  tbl->class= 1;		/* reset to no dup */
  n= (hentry*) malloc (sizeof (hentry));
  if (n == NULL)
    fatal ("STHinit run out of memory");
  n->idx= i;
  n->next= htbl[h];
  htbl[h]= n;
  return i;
}

PUBLIC IT*
STsortP (tbl)
  ST* tbl;
{
  int i, j, m;
  char* 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 (tbl->ecase) {
	if (strcmp (tbl->data[j], tbl->data[m]) < 0)
	  m= j;
      }
      else {
	if (cstrcmp (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;
}
