SimpleHashSet.java

/**
 * A superclass for implementations of hash-sets implementing the SimpleSet interface.
 * @author avishavtal
 */
public abstract class SimpleHashSet implements SimpleSet {
 /**
 * Describes the higer load factor of a newly created hash set
 */
 protected static final float DEFAULT_HIGHER_CAPACITY = 0.75f;
 /**
 * Describes the lower load factor of a newly created hash set
 */
 protected static final float DEFAULT_LOWER_CAPACITY = 0.25f;
 /**
 * Describes the capacity of a newly created hash set
 */
 protected static final int INITIAL_CAPACITY = 16;
 /*upper load factor of this set.*/
 private float upperLoadFactor;
 /*lower load factor of this set.*/
 private float lowerLoadFactor;

 // counter of the elements in the set.
 private int size;


 /**
 * Constructs a new hash set with the default capacities given in DEFAULT_LOWER_CAPACITY
 * and DEFAULT_HIGHER_CAPACITY
 */
 protected SimpleHashSet(){

 upperLoadFactor = DEFAULT_HIGHER_CAPACITY;
 lowerLoadFactor = DEFAULT_LOWER_CAPACITY;

 }

 /**
 * Constructs a new hash set with capacity INITIAL_CAPACITY
 * @param upperLoadFactor the upper load factor before rehashing
 * @param lowerLoadFactor the lower load factor before rehashing
 */
 protected SimpleHashSet(float upperLoadFactor, float lowerLoadFactor){
 this.upperLoadFactor = upperLoadFactor;
 this.lowerLoadFactor = lowerLoadFactor;

 }

 /**
 * Clamps hashing indices to fit within the current table capacity
 * (see the exercise description for details)
 * @param index the index before clamping
 * @return an index properly clamped
 */
 protected int clamp(int index){
 return clampHelper(index, null);

 }
 /* find the index of the string if given, else return the location to put ut there. */
 private int clampHelper(int index, String searchVal){
 int i = 0;
 int newIndex;
 while (i < capacity()){
 newIndex = (index+(i+i*i)/2)&(capacity()-1);
 if (searchVal != null) {

 if (isThere(newIndex, searchVal)) {
 return newIndex;
 } else if (isFreeCell(newIndex)&&!isDelete(newIndex)){
 return -1;
 }


 } else if (isFreeCell(newIndex)){
 return newIndex;
 }
 i++;
 }
 return -1;
 }

 /**
 * check if was value in the cell with the given index.
 *
 * @param newIndex the index of the cell we want to check.
 * @return true iff was value in the cell with the given index and we care about it.
 */
 protected boolean isDelete(int newIndex) {
 return false;
 }

 /**
 * check if the given value in the cell with the given index.
 * @param newIndex the index we want to check.
 * @param searchVal the value we want to check.
 * @return true if the given value in the cell with the given index, false otherwise.
 */
 protected abstract boolean isThere(int newIndex, String searchVal);

 /**
 * @return The lower load factor of the table.
 */
 protected float getLowerLoadFactor(){
 return lowerLoadFactor;
 }

 /**
 * @return The higher load factor of the table.
 */
 protected float getUpperLoadFactor(){
 return upperLoadFactor;
 }

 /**
 * @return The current capacity (number of cells) of the table.
 */
 public abstract int capacity();

 /**
 * check if the cell with the given index can get more value.
 * @param index the index of the cell we check.
 * @return true if the cell with the given index can get more value, false otherwise.
 */
 protected abstract boolean isFreeCell(int index);


 /**
 * Look for a specified value in the set.
 * @param newValue New value to add to the set
 * @return False iff newValue already exists in the set
 */
 @Override
 public boolean add(String newValue) {
 if (contains(newValue)){
 return false;
 }
 if ((float)(size+1)/capacity() > upperLoadFactor){
 reHash(false);
 }
 int index = clamp(newValue.hashCode());
 insert(newValue, index);
 size++;
 return true;
 }

 /**
 * @param searchVal Value to search for.
 * @return true if searchVal in the set, false otherwise.
 */
 @Override
 public boolean contains(String searchVal) {
 int index = searchVal.hashCode();
 int newIndex = clampHelper(index, searchVal);
 return newIndex >= 0;
 }


 /**
 * insert the given value to the set.
 * @param newValue New value to add to the set.
 * @param index the index of the new value in the table.
 */
 protected abstract void insert(String newValue, int index);


 /**
 * Remove the input element from the set.
 * @param toDelete Value to delete.
 * @return True iff toDelete is found and deleted.
 */
 @Override
 public boolean delete(String toDelete) {
 int index = toDelete.hashCode();
 int newIndex = clampHelper(index,toDelete);
 if (newIndex < 0){
 return false;
 }
 remove(toDelete, newIndex);
 size--;
 if (((float)size/capacity()) < lowerLoadFactor){
 reHash(true);
 }
 return true;

 }


 /**
 * remove the given string from the table.
 * @param toDelete value to delete.
 * @param newIndex the index of toDelete in the table.
 */
 protected abstract void remove(String toDelete, int newIndex);

 /**
 * @return The number of elements currently in the set
 */
 @Override
 public int size() {
 return size;
 }

 /**
 * rehash the set.
 * @param toSmaller true if need smaller table, false otherwise.
 */
 protected abstract void reHash(boolean toSmaller);

 /**
 * add to the set all the strings in the given array.
 * @param data array of strings to add.
 */
 protected void addAll(String[] data){
 for (String string: data){
 add(string);
 }
 }
}