Java/Collections Data Structure/Dictionary
Random-access dictionary
// 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.
* <p>This class does <em>not</em> 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 <em>not</em> 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, <em>using</em> (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, <em>using</em> (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 <strong>true</strong> if there are no entries,
* <strong>false></strong> 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++] ;
}
}
