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: /**
044: * A map with integer keys
045: *
046: * @author Stan Bailes
047: */
048: public class IntMap {
049: int size;
050: Entry[] entries;
051: Entry freeList;
052:
053: public IntMap(int initSize) {
054: this .size = initSize | 1;
055: while (!isPrime(size))
056: size += 2;
057: entries = new Entry[size];
058: }
059:
060: public final Object get(int key) {
061: int h = hash(key);
062: for (Entry entry = entries[h]; entry != null; entry = entry.next) {
063: if (entry.key == key)
064: return entry.val;
065: }
066: return null;
067: }
068:
069: public final void put(int key, Object val) {
070: int h = hash(key);
071: Entry entry = getEntry(key, val);
072: entry.next = entries[h];
073: entries[h] = entry;
074: }
075:
076: public final void remove(int key) {
077: int h = hash(key);
078: Entry prev = null;
079: for (Entry entry = entries[h]; entry != null; entry = entry.next) {
080: if (entry.key == key) {
081: if (prev == null) {
082: entries[h] = entry.next;
083: } else {
084: prev.next = entry.next;
085: }
086: freeEntry(entry);
087: }
088: prev = entry;
089: }
090: }
091:
092: final Entry getEntry(int key, Object val) {
093: Entry entry = freeList;
094: if (entry == null) {
095: entry = new Entry();
096: } else {
097: freeList = entry.next;
098: }
099: entry.key = key;
100: entry.val = val;
101: return entry;
102: }
103:
104: final void freeEntry(Entry entry) {
105: entry.next = freeList;
106: freeList = entry;
107: }
108:
109: public final static boolean isPrime(int x) {
110: if ((x & 1) == 0)
111: return false;
112: for (int i = 3; i * i <= x; i += 2) {
113: if ((x % i) == 0)
114: return false;
115: }
116: return true;
117: }
118:
119: public Iterator keys() {
120: return new IntMapIterator(this );
121: }
122:
123: final int hash(int key) {
124: int h = key % size;
125: if (h < 0) {
126: h = 0 - h;
127: }
128: return h;
129: }
130:
131: class Entry {
132: int key;
133: Object val;
134: Entry next;
135: }
136:
137: class IntMapIterator implements Iterator {
138: IntMap map;
139: int epos = 0;
140: Entry entry = null;
141:
142: public IntMapIterator(IntMap map) {
143: this .map = map;
144: }
145:
146: public boolean hasNext() {
147: while (epos < map.size && entry == null) {
148: entry = map.entries[epos++];
149: }
150: return entry != null;
151: }
152:
153: public Object next() {
154: Integer ret = null;
155: if (hasNext()) {
156: ret = new Integer(entry.key);
157: entry = entry.next;
158: }
159: return ret;
160: }
161:
162: public void remove() {
163: }
164: }
165:
166: }
|