package dataStructures;

import java.util.*;

/**
 * <p>Titulo: O tipo dos registos a guardar na Tabela</p>
 * @version 1.0
 */

class HashRegister implements Cloneable {
  public Object item;
  public Object key;

  public HashRegister(Object o, Object k) {
    item = o;
    key = k;
  }

  public String toString() {
    return "(" + key + ":" + item + ")";
  }

  public Object clone() {
    return new HashRegister(item,key);
  }
} // endClass HashRegister
///////////////////////////////////////////////////////

/**
 * <p>Titulo: Uma implementaçao vectorial da Tabela</p>
 * <p>Descrição: Esta implementaçao usa funções de Dispersão para acesso
 *               extremamente rápido ao seu conteúdo -> Hash Table</p>
 *
 * @author João Neto
 * @version 1.0
 */

public class HashTable implements Table,Cloneable {

  private final int DELTA = 1001;

  protected final double LOAD_FACTOR = 0.75;
  protected static final HashRegister availableCell = new HashRegister(null,null);

  private int nElems;         // Quantos elementos existem na tabela
  private HashRegister[] table;   // O vector que guarda a tabela
  private HashFunction h;     // A função de dispersão

  public HashTable( HashFunction h ) {
    this.h = h;
    table  = new HashRegister[DELTA];
    nElems = 0;
  }

  public Table empty() {
    return new HashTable(h);
  }

  public boolean isEmpty() {
    return nElems == 0;
  }

  private boolean isCellAvailable(int n) {
    return table[n] == availableCell;
  }

  private boolean isCellFree(int n) {
    return table[n] == null;
  }

 /**
  * Devolve a posiçao da chave (se existir)
  * @param key A chava a procurar
  * @return A posição de uma dada chave, ou -1 se nao existir
  */

  private int searchPos(Object key) {
    int pos    = h.hashValue(key) % table.length;
    int back   = pos;

    do {
      if (isCellFree(pos))
        return -1;
      if (isCellAvailable(pos))
        pos = h.nextValue() % table.length;
      else if (key.equals(table[pos].key))
             return pos;
           else
             pos = h.nextValue() % table.length;
    } while (back!=pos);

    return -1;
  }

  public boolean contains(Object key) {
    return searchPos(key) >= 0;
  }

  public Object retrieve(Object key) {
    return table[searchPos(key)].item;
  }

  public void remove(Object key) {
    int n = searchPos(key);

    if (n!=-1) {
      table[n] = availableCell;
      nElems--;
    }
  }

  public void insert(Object item, Object key) {
    if ((double)nElems/table.length > LOAD_FACTOR)
      grow();

    int pos = h.hashValue(key) % table.length;

    while(!isCellFree(pos) && !isCellAvailable(pos))
      pos = h.nextValue() % table.length;

    table[pos] = new HashRegister(item,key);
    nElems++;
  }

  ///////////////////////////////////////////////////////

  //@requires n>1;
  private boolean isPrime(int n) {
    if (n%2 == 0)
      return n==2;

    int limit = (int)Math.round(Math.sqrt(n));
    for(int i=3;i<=limit;i+=2)
      if (n%i == 0)
        return false;

    return true;
  }

  private int getNextPrime(int n) {
    while (!isPrime(n))
      n++;
    return n;
  }

  private void grow() {
    HashRegister[] oldTable = table;

    int newSize = getNextPrime(table.length + DELTA);
    table       = new HashRegister[newSize];
    nElems      = 0;

    for(int i=0;i<oldTable.length;i++)
      if (oldTable[i] != availableCell && oldTable[i] != null)
        insert(oldTable[i].item, oldTable[i].key);
  }

  ///////////////////////////////////////////////////////

  /**
   * Traduz o conteudo todo da tabela numa string
   * @return a string que descreve a tabela, eg, [| (), 5, ->, 2, (), () |]
   */
   public String verbose() {
     String s="[| ";

     for(int i=0;i<table.length;i++)
       if (isCellFree(i))
          s += "(),";
       else
         s += isCellAvailable(i) ? "->," : table[i].item+",";

     return s.substring(0,s.length()-1) + " |]";
   }

  /**
   * Traduz a tabela numa string
   * @return a string que descreve a tabela, eg, [| (key1:item1), (key2:item2) |]
   */
   public String toString() {
     String s="[| ";

     for(int i=0;i<table.length;i++)
       if (!isCellFree(i) && !isCellAvailable(i))
         s += table[i]+",";

     return s.substring(0,s.length()-1) + " |]";
   }

  public boolean equals(Table t) {
    Iterator it = t.iterator();
    while (it.hasNext())
      if (!contains(((HashRegister)it.next()).key))
        return false;

    it = iterator();
    while (it.hasNext())
      if (!t.contains(((HashRegister)it.next()).key))
        return false;

    return true;
  }

  public Object clone() {
    HashTable cp = new HashTable(h);
    cp.table     = new HashRegister[table.length];
    cp.nElems    = nElems;
    cp.h         = h;

    for(int i=0;i<table.length;i++) {
      if (isCellFree(i))
        continue;
      if (isCellAvailable(i))
        cp.table[i] = availableCell;
      else
        cp.table[i] = (HashRegister)(table[i].clone());
    }
    return cp;
  }

  public Iterator iterator() {
     return new TableIterator();
  }

  //********************************************************************
  //** Iterator

  private class TableIterator implements Iterator {

    private int nextElem;

    private TableIterator() {
      nextElem = isEmpty() ? -1 : 0;
    }

    public Object next() {
      if (nextElem >= 0)
        for (int i=nextElem; i<table.length; i++)
          if (!isCellAvailable(i) && !isCellFree(i)) {
            nextElem = i+1;
            return table[i];
          }
      nextElem = -1;
      return null;
    }

    public boolean hasNext() {
      if (nextElem != -1)
        for (int i=nextElem; i<table.length; i++)
          if (!isCellAvailable(i) && !isCellFree(i))
            return true;
      return false;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }

  } // endLocalClass TableIterator

  //*************************************************************
  public static void main(String[] args) {

    HashTable  ht = new HashTable(new HashString());

    ht.insert("elefante","03e");
    ht.insert("tigre","12t");
    ht.insert("zebra","03z");
    ht.insert("pantera","54p");
    ht.remove("12t");
    ht.insert("foca","02f");
    HashTable cp = (HashTable)(ht.clone());
    System.out.println(ht.equals(cp));
    ht.insert("tigre2","13t");
    System.out.println(ht);
    System.out.println("13t -> " + ht.retrieve("13t"));
    System.out.println(cp);
    System.out.println(cp.equals(ht));

  }
} // endClass HashTable

//***** Exemplo de Funçao de Dispersão

class HashString implements HashFunction {

  private int actualValue;

  public HashString() {
    actualValue = 0;
  }

  public int hashValue(Object key) {
    actualValue=0;

    for(int i=0;i<((String)key).length();i++)
      actualValue += (int)((String)key).charAt(i);

    return actualValue;
  }

  public boolean isHashable(Object key) {
    return key instanceof String;
  }

  public int nextValue() {
    actualValue += 4;
    return actualValue;
  }
}