Java/Collections Data Structure/Dictionary

Random-access dictionary

   <source lang="java">
 

// ArrayDictionary.java // $Id: ArrayDictionary.java,v 1.16 2000/08/16 21:37:57 ylafon Exp $ // (c) COPYRIGHT MIT and INRIA, 1996. // Please first read the full copyright statement in file COPYRIGHT.html

import java.util.Dictionary; import java.util.Enumeration; import java.util.Vector; import java.io.DataInputStream; import java.io.InputStream; import java.io.PrintStream; /**

* Random-access dictionary:
* like a dictionary but with a certain Vector-ness to it
* Besides all the methods from Dictionary, it also has methods that
* permit direct access to the nth element or nth key.
* Should be used with care...it"s not too well tested yet, and it
* is very exposed.

*

This class does not provide thread-safeness, for the sake of * efficiency, again it should be used with care ! * @author Antonio Ramírez */ public class ArrayDictionary extends Dictionary implements Cloneable { /** The array of keys */ protected Object[] keys ; /** The array of corresponding values */ protected Object[] values ; /** How many real elements are in */ protected int nelems ; /** By how much to grow */ protected int incr ; /** * Create an ArrayDictionary using default values for initial size and * increment. */ public ArrayDictionary() { this(10,10) ; } /** * Create an ArrayDictionary using the given initial size. * (The increment is set to the same value). * @param init The initial size */ public ArrayDictionary(int init) { this(init,init) ; } /** * Clone this array dictionary. * <p>As for hashtables, a shallow copy is made, the keys and elements * themselves are not cloned. * @return The clone. */ public Object clone() { try { ArrayDictionary cl = (ArrayDictionary) super.clone(); cl.values = new Object[values.length]; System.arraycopy(values, 0, cl.values, 0, values.length); cl.keys = new Object[values.length]; System.arraycopy(keys, 0, cl.keys, 0, keys.length); return cl; } catch (CloneNotSupportedException ex) { throw new InternalError(); } } /** * Create an ArrayDictionary using the given initial size and * the given increment for growing the array. * @param init the initial size * @param incr the increment */ public ArrayDictionary(int init, int incr) { keys = new Object[init] ; values = new Object[init] ; this.incr = incr ; nelems = 0 ; } /** * Create an ArrayDictionary, contructing the arrays of keys and * values from the two given vectors. * The two vectors should have the same size. * The increment is set to the number of elements. * @param keys the vector of keys * @param values the vector of values */ public ArrayDictionary(Vector keys,Vector values) { this(keys,values,values.size()) ; } /** * Create an ArrayDictionary, contructing the arrays of keys and * values from the two given vectors. * The two vectors should have the same size. * @param keys the vector of keys * @param values the vector of values * @param incr the increment for growing the arrays */ public ArrayDictionary(Vector keys, Vector values, int incr) { this.incr = incr ; nelems = keys.size() ; this.keys = new Object[nelems] ; this.values = new Object[nelems] ; keys.copyInto(this.keys) ; values.copyInto(this.values) ; } /** * Create an ArrayDicitonary, using (not copying) the given pair * of arrays as keys and values. The increment is set to the length of the * arrays. * @param keys the array of keys * @param values the array of values */ public ArrayDictionary(Object[] keys, Object[] values) { this(keys,values,values.length) ; } /** * Create an ArrayDicitonary, using (not copying) the given pair * of arrays as keys and values. * @param keys the array of keys * @param values the array of values * @param incr the increment for growing the arrays */ public ArrayDictionary(Object[] keys, Object[] values, int incr) { this.incr = incr ; nelems = keys.length ; this.keys = keys ; this.values = values ; } protected final void grow() { grow(keys.length+incr) ; } protected void grow(int newCapacity) { Object[] newKeys = new Object[newCapacity] ; Object[] newVals = new Object[newCapacity] ; System.arraycopy(keys,0,newKeys,0,keys.length) ; System.arraycopy(values,0,newVals,0,values.length) ; keys = newKeys ; values = newVals ; } /** * Returns an enumeration of the elements of the dictionary. * @return the enumeration */ public Enumeration elements() { return new ArrayEnumeration(values,nelems) ; } /** * Returns the value that maps to the given key. * @param key the key * @return the value */ public Object get(Object key) { int n,i; for(i=0,n=0;i<keys.length;i++) { if(n >= nelems) break ; if ( keys[i] == null ) continue; if(keys[i].equals(key)) return values[i] ; n++ ; } return null; } /** * "Optimized" method to obtain the values * corresponding to several keys, in one swoop. * @param rKeys An array of requested keys * @return An array of corresponding values */ public Object[] getMany(Object[] rKeys) { Object[] rValues = new Object[rKeys.length] ; int i,n ; for(i=0,n=0;i<keys.length;i++) { if(n >= nelems) break ; if(keys[i]==null) continue ; inloop: for(int j=0;j<rKeys.length;j++) if(keys[i].equals(rKeys[j])) { rValues[j] = values[i] ; break inloop ; } n++ ; } return rValues ; } /** * Are there any entries in the dictionary? * @return true if there are no entries, * false> otherwise. */ public final boolean isEmpty() { return nelems==0 ; } /** * Increases the capacity of this dictionary to at least the * specified number of key/value mappings. * @param minCapacity the desired minimum capacity */ public final void ensureCapacity(int minCapacity) { if(minCapacity>keys.length) grow(minCapacity) ; } /** * Returns an enumeration of the keys of the dictionary. * @return the enumeration */ public Enumeration keys() { return new ArrayEnumeration(keys,nelems) ; } /** * Adds a mapping between a key and a value to the dictionary. * Will grow the arrays if necessary. * @param key the key * @param value the corresponding value * @return the previous value corresponding to the key, or null if * the key is new. */ public Object put(Object key,Object value) { int empty = -1 ; int i,n ; for(i=0,n=0;i<keys.length;i++) { if(n >= nelems) break ; if(keys[i] == null) { empty = i ; continue ; } if(keys[i].equals(key)) { Object prev = values[i] ; values[i]=value; return prev ; } n++ ; } if(empty!=-1) { keys[empty]=key ; values[empty]=value ; nelems++ ; } else { grow() ; keys[nelems] = key ; values[nelems++] = value ; } return null ; } /** * Removes a key (and its value) from the dictionary; * @param key the key to remove * @return the value that used to map to that key */ public Object remove(Object key) { int i,n ; for(i=0,n=0;i<keys.length;i++) { if(n >= nelems) break ; if(keys[i] == null) continue ; if(keys[i].equals(key)) { nelems-- ; Object prev = values[i] ; keys[i] = values[i] = null ; return prev ; } n++ ; } return null ; } /** * Returns the number of elements in the dictionary * @return the number of elements */ public final int size() { return nelems ; } /** * Returns the maximum number of keys the dictionary can hold * without reallocating an array. * @return the capacity of the dictionary */ public final int capacity() { return keys.length ; } /** * Returns the nth key. * @param n the index of the desired key * @return the nth key, or null if no key in that place. */ public final Object keyAt(int n) { return keys[n] ; } /** * Returns the nth element (value). * @param n the index of the desired element * @return the nth element, or null if no element in that place. */ public final Object elementAt(int n) { return values[n] ; } /** * Sets the element at the nth place in the array. * @param n the index of the element to change * @param newVal the value to change it to * @return the old value */ public Object setElementAt(int n,Object newVal) { Object prev = values[n] ; values[n] = newVal ; return prev ; } /** * Removes the nth mapping (key/value pair) in the dictionary. * @param n the index of the element to remove * @return the old value of the element at the nth place */ public Object removeElementAt(int n) { if(values[n]!=null) { Object prev = values[n] ; values[n] = keys[n] = null ; nelems--; return prev; } else return null ; } /** * Creates a string representation of the dictionary * @return the string representation. */ public String toString() { StringBuffer buf = new StringBuffer(100) ; buf.append("[") ; for(int i=0;i<keys.length;i++) { if(keys[i]==null) continue ; buf.append(keys[i]) ; buf.append("=") ; buf.append(values[i]) ; buf.append(" ") ; } buf.append("]") ; return buf.toString() ; } /** * A kludge for testing ArrayDictionary */ public static void main(String[] args) { try { PrintStream out = System.out ; DataInputStream in = new DataInputStream(System.in) ; String line = null ; out.print("n ? ") ; out.flush() ; line = in.readLine() ; int n = Integer.parseInt(line) ; ArrayDictionary ad = new ArrayDictionary(n) ; String key = null, value = null; while(true) { out.print("action ? ") ; out.flush() ; line = in.readLine() ; switch(line.charAt(0)) { case "p": case "P": out.print("key ? ") ; out.flush() ; key = in.readLine() ; out.print("value ? ") ; out.flush() ; value = in.readLine() ; value = (String ) ad.put(key,value) ; out.println("old: "+value) ; break ; case "r": case "R": out.print("key ? ") ; out.flush() ; key = in.readLine() ; value = (String) ad.remove(key) ; out.println("old: "+value) ; break ; case "g": case "G": out.print("key ? ") ; out.flush() ; key = in.readLine() ; value = (String) ad.get(key) ; out.println("value: "+value) ; break ; case "d": case "D": out.println(ad.toString()) ; break ; case "q": case "Q": return ; } } } catch(Exception ex) { ex.printStackTrace() ; } } } //ArrayEnumeration.java //$Id: ArrayEnumeration.java,v 1.3 2000/08/16 21:37:57 ylafon Exp $ //(c) COPYRIGHT MIT and INRIA, 1996. //Please first read the full copyright statement in file COPYRIGHT.html /** Iterates through array skipping nulls. */ class ArrayEnumeration implements Enumeration { private int nelems ; private int elemCount ; private int arrayIdx ; private Object[] array ; public ArrayEnumeration(Object[] array) { this(array,array.length) ; } public ArrayEnumeration(Object[] array,int nelems) { arrayIdx = elemCount = 0 ; this.nelems = nelems ; this.array = array ; } public final boolean hasMoreElements() { return elemCount<nelems ; } public final Object nextElement() { while(array[arrayIdx]==null && arrayIdx<array.length) arrayIdx++ ; if(arrayIdx>=array.length) throw new RuntimeException() ; elemCount++; return array[arrayIdx++] ; } } </source>