0001: /*
0002: * $Id: Hashlist.java,v 1.3 2002/09/16 08:05:03 jkl Exp $
0003: *
0004: * Copyright (c) 2002 Njet Communications Ltd. All Rights Reserved.
0005: *
0006: * Use is subject to license terms, as defined in
0007: * Anvil Sofware License, Version 1.1. See LICENSE
0008: * file, or http://njet.org/license-1.1.txt
0009: */
0010: package anvil.java.util;
0011:
0012: import java.io.IOException;
0013: import java.io.ObjectInputStream;
0014: import java.io.ObjectOutputStream;
0015: import java.io.Serializable;
0016: import java.util.Collection;
0017: import java.util.Comparator;
0018: import java.util.Dictionary;
0019: import java.util.Enumeration;
0020: import java.util.Iterator;
0021: import java.util.ListIterator;
0022: import java.util.Map;
0023: import java.util.NoSuchElementException;
0024: import java.util.Set;
0025:
0026: /**
0027: * This class implements a hashlist, which maps keys to values. Any
0028: * non-<code>null</code> object can be used as a key or as a value.
0029: * <p>
0030: * To successfully store and retrieve objects from a hashlist, the
0031: * objects used as keys must implement the <code>hashCode</code>
0032: * method and the <code>equals</code> method.
0033: * <p>
0034: * An instance of <code>Hashlist</code> has two parameters that
0035: * affect its efficiency: its <i>capacity</i> and its <i>load
0036: * factor</i>. The load factor should be between 0.0 and 1.0. When
0037: * the number of entries in the hashlist exceeds the product of the
0038: * load factor and the current capacity, the capacity is increased by
0039: * calling the <code>rehash</code> method. Larger load factors use
0040: * memory more efficiently, at the expense of larger expected time
0041: * per lookup.
0042: * <p>
0043: * If many entries are to be made into a <code>Hashlist</code>,
0044: * creating it with a sufficiently large capacity may allow the
0045: * entries to be inserted more efficiently than letting it perform
0046: * automatic rehashing as needed to grow the table.
0047: * <p>
0048: * This example creates a hashlist of numbers. It uses the names of
0049: * the numbers as keys:
0050: * <p><blockquote><pre>
0051: * Hashlist numbers = new Hashlist();
0052: * numbers.put("one", new Integer(1));
0053: * numbers.put("two", new Integer(2));
0054: * numbers.put("three", new Integer(3));
0055: * </pre></blockquote>
0056: * <p>
0057: * To retrieve a number, use the following code:
0058: * <p><blockquote><pre>
0059: * Integer n = (Integer)numbers.get("two");
0060: * if (n != null) {
0061: * System.out.println("two = " + n);
0062: * }
0063: * </pre></blockquote>
0064: *
0065: * @author Jani Lehtimäki
0066: * @version 1.41, 01/28/97
0067: * @see java.util.Hashlist#rehash()
0068: */
0069: public class Hashlist extends Dictionary implements Map, Cloneable,
0070: java.io.Serializable {
0071:
0072: /**
0073: * Hashlist collision list.
0074: */
0075: class Entry implements Holder {
0076: int hash;
0077: Object key;
0078: Object value;
0079: Entry next;
0080: Entry prevEntry;
0081: Entry nextEntry;
0082:
0083: public Object getKey() {
0084: return key;
0085: }
0086:
0087: public Object getValue() {
0088: return value;
0089: }
0090:
0091: public Object setValue(Object value) {
0092: Object oldvalue = this .value;
0093: this .value = value;
0094: return oldvalue;
0095: }
0096:
0097: public Object remove() {
0098: return Hashlist.this .remove(key);
0099: }
0100:
0101: }
0102:
0103: /**
0104: * A hashlist enumerator class. This class should remain opaque
0105: * to the client. It will use the Enumeration interface.
0106: */
0107: class HashlistEnumerator implements BindingEnumeration {
0108: Entry current = null;
0109: boolean keys = false;
0110:
0111: HashlistEnumerator(boolean keys) {
0112: this .keys = keys;
0113: }
0114:
0115: public boolean hasMoreElements() {
0116: Entry e = current;
0117: if (e != null) {
0118: return (e.nextEntry != null);
0119: } else {
0120: return (Hashlist.this .head != null);
0121: }
0122: }
0123:
0124: public Object nextElement() {
0125: Entry e = current;
0126: if (e == null) {
0127: current = (e = Hashlist.this .head);
0128: } else {
0129: current = (e = current.nextEntry);
0130: }
0131: if (e == null) {
0132: throw new NoSuchElementException("HashlistEnumerator");
0133: }
0134: return keys ? e.key : e.value;
0135: }
0136:
0137: public Object nextKey() {
0138: Entry e = current;
0139: if (e == null) {
0140: e = Hashlist.this .head;
0141: } else {
0142: e = e.nextEntry;
0143: }
0144: if (e == null) {
0145: throw new NoSuchElementException("HashlistEnumerator");
0146: }
0147: return e.key;
0148: }
0149:
0150: }
0151:
0152: /**
0153: * A hashlist iterator class.
0154: */
0155: class Iterator implements HashlistIterator {
0156: int index;
0157: Entry current;
0158: Entry prev;
0159: Entry next;
0160:
0161: protected Iterator() {
0162: start();
0163: }
0164:
0165: public void start() {
0166: index = -1;
0167: current = null;
0168: prev = null;
0169: next = Hashlist.this .head;
0170: }
0171:
0172: public void end() {
0173: index = Hashlist.this .count;
0174: current = null;
0175: prev = Hashlist.this .tail;
0176: next = null;
0177: }
0178:
0179: public boolean hasPrevious() {
0180: return (prev != null);
0181: }
0182:
0183: public boolean hasCurrent() {
0184: return (current != null);
0185: }
0186:
0187: public boolean hasNext() {
0188: return (next != null);
0189: }
0190:
0191: public Object previous() {
0192: current = prev;
0193: if (current != null) {
0194: index--;
0195: prev = current.prevEntry;
0196: next = current.nextEntry;
0197: return current.value;
0198: } else {
0199: index = -1;
0200: prev = null;
0201: next = Hashlist.this .head;
0202: return null;
0203: }
0204: }
0205:
0206: public int previousIndex() {
0207: if (index > -1) {
0208: return index - 1;
0209: } else {
0210: return -1;
0211: }
0212: }
0213:
0214: public Object next() {
0215: current = next;
0216: if (current != null) {
0217: index++;
0218: prev = current.prevEntry;
0219: next = current.nextEntry;
0220: return current.value;
0221: } else {
0222: index = Hashlist.this .count;
0223: prev = Hashlist.this .tail;
0224: next = null;
0225: return null;
0226: }
0227: }
0228:
0229: public int nextIndex() {
0230: int max = Hashlist.this .count;
0231: if (index < max) {
0232: return index + 1;
0233: } else {
0234: return max;
0235: }
0236: }
0237:
0238: public int index() {
0239: return index;
0240: }
0241:
0242: public Object key() {
0243: return (current != null) ? current.key : null;
0244: }
0245:
0246: public Object value() {
0247: return (current != null) ? current.value : null;
0248: }
0249:
0250: public void add(Object value) {
0251: }
0252:
0253: public void remove() {
0254: /*if (current != null) {
0255: Hashlist.this.remove(current.key);
0256: }*/
0257: }
0258:
0259: public void set(Object value) {
0260: if (current != null) {
0261: current.setValue(value);
0262: }
0263: }
0264:
0265: }
0266:
0267: /**
0268: * The hash table data.
0269: */
0270: private transient Entry table[];
0271:
0272: /**
0273: * First item in the list
0274: */
0275: private transient Entry head = null;
0276:
0277: /**
0278: * Last item in the list
0279: */
0280: private transient Entry tail = null;
0281:
0282: /**
0283: * The total number of entries in the hash table.
0284: */
0285: private transient int count;
0286:
0287: /**
0288: * Next available integer index.
0289: */
0290: private int nextSequence = 0;
0291:
0292: /**
0293: * Rehashes the table when count exceeds this threshold.
0294: * @serial Integer
0295: */
0296: private int threshold;
0297:
0298: /**
0299: * The load factor for the hashlist.
0300: * @serial Float
0301: */
0302: private float loadFactor;
0303:
0304: /* use serialVersionUID from JDK 1.0.2 for interoperability */
0305: /*private static final long serialVersionUID = 1421746759512286392L;*/
0306:
0307: /**
0308: * Constructs a new, empty hashlist with the specified initial
0309: * capacity and the specified load factor.
0310: *
0311: * @param initialCapacity the initial capacity of the hashlist.
0312: * @param loadFactor a number between 0.0 and 1.0.
0313: * @exception IllegalArgumentException if the initial capacity is less
0314: * than or equal to zero, or if the load factor is less than
0315: * or equal to zero.
0316: */
0317: public Hashlist(int initialCapacity, float loadFactor) {
0318: if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
0319: throw new IllegalArgumentException();
0320: }
0321: this .loadFactor = loadFactor;
0322: table = new Entry[initialCapacity];
0323: threshold = (int) (initialCapacity * loadFactor);
0324: }
0325:
0326: /**
0327: * Constructs a new, empty hashlist with the specified initial capacity
0328: * and default load factor.
0329: *
0330: * @param initialCapacity the initial capacity of the hashlist.
0331: */
0332: public Hashlist(int initialCapacity) {
0333: this (initialCapacity, 0.75f);
0334: }
0335:
0336: /**
0337: * Constructs a new, empty hashlist with a default capacity and load
0338: * factor.
0339: *
0340: */
0341: public Hashlist() {
0342: this (101, 0.75f);
0343: }
0344:
0345: /**
0346: * Returns the number of keys in this hashlist.
0347: *
0348: * @return the number of keys in this hashlist.
0349: */
0350: public int size() {
0351: return count;
0352: }
0353:
0354: /**
0355: * Tests if this hashlist maps no keys to values.
0356: *
0357: * @return <code>true</code> if this hashlist maps no keys to values;
0358: * <code>false</code> otherwise.
0359: */
0360: public boolean isEmpty() {
0361: return count == 0;
0362: }
0363:
0364: /**
0365: * Returns an enumeration of the keys in this hashlist.
0366: *
0367: * @return an enumeration of the keys in this hashlist.
0368: * @see java.util.Hashlist#elements()
0369: */
0370: public synchronized Enumeration keys() {
0371: return new HashlistEnumerator(true);
0372: }
0373:
0374: /**
0375: * Returns an enumeration of the values in this hashlist.
0376: * Use the Enumeration methods on the returned object to fetch the elements
0377: * sequentially.
0378: *
0379: * @return an enumeration of the values in this hashlist.
0380: * @see java.util.Hashlist#keys()
0381: */
0382: public synchronized Enumeration elements() {
0383: return new HashlistEnumerator(false);
0384: }
0385:
0386: public synchronized Collection values() {
0387: return null;
0388: }
0389:
0390: /**
0391: * Returns an enumeration of the values in this hashlist.
0392: * Use the Enumeration methods on the returned object to fetch the elements
0393: * sequentially.
0394: *
0395: * @return an enumeration of the values in this hashlist.
0396: * @see java.util.Hashlist#keys()
0397: */
0398: public synchronized BindingEnumeration keysAndElements() {
0399: return new HashlistEnumerator(false);
0400: }
0401:
0402: /**
0403: * Returns an iterator for hashlist.
0404: * User iterator to browse through the keys and values in the
0405: * insertion order.
0406: *
0407: * @return an iterator for this hashlist.
0408: */
0409: public synchronized HashlistIterator hashlistIterator() {
0410: return new Iterator();
0411: }
0412:
0413: public synchronized ListIterator listIterator() {
0414: return new Iterator();
0415: }
0416:
0417: public synchronized Iterator iterator() {
0418: return new Iterator();
0419: }
0420:
0421: public Set keySet() {
0422: throw new RuntimeException("Not supported");
0423: }
0424:
0425: public Set entrySet() {
0426: throw new RuntimeException("Not supported");
0427: }
0428:
0429: public boolean containsValue(Object value) {
0430: return contains(value);
0431: }
0432:
0433: /**
0434: * Tests if some key maps into the specified value in this hashlist.
0435: * This operation is more expensive than the <code>containsKey</code>
0436: * method.
0437: *
0438: * @param value a value to search for.
0439: * @return <code>true</code> if some key maps to the
0440: * <code>value</code> argument in this hashlist;
0441: * <code>false</code> otherwise.
0442: * @exception NullPointerException if the value is <code>null</code>.
0443: * @see java.util.Hashlist#containsKey(java.lang.Object)
0444: */
0445: public synchronized boolean contains(Object value) {
0446: if (value == null) {
0447: throw new NullPointerException();
0448: }
0449:
0450: Entry tab[] = table;
0451: for (int i = tab.length; i-- > 0;) {
0452: for (Entry e = tab[i]; e != null; e = e.next) {
0453: if (e.value.equals(value)) {
0454: return true;
0455: }
0456: }
0457: }
0458: return false;
0459: }
0460:
0461: /**
0462: * Tests if the specified object is a key in this hashlist.
0463: *
0464: * @param key possible key.
0465: * @return <code>true</code> if the specified object is a key in this
0466: * hashlist; <code>false</code> otherwise.
0467: * @see java.util.Hashlist#contains(java.lang.Object)
0468: */
0469: public synchronized boolean containsKey(Object key) {
0470: Entry tab[] = table;
0471: int hash = key.hashCode();
0472: int index = (hash & 0x7FFFFFFF) % tab.length;
0473: for (Entry e = tab[index]; e != null; e = e.next) {
0474: if ((e.hash == hash) && e.key.equals(key)) {
0475: return true;
0476: }
0477: }
0478: return false;
0479: }
0480:
0481: /**
0482: * Returns the value to which the specified key is mapped in this hashlist.
0483: *
0484: * @param key a key in the hashlist.
0485: * @return the value to which the key is mapped in this hashlist;
0486: * <code>null</code> if the key is not mapped to any value in
0487: * this hashlist.
0488: * @see java.util.Hashlist#put(java.lang.Object, java.lang.Object)
0489: */
0490: public synchronized Object get(Object key) {
0491: Entry tab[] = table;
0492: int hash = key.hashCode();
0493: int index = (hash & 0x7FFFFFFF) % tab.length;
0494: for (Entry e = tab[index]; e != null; e = e.next) {
0495: if ((e.hash == hash) && e.key.equals(key)) {
0496: return e.value;
0497: }
0498: }
0499: return null;
0500: }
0501:
0502: /**
0503: * Returns the entry to which the specified key is mapped in this hashlist.
0504: *
0505: * @param key a key in the hashlist.
0506: * @return the entry to which the key is mapped in this hashlist;
0507: * <code>null</code> if the key is not mapped to any entry in
0508: * this hashlist.
0509: * @see java.util.Hashlist#put(java.lang.Object, java.lang.Object)
0510: */
0511: protected synchronized Entry getEntry(Object key) {
0512: Entry tab[] = table;
0513: int hash = key.hashCode();
0514: int index = (hash & 0x7FFFFFFF) % tab.length;
0515: for (Entry e = tab[index]; e != null; e = e.next) {
0516: if ((e.hash == hash) && e.key.equals(key)) {
0517: return e;
0518: }
0519: }
0520: return null;
0521: }
0522:
0523: /**
0524: * Returns the holder to which the specified key is mapped in this hashlist.
0525: *
0526: * @param key a key in the hashlist.
0527: * @return the <code>Holder</code> to which the key is mapped in this hashlist;
0528: * <code>null</code> if the key is not mapped to any entry in
0529: * this hashlist.
0530: * @see java.util.Hashlist#put(java.lang.Object, java.lang.Object)
0531: */
0532: public Holder getHolder(Object key) {
0533: return getEntry(key);
0534: }
0535:
0536: /**
0537: * Returns the Object to which the specified index (Integer) is mapped in this hashlist.
0538: *
0539: * @param key an index in the hashlist.
0540: * @return the <code>Holder</code> to which the index is mapped in this hashlist;
0541: * <code>null</code> if the index is not mapped to any entry in
0542: * this hashlist.
0543: * @see java.util.Hashlist#put(java.lang.Object, java.lang.Object)
0544: */
0545: public Object get(int index) {
0546: return get(new Integer(index));
0547: }
0548:
0549: /**
0550: * Returns the <code>Holder</code> to which the specified index (Integer)
0551: * is mapped in this hashlist.
0552: *
0553: * @param key an index in the hashlist.
0554: * @return the <code>Holder</code> to which the index is mapped in this hashlist;
0555: * <code>null</code> if the index is not mapped to any <code>Holder</code> in
0556: * this hashlist.
0557: * @see java.util.Hashlist#put(java.lang.Object, java.lang.Object)
0558: */
0559: public Holder getHolder(int index) {
0560: return getEntry(new Integer(index));
0561: }
0562:
0563: /**
0564: * Rehashes the contents of the hashlist into a hashlist with a
0565: * larger capacity. This method is called automatically when the
0566: * number of keys in the hashlist exceeds this hashlist's capacity
0567: * and load factor.
0568: *
0569: */
0570: protected void rehash() {
0571: int oldCapacity = table.length;
0572: Entry oldTable[] = table;
0573:
0574: int newCapacity = oldCapacity * 2 + 1;
0575: Entry newTable[] = new Entry[newCapacity];
0576:
0577: threshold = (int) (newCapacity * loadFactor);
0578: table = newTable;
0579:
0580: //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
0581:
0582: for (int i = oldCapacity; i-- > 0;) {
0583: for (Entry old = oldTable[i]; old != null;) {
0584: Entry e = old;
0585: old = old.next;
0586:
0587: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
0588: e.next = newTable[index];
0589: newTable[index] = e;
0590: }
0591: }
0592: }
0593:
0594: public void putAll(Map map) {
0595: Set keys = map.keySet();
0596: java.util.Iterator i = keys.iterator();
0597: while (i.hasNext()) {
0598: Object key = i.next();
0599: Object value = map.get(key);
0600: put(key, value);
0601: }
0602: }
0603:
0604: /**
0605: * Maps the specified <code>key</code> to the specified
0606: * <code>value</code> in this hashlist. Neither the key nor the
0607: * value can be <code>null</code>.
0608: * <p>
0609: * The value can be retrieved by calling the <code>get</code> method
0610: * with a key that is equal to the original key.
0611: *
0612: * @param key the hashlist key.
0613: * @param value the value.
0614: * @return the previous value of the specified key in this hashlist,
0615: * or <code>null</code> if it did not have one.
0616: * @exception NullPointerException if the key or value is
0617: * <code>null</code>.
0618: * @see java.util.Hashlist#get(java.lang.Object)
0619: */
0620: public synchronized Object put(Object key, Object value) {
0621:
0622: // Make sure the value is not null
0623:
0624: if (key == null || value == null) {
0625: throw new NullPointerException();
0626: }
0627:
0628: // Makes sure the key is not already in the hashlist.
0629: Entry tab[] = table;
0630: int hash = key.hashCode();
0631: int index = (hash & 0x7FFFFFFF) % tab.length;
0632: for (Entry e = tab[index]; e != null; e = e.next) {
0633: if ((e.hash == hash) && e.key.equals(key)) {
0634: Object old = e.value;
0635: e.value = value;
0636: return old;
0637: }
0638: }
0639:
0640: if (count >= threshold) {
0641: // Rehash the table if the threshold is exceeded
0642: rehash();
0643: return put(key, value);
0644: }
0645:
0646: if (key instanceof Integer) {
0647: int i = ((Integer) key).intValue();
0648: if (i >= nextSequence) {
0649: nextSequence = i + 1;
0650: }
0651: }
0652:
0653: // Creates the new entry.
0654: Entry e = new Entry();
0655: e.hash = hash;
0656: e.key = key;
0657: e.value = value;
0658: e.next = tab[index];
0659: e.prevEntry = tail;
0660: e.nextEntry = null;
0661: tab[index] = e;
0662: count++;
0663:
0664: if (head == null) {
0665: head = e;
0666: }
0667: if (tail != null) {
0668: tail.nextEntry = e;
0669: }
0670: tail = e;
0671:
0672: return null;
0673: }
0674:
0675: protected synchronized Object putBefore(Object key, Object value,
0676: Entry before) {
0677:
0678: // Make sure the value is not null
0679:
0680: if (key == null || value == null) {
0681: throw new NullPointerException();
0682: }
0683:
0684: // Makes sure the key is not already in the hashlist.
0685: Entry tab[] = table;
0686: int hash = key.hashCode();
0687: int index = (hash & 0x7FFFFFFF) % tab.length;
0688: for (Entry e = tab[index]; e != null; e = e.next) {
0689: if ((e.hash == hash) && e.key.equals(key)) {
0690: Object old = e.value;
0691: e.value = value;
0692: return old;
0693: }
0694: }
0695:
0696: if (count >= threshold) {
0697: // Rehash the table if the threshold is exceeded
0698: rehash();
0699: return putBefore(key, value, before);
0700: }
0701:
0702: if (key instanceof Integer) {
0703: int i = ((Integer) key).intValue();
0704: if (i >= nextSequence) {
0705: nextSequence = i + 1;
0706: }
0707: }
0708:
0709: // Creates the new entry.
0710: Entry e = new Entry();
0711: e.hash = hash;
0712: e.key = key;
0713: e.value = value;
0714: e.next = tab[index];
0715: tab[index] = e;
0716: count++;
0717:
0718: if (before == null) {
0719: before = head;
0720: }
0721: if (before == null) {
0722: e.prevEntry = null;
0723: e.nextEntry = null;
0724: head = tail = e;
0725: } else if (before == head) {
0726: e.prevEntry = null;
0727: e.nextEntry = before;
0728: before.prevEntry = e;
0729: head = e;
0730: } else {
0731: Entry prev = before.prevEntry;
0732: e.prevEntry = prev;
0733: // previous if guarantees that (prev != null)
0734: prev.nextEntry = e;
0735: e.nextEntry = before;
0736: before.prevEntry = e;
0737: }
0738:
0739: return null;
0740: }
0741:
0742: /**
0743: * Maps the specified <code>key</code> to the specified
0744: * <code>value</code> in this hashlist. Neither the key nor the
0745: * value can be <code>null</code>.
0746: * <p>
0747: * The value can be retrieved by calling the <code>get</code> method
0748: * with a key that is equal to the original key.
0749: *
0750: * @param key the hashlist key.
0751: * @param value the value.
0752: * @return Holder where the key and value were stored
0753: * @exception NullPointerException if the key or value is
0754: * <code>null</code>.
0755: * @see java.util.Hashlist#getHolder(java.lang.Object)
0756: */
0757: public synchronized Holder putHolder(Object key, Object value) {
0758:
0759: // Make sure the value is not null
0760:
0761: if (key == null || value == null) {
0762: throw new NullPointerException();
0763: }
0764:
0765: // Makes sure the key is not already in the hashlist.
0766: Entry tab[] = table;
0767: int hash = key.hashCode();
0768: int index = (hash & 0x7FFFFFFF) % tab.length;
0769: for (Entry e = tab[index]; e != null; e = e.next) {
0770: if ((e.hash == hash) && e.key.equals(key)) {
0771: e.value = value;
0772: return e;
0773: }
0774: }
0775:
0776: if (count >= threshold) {
0777: // Rehash the table if the threshold is exceeded
0778: rehash();
0779: return putHolder(key, value);
0780: }
0781:
0782: if (key instanceof Integer) {
0783: int i = ((Integer) key).intValue();
0784: if (i >= nextSequence) {
0785: nextSequence = i + 1;
0786: }
0787: }
0788:
0789: // Creates the new entry.
0790: Entry e = new Entry();
0791: e.hash = hash;
0792: e.key = key;
0793: e.value = value;
0794: e.next = tab[index];
0795: e.prevEntry = tail;
0796: e.nextEntry = null;
0797: tab[index] = e;
0798: count++;
0799:
0800: if (head == null) {
0801: head = e;
0802: }
0803: if (tail != null) {
0804: tail.nextEntry = e;
0805: }
0806: tail = e;
0807:
0808: return e;
0809: }
0810:
0811: /**
0812: * Maps the specified <code>index</code> to the specified
0813: * <code>value</code> in this hashlist. Neither the index nor the
0814: * value can be <code>null</code>.
0815: * <p>
0816: * The value can be retrieved by calling the <code>get</code> method
0817: * with a key that is equal to the original key.
0818: *
0819: * @param index the hashlist index.
0820: * @param value the value.
0821: * @return the previous value of the specified key in this hashlist,
0822: * or <code>null</code> if it did not have one.
0823: * @exception NullPointerException if the index or value is
0824: * <code>null</code>.
0825: * @see java.util.Hashlist#get(int)
0826: */
0827: public Object put(int index, Object value) {
0828: return put(new Integer(index), value);
0829: }
0830:
0831: /**
0832: * Maps the specified <code>index</code> to the specified
0833: * <code>value</code> in this hashlist. Neither the index nor the
0834: * value can be <code>null</code>.
0835: * <p>
0836: * The value can be retrieved by calling the <code>get</code> method
0837: * with a key that is equal to the original key.
0838: *
0839: * @param index the hashlist index.
0840: * @param value the value.
0841: * @return Holder where key and value were stored
0842: * @exception NullPointerException if the index or value is
0843: * <code>null</code>.
0844: * @see java.util.Hashlist#get(java.lang.Integer)
0845: */
0846: public Holder putHolder(int index, Object value) {
0847: return putHolder(new Integer(index), value);
0848: }
0849:
0850: protected Object putBefore(int index, Object value, Entry entry) {
0851: return putBefore(new Integer(index), value, entry);
0852: }
0853:
0854: protected Object putBefore(Object value, Entry entry) {
0855: return putBefore(new Integer(nextSequence), value, entry);
0856: }
0857:
0858: /**
0859: * Removes the key (and its corresponding value) from this
0860: * hashlist. This method does nothing if the key is not in the hashlist.
0861: *
0862: * @param key the key that needs to be removed.
0863: * @return the value to which the key had been mapped in this hashlist,
0864: * or <code>null</code> if the key did not have a mapping.
0865: */
0866: public synchronized Object remove(Object key) {
0867: Entry tab[] = table;
0868: int hash = key.hashCode();
0869: int index = (hash & 0x7FFFFFFF) % tab.length;
0870: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
0871: if ((e.hash == hash) && e.key.equals(key)) {
0872:
0873: if (prev != null) {
0874: prev.next = e.next;
0875: } else {
0876: tab[index] = e.next;
0877: }
0878:
0879: if (head == e) {
0880: head = e.nextEntry;
0881: }
0882: if (tail == e) {
0883: tail = e.prevEntry;
0884: }
0885:
0886: if (e.nextEntry != null) {
0887: e.nextEntry.prevEntry = e.prevEntry;
0888: }
0889: if (e.prevEntry != null) {
0890: e.prevEntry.nextEntry = e.nextEntry;
0891: }
0892:
0893: count--;
0894: return e.value;
0895: }
0896: }
0897: return null;
0898: }
0899:
0900: /**
0901: * Clears this hashlist so that it contains no keys.
0902: *
0903: */
0904: public synchronized void clear() {
0905: Entry tab[] = table;
0906: for (int index = tab.length; --index >= 0;) {
0907: tab[index] = null;
0908: }
0909: head = null;
0910: tail = null;
0911: count = 0;
0912: nextSequence = 0;
0913: }
0914:
0915: /**
0916: * Creates a shallow copy of this hashlist. The keys and values
0917: * themselves are not cloned.
0918: * This is a rather expensive operation.
0919: *
0920: * @return a clone of the hashlist.
0921: */
0922: public synchronized Object clone() {
0923: Entry p = head;
0924: Hashlist t = new Hashlist(table.length, loadFactor);
0925: while (p != null) {
0926: t.put(p.key, p.value);
0927: p = p.nextEntry;
0928: }
0929: return t;
0930: }
0931:
0932: /**
0933: * Returns a rather long string representation of this hashlist.
0934: *
0935: * @return a string representation of this hashlist.
0936: */
0937: public synchronized String toString() {
0938: StringBuffer buf = new StringBuffer();
0939: Entry e = head;
0940: boolean first = true;
0941: int max = size() - 1;
0942:
0943: buf.append('[');
0944:
0945: while (e != null) {
0946: if (first) {
0947: first = false;
0948: } else {
0949: buf.append(',');
0950: buf.append(' ');
0951: }
0952: buf.append(e.key.toString());
0953: buf.append('=');
0954: buf.append(e.value.toString());
0955: e = e.nextEntry;
0956: }
0957:
0958: buf.append(']');
0959:
0960: return buf.toString();
0961: }
0962:
0963: /**
0964: * Gets the next available integer slot.
0965: *
0966: * @return Sequence
0967: */
0968: public synchronized int getNextSequence() {
0969: return nextSequence;
0970: }
0971:
0972: /**
0973: * List operations
0974: */
0975:
0976: protected Entry entryAt(int index) {
0977: if ((index < 0) || (index >= count)) {
0978: return null;
0979: } else if (index < count / 2) {
0980: Entry e = head;
0981: while (e != null) {
0982: if ((index--) <= 0) {
0983: return e;
0984: }
0985: e = e.nextEntry;
0986: }
0987: } else {
0988: index = count - index;
0989: Entry e = tail;
0990: while (e != null) {
0991: if ((--index) <= 0) {
0992: return e;
0993: }
0994: e = e.prevEntry;
0995: }
0996: }
0997: return null;
0998: }
0999:
1000: public synchronized int indexOf(Object key) {
1001: Entry start = getEntry(key);
1002: if (start != null) {
1003: Entry end = start;
1004: int pos = 0;
1005: for (;;) {
1006: pos++;
1007: start = start.prevEntry;
1008: end = end.prevEntry;
1009: if (start == null) {
1010: return pos - 1;
1011: } else if (end == null) {
1012: return count - pos;
1013: }
1014: }
1015: } else {
1016: return -1;
1017: }
1018: }
1019:
1020: public synchronized Holder holderAt(int index) {
1021: return entryAt(index);
1022: }
1023:
1024: public synchronized Object keyAt(int index) {
1025: Entry e = entryAt(index);
1026: return (e != null) ? e.key : null;
1027: }
1028:
1029: public synchronized Object elementAt(int index) {
1030: Entry e = entryAt(index);
1031: return (e != null) ? e.value : null;
1032: }
1033:
1034: public synchronized boolean addAll(Collection c) {
1035: return true;
1036: }
1037:
1038: public synchronized Hashlist add(Object value) {
1039: put(nextSequence, value);
1040: return this ;
1041: }
1042:
1043: public Hashlist add(int index, Object value) {
1044: put(index, value);
1045: return this ;
1046: }
1047:
1048: public Hashlist add(Object key, Object value) {
1049: put(key, value);
1050: return this ;
1051: }
1052:
1053: public synchronized Hashlist insert(Object value) {
1054: putBefore(new Integer(nextSequence), value, this .head);
1055: return this ;
1056: }
1057:
1058: public synchronized Hashlist insert(Object key, Object value) {
1059: putBefore(key, value, this .head);
1060: return this ;
1061: }
1062:
1063: public synchronized Hashlist insertAt(int index, Object key,
1064: Object value) {
1065: if (index >= count) {
1066: add(key, value);
1067: } else {
1068: putBefore(key, value, entryAt(index));
1069: }
1070: return this ;
1071: }
1072:
1073: public synchronized Hashlist insertAt(int index, Object value) {
1074: if (index >= count) {
1075: add(value);
1076: } else {
1077: putBefore(new Integer(nextSequence), value, entryAt(index));
1078: }
1079: return this ;
1080: }
1081:
1082: public synchronized Object setAt(int index, Object value) {
1083: Entry e = entryAt(index);
1084: if (e != null) {
1085: Object old = e.value;
1086: e.value = value;
1087: return old;
1088: } else {
1089: return null;
1090: }
1091: }
1092:
1093: public synchronized Object removeAt(int index) {
1094: Entry e = entryAt(index);
1095: if (e != null) {
1096: return remove(e.key);
1097: } else {
1098: return null;
1099: }
1100: }
1101:
1102: public synchronized Holder previousOf(Object index) {
1103: Entry e = getEntry(index);
1104: if (e != null) {
1105: e = e.prevEntry;
1106: }
1107: return e;
1108: }
1109:
1110: public synchronized Holder nextOf(Object index) {
1111: Entry e = getEntry(index);
1112: if (e != null) {
1113: e = e.nextEntry;
1114: }
1115: return e;
1116: }
1117:
1118: public synchronized Object[] toArray() {
1119: Object[] array = new Object[count];
1120: Entry p = head;
1121: int i = 0;
1122: while (p != null) {
1123: array[i++] = p.value;
1124: p = p.nextEntry;
1125: }
1126: return array;
1127: }
1128:
1129: public synchronized Object[] toArray(Class ofClass) {
1130: Object[] array = (Object[]) java.lang.reflect.Array
1131: .newInstance(ofClass, count);
1132: Entry p = head;
1133: int i = 0;
1134: while (p != null) {
1135: array[i++] = p.value;
1136: p = p.nextEntry;
1137: }
1138: return array;
1139: }
1140:
1141: public synchronized Hashlist slice(int start, int length) {
1142: boolean forward = true;
1143: if (length < 0) {
1144: length = -length;
1145: start -= (length - 1);
1146: forward = false;
1147: }
1148: if (start < 0) {
1149: length -= -start;
1150: if (length < 0) {
1151: length = 0;
1152: }
1153: start = 0;
1154: } else if (start > count) {
1155: start = count;
1156: }
1157: if (start + length > count) {
1158: length = count - start;
1159: }
1160: if (length > 0) {
1161: Hashlist slice = new Hashlist(4 * length / 3);
1162: if (forward) {
1163: Entry p = entryAt(start);
1164: while (length-- > 0) {
1165: slice.put(p.key, p.value);
1166: p = p.nextEntry;
1167: }
1168: } else {
1169: Entry p = entryAt(start + length - 1);
1170: while (length-- > 0) {
1171: slice.put(p.key, p.value);
1172: p = p.prevEntry;
1173: }
1174: }
1175: return slice;
1176: } else {
1177: return null;
1178: }
1179: }
1180:
1181: public synchronized Hashlist cut(int start, int length) {
1182: if (length < 0) {
1183: length = -length;
1184: start -= (length - 1);
1185: }
1186: if (start < 0) {
1187: length -= -start;
1188: if (length < 0) {
1189: length = 0;
1190: }
1191: start = 0;
1192: } else if (start > count) {
1193: start = count;
1194: }
1195: if (start + length > count) {
1196: length = count - start;
1197: }
1198:
1199: Entry p = entryAt(start);
1200: Entry q;
1201: while (length-- > 0) {
1202: q = p.nextEntry;
1203: remove(p.key);
1204: p = q;
1205: }
1206:
1207: return this ;
1208: }
1209:
1210: public synchronized Hashlist insert(int start, int length,
1211: Hashlist array) {
1212: if (length < 0) {
1213: length = -length;
1214: start -= (length - 1);
1215: }
1216: if (start < 0) {
1217: length -= -start;
1218: if (length < 0) {
1219: length = 0;
1220: }
1221: start = 0;
1222: } else if (start > count) {
1223: start = count;
1224: }
1225: if (start + length > count) {
1226: length = count - start;
1227: }
1228:
1229: Entry p = entryAt(start);
1230: Entry q;
1231: while (length-- > 0) {
1232: q = p.nextEntry;
1233: remove(p.key);
1234: p = q;
1235: }
1236: if (p == null) {
1237: q = array.head;
1238: while (q != null) {
1239: add(q.value);
1240: q = q.nextEntry;
1241: }
1242: } else {
1243: q = array.tail;
1244: while (q != null) {
1245: putBefore(q.value, p);
1246: q = q.prevEntry;
1247: }
1248: }
1249: return this ;
1250: }
1251:
1252: public synchronized Hashlist union(Hashlist array) {
1253: Entry p = array.head;
1254: while (p != null) {
1255: if (!containsKey(p.key)) {
1256: put(p.key, p.value);
1257: }
1258: p = p.nextEntry;
1259: }
1260: return this ;
1261: }
1262:
1263: public synchronized Hashlist intersect(Hashlist array) {
1264: Entry p = head;
1265: while (p != null) {
1266: if (!array.containsKey(p.key)) {
1267: remove(p.key);
1268: }
1269: p = p.nextEntry;
1270: }
1271: return this ;
1272: }
1273:
1274: public synchronized Hashlist sort(Comparator comparator,
1275: boolean ascending) {
1276: if (count == 2) {
1277: if (comparator.compare(head, tail) > 0) {
1278: Entry p = head;
1279: head = tail;
1280: tail = p;
1281: head.nextEntry = tail;
1282: head.prevEntry = null;
1283: tail.nextEntry = null;
1284: tail.prevEntry = head;
1285: }
1286: } else if (count > 2) {
1287: int i = 0;
1288: int n = count;
1289: Entry[] array = new Entry[n];
1290: if (ascending) {
1291: Entry p = head;
1292: while (p != null) {
1293: array[i++] = p;
1294: p = p.nextEntry;
1295: }
1296: } else {
1297: Entry p = tail;
1298: while (p != null) {
1299: array[i++] = p;
1300: p = p.prevEntry;
1301: }
1302: }
1303: java.util.Arrays.sort(array, comparator);
1304: Entry p;
1305: n--;
1306: for (i = 0; i <= n; i++) {
1307: p = array[i];
1308: p.prevEntry = (i > 0) ? array[i - 1] : null;
1309: p.nextEntry = (i < n) ? array[i + 1] : null;
1310: }
1311: head = array[0];
1312: tail = array[n];
1313: }
1314: return this ;
1315: }
1316:
1317: /**
1318: * WriteObject is called to save the state of the hashlist to a stream.
1319: * Only the keys and values are serialized since the hash values may be
1320: * different when the contents are restored.
1321: * iterate over the contents and write out the keys and values.
1322: */
1323: private synchronized void writeObject(java.io.ObjectOutputStream s)
1324: throws IOException {
1325: // Write out the length, threshold, loadfactor
1326: s.defaultWriteObject();
1327:
1328: // Write out length, count of elements and then the key/value objects
1329: s.writeInt(table.length);
1330: s.writeInt(count);
1331: Entry entry = head;
1332: while (entry != null) {
1333: s.writeObject(entry.key);
1334: s.writeObject(entry.value);
1335: entry = entry.nextEntry;
1336: }
1337: }
1338:
1339: /**
1340: * readObject is called to restore the state of the hashlist from
1341: * a stream. Only the keys and values are serialized since the
1342: * hash values may be different when the contents are restored.
1343: * Read count elements and insert into the hashlist.
1344: */
1345: private synchronized void readObject(java.io.ObjectInputStream s)
1346: throws IOException, ClassNotFoundException {
1347: // Read in the length, threshold, and loadfactor
1348: s.defaultReadObject();
1349:
1350: // Read the original length of the array and number of elements
1351: int origlength = s.readInt();
1352: int elements = s.readInt();
1353:
1354: // Compute new size with a bit of room 5% to grow but
1355: // No larger than the original size. Make the length
1356: // odd if it's large enough, this helps distribute the entries.
1357: // Guard against the length ending up zero, that's not valid.
1358: int length = (int) (elements * loadFactor) + (elements / 20)
1359: + 3;
1360: if (length > elements && (length & 1) == 0)
1361: length--;
1362: if (origlength > 0 && length > origlength)
1363: length = origlength;
1364:
1365: table = new Entry[length];
1366: count = 0;
1367:
1368: // Read the number of elements and then all the key/value objects
1369: for (; elements > 0; elements--) {
1370: Object key = s.readObject();
1371: Object value = s.readObject();
1372: put(key, value);
1373: }
1374: }
1375:
1376: }
|