// -*- c++ -*-

/*
 * Jakelib2 - General purpose C++ library
 * Copyright (C) 2001 Florian Wolff  (florian@donuz.de)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * $Id: Hashtable.jlc,v 1.5 2003/09/27 08:10:29 florian Exp $
 */


#include "jakelib2.h"
#include "jakelib2/util/Hashtable.h"
#include "jakelib2/util/HashEntry.h"
#include "jakelib2/util/HashtableIterator.h"
#include <string.h>

using namespace jakelib::lang;
using namespace jakelib::util;

JAKELIB_IMPLEMENT_CLASS("jakelib.util.Hashtable", Hashtable, Dictionary)


/*****************************************************************************\
 * Hashtable                                                                  |
 *****************************************************************************/
Hashtable::Hashtable(int initialCapacity, float loadFactor)
{
  if (initialCapacity < 0)
    throw new IllegalArgumentException(`"Illegal Capacity: "` .. initialCapacity
				   .. JAKELIB_AT2("jakelib.util.Hashtable.Hashtable"));
  
  if (loadFactor <= 0)
    throw new IllegalArgumentException(`"Illegal Load: <= 0"`
				     .. JAKELIB_AT2("jakelib.util.Hashtable.Hashtable"));
  
  if (initialCapacity==0)
    initialCapacity = 1;
  
  this->loadFactor = loadFactor;
  table = (HashEntry**) GC_MALLOC(sizeof(HashEntry**) * initialCapacity);
  memset(table, 0, sizeof(HashEntry**) * initialCapacity);
  threshold = (int) (initialCapacity * loadFactor);
  capacity = initialCapacity;
  elementCount = 0;
}

Hashtable::~Hashtable()
{
  clear();
  GC_FREE(table);
}


/*****************************************************************************\
 * get                                                                        |
 *****************************************************************************/
Object* Hashtable::get(Object* key)
{
  int hash = key->hashCode();
  int startIndex = (hash & 0x7FFFFFFF) % capacity;
  int index = startIndex ;
  
  HashEntry*  e;
  while((e = table[index ++]) != null) {
    if ((e->hash == hash) && (e->key->equals(key))) {
      return e->value;
    }
    
    if (index >= capacity)
      index = 0;
    if (index == startIndex)
      return null;    
  }
  
  return null;
}

Object* Hashtable::get(char* key)
{
  String keyStr(key);
  return get(&keyStr);
}


/*****************************************************************************\
 * put                                                                        |
 *****************************************************************************/
void Hashtable::put(Object* key, Object* value)
{
  if (key == null)
    throw new NullPointerException(JAKELIB_AT2("jakelib.util.Hashtable.put"));

  int hash = key->hashCode();
  int startIndex = (hash & 0x7FFFFFFF) % capacity;
  int index = startIndex ;
  
  // Creates the new entry.
  HashEntry* newEntry = new HashEntry(hash, key, value);

  // Makes sure the key is not already in the hashtable.
  HashEntry* e;
  while((e = table[index]) != null) {
    if ((e->hash == hash) && (e->key->equals(key))) {
      delete e;
      table[index] = newEntry;
      return;
    }
    
    index = (index + 1) % capacity;      
  }

  if (elementCount >= threshold -1) {
    // Rehash the table if the threshold is exceeded
    rehash();
    index = (hash & 0x7FFFFFFF) % capacity;
  } 
  
  // look for empty space to store new entry
  while((table[index]) != null) {
    index ++;
    if (index >= capacity)
      index = 0;
  }
  
  table[index] = newEntry;
  
  elementCount ++;
  return;
}

void Hashtable::put(char* key, char* value)
{
  put(new String(key), new String(value));
}

void Hashtable::put(char* key, Object* value)
{
  put(new String(key), value);
}


/*****************************************************************************\
 * remove                                                                     |
 *****************************************************************************/
void Hashtable::remove(Object* key)
{
  if (key == null) {
    throw new NullPointerException(JAKELIB_AT2("jakelib.util.Hashtable.remove"));
  }
  
  int hash = key->hashCode();
  int index = (hash & 0x7FFFFFFF) % capacity;
  int prevIndex;
  HashEntry* e;
  
  while((e = table[index]) != null) {
    if ((e->hash == hash) && (e->key->equals(key))) {
      // We have found the item to be deleted:
      delete e;
      elementCount --;
      table[index] = null;
      
      prevIndex = index;
      index = (index + 1) % capacity;
      while((e = table[index]) != null) {
	if ((e->hash & 0x7FFFFFFF) % capacity == index)
	  break;
	
	table[prevIndex] = table[index];
	table[index] = null;

	prevIndex = index;
	index = (index + 1) % capacity;      
      }
      
      break;
    }
    
    index = (index + 1) % capacity;      
  }                                          
}

void Hashtable::remove(char* key)
{
  String keyStr(key);
  remove(&keyStr);
}


/*****************************************************************************\
 * rehash                                                                     |
 *****************************************************************************/
void Hashtable::rehash()
{
  int newCapacity = capacity * 2 + 1;
  HashEntry** newMap = (HashEntry**) GC_MALLOC(sizeof(HashEntry**) * newCapacity);
  memset(newMap, 0, sizeof(HashEntry**) * newCapacity);

  if (newMap == null)
    throw new MemoryException(`"Unable to enlarge table from "`
			  .. capacity .. `" to "` .. newCapacity
			  .. `" elements"`
			  .. JAKELIB_AT2("jakelib.util.Hashtable.rehash"));
  
  threshold = (int) (newCapacity * loadFactor);
  
  HashEntry* old;
  int index;
  
  for (int idx = 0; idx < capacity; idx++) {
    old = table[idx];
    
    if (old != null) {
      index = (old->hash & 0x7FFFFFFF) % newCapacity;
      
      while((newMap[index]) != null) {
	index ++;
	if (index >= newCapacity)
	  index = 0;
      }
      
      // Creates the new entry.
      newMap[index] = old;
    }
  }
  
  GC_FREE(table);
  table = newMap;
  capacity = newCapacity;
}


/*****************************************************************************\
 * isEmpty                                                                    |
 *****************************************************************************/
jboolean Hashtable::isEmpty()
{ 
  return elementCount == 0; 
}


/*****************************************************************************\
 * size                                                                       |
 *****************************************************************************/
int Hashtable::size() 
{ 
  return elementCount; 
}


/*****************************************************************************\
 * clear                                                                      |
 *****************************************************************************/
void Hashtable::clear()
{
  for (int idx = 0; idx < capacity; idx++) {
    delete table[idx];
    table[idx] = null;
  }
  elementCount = 0;
}


/*****************************************************************************\
 * keys                                                                       |
 *****************************************************************************/
HashtableIterator* Hashtable::keys()
{
  return new HashtableIterator(this);
}


/*****************************************************************************\
 * toString                                                                   |
 *****************************************************************************/
String* Hashtable::toString()
{
  StringBuffer buf("{");
  jboolean first = true;

  for (int idx = 0; idx < capacity; idx++) {
    HashEntry* e = table[idx];
    if (e != null) {
      if (!first)
        buf.append(", ");
      first = false;
      buf.append(e->key->toString())->
        append("=")->append(e->value->toString());
    }
  }
  buf.append("}");

  return buf.toString();
}