/*
 * โครงสร้างข้อมูล : ฉบับวาจาวา
 * http://www.cp.eng.chula.ac.th/~somchai/books
 */
package dataStructures;

import java.math.BigInteger;

/**
 * คลาสที่สร้างเซตด้วยตารางแฮชแบบตรวจกำลังสอง
 * @author สมชาย ประสิทธิ์จูตระกูล
 */
public class QuadraticProbingHashSet implements Set {
  private static final Object DELETED = new Object();
  private Object[] table;
  private int size, numNonNulls;

  public QuadraticProbingHashSet(int m) {
    table = new Object[nextPrime(m)];
  }
  private int nextPrime(int n) {
    BigInteger bi = new BigInteger(Integer.toString(n));
    return bi.nextProbablePrime().intValue();
  }
  private void rehash() {
    Object[] old = table;
    table = new Object[nextPrime(4*size)];
    size = numNonNulls = 0;
    for(int i = 0; i< old.length; i++)
      if (old[i] != null && old[i] != DELETED) add(old[i]);
  }
  public boolean isEmpty() {
    return size == 0;
  }
  public int size() {
    return size;
  }

  public boolean contains(Object e) {
    return table[indexOf(e)] != null;
  }
  private int indexOf(Object e) {
    int h = h(e);
    for (int j=1; j<table.length; j++) {
      if (table[h] == null) return h;
      if (table[h].equals(e)) return h;
      h = (h + 2*j - 1) % table.length;
    }
    throw new AssertionError("ตารางเต็มได้ไง");
  }
  private int h(Object e) {
    return Math.abs(e.hashCode()) % table.length;
  }
  public void remove(Object e) {
    int i = indexOf(e);
    if (table[i] != null) {
      table[i] = DELETED; --size;
    }
  }
  public void add(Object e) {
    int empty = -1;
    int h = h(e);
    for (int j=1; j<table.length; j++) {
      if (table[h] == DELETED && empty == -1) empty = h;
      if (table[h] == null || table[h].equals(e)) break;
      h = (h + 2*j-1) % table.length;
    }
    if (table[h] == null) {
      if (empty != -1) h = empty;
      table[h] = e;
      ++size; if (empty == -1) ++numNonNulls;
      if (numNonNulls > table.length/2) rehash();
    }
  }
}