001: // LookupTable.java
002: // $Id: LookupTable.java,v 1.3 2000/08/16 21:37:58 ylafon Exp $
003: // (c) COPYRIGHT MIT, INRIA and Keio, 1999.
004: // Please first read the full copyright statement in file COPYRIGHT.html
005: package org.w3c.util;
006:
007: import java.io.Serializable;
008:
009: import java.util.Enumeration;
010:
011: /**
012: * A kind of hashtable (maps keys to values), useful for a limited number
013: * of elements.
014: * @version $Revision: 1.3 $
015: * @author Benoît Mahé (bmahe@w3.org)
016: */
017: public class LookupTable implements Cloneable, Serializable {
018:
019: /**
020: * The default capacity.
021: */
022: public static final int DEFAULT_CAPACITY = 10;
023:
024: private Object elements[] = null;
025:
026: private Object keys[] = null;
027:
028: private int count = 0;
029:
030: private int capacity = 0;
031:
032: /**
033: * Returns the number of keys in this lookuptable.
034: *
035: * @return the number of keys in this lookuptable.
036: */
037: public int size() {
038: return count;
039: }
040:
041: /**
042: * Tests if this lookuptable maps no keys to values.
043: * @return <code>true</code> if this lookuptable maps no keys to values;
044: * <code>false</code> otherwise.
045: */
046: public boolean isEmpty() {
047: return count == 0;
048: }
049:
050: /**
051: * Returns an enumeration of the keys in this lookuptable.
052: *
053: * @return an enumeration of the keys in this lookuptable.
054: * @see java.util.Enumeration
055: * @see #elements()
056: */
057: public synchronized Enumeration keys() {
058: return new ArrayEnumeration(keys, count);
059: }
060:
061: /**
062: * Returns an enumeration of the values in this lookuptable.
063: * Use the Enumeration methods on the returned object to fetch the elements
064: * sequentially.
065: *
066: * @return an enumeration of the values in this lookuptable.
067: * @see java.util.Enumeration
068: * @see #keys()
069: */
070: public synchronized Enumeration elements() {
071: return new ArrayEnumeration(elements, count);
072: }
073:
074: /**
075: * Tests if some key maps into the specified value in this lookuptable.
076: * @param value a value to search for.
077: * @return <code>true</code> if and only if some key maps to the
078: * <code>value</code> argument in this lookuptable as
079: * determined by the <tt>equals</tt> method;
080: * <code>false</code> otherwise.
081: * @exception NullPointerException if the value is <code>null</code>.
082: * @see #containsKey(Object)
083: */
084: public synchronized boolean contains(Object value) {
085: return (contains(elements, count, value) != -1);
086: }
087:
088: /**
089: * Tests if the specified object is a key in this lookuptable.
090: * @param key possible key.
091: * @return <code>true</code> if and only if the specified object
092: * is a key in this lookuptable, as determined by the
093: * <tt>equals</tt> method; <code>false</code> otherwise.
094: * @see #contains(Object)
095: */
096: public synchronized boolean containsKey(Object key) {
097: return (contains(keys, count, key) != -1);
098: }
099:
100: private int contains(Object array[], int size, Object value) {
101: if (value == null) {
102: throw new NullPointerException();
103: }
104: for (int i = 0; i < size; i++) {
105: if (array[i].equals(value))
106: return i;
107: }
108: return -1;
109: }
110:
111: /**
112: * Returns the value to which the specified key is mapped in this
113: * lookuptable.
114: * @param key a key in the lookuptable.
115: * @return the value to which the key is mapped in this lookuptable;
116: * <code>null</code> if the key is not mapped to any value in
117: * this lookuptable.
118: * @see #put(Object, Object)
119: */
120: public synchronized Object get(Object key) {
121: int idx = contains(keys, count, key);
122: if (idx != -1)
123: return elements[idx];
124: return null;
125: }
126:
127: /**
128: * Maps the specified <code>key</code> to the specified
129: * <code>value</code> in this lookuptable. Neither the key nor the
130: * value can be <code>null</code>. <p>
131: *
132: * The value can be retrieved by calling the <code>get</code> method
133: * with a key that is equal to the original key.
134: *
135: * @param key the lookuptable key.
136: * @param value the value.
137: * @return the previous value of the specified key in this lookuptable,
138: * or <code>null</code> if it did not have one.
139: * @exception NullPointerException if the key or value is
140: * <code>null</code>.
141: * @see Object#equals(Object)
142: * @see #get(Object)
143: */
144: public synchronized Object put(Object key, Object value) {
145: if (value == null) {
146: throw new NullPointerException();
147: }
148: int idx = contains(keys, count, key);
149: if (idx == -1) {
150: if (count >= capacity) {
151: grow();
152: }
153: keys[count] = key;
154: elements[count] = value;
155: count++;
156: return null;
157: } else {
158: Object previousValue = elements[idx];
159: elements[idx] = value;
160: return previousValue;
161: }
162: }
163:
164: /**
165: * Increases the capacity. This method is called automatically when the
166: * number of keys in the lookuptable exceeds this lookuptable's capacity.
167: */
168: protected void grow() {
169: int newCapacity = capacity * 2 + 1;
170: Object newElements[] = new Object[newCapacity];
171: Object newKeys[] = new Object[newCapacity];
172: System.arraycopy(elements, 0, newElements, 0, count);
173: System.arraycopy(keys, 0, newKeys, 0, count);
174: this .keys = newKeys;
175: this .elements = newElements;
176: this .capacity = newCapacity;
177: }
178:
179: /**
180: * Removes the key (and its corresponding value) from this
181: * lookuptable. This method does nothing if the key is not in the
182: * lookuptable.
183: *
184: * @param key the key that needs to be removed.
185: * @return the value to which the key had been mapped in this lookuptable,
186: * or <code>null</code> if the key did not have a mapping.
187: */
188: public synchronized Object remove(Object key) {
189: int idx = contains(keys, count, key);
190: if (idx != -1) {
191: //remove this one by moving the last one here.
192: Object oldvalue = elements[idx];
193: count--;
194: keys[idx] = keys[count];
195: elements[idx] = elements[count];
196: keys[count] = null;
197: elements[count] = null;
198: return oldvalue;
199: }
200: return null;
201: }
202:
203: /**
204: * Clears this lookuptable so that it contains no keys.
205: */
206: public synchronized void clear() {
207: this .count = 0;
208: this .keys = new Object[capacity];
209: this .elements = new Object[capacity];
210: }
211:
212: /**
213: * Creates a shallow copy of this lookuptable. All the structure of the
214: * lookuptable itself is copied, but the keys and values are not cloned.
215: * This is a relatively expensive operation.
216: *
217: * @return a clone of the lookuptable.
218: */
219: public synchronized Object clone() {
220: try {
221: LookupTable l = (LookupTable) super .clone();
222: l.keys = new Object[capacity];
223: System.arraycopy(keys, 0, l.keys, 0, count);
224: l.elements = new Object[capacity];
225: System.arraycopy(elements, 0, l.elements, 0, count);
226: l.capacity = capacity;
227: l.count = count;
228: return l;
229: } catch (CloneNotSupportedException e) {
230: // this shouldn't happen, since we are Cloneable
231: throw new InternalError();
232: }
233: }
234:
235: /**
236: * Returns a string representation of this <tt>Lookuptable</tt> object
237: * in the form of a set of entries, enclosed in braces and separated
238: * by the ASCII characters "<tt>, </tt>" (comma and space). Each
239: * entry is rendered as the key, an equals sign <tt>=</tt>, and the
240: * associated element, where the <tt>toString</tt> method is used to
241: * convert the key and element to strings. <p>Overrides to
242: * <tt>toString</tt> method of <tt>Object</tt>.
243: *
244: * @return a string representation of this lookuptable.
245: */
246: public synchronized String toString() {
247: StringBuffer buffer = new StringBuffer();
248: for (int i = 0; i < count; i++) {
249: buffer.append("[" + keys[i] + "," + elements[i] + "]");
250: }
251: return buffer.toString();
252: }
253:
254: /**
255: * Constructor.
256: * @param capacity the initial capacity
257: */
258: public LookupTable(int capacity) {
259: this .count = 0;
260: this .capacity = capacity;
261: this .elements = new Object[capacity];
262: this .keys = new Object[capacity];
263: }
264:
265: /**
266: * Constructor, build a LookupTable with a initial capacity set to
267: * DEFAULT_CAPACITY.
268: */
269: public LookupTable() {
270: this(DEFAULT_CAPACITY);
271: }
272:
273: }
|