/***********************************************************************
*
*               Projet   : DilibPro
*               Module   : StrSearch
*               Fichier  : StrSearch.c
*               Auteur   : J. DUCLOY
*               Date     : Aout 93
*               Modifications
*                        20 Octobre 93 (fonction StrSearchTableFree)
*    $Id: StrSearch.c,v 1.3 2005/06/22 15:35:28 parmentf Exp $
************************************************************************
*
* Copyright (c) 1995 CNRS/CRIN & INRIA Lorraine
* 
************************************************************************/

#include "StrSearch.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
       
void qsort();

char *StrSearchLastKey;

int StrSearchCompare(node1,node2) 
const void *node1;
const void *node2;
{
 return (strcmp(  ((StrSearchDatum*)node1)->key,
		  ((StrSearchDatum*)node2)->key   ));
}

/* 
int StrSearchCompare(n1, n2)
     StrSearchDatum *n1;
     StrSearchDatum *n2;
{
  return strcmp(n1->key, n2->key);
} */

void StrSearchTableReset(StrSearchTable* curTable)
{
  curTable->etat=0;	
  curTable->numberOfElements=0;
  curTable->currentPos=-1;
}

StrSearchTable* StrSearchTableCreate(int number, int incr)
{
  StrSearchTable *newTable;

  newTable = (StrSearchTable *) malloc(sizeof(StrSearchTable));

  newTable->size=number;
  newTable->incr=incr;
  newTable->table=(StrSearchDatum *)malloc(number*sizeof(StrSearchDatum));

  StrSearchTableReset(newTable);

  return(newTable);
}


char *StrSearchNext(StrSearchTable *curTable)
{
  if(curTable->currentPos+2>curTable->numberOfElements)return NULL;
  curTable->currentPos++;
  return curTable->table[curTable->currentPos].key;
}


char *StrSearchPrevious(StrSearchTable *curTable)
{
  if(curTable->currentPos<=0)return NULL;
  curTable->currentPos--;
  return curTable->table[curTable->currentPos].key;
}

void StrSearchTableFree(StrSearchTable *t)
{
  free(t->table);
  free(t);
}

void StrSearchTableFreeStr(StrSearchTable *t)
{
  char *key;
  char *value;
  if(t)
    {
      StrSearchIteratorReset(t);
      while ((key=StrSearchNext(t)))
	{
	  free(key);
	  if((value=StrSearchValue(t)))free(value);
	}
      StrSearchTableFree(t);
    }
}

void StrSearchTableFreeValue(StrSearchTable *t)
{
  char *key;
  char *value;
  if(t)
    {
      StrSearchIteratorReset(t);
      while ((key=StrSearchNext(t)))
	{
	  if((value=StrSearchValue(t)))free(value);
	}
      StrSearchTableFree(t);
    }
}


void StrSearchTableFreeKey(StrSearchTable *t)
{
  char *key;
  if(t)
    {
      StrSearchIteratorReset(t);
      while ((key=StrSearchNext(t)))
	{
	  free(key);
	}
      StrSearchTableFree(t);
    }
}

int StrSearchTableToFile(StrSearchTable *t, char  *f)
{
  FILE *f1;
  char *key;
  char *value;
  if((f1=fopen(f,"w")))
    {
      StrSearchIteratorReset(t);
      while ((key=StrSearchNext(t)))
	{
	  fprintf(f1, "%s", key);
	  if((value=StrSearchValue(t)))fprintf(f1, "\t%s", value);
	  fprintf(f1, "\n");
	}
      fclose(f1);
    }
  else return 0;
  return 1;
}

void StrSearchAdd(StrSearchTable *t,
		  char *s1,
		  char *s2)
{

  if(t->size <= t->numberOfElements)
    {
      t->size+=t->incr;
      t->table=(StrSearchDatum*)
	realloc(t->table,t->size*(sizeof(StrSearchDatum)));
    };
  t->table[t->numberOfElements].key = s1;
  t->table[t->numberOfElements].value = s2;

  switch(t->etat)
    {
    case 0 : 
      t->numberOfElements=1;
      t->greatest=s1;
      t->etat=1;
      break;
    case 1 : 
      t->numberOfElements++;
      if (strcmp(s1,t->greatest)>=0)
	{
	  t->greatest=s1;
	}
      else
	{
	  t->etat=2;
	}
      break;
    case 2 : 
      t->numberOfElements++;
      break;
    case 3 : 
      t->numberOfElements++;
      if (strcmp(s1,t->greatest)>=0)
	{
	  t->greatest=s1;
	  t->etat=1;
	}
      else
	{
	  t->etat=2;
	}
       break;
    };
}

/* verification de l'etat de la table avant une operation et tri
   eventuel */
int StrSearchSortTable(StrSearchTable *t)
{
  switch(t->etat)
    {
    case 0 : 
      return 0;
    case 1 : 
      t->etat=3;
      return 1;
    case 3 :
      return 1;
    case 2 : 
      qsort(t->table, t->numberOfElements,
	    sizeof(StrSearchDatum),StrSearchCompare);
      t->etat=3;
      t->greatest=t->table[t->numberOfElements-1].key;
      return 1;
    };
  return 0;
}

char *StrSearch(StrSearchTable *t, char *s1)
{
  StrSearchDatum *resu;
  StrSearchDatum datum;
  if (!s1)return NULL;
  if (StrSearchSortTable(t))
    {
      datum.key=s1;
      resu=
	(StrSearchDatum *)bsearch
	((char *)&datum,t->table,t->numberOfElements,
	 sizeof(StrSearchDatum),StrSearchCompare);
      if(resu)
	{
	  StrSearchLastKey=resu->key;
	  return resu->value;
	}
      else 
	{
	  StrSearchLastKey=NULL;
	  return NULL;
	}
    }
  else return NULL;
}

void StrSearchPut(StrSearchTable *t,
		  char *s1,
		  char *s2)
{
  StrSearchDatum *resu;
  StrSearchDatum datum;

  if (StrSearchSortTable(t))
    {
      datum.key=s1;
      resu=
	(StrSearchDatum *)bsearch
	((char *)&datum,t->table,t->numberOfElements,
	 sizeof(StrSearchDatum),StrSearchCompare);
      if(resu)
	{
	  resu->value=s2;
	  return;
	}
    }
  StrSearchAdd(t,s1,s2);
  return;
}

void StrSearchIteratorReset(StrSearchTable* curTable)
{
  curTable->currentPos=-1;
  StrSearchSortTable(curTable);
}

void StrSearchIteratorReverseReset(StrSearchTable* curTable)
{
  curTable->currentPos=curTable->numberOfElements;
  StrSearchSortTable(curTable);
}


int StrSearchNumLessEqual(StrSearchDatum *datumTable,
			  char *elem,
			  int beginPos,
			  int endPos)
{
  int cmpVal;
  int mediumPos;

  if (endPos<0)return -1;
  if(beginPos==endPos)
    {
      cmpVal=strcmp(elem,datumTable[endPos].key);
      if(cmpVal>=0)return endPos;
      else return -1;
    }
  if(endPos==(beginPos+1))
    {      
      cmpVal=strcmp(elem,datumTable[beginPos].key);
      if(cmpVal==0)return beginPos;
      if(cmpVal<0)return -1;
      cmpVal=strcmp(elem,datumTable[endPos].key);
      if(cmpVal>=0)return endPos;
      return beginPos;
    }
  mediumPos=(beginPos+endPos)/2;
  cmpVal=strcmp(elem,datumTable[mediumPos].key);
  if(cmpVal==0)return mediumPos;
  if(cmpVal>0)
    return StrSearchNumLessEqual(datumTable, elem, mediumPos, endPos);
  return StrSearchNumLessEqual(datumTable, elem, beginPos, mediumPos-1);
}

char *StrSearchKeyLessEqual(StrSearchTable *curTable, char *s1)
{
  int indice;
  if (StrSearchSortTable(curTable))
    {
      indice=StrSearchNumLessEqual
	(curTable->table, 
	 s1,
	 0, 
	 curTable->numberOfElements-1);
      if (indice<0)return NULL;
      curTable->currentPos=indice;
      return (StrSearchKey(curTable));
    }
  else return NULL;
}
/* external iterator */

StrSearchTableIter *StrSearchTableIterCreate(StrSearchTable *tab)
{
  StrSearchTableIter *iter;
  iter=(StrSearchTableIter *)malloc(sizeof(StrSearchTableIter));
  if(iter)
    {
      iter->ssTab=tab;
      iter->currentPos=tab->currentPos;
    }
  return iter;
}

void StrSearchTableIterFree(StrSearchTableIter *iter)
{
  if(iter)free((char *)iter);
}

char *StrSearchTableIterNext(StrSearchTableIter *curTable)
{
  if(curTable->currentPos+2>curTable->ssTab->numberOfElements)return NULL;
  curTable->currentPos++;
  return curTable->ssTab->table[curTable->currentPos].key;
}

/* external iterator v2 */

int StrSearchIndicReset(StrSearchTable *t1)
{
  StrSearchSortTable(t1);
  return -1;
}

int StrSearchIndicNext(StrSearchTable *t1, int i1)
{
  if(i1+2>t1->numberOfElements)return StrSearchOutOfRange;
  return i1+1;
}