GBCKRUYx

1/**
2 * Copyright (c) 2017 Ashley Jason Scopes
3 * 
4 * This software is provided 'as-is', without any express or implied
5 * warranty. In no event will the authors be held liable for any damages
6 * arising from the use of this software.
7 * 
8 * Permission is granted to anyone to use this software for any purpose,
9 * including commercial applications, and to alter it and redistribute it
10 * freely, subject to the following restrictions:
11 * 
12 * 1. The origin of this software must not be misrepresented; you must not
13 *    claim that you wrote the original software. If you use this software
14 *    in a product, an acknowledgment in the product documentation would be
15 *    appreciated but is not required.
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 *    misrepresented as being the original software.
18 * 3. This notice may not be removed or altered from any source distribution.
19 */
20package hashing;
21
22import java.io.IOException;
23import java.io.ObjectInputStream;
24import java.io.ObjectOutputStream;
25import java.io.Serializable;
26import java.util.Iterator;
27
28/**
29 * Abstract class representing a generic HashTable data type.
30 * @author Ashley Jason Scopes
31 * @param <T> datatype to store within the hash table.
32 */
33public abstract class HashTable<T> 
34        implements Serializable {
35  
36  /**
37   * Default getCapacity for a new hash table.
38   */
39  protected static final int DEFAULT_CAPACITY = 11;
40  
41  /**
42   * The default getSize of a new hash table.
43   */
44  protected static final int DEFAULT_SIZE = 0;
45  
46  /**
47   * When to rehash the table for performance.
48   */
49  protected static final double DEFAULT_LOAD_FACTOR = 0.75f;
50  
51  /**
52   * The getCapacity of the hash table.
53   */
54  protected int capacity;
55  
56  /**
57   * Maximum load factor for this data structure before we resize
58   */
59  private double maxLoadFactor;  
60  
61  /**
62   * The getSize of the hash table.
63   */
64  protected int size;
65  
66  /**
67   * Create a new instance of this hash table base abstract class.
68   * 
69   * Use the default getCapacity and default getSize.
70 
71 (Called by other subclasses)
72   */
73  protected HashTable() {
74    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
75  }
76  
77  /**
78   * Init this hash table instance.
79   * @param capacity base getCapacity.
80   * @param loadFactor the load factor to rehash at.
81   * @throws IllegalStateException if a negative getCapacity is given.
82   */
83  protected HashTable(int capacity, double loadFactor)
84  {
85    if(capacity < 0)
86      throw new IllegalStateException("Cannot have a negative capacity");
87    
88    if(loadFactor < 0)
89      throw new IllegalStateException("Cannot have a negative load factor");
90    
91    this.capacity = capacity;
92    maxLoadFactor = loadFactor;
93    size = DEFAULT_SIZE;
94  }
95  
96  /**
97   * Add a given element into the hash table.
98   * @param obj element to add
99   * @return true if we could add it, or false if it already exists, or the
100   * map is full.
101   */
102  public abstract boolean add(T obj);
103  
104  /**
105   * @param obj element to search for
106   * @return true if the hash table contains the given element, or false if it is
107   * not found.
108   */
109  public abstract boolean contains(T obj);
110  
111  /**
112   * @return the getCapacity of the hash table.
113   */
114  public final int getCapacity() { return this.capacity; }
115  
116  /**
117   * @return the load factor for this instance, defined as getSize/getCapacity.
118   */
119  public final double getLoadFactor() {
120    return ((double) size) / capacity;
121  }
122  
123  /**
124   * @return Maximum load factor to accept before rehashing.
125   */
126  public final double getMaxLoadFactor() { return this.maxLoadFactor; }
127  
128  /**
129   * @return number of elements in the hash table.
130   */
131  public final int getSize() { return this.size; }
132  
133  /**
134   * @return an iterator across each object.
135   */
136  public abstract Iterator<T> iterator();
137  
138  /**
139   * Attempt to read a serialised instance of an OpenAddressingHashTable from
140   * file.
141   * @param in the input stream to read from.
142   * @throws IOException if errors occur with hardware IO.
143   * @throws ClassNotFoundException if the class definition is not found.
144   */
145  protected abstract void readObject(ObjectInputStream in)
146          throws IOException, ClassNotFoundException;
147  
148  /**
149   * Remove an element from the hash table.
150   * @param obj element to remove
151   * @return true if we were able to remove the object, or false if it was not
152   * removable.
153   */
154  public abstract boolean remove(T obj);
155  
156  /**
157   * If we are above the load factor, we will grow the structure, otherwise
158   * we will shrink it to the specified load factor given.
159   */
160  public abstract void resize();
161  
162  /**
163   * Attempt to dump the contents of this file to a serialised object on 
164   * secondary storage.
165   * @param out the stream output data to.
166   * @throws IOException if errors occur with hardware IO.
167   */
168  protected abstract void writeObject(ObjectOutputStream out) 
169          throws IOException;
170}