Source code: com/port80/util/struct/IntValueHashMap.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.util.struct;
6
7 import java.util.ArrayList;
8 import java.util.HashMap;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.List;
12 import java.util.Map;
13 import java.util.Set;
14 import java.util.TreeSet;
15
16 import com.port80.util.msg;
17 import com.port80.util.sprint;
18
19 /** Object->int hash.
20 */
21 public class IntValueHashMap {
22
23 // Instance fields /////////////////////////////////////////////////////
24 //
25
26 public Object[] keyTable;
27 public int[] valueTable;
28 int size; /** Number of entries. */
29 int capacity; /** Size of hash table. */
30 int threshold; /** Capacity increase if size>=threshold. */
31
32 // Constructors ////////////////////////////////////////////////////////
33 //
34
35 public IntValueHashMap() {this(13);}
36
37 public IntValueHashMap(int threshold) {
38 size=0;
39 this.threshold=threshold;
40 capacity=(int)(threshold*1.75f);
41 if (capacity==threshold) capacity++;
42 keyTable = new Object[capacity];
43 valueTable = new int[capacity];
44 }
45
46
47 // Instance methods ////////////////////////////////////////////////////
48 //
49
50 public boolean containsKey(Object key) {
51 int index=(key.hashCode() & 0x7FFFFFFF) % capacity;
52 Object currentKey;
53 while ((currentKey=keyTable[index]) != null) {
54 if (currentKey.equals(key)) return true;
55 index=(index + 1) % keyTable.length;
56 }
57 return false;
58 }
59 /**
60 * Returns the value at the given key.
61 * Returns -1 if not found.
62 */
63 public int get(Object key) {
64 int index=(key.hashCode() & 0x7FFFFFFF) % capacity;
65 Object k;
66 while ((k=keyTable[index]) != null) {
67 if (k.equals(key)) return valueTable[index];
68 index=(index + 1) % capacity;
69 }
70 return -1;
71 }
72 public int put(Object key, int value) {
73 int index=(key.hashCode() & 0x7FFFFFFF) % capacity;
74 Object k;
75 while ((k=keyTable[index]) != null) {
76 if (k.equals(key)) {
77 int ret=valueTable[index];
78 valueTable[index]=value;
79 return ret;
80 }
81 index=(index + 1) % capacity;
82 }
83 keyTable[index]=key;
84 valueTable[index]=value;
85
86 // assumes the threshold is never equal to the size of the table
87 if (++size > threshold) rehash();
88 return value;
89 }
90 public int size() {
91 return size;
92 }
93 /** Return the keys.
94 */
95 public Set keySet() {
96 Set ret=new HashSet();
97 for(int i=0; i<capacity; ++i) {
98 if(keyTable[i]!=null) ret.add(keyTable[i]);
99 }
100 return ret;
101 }
102
103 /**
104 * @return keys sorted by their values. More efficient if max *
105 * value is known.
106 */
107 public Object[] sortedKeys(int maxValue) {
108 Object[] result=new Object[size];
109 int[] endPos=new int[maxValue+1];
110 for(int i=0; i<capacity; i++) {
111 Object key=keyTable[i];
112 if (key != null) {
113 for(int j=valueTable[i]; j <= maxValue; j++) {
114 endPos[j]++;
115 }
116 }
117 }
118
119 // store the keys in order of their values
120 for (int i=0; i<capacity; i++) {
121 Object key=keyTable[i];
122 if (key != null) {
123 int value=valueTable[i];
124 int index=--endPos[value];
125 result[index]=key;
126 }
127 }
128 return result;
129 }
130 public Object[] sortedKeys() {
131 Object[] ret=new Object[size];
132 Map sorted=new HashMap();
133 int n=0;
134 // Sort by counts.
135 for(Iterator it=keySet().iterator(); it.hasNext();) {
136 Object key=it.next();
137 String valuestr=sprint.f("%08d").a(get(key)).end();
138 List a=(List)sorted.get(valuestr);
139 if(a==null) a=new ArrayList();
140 a.add(key);
141 sorted.put(valuestr,a);
142 }
143 for(Iterator it=(new TreeSet(sorted.keySet()).iterator()); it.hasNext();) {
144 String valuestr=(String)it.next();
145 List a=(List)sorted.get(valuestr);
146 for(int i=0; i<a.size(); ++i) ret[n++]=a.get(i);
147 }
148 if(n!=size) msg.err("IntHash.sortedKeys(): n!=size");
149 return ret;
150 }
151 public String toString() {
152 StringBuffer buffer=new StringBuffer();
153 for (int i=0, length=capacity; i < length; i++) {
154 Object key=keyTable[i];
155 if (key != null) {
156 buffer.append(key);
157 buffer.append("->"); //$NON-NLS-1$
158 buffer.append(valueTable[i]);
159 buffer.append("\n"); //$NON-NLS-1$
160 }
161 }
162 return buffer.toString();
163 }
164
165 ////////////////////////////////////////////////////////////////////////
166
167 private void rehash() {
168 IntValueHashMap newHashtable=new IntValueHashMap(size * 2+1); // double the number of expected elements
169 Object k;
170 for (int i=capacity; --i >= 0;)
171 if ((k=keyTable[i]) != null)
172 newHashtable.put(k, valueTable[i]);
173
174 keyTable=newHashtable.keyTable;
175 valueTable=newHashtable.valueTable;
176 threshold=newHashtable.threshold;
177 capacity=newHashtable.capacity;
178 }
179
180 // Test ////////////////////////////////////////////////////////////////
181 //
182
183 public static void main(String[] args) {
184 test();
185 }
186
187 private static void test() {
188 IntValueHashMap h=new IntValueHashMap();
189 int[] data=new int[] {1,2,10,100,101,200,33,5,8,20,30};
190 for(int i=0; i<data.length; ++i) {
191 h.put(""+data[i],data[i]);
192 }
193 data=new int[] {2,3,15,10,33};
194 for(int i=0; i<data.length; ++i) {
195 h.put("a"+data[i],data[i]);
196 }
197 System.out.println("### toString():\n"+h.toString());
198 System.out.println("### keySet():\n"+h.keySet());
199 System.out.println("### sortedKeys():\n");
200 Object[] ret=h.sortedKeys();
201 for(int i=0; i<ret.length; i++) {
202 System.out.println("\t"+ret[i]+"="+h.get(ret[i]));
203 }
204 System.out.println("### sortedKeys(int):\n");
205 h.put("150",150);
206 h.put("33a",33);
207 h.put("2a",2);
208 ret=h.sortedKeys(200);
209 for(int i=0; i<ret.length; i++) {
210 System.out.println("\t"+ret[i]+"="+h.get(ret[i]));
211 }
212 }
213
214 ////////////////////////////////////////////////////////////////////////
215
216 }