Mega Code Archive
A simple Map implementation
<![CDATA[
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.com/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun's Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun's, and James Gosling's,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
import java.util.*;
/** A simple Map implementation, implemented in terms of a
* pair of ArrayLists just to show what a Map has to do (it would
* have been easier, but less informative, to subclass AbstractMap).
* This Map implementation, like TreeSet, guarantees that the
* Map's contents will be kept in ascending element order,
* sorted according to the natural order of the elements;
* see Comparable. This does not (yet) allow you to specify your own
* Comparator.
* <p>
* It is a requirement that all objects inserted be able to
* call compareTo on all other objects, i.e., they must all
* be of the same or related classes.
* <p>
* Be warned that the entrySet() method is <b>not implemented</b> yet.
*/
public class MyMap implements Map {
private ArrayList keys;
private ArrayList values;
public MyMap() {
keys = new ArrayList();
values = new ArrayList();
}
/** Return the number of mappings in this Map. */
public int size() {
return keys.size();
}
/** Return true if this map is empty. */
public boolean isEmpty() {
return size() == 0;
}
/** Return true if o is contained as a Key in this Map. */
public boolean containsKey(Object o) {
return keys.contains(o);
}
/** Return true if o is contained as a Value in this Map. */
public boolean containsValue(Object o) {
return keys.contains(o);
}
/** Get the object value corresponding to key k. */
public Object get(Object k) {
int i = keys.indexOf(k);
if (i == -1)
return null;
return values.get(i);
}
/** Put the given pair (k, v) into this map, by maintaining "keys"
* in sorted order.
*/
public Object put(Object k, Object v) {
for (int i=0; i < keys.size(); i++) {
Object old = keys.get(i);
/* Does the key already exist? */
if (((Comparable)k).compareTo(keys.get(i)) == 0) {
keys.set(i, v);
return old;
}
/* Did we just go past where to put it?
* i.e., keep keys in sorted order.
*/
if (((Comparable)k).compareTo(keys.get(i)) == +1) {
int where = i > 0 ? i -1 : 0;
keys.add(where, k);
values.add(where, v);
return null;
}
}
// Else it goes at the end.
keys.add(k);
values.add(v);
return null;
}
/** Put all the pairs from oldMap into this map */
public void putAll(java.util.Map oldMap) {
Iterator keysIter = oldMap.keySet().iterator();
while (keysIter.hasNext()) {
Object k = keysIter.next();
Object v = oldMap.get(k);
put(k, v);
}
}
public Object remove(Object k) {
int i = keys.indexOf(k);
if (i == -1)
return null;
Object old = values.get(i);
keys.remove(i);
values.remove(i);
return old;
}
public void clear() {
keys.clear();
values.clear();
}
public java.util.Set keySet() {
return new TreeSet(keys);
}
public java.util.Collection values() {
return values;
}
/** The Map.Entry objects contained in the Set returned by entrySet().
*/
private class MyMapEntry implements Map.Entry, Comparable {
private Object key, value;
MyMapEntry(Object k, Object v) {
key = k;
value = v;
}
public Object getKey() { return key; }
public Object getValue() { return value; }
public Object setValue(Object nv) {
throw new UnsupportedOperationException("setValue");
}
public int compareTo(Object o2) {
if (!(o2 instanceof MyMapEntry))
throw new IllegalArgumentException(
"Huh? Not a MapEntry?");
Object otherKey = ((MyMapEntry)o2).getKey();
return ((Comparable)key).compareTo((Comparable)otherKey);
}
}
/** The set of Map.Entry objects returned from entrySet(). */
private class MyMapSet extends AbstractSet {
List list;
MyMapSet(ArrayList al) {
list = al;
}
public Iterator iterator() {
return list.iterator();
}
public int size() {
return list.size();
}
}
/** Returns a set view of the mappings contained in this Map.
* Each element in the returned set is a Map.Entry.
* NOT guaranteed fully to implement the contract of entrySet
* declared in java.util.Map.
*/
public java.util.Set entrySet() {
if (keys.size() != values.size())
throw new IllegalStateException(
"InternalError: keys and values out of sync");
ArrayList al = new ArrayList();
for (int i=0; i<keys.size(); i++) {
al.add(new MyMapEntry(keys.get(i), values.get(i)));
}
return new MyMapSet(al);
}
public static void main(String[] argv) {
// Construct and load the hash. This simulates loading a
// database or reading from a file, or wherever the data is.
Map map = new MyMap();
// The hash maps from company name to address.
// In real life this might map to an Address object...
map.put("Adobe", "Mountain View, CA");
map.put("Learning Tree", "Los Angeles, CA");
map.put("IBM", "White Plains, NY");
map.put("Netscape", "Mountain View, CA");
map.put("Microsoft", "Redmond, WA");
map.put("Sun", "Mountain View, CA");
map.put("O'Reilly", "Sebastopol, CA");
// Two versions of the "retrieval" phase.
// Version 1: get one pair's value given its key
// (presumably the key would really come from user input):
String queryString = "O'Reilly";
System.out.println("You asked about " + queryString + ".");
String resultString = (String)map.get(queryString);
System.out.println("They are located in: " + resultString);
System.out.println();
// Version 2: get ALL the keys and pairs
// (maybe to print a report, or to save to disk)
Iterator k = map.keySet().iterator();
while (k.hasNext()) {
String key = (String) k.next();
System.out.println("Key " + key + "; Value " +
(String) map.get(key));
}
// Step 3 - try out the entrySet() method.
Set es = map.entrySet();
System.out.println("entrySet() returns " + es.size() + " Map.Entry's");
}
}
]]>