package conc;

import java.util.Arrays;
import java.util.Random;


public class LockFreeSet {
  private final Object[][] array;
  
  private static final Object[] EMPTY_ARRAY = new Object[0];
  
  public LockFreeSet(int concurrencyLevel) {
    array = new Object[concurrencyLevel][];
    Arrays.fill(array, EMPTY_ARRAY);
  }
  
  public boolean add(Object o) {
    int index = (o.hashCode() & 0x7FFFFFFF) % array.length;
    Object[] collisionArray = array[index];
    int length = collisionArray.length;
    for(int i=0; i<length; i++) {
      if (collisionArray[i].equals(o)) {
        return false;
      }
    }
    Object[] newArray = Arrays.copyOf(collisionArray, length + 1);
    newArray[length] = o;
    array[index] = newArray;
    return true;
  }
  
  public boolean contains(Object o) {
    int index = (o.hashCode() & 0x7FFFFFFF) % array.length;
    Object[] collisionArray = array[index];
    int length = collisionArray.length;
    for(int i=0; i<length; i++) {
      if (collisionArray[i].equals(o)) {
        return true;
      }
    }
    return false;
  }
  
  public static void main(String[] args) {
    final LockFreeSet set = new LockFreeSet(16);
    for(int i=0; i<2; i++) {
      new Thread(new Runnable() {
        @Override
        public void run() {
          Random random = new Random();
          for(;;) {
            Integer value = random.nextInt(10000);
            set.add(value);
            if (!set.contains(value)) {
              System.out.println("error !");
            }
          }
        }
      }).start();
    }
  }
}