001: package com.quadcap.util.collections;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.util.Iterator;
042:
043: import com.quadcap.util.Debug;
044:
045: /**
046: * A map with long values as keys
047: *
048: * @author Stan Bailes
049: */
050: public class LongMap {
051: int size = 0;
052: Entry[] entries;
053: Entry freeList;
054:
055: /**
056: * Create an empty map with a specified number of buckets.
057: */
058: public LongMap(int initSize) {
059: initSize |= 1;
060: while (!isPrime(initSize))
061: initSize += 2;
062: entries = new Entry[initSize];
063: }
064:
065: /**
066: * Return the Object with the specified key value
067: */
068: public synchronized final Object get(long key) {
069: int h = hash(key);
070: for (Entry entry = entries[h]; entry != null; entry = entry.next) {
071: if (entry.key == key)
072: return entry.val;
073: }
074: return null;
075: }
076:
077: /**
078: * Insert a key, value pair
079: */
080: public synchronized final void put(long key, Object val) {
081: int h = hash(key);
082: for (Entry entry = entries[h]; entry != null; entry = entry.next) {
083: if (entry.key == key) {
084: entry.val = val;
085: return;
086: }
087: }
088: Entry entry = getEntry(key, val);
089: entry.next = entries[h];
090: entries[h] = entry;
091: }
092:
093: /**
094: * Remove the specified key
095: */
096: public synchronized final void remove(long key) {
097: int h = hash(key);
098: Entry prev = null;
099: Entry entry = entries[h];
100: while (entry != null) {
101: Entry next = entry.next;
102: if (entry.key == key) {
103: if (prev == null) {
104: entries[h] = next;
105: } else {
106: prev.next = next;
107: }
108: freeEntry(entry);
109: return;
110: }
111: prev = entry;
112: entry = next;
113: }
114: }
115:
116: public String toString() {
117: StringBuffer sb = new StringBuffer("{");
118: LongIterator k = keys();
119: String delim = "";
120: while (k.hasNext()) {
121: long v = k.nextLong();
122: Object d = get(v);
123: sb.append(delim);
124: sb.append(v);
125: sb.append('=');
126: sb.append(String.valueOf(d));
127: delim = ",";
128: }
129: sb.append("}");
130: return sb.toString();
131: }
132:
133: /**
134: * Return the number of entries
135: */
136: public final int size() {
137: return size;
138: }
139:
140: public final int buckets() {
141: return entries.length;
142: }
143:
144: //-------------------------------------------------------
145: final Entry getEntry(long key, Object val) {
146: Entry entry = freeList;
147: if (entry == null) {
148: entry = new Entry();
149: } else {
150: freeList = entry.next;
151: }
152: entry.key = key;
153: entry.val = val;
154: size++;
155: return entry;
156: }
157:
158: final void freeEntry(Entry entry) {
159: size--;
160: entry.val = null;
161: entry.next = freeList;
162: freeList = entry;
163: }
164:
165: final boolean isPrime(int x) {
166: return IntMap.isPrime(x);
167: }
168:
169: public LongIterator keys() {
170: return new LongMapIterator(this );
171: }
172:
173: final int hash(long key) {
174: int h = (int) (key % entries.length);
175: if (h < 0) {
176: h = 0 - h;
177: }
178: return h;
179: }
180:
181: class Entry {
182: long key;
183: Object val;
184: Entry next;
185: }
186:
187: public class LongMapIterator implements LongIterator {
188: LongMap map;
189: int epos = 0;
190: Entry entry = null;
191: Entry last = null;
192:
193: public LongMapIterator(LongMap map) {
194: this .map = map;
195: advance();
196: }
197:
198: public boolean hasNext() {
199: return entry != null;
200: }
201:
202: void advance() {
203: last = entry;
204: if (entry != null && entry.next != null) {
205: entry = entry.next;
206: } else {
207: entry = null;
208: }
209: while (epos < map.entries.length && entry == null) {
210: entry = map.entries[epos++];
211: }
212: }
213:
214: public Object next() {
215: Long ret = null;
216: if (entry != null) {
217: ret = new Long(entry.key);
218: advance();
219: }
220: return ret;
221: }
222:
223: public long nextLong() {
224: long ret = 0;
225: if (entry != null) {
226: ret = entry.key;
227: advance();
228: }
229: return ret;
230: }
231:
232: public void remove() {
233: if (last != null) {
234: map.remove(last.key);
235: last = null;
236: }
237: }
238: }
239: }
|