KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > quadcap > util > collections > IntMap


1 package com.quadcap.util.collections;
2
3 /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
4  *
5  * This software is distributed under the Quadcap Free Software License.
6  * This software may be used or modified for any purpose, personal or
7  * commercial. Open Source redistributions are permitted. Commercial
8  * redistribution of larger works derived from, or works which bundle
9  * this software requires a "Commercial Redistribution License"; see
10  * http://www.quadcap.com/purchase.
11  *
12  * Redistributions qualify as "Open Source" under one of the following terms:
13  *
14  * Redistributions are made at no charge beyond the reasonable cost of
15  * materials and delivery.
16  *
17  * Redistributions are accompanied by a copy of the Source Code or by an
18  * irrevocable offer to provide a copy of the Source Code for up to three
19  * years at the cost of materials and delivery. Such redistributions
20  * must allow further use, modification, and redistribution of the Source
21  * Code under substantially the same terms as this license.
22  *
23  * Redistributions of source code must retain the copyright notices as they
24  * appear in each source code file, these license terms, and the
25  * disclaimer/limitation of liability set forth as paragraph 6 below.
26  *
27  * Redistributions in binary form must reproduce this Copyright Notice,
28  * these license terms, and the disclaimer/limitation of liability set
29  * forth as paragraph 6 below, in the documentation and/or other materials
30  * provided with the distribution.
31  *
32  * The Software is provided on an "AS IS" basis. No warranty is
33  * provided that the Software is free of defects, or fit for a
34  * particular purpose.
35  *
36  * Limitation of Liability. Quadcap Software shall not be liable
37  * for any damages suffered by the Licensee or any third party resulting
38  * from use of the Software.
39  */

40
41 import java.util.Iterator JavaDoc;
42
43 /**
44  * A map with integer keys
45  *
46  * @author Stan Bailes
47  */

48 public class IntMap {
49     int size;
50     Entry[] entries;
51     Entry freeList;
52     
53     public IntMap(int initSize) {
54         this.size = initSize | 1;
55         while (!isPrime(size)) size += 2;
56         entries = new Entry[size];
57     }
58     
59     public final Object JavaDoc get(int key) {
60         int h = hash(key);
61         for (Entry entry = entries[h]; entry != null; entry = entry.next) {
62             if (entry.key == key) return entry.val;
63         }
64         return null;
65     }
66
67     public final void put(int key, Object JavaDoc val) {
68         int h = hash(key);
69         Entry entry = getEntry(key, val);
70         entry.next = entries[h];
71         entries[h] = entry;
72     }
73
74     public final void remove(int key) {
75         int h = hash(key);
76         Entry prev = null;
77         for (Entry entry = entries[h]; entry != null; entry = entry.next) {
78             if (entry.key == key) {
79                 if (prev == null) {
80                     entries[h] = entry.next;
81                 } else {
82                     prev.next = entry.next;
83                 }
84                 freeEntry(entry);
85             }
86             prev = entry;
87         }
88     }
89
90     final Entry getEntry(int key, Object JavaDoc val) {
91         Entry entry = freeList;
92         if (entry == null) {
93             entry = new Entry();
94         } else {
95             freeList = entry.next;
96         }
97         entry.key = key;
98         entry.val = val;
99         return entry;
100     }
101
102     final void freeEntry(Entry entry) {
103         entry.next = freeList;
104         freeList = entry;
105     }
106
107     public final static boolean isPrime(int x) {
108         if ((x & 1) == 0) return false;
109         for (int i = 3; i*i <= x; i += 2) {
110             if ((x % i) == 0) return false;
111         }
112         return true;
113     }
114
115     public Iterator JavaDoc keys() {
116         return new IntMapIterator(this);
117     }
118
119     final int hash(int key) {
120         int h = key % size;
121         if (h < 0) {
122             h = 0 - h;
123         }
124         return h;
125     }
126
127     class Entry {
128         int key;
129         Object JavaDoc val;
130         Entry next;
131     }
132
133     class IntMapIterator implements Iterator JavaDoc {
134         IntMap map;
135         int epos = 0;
136         Entry entry = null;
137         
138         public IntMapIterator(IntMap map) { this.map = map; }
139
140         public boolean hasNext() {
141             while (epos < map.size && entry == null) {
142                 entry = map.entries[epos++];
143             }
144             return entry != null;
145         }
146
147         public Object JavaDoc next() {
148             Integer JavaDoc ret = null;
149             if (hasNext()) {
150                 ret = new Integer JavaDoc(entry.key);
151                 entry = entry.next;
152             }
153             return ret;
154         }
155
156         public void remove() {}
157     }
158         
159 }
160
Popular Tags