001: // ArrayDictionary.java
002: // $Id: ArrayDictionary.java,v 1.16 2000/08/16 21:37:57 ylafon Exp $
003: // (c) COPYRIGHT MIT and INRIA, 1996.
004: // Please first read the full copyright statement in file COPYRIGHT.html
005:
006: package org.w3c.util;
007:
008: import java.util.Dictionary;
009: import java.util.Enumeration;
010: import java.util.Vector;
011:
012: import java.io.DataInputStream;
013: import java.io.InputStream;
014: import java.io.PrintStream;
015:
016: /**
017: * Random-access dictionary:
018: * like a dictionary but with a certain Vector-ness to it
019: * Besides all the methods from Dictionary, it also has methods that
020: * permit direct access to the nth element or nth key.
021: * Should be used with care...it's not too well tested yet, and it
022: * is very exposed.
023: * <p>This class does <em>not</em> provide thread-safeness, for the sake of
024: * efficiency, again it should be used with care !
025: * @author Antonio Ramírez
026: */
027:
028: public class ArrayDictionary extends Dictionary implements Cloneable {
029: /** The array of keys */
030: protected Object[] keys;
031:
032: /** The array of corresponding values */
033: protected Object[] values;
034:
035: /** How many real elements are in */
036: protected int nelems;
037:
038: /** By how much to grow */
039: protected int incr;
040:
041: /**
042: * Create an ArrayDictionary using default values for initial size and
043: * increment.
044: */
045: public ArrayDictionary() {
046: this (10, 10);
047: }
048:
049: /**
050: * Create an ArrayDictionary using the given initial size.
051: * (The increment is set to the same value).
052: * @param init The initial size
053: */
054: public ArrayDictionary(int init) {
055: this (init, init);
056: }
057:
058: /**
059: * Clone this array dictionary.
060: * <p>As for hashtables, a shallow copy is made, the keys and elements
061: * themselves are <em>not</em> cloned.
062: * @return The clone.
063: */
064:
065: public Object clone() {
066: try {
067: ArrayDictionary cl = (ArrayDictionary) super .clone();
068: cl.values = new Object[values.length];
069: System.arraycopy(values, 0, cl.values, 0, values.length);
070: cl.keys = new Object[values.length];
071: System.arraycopy(keys, 0, cl.keys, 0, keys.length);
072: return cl;
073: } catch (CloneNotSupportedException ex) {
074: throw new InternalError();
075: }
076: }
077:
078: /**
079: * Create an ArrayDictionary using the given initial size and
080: * the given increment for growing the array.
081: * @param init the initial size
082: * @param incr the increment
083: */
084: public ArrayDictionary(int init, int incr) {
085: keys = new Object[init];
086: values = new Object[init];
087: this .incr = incr;
088: nelems = 0;
089: }
090:
091: /**
092: * Create an ArrayDictionary, contructing the arrays of keys and
093: * values from the two given vectors.
094: * The two vectors should have the same size.
095: * The increment is set to the number of elements.
096: * @param keys the vector of keys
097: * @param values the vector of values
098: */
099: public ArrayDictionary(Vector keys, Vector values) {
100: this (keys, values, values.size());
101: }
102:
103: /**
104: * Create an ArrayDictionary, contructing the arrays of keys and
105: * values from the two given vectors.
106: * The two vectors should have the same size.
107: * @param keys the vector of keys
108: * @param values the vector of values
109: * @param incr the increment for growing the arrays
110: */
111: public ArrayDictionary(Vector keys, Vector values, int incr) {
112: this .incr = incr;
113: nelems = keys.size();
114: this .keys = new Object[nelems];
115: this .values = new Object[nelems];
116: keys.copyInto(this .keys);
117: values.copyInto(this .values);
118: }
119:
120: /**
121: * Create an ArrayDicitonary, <em>using</em> (not copying) the given pair
122: * of arrays as keys and values. The increment is set to the length of the
123: * arrays.
124: * @param keys the array of keys
125: * @param values the array of values
126: */
127: public ArrayDictionary(Object[] keys, Object[] values) {
128: this (keys, values, values.length);
129: }
130:
131: /**
132: * Create an ArrayDicitonary, <em>using</em> (not copying) the given pair
133: * of arrays as keys and values.
134: * @param keys the array of keys
135: * @param values the array of values
136: * @param incr the increment for growing the arrays
137: */
138: public ArrayDictionary(Object[] keys, Object[] values, int incr) {
139: this .incr = incr;
140: nelems = keys.length;
141: this .keys = keys;
142: this .values = values;
143: }
144:
145: protected final void grow() {
146: grow(keys.length + incr);
147: }
148:
149: protected void grow(int newCapacity) {
150: Object[] newKeys = new Object[newCapacity];
151: Object[] newVals = new Object[newCapacity];
152:
153: System.arraycopy(keys, 0, newKeys, 0, keys.length);
154: System.arraycopy(values, 0, newVals, 0, values.length);
155:
156: keys = newKeys;
157: values = newVals;
158: }
159:
160: /**
161: * Returns an enumeration of the elements of the dictionary.
162: * @return the enumeration
163: */
164: public Enumeration elements() {
165: return new ArrayEnumeration(values, nelems);
166: }
167:
168: /**
169: * Returns the value that maps to the given key.
170: * @param key the key
171: * @return the value
172: */
173: public Object get(Object key) {
174: int n, i;
175: for (i = 0, n = 0; i < keys.length; i++) {
176: if (n >= nelems)
177: break;
178: if (keys[i] == null)
179: continue;
180: if (keys[i].equals(key))
181: return values[i];
182: n++;
183: }
184: return null;
185: }
186:
187: /**
188: * "Optimized" method to obtain the values
189: * corresponding to several keys, in one swoop.
190: * @param rKeys An array of requested keys
191: * @return An array of corresponding values
192: */
193: public Object[] getMany(Object[] rKeys) {
194: Object[] rValues = new Object[rKeys.length];
195: int i, n;
196: for (i = 0, n = 0; i < keys.length; i++) {
197: if (n >= nelems)
198: break;
199: if (keys[i] == null)
200: continue;
201: inloop: for (int j = 0; j < rKeys.length; j++)
202: if (keys[i].equals(rKeys[j])) {
203: rValues[j] = values[i];
204: break inloop;
205: }
206:
207: n++;
208: }
209: return rValues;
210: }
211:
212: /**
213: * Are there any entries in the dictionary?
214: * @return <strong>true</strong> if there are no entries,
215: * <strong>false></strong> otherwise.
216: */
217: public final boolean isEmpty() {
218: return nelems == 0;
219: }
220:
221: /**
222: * Increases the capacity of this dictionary to at least the
223: * specified number of key/value mappings.
224: * @param minCapacity the desired minimum capacity
225: */
226: public final void ensureCapacity(int minCapacity) {
227: if (minCapacity > keys.length)
228: grow(minCapacity);
229: }
230:
231: /**
232: * Returns an enumeration of the keys of the dictionary.
233: * @return the enumeration
234: */
235: public Enumeration keys() {
236: return new ArrayEnumeration(keys, nelems);
237: }
238:
239: /**
240: * Adds a mapping between a key and a value to the dictionary.
241: * Will grow the arrays if necessary.
242: * @param key the key
243: * @param value the corresponding value
244: * @return the previous value corresponding to the key, or null if
245: * the key is new.
246: */
247: public Object put(Object key, Object value) {
248: int empty = -1;
249: int i, n;
250: for (i = 0, n = 0; i < keys.length; i++) {
251: if (n >= nelems)
252: break;
253: if (keys[i] == null) {
254: empty = i;
255: continue;
256: }
257: if (keys[i].equals(key)) {
258: Object prev = values[i];
259: values[i] = value;
260: return prev;
261: }
262: n++;
263: }
264:
265: if (empty != -1) {
266: keys[empty] = key;
267: values[empty] = value;
268: nelems++;
269: } else {
270: grow();
271: keys[nelems] = key;
272: values[nelems++] = value;
273: }
274:
275: return null;
276: }
277:
278: /**
279: * Removes a key (and its value) from the dictionary;
280: * @param key the key to remove
281: * @return the value that used to map to that key
282: */
283: public Object remove(Object key) {
284: int i, n;
285: for (i = 0, n = 0; i < keys.length; i++) {
286: if (n >= nelems)
287: break;
288: if (keys[i] == null)
289: continue;
290: if (keys[i].equals(key)) {
291: nelems--;
292: Object prev = values[i];
293: keys[i] = values[i] = null;
294: return prev;
295: }
296: n++;
297: }
298: return null;
299: }
300:
301: /**
302: * Returns the number of elements in the dictionary
303: * @return the number of elements
304: */
305: public final int size() {
306: return nelems;
307: }
308:
309: /**
310: * Returns the maximum number of keys the dictionary can hold
311: * without reallocating an array.
312: * @return the capacity of the dictionary
313: */
314: public final int capacity() {
315: return keys.length;
316: }
317:
318: /**
319: * Returns the nth key.
320: * @param n the index of the desired key
321: * @return the nth key, or null if no key in that place.
322: */
323: public final Object keyAt(int n) {
324: return keys[n];
325: }
326:
327: /**
328: * Returns the nth element (value).
329: * @param n the index of the desired element
330: * @return the nth element, or null if no element in that place.
331: */
332: public final Object elementAt(int n) {
333: return values[n];
334: }
335:
336: /**
337: * Sets the element at the nth place in the array.
338: * @param n the index of the element to change
339: * @param newVal the value to change it to
340: * @return the old value
341: */
342: public Object setElementAt(int n, Object newVal) {
343: Object prev = values[n];
344: values[n] = newVal;
345: return prev;
346: }
347:
348: /**
349: * Removes the nth mapping (key/value pair) in the dictionary.
350: * @param n the index of the element to remove
351: * @return the old value of the element at the nth place
352: */
353: public Object removeElementAt(int n) {
354: if (values[n] != null) {
355: Object prev = values[n];
356: values[n] = keys[n] = null;
357: nelems--;
358: return prev;
359: } else
360: return null;
361: }
362:
363: /**
364: * Creates a string representation of the dictionary
365: * @return the string representation.
366: */
367: public String toString() {
368: StringBuffer buf = new StringBuffer(100);
369: buf.append('[');
370: for (int i = 0; i < keys.length; i++) {
371: if (keys[i] == null)
372: continue;
373: buf.append(keys[i]);
374: buf.append('=');
375: buf.append(values[i]);
376: buf.append(' ');
377: }
378: buf.append(']');
379: return buf.toString();
380:
381: }
382:
383: /**
384: * A kludge for testing ArrayDictionary
385: */
386: public static void main(String[] args) {
387: try {
388: PrintStream out = System.out;
389: DataInputStream in = new DataInputStream(System.in);
390:
391: String line = null;
392:
393: out.print("n ? ");
394: out.flush();
395: line = in.readLine();
396: int n = Integer.parseInt(line);
397: ArrayDictionary ad = new ArrayDictionary(n);
398:
399: String key = null, value = null;
400: while (true) {
401: out.print("action ? ");
402: out.flush();
403: line = in.readLine();
404:
405: switch (line.charAt(0)) {
406: case 'p':
407: case 'P':
408: out.print("key ? ");
409: out.flush();
410: key = in.readLine();
411: out.print("value ? ");
412: out.flush();
413: value = in.readLine();
414: value = (String) ad.put(key, value);
415: out.println("old: " + value);
416: break;
417: case 'r':
418: case 'R':
419: out.print("key ? ");
420: out.flush();
421: key = in.readLine();
422: value = (String) ad.remove(key);
423: out.println("old: " + value);
424: break;
425: case 'g':
426: case 'G':
427: out.print("key ? ");
428: out.flush();
429: key = in.readLine();
430: value = (String) ad.get(key);
431: out.println("value: " + value);
432: break;
433: case 'd':
434: case 'D':
435: out.println(ad.toString());
436: break;
437: case 'q':
438: case 'Q':
439: return;
440: }
441: }
442: } catch (Exception ex) {
443: ex.printStackTrace();
444: }
445: }
446:
447: }
|