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

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

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