Re: Hashtable question
From: Roedy Green (look-on_at_mindprod.com.invalid)
Date: 05/11/04
- Next message: Roedy Green: "Re: java help"
- Previous message: Lev Kaplun: "EncryptDecrypt"
- In reply to: Roedy Green: "Re: Hashtable question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 11 May 2004 21:03:56 GMT
On Tue, 11 May 2004 20:59:09 GMT, Roedy Green
<look-on@mindprod.com.invalid> wrote or quoted :
>Here is some code that does that sort of thing:
here is some more
// com.mindprod.pim.PIMEngine.java
package com.mindprod.pim;
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OptionalDataException;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.TreeMap;
/**
* Engine for a ram-based Personal Information Manager.
* Internally it has a HashMap of Items and a TreeMap of Keys.
* Each key can point directly to several Items, and each Item can
point to several keys.
* @author copyright (c) 1999-2004 Roedy Green, Canadian Mind
Products
* may be copied and used freely for any purpose but military.
*
* Roedy Green
* Canadian Mind Products
* #327 - 964 Heywood Avenue
* Victoria, BC Canada V8V 2Y5
* tel: (250) 361-9093
* mailto:roedyg@mindprod.com
* http://mindprod.com
*
* version 1.0 1999 October 12 8:30 PM -- 9:30 PM
* version 1.1 1999 October 13 - 9:30 PM -- 12:20 PM
* - clean compile of code, no testing.
* - no pickle
* version 1.2 1999 October 13 - 9:10 AM -- 10:10 AM
* - add find all strings for item
* - add sort to keep Keys per item in
order
* - remove requirement for makeUnique.
* - get rid of compiler errors
* - deal with null initial case in
addKey and addItem
* version 1.3 1999 October 13 - 10:40 AM -- 11:15 AM
* - make allKeys use String -> key
consistently.
* - crude test of add/display functions.
* version 1.4 1999 October 13 - 2:20 PM -- 3:20 PM 7:00 PM -- 8:00
PM
* - add pickle/reconstitute
* - only sort keyList just prior to
display to save overhead
* of repeated sorts during
reconstitution.
* - change constructor to take String
instead of File.
* - add showAll debug tool
* - clone rather than give access to
internal array in find.
*
*/
public class PIMEngine implements java.io.Serializable
{
/**
* public constructor.
* @param modelName is a filename less the .pim extension where the
PIM data are stored,
* e.g. "C:\\myDir\\plays"
*/
public PIMEngine(String modelName) throws IOException,
FileNotFoundException {
this.modelName = modelName;
this.load();
} // end constructor
/**
* load a previously saved pickled version of the entire data
structure.
*/
public void load() throws IOException {
File current = new File(modelName + ".pim");
if ( current.exists() )
{
// O P E N
try
{
FileInputStream fis = new FileInputStream(current);
BufferedInputStream bis = new BufferedInputStream(fis,
4096 /* buffsize */);
ObjectInputStream ois = new ObjectInputStream(bis);
// R E A D
// reconstitute fields individually rather than
// "this" because of readObject/writeObject asymmetry
allKeys = (TreeMap) ois.readObject();
// restore transient fields, namely the allItems HashMap
and the
// Item.keyList[] back pointers.
allItems = new java.util.HashMap();
// enumerate all the Key objects in the TreeMap
Collection keys = allKeys.values();
Iterator eachKey = keys.iterator();
while ( eachKey.hasNext() )
{
Key key = (Key)eachKey.next();
int numItems = key.itemList.length;
for ( int i=0; i<numItems; i++ )
{
// itemList[i] is already unique, we use makeUnique
for the side effect
// of adding the item to the allItems HashMap
Item item = makeUnique(key.itemList[i]);
// build item.keyList[] back pointer
item.addKey(key);
} // end for
} // end while
// C L O S E
ois.close();
}
catch ( ClassNotFoundException e )
{
throw new IOException("PIM file corrupt");
}
catch ( OptionalDataException e )
{
throw new IOException("PIM file corrupt");
}
catch ( IOException e )
{
throw new IOException("PIM file corrupt");
}
}
else
{
// starting from scratch
allKeys = new java.util.TreeMap();
allItems = new java.util.HashMap();
}
} // end load
/**
* save the entire data structure in pickled form in a file.
* @param File to store program state in pickled form.
*/
public void save() throws IOException {
// rename old, as .old save as .pim
File prev = new File(modelName + ".old");
File current = new File(modelName + ".pim");;
prev.delete();
current.renameTo(prev);
// O P E N
FileOutputStream fos = new FileOutputStream(current);
BufferedOutputStream bos = new BufferedOutputStream(fos, 4096 /*
buffsize */);
ObjectOutputStream oos = new ObjectOutputStream(bos);
// W R I T E
// pickle fields individually rather than
// "this" because of readObject/writeObject asymmetry
// Write out the allKeys TreeMap but leave behind the allItems
HashMap
// Also leave out the Key[] Item.KeyList back pointers.
oos.writeObject(allKeys);
// C L O S E
oos.close();
} // end save
/**
* create an association between the given key and the given item.
* Items may have many associated keys, and keys may associate to
many items.
* @param keystring key for the association
* @param item data object derived from Item class.
*/
public void add(String keyString, Item item)
{
Item uniqueItem = makeUnique(item);
Key key = lookup(keyString);
if ( key == null )
{
key = new Key(keyString);
allKeys.put(keyString, key);
}
key.addItem(uniqueItem);
uniqueItem.addKey(key);
} // end add
/**
* create an association between the given list of keys and the
given item.
* Items may have many associated keys, and keys may associate to
many items.
* @param keystring list of keys for the association
* @param item data object derived from Item class.
*/
public void add(String[] keyString, Item item)
{
Item uniqueItem = makeUnique(item);
int numKeyStrings = keyString.length;
for ( int i=0; i<numKeyStrings; i++ )
{
add(keyString[i], uniqueItem);
} // end for
} // end add
/**
* Break an existing association between a key and an item.
* This will not destroy either the key or the item, though
* it will remove references to them, which may eventually lead to
* them being garbage collected.
* It is not considered an error to remove a pair that has not
been previously added.
* @param keystring key for the association.
* @param item data object derived from Item class.
*/
public void remove(String keyString, Item item)
{
Item uniqueItem = makeUnique(item);
Key key = lookup(keyString);
if ( key == null )
{
// was no such keyString
return;
}
key.removeItem(uniqueItem);
if ( key.itemList == null )
{
allKeys.remove(key.keyString);
}
uniqueItem.removeKey(key);
if ( uniqueItem.keyList == null )
{
allItems.remove(uniqueItem);
}
} // end remove
/**
* Break an existing association between a list of keys and an
item.
* This will not destroy either the key or the item, though
* it will remove references to them, which may eventually lead to
* them being garbage collected.
* It is not considered an error to remove a pair that has not
been previously added.
* @param keystring list of keys for the association.
* @param item data object derived from Item class.
*/
public void remove(String[] keyString, Item item)
{
Item uniqueItem = makeUnique(item);
int numKeyStrings = keyString.length;
for ( int i=0; i<numKeyStrings; i++ )
{
remove(keyString[i], uniqueItem);
}
} // end remove
/**
* Break all existing associations between the given key and any
items.
* This will not destroy either the key or the item, though
* it will remove references to them, which may eventually lead to
* them being garbage collected.
* It is not considered an error to remove a key that has not been
previously added.
* @param keystring key to remove.
*/
public void remove(String keyString)
{
Key key = lookup(keyString);
if ( key == null )
{
// was no such keyString
return;
}
int numItems = key.itemList.length;
for ( int i=0; i<numItems; i++ )
{
Item item = key.itemList[i];
item.removeKey(key);
if ( item.keyList == null )
{
allItems.remove(item);
}
} // end for
key.itemList = null;
allKeys.remove(key.keyString);
} // end remove
/**
* Break all existing associations between the given item and all
associated keys.
* This will not destroy either the key or the item, though
* it will remove references to them, which may eventually lead to
* them being garbage collected.
* It is not considered an error to remove a key that has not been
previously added.
* @param item data object derived from Item class.
*/
public void remove(Item item)
{
Item uniqueItem = makeUnique(item);
int numKeys = uniqueItem.keyList.length;
for ( int i=0; i<numKeys; i++ )
{
Key key = uniqueItem.keyList[i];
key.removeItem(uniqueItem);
if ( key.itemList == null )
{
allKeys.remove(key.keyString);
}
} // end for
uniqueItem.keyList = null;
allItems.remove(uniqueItem);
} // end remove
/**
* Find all items associated with the given key.
* @param keyString the string to lookup by.
*/
public Item[] find(String keyString)
{
Key key = lookup(keyString);
if ( key == null )
{
System.out.println("lookup fail");
return null;
}
Item[] itemList = key.itemList;
if ( itemList == null )
{
return null;
}
int numItems = itemList.length;
// can't use Item[].clone because it is protected.
Item[] clonedItemList = new Item[numItems];
System.arraycopy(itemList, 0, clonedItemList, 0, numItems);
return clonedItemList;
} // end find
/**
* Find all KeyStrings associated with the given item
* @param item data object derived from Item class.
* @return array of Strings representing associated keys.
*/
public String[] find(Item item)
{
Item uniqueItem = makeUnique(item);
Key[] keyList = uniqueItem.keyList;
if ( keyList == null )
{
return null;
}
// put in alphabetical order, preparatory to display
Arrays.sort(keyList);
int numKeyStrings = keyList.length;
String[] keyStringList = new String[numKeyStrings];
for ( int i=0; i<numKeyStrings; i++ )
{
keyStringList[i] = keyList[i].keyString;
}
return keyStringList;
} // end find
/**
* Ensure the Item is unique by returning a reference to the master
version which
* already lives in the allKeys HashTable. If the Item has never
been seen before,
* it is added to the HashTable.
* @param item data object derived from Item class.
*/
public Item makeUnique(Item item)
{
Item uniqueItem = (Item) allItems.get(item);
if ( uniqueItem != null )
{
return uniqueItem;
}
uniqueItem = item;
allItems.put(uniqueItem, uniqueItem);
return uniqueItem;
}
/**
* lookup the given Keystring to find the associated Key object.
* @param keyString the lookup string.
* @return Key object, or null if not found.
*/
private Key lookup(String keyString)
{
return(Key) allKeys.get(keyString);
} // end lookup
/**
* Lookup structure keys -> Items.
* Access either directy by key or by alphabetic order.
* indexed by KeyString, gives Key, which then points to Items.
*/
protected java.util.TreeMap allKeys;
/**
* Lookup structure data contents -> Item.
* Only used internally. Helps prevent duplicate Items.
* indexed by Item, gives Item, which then points to assocated Keys
which then give keyStrings.
*/
transient protected java.util.HashMap allItems;
/**
* the filename, without .pim extension where the model is stored,
in pickled form.
*/
transient protected String modelName;
/**
* debugging tool that displays all the Key and Item objects.
*/
public void showAll()
{
if ( true )
{
if ( allKeys != null )
{
System.out.println("BY KEY");
Collection keys = allKeys.values();
Iterator eachKey = keys.iterator();
while ( eachKey.hasNext() )
{
Key key = (Key)eachKey.next();
System.out.println("key " + key.keyString);
if ( key.itemList != null )
{
int numItems = key.itemList.length;
for ( int i=0; i<numItems; i++ )
{
TextItem item = (TextItem) key.itemList[i];
System.out.println(" item " + item.getText());
} // end for
} // if
} // end while
} // end if allKeys
if ( allItems != null )
{
System.out.println("BY ITEM");
Collection items = allItems.values();
Iterator eachItem = items.iterator();
while ( eachItem.hasNext() )
{
TextItem item = (TextItem)eachItem.next();
System.out.println("item " + item.getText());
String [] keyStrings = find(item);
if ( keyStrings != null )
{
int numKeyStrings = keyStrings.length;
for ( int j=0; j<numKeyStrings; j++ )
{
System.out.println(" key " + keyStrings[j]);
} // end for
} // end if
} // end while
} // end if allItems
} // end if
} // end showAll
public static void main (String[] args)
{
try
{
PIMEngine p = new PIMEngine("C:\\temp\\temp1");
Item t1 = new TextItem("Love's Labour Lost");
Item t2 = new TextItem("The Tempest");
Item t3 = new TextItem("Macbeth");
Item t4 = new TextItem("The Tempest");
Item t5 = new TextItem("Duncan the Wonder Dog");
p.add("Duncan",t3);
p.add("Duncan",t5);
p.add("Banquo",t3);
p.add("Ariel",t4);
System.out.println("corresponding keys to item Macbeth");
String[] foundKeyStrings = p.find(t3);
if ( foundKeyStrings != null )
{
for ( int i=0; i<foundKeyStrings.length; i++ )
{
System.out.println(foundKeyStrings[i]);
}
}
System.out.println("corresponding items to key Duncan");
Item[] foundItems = p.find("Duncan");
if ( foundItems != null )
{
for ( int i=0; i<foundItems.length; i++ )
{
System.out.println(((TextItem)foundItems[i]).getText());
}
}
p.showAll();
p.save();
}
catch ( IOException e )
{
System.out.println(e);
}
} // end main
} // end class PIMEngine
------------------
// com.mindprod.pim.Item.java
package com.mindprod.pim;
/**
* Base class to represent an data item in the PIM. It might
represent a
* URL, the name of file, a hunk of text, a GIF, etc. Different items
types
* would hold different types of data. All Item types are derived
from this
* base class.
*/
public abstract class Item implements java.io.Serializable
{
/**
* List of associated Key objects, not key Strings.
* Put in alphabetical order, just prior to display, but otherwise
we allow it to
* be in any order.
* Array is compact even if a bit clumsy to add and remove an
element.
* We don't include this in the pickle, because the recursion could
overflow
* the stack. PIMEngine.load reconstitutes these, not
Item.readObject.
*/
transient protected Key[] keyList;
/**
* add given key to the keylist if it is not already there.
*/
protected void addKey(Key key)
{
int len;
if ( keyList == null )
{
len = 0;
}
else
{
len = keyList.length;
}
for ( int i=0; i<len; i++ )
{
// since unique, can use == instead of equals.
if ( key == keyList[i] )
{
// already in list
return;
}
} // end for
// grow the array to make room to add item at the end
Key[] newKeyList = new Key[len+1];
if ( len > 0 )
{
System.arraycopy(keyList, 0, newKeyList, 0, len);
}
newKeyList[len] = key;
// allow to get out of alphabetical order
keyList = newKeyList;
} // end addKey
/**
* remove given key from the keylist.
* If it is already removed, that's ok.
*/
protected void removeKey(Key key)
{
int len = keyList.length;
for ( int i=0; i<len; i++ )
{
// since unique, can use == instead of equals.
if ( key == keyList[i] )
{
// found in list
if ( len == 1 )
{
keyList = null;
return;
}
// shrink the array to remove ith element
Key[] newKeyList = new Key[len-1];
// copy elts below i, if any
if ( i > 0 )
{
System.arraycopy(keyList, 0, newKeyList, 0, i);
}
// copy elts above i, if any
int upper = len-i;
if ( upper > 0 )
{
System.arraycopy(keyList, i+1, newKeyList, i, upper);
}
keyList = newKeyList;
// won't disturb sort order
return;
} // end if
} // end for
// not in list, nothing to do
} // end removeKey
/**
* Returns a hashcode based solely on the data contents of the
Item, not the keylist.
*
* @return a hash code value for this object.
*/
public abstract int hashCode();
/**
* Compares two Items, basing equality on the data contents of the
Item, not the keylist.
* @param anObject other Item to compare to.
* @return true if the Items are equal. Return false if anObject is
not of the same type.
*/
public abstract boolean equals(Object anObject);
} // end class Item
----------------
// com.mindprod.pim.Key.java
package com.mindprod.pim;
/**
* The Key our lookup engine works with in the TreeMap. It points to
several Items.
*/
public final class Key implements Comparable, java.io.Serializable
{
/**
* public constructor
*/
public Key (String keyString)
{
this.keyString = keyString;
this.itemList = null;
} // end constructor
/**
* the lookup key
*/
protected String keyString;
/**
* List of associated Items
* Array is compact even if a bit clumsy to add and remove an
element.
*/
protected Item[] itemList;
/**
* Returns a hashcode based solely on the lookup key, not the
items.
*
* @return a hash code value for this object.
*/
public int hashCode()
{
return keyString != null ? keyString.hashCode(): 0;
}
/**
* Compares two Keys, basing equality on the key, not the Itemlist.
* @param anObject other Item to compare to.
* @return true if the Items are equal. Return false if anObject is
not of the same type.
*/
public boolean equals(Object anObject)
{
if ( keyString == null ) return false;
if ( anObject instanceof Key )
{
return this.keyString.equals(((Key)anObject).keyString);
}
if ( anObject instanceof String )
{
return this.keyString.equals((String)anObject);
}
return false;
} // end equals
/**
* add an Item to the ItemList if it is not already there.
* @param Item to add, must be unique.
*/
protected void addItem(Item uniqueItem)
{
int len;
if ( itemList == null )
{
len = 0;
}
else
{
len = itemList.length;
}
for ( int i=0; i<len; i++ )
{
// since unique, can use == instead of equals.
if ( uniqueItem == itemList[i] )
{
// already in list
return;
}
} // end for
// grow the array to make room to add item at the end
Item[] newItemList = new Item[len+1];
int below = len;
if ( below > 0 )
{
System.arraycopy(itemList, 0, newItemList, 0, below);
}
newItemList[len] = uniqueItem;
itemList = newItemList;
// order does not matter
} // end addItem
/**
* remove given item from this key's itemList.
* If it is already removed, that's ok.
*/
protected void removeItem(Item uniqueItem)
{
int len = itemList.length;
for ( int i=0; i<len; i++ )
{
// since unique, can use == instead of equals.
if ( uniqueItem == itemList[i] )
{
// found in list
if ( len == 1 )
{
itemList = null;
return;
}
// shrink the array to remove ith element
Item[] newItemList = new Item[len-1];
// copy elts below i, if any
int below = i;
if ( below > 0 )
{
System.arraycopy(itemList, 0, newItemList, 0, below);
}
// copy elts above i, if any
int above = len-i;
if ( above > 0 )
{
System.arraycopy(itemList, i+1, newItemList, i, above);
}
itemList = newItemList;
// existing order is just fine
return;
} // end if
} // end for
// not in list, nothing to do
} // end removeItem
/* compares this Key's Keystring to another's.
* @param o Key to be compared with this one.
* @return +ve if this one is bigger, 0 if equal, -ve if smaller.
*/
public int compareTo (Object o) throws ClassCastException
{
return this.keyString.compareTo(((Key)o).keyString);
}
/**
* @return a String that represents this Key
*/
public String toString()
{
return keyString;
}
} // end class Key
--------------------
// com.mindprod.pim.TextItem.java
package com.mindprod.pim;
/**
* Item to associate, holds simple string, without embedded \n chars.
*/
public class TextItem extends Item
{
/**
* public constructor
*/
public TextItem (String text)
{
super();
this.text = text;
} // end constructor
/**
* text data to be associated with keys
*/
private String text;
/**
* get text data string for this TextItem
* Note there is no corresponding setText, since the data must be
immutable.
* @return text string.
*/
public String getText()
{
return text;
} // end getText
/**
* @return a String that represents this TextItem
*/
public String toString()
{
return text;
}
/**
* Returns a hashcode based solely on the data contents of the
Item, not the keylist.
*
* @return a hash code value for this object.
*/
public int hashCode()
{
return text.hashCode();
}
/**
* Compares two Items, basing equality on the data contents of the
Item, not the keylist.
* @param anObject other Item to compare to.
* @return true if the Items are equal. Return false if anObject is
not of the same type.
*/
public boolean equals(Object anObject)
{
if ( text == null ) return false;
if ( anObject instanceof TextItem )
{
return text.equals(((TextItem)anObject).text);
}
if ( anObject instanceof String )
{
return text.equals((String)anObject);
}
return false;
} // end equals
} // end class TextItem
-------------------
I have two other variants, one uses a TreeMap and one supports Many to
One mappings, not many to many.
-- Canadian Mind Products, Roedy Green. Coaching, problem solving, economical contract programming. See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
- Next message: Roedy Green: "Re: java help"
- Previous message: Lev Kaplun: "EncryptDecrypt"
- In reply to: Roedy Green: "Re: Hashtable question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
