/*  Last edited: Dec 20 09:33 2008 (rd) */
/* Author: Richard Durbin, started July 2003, copyright Genome Research Limited (2003) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dict.h"

/****************************************/

void* remap (void *old, int oldSize, int newSize)
{
  void* new = calloc (newSize, 1) ;
  memcpy (new, old, oldSize) ;
  free (old) ;
  return new ;
}

/****************************************/

static int hashString (char *cp, int n, int isDiff)
{
  int i ;
  unsigned int j, x = 0 ;
  int rotate = isDiff ? 21 : 13 ;
  int leftover = 8 * sizeof(int) - rotate ;

  while (*cp)
    x = (*cp++) ^ ((x >> leftover) | (x << rotate)) ;

  for (j = x, i = n ; i < sizeof(int) ; i += n)
    j ^= (x >> i) ;
  j &= (1 << n) - 1 ;

  if (isDiff)
    j |= 1 ;

  return j ;
}

/*****************************/

DICT *dictCreate (int size)
{
  DICT *dict = (DICT*) calloc (1, sizeof(DICT)) ;

  for (dict->dim = 10, dict->size = 1024 ; dict->size < size ; ++dict->dim, dict->size *= 2) ;
  dict->table = (int*) calloc (dict->size, sizeof(int)) ;
  dict->names = (char**) calloc (dict->size/2, sizeof(char*)) ;
  return dict ; 
}

/*****************************/

void *dictDestroy (DICT *dict)
{
  int i ;
  for (i = 1 ; i <= dict->max ; ++i) free (dict->names[i]) ;
  free (dict->names) ;
  free (dict->table) ;
  free (dict) ;
}

/*****************************/

static int newPos ;		/* communication between dictFind() and dictAdd() */

int dictFind (DICT *dict, char *s, int *ip)
{
  int i, x, d ;

  if (!dict) { fprintf (stderr, "dictAdd received null dict\n") ; exit (-1) ; }
  if (!s) { fprintf (stderr, "dictAdd received null string\n") ; exit (-1) ; }

  x = hashString (s, dict->dim, 0) ;
  if (!(i = dict->table[x]))
    { newPos = x ; 
      return 0 ; 
    }
  else if (!strcmp (s, dict->names[i]))
    { if (ip) *ip = i-1 ; 
      return 1 ; 
    }
  else
    { d = hashString (s, dict->dim, 1) ;
      while (1)
	{ x = (x + d) & ((1 << dict->dim) - 1) ;
	  if (!(i = dict->table[x]))
	    { newPos = x ; 
	      return 0 ; 
	    }
	  else if (!strcmp (s, dict->names[i]))
	    { if (ip) *ip = i-1 ; 
	      return 1 ; 
	    }
	}
    }
}

/*****************************/

int dictAdd (DICT *dict, char *s, int *ip)
{
  int i, x ;

  if (dictFind (dict, s, ip)) return 0 ;

  i = ++dict->max ;
  dict->table[newPos] = i ;
  dict->names[i] = (char*) malloc (strlen(s) + 1) ;
  strcpy (dict->names[i], s) ;
  if (ip) *ip = i-1 ;

  if (dict->max > 0.3 * dict->size) /* double table size and remap */
    { int *newTable ;
      ++dict->dim ; dict->size *= 2 ;
      dict->names = (char**) remap (dict->names, (dict->max+1)*sizeof(char*), (dict->size/2)*sizeof(char*)) ;
      newTable = (int*) calloc (dict->size, sizeof(int)) ;
      for (i = 1 ; i <= dict->max ; ++i)
	{ s = dict->names[i] ;
	  x = hashString (s, dict->dim, 0) ;
	  if (!newTable[x])
	    newTable[x] = i ;
	  else
	    { int d = hashString (s, dict->dim, 1) ;
	      while (1)
		{ x = (x + d) & ((1 << dict->dim) - 1) ;
		  if (!newTable[x])
		    { newTable[x] = i ; break ; }
		}
	    }
	}
      free (dict->table) ; dict->table = newTable ;
    }

  return 1 ;
}

/*****************************/

char* dictName (DICT *dict, int i)
{ return dict->names[i+1] ; }

/*********** end of file ***********/