Mercurial > lasercutter
comparison src/clojure/lang/PersistentArrayMap.java @ 10:ef7dbbd6452c
added clojure source goodness
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 21 Aug 2010 06:25:44 -0400 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
9:35cf337adfcf | 10:ef7dbbd6452c |
---|---|
1 /** | |
2 * Copyright (c) Rich Hickey. All rights reserved. | |
3 * The use and distribution terms for this software are covered by the | |
4 * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) | |
5 * which can be found in the file epl-v10.html at the root of this distribution. | |
6 * By using this software in any fashion, you are agreeing to be bound by | |
7 * the terms of this license. | |
8 * You must not remove this notice, or any other, from this software. | |
9 **/ | |
10 | |
11 package clojure.lang; | |
12 | |
13 import java.io.Serializable; | |
14 import java.util.Arrays; | |
15 import java.util.Iterator; | |
16 import java.util.Map; | |
17 | |
18 /** | |
19 * Simple implementation of persistent map on an array | |
20 * <p/> | |
21 * Note that instances of this class are constant values | |
22 * i.e. add/remove etc return new values | |
23 * <p/> | |
24 * Copies array on every change, so only appropriate for _very_small_ maps | |
25 * <p/> | |
26 * null keys and values are ok, but you won't be able to distinguish a null value via valAt - use contains/entryAt | |
27 */ | |
28 | |
29 public class PersistentArrayMap extends APersistentMap implements IObj, IEditableCollection { | |
30 | |
31 final Object[] array; | |
32 static final int HASHTABLE_THRESHOLD = 16; | |
33 | |
34 public static final PersistentArrayMap EMPTY = new PersistentArrayMap(); | |
35 private final IPersistentMap _meta; | |
36 | |
37 static public IPersistentMap create(Map other){ | |
38 ITransientMap ret = EMPTY.asTransient(); | |
39 for(Object o : other.entrySet()) | |
40 { | |
41 Map.Entry e = (Entry) o; | |
42 ret = ret.assoc(e.getKey(), e.getValue()); | |
43 } | |
44 return ret.persistent(); | |
45 } | |
46 | |
47 protected PersistentArrayMap(){ | |
48 this.array = new Object[]{}; | |
49 this._meta = null; | |
50 } | |
51 | |
52 public PersistentArrayMap withMeta(IPersistentMap meta){ | |
53 return new PersistentArrayMap(meta, array); | |
54 } | |
55 | |
56 PersistentArrayMap create(Object... init){ | |
57 return new PersistentArrayMap(meta(), init); | |
58 } | |
59 | |
60 IPersistentMap createHT(Object[] init){ | |
61 return PersistentHashMap.create(meta(), init); | |
62 } | |
63 | |
64 static public PersistentArrayMap createWithCheck(Object[] init){ | |
65 for(int i=0;i< init.length;i += 2) | |
66 { | |
67 for(int j=i+2;j<init.length;j += 2) | |
68 { | |
69 if(equalKey(init[i],init[j])) | |
70 throw new IllegalArgumentException("Duplicate key: " + init[i]); | |
71 } | |
72 } | |
73 return new PersistentArrayMap(init); | |
74 } | |
75 /** | |
76 * This ctor captures/aliases the passed array, so do not modify later | |
77 * | |
78 * @param init {key1,val1,key2,val2,...} | |
79 */ | |
80 public PersistentArrayMap(Object[] init){ | |
81 this.array = init; | |
82 this._meta = null; | |
83 } | |
84 | |
85 | |
86 public PersistentArrayMap(IPersistentMap meta, Object[] init){ | |
87 this._meta = meta; | |
88 this.array = init; | |
89 } | |
90 | |
91 public int count(){ | |
92 return array.length / 2; | |
93 } | |
94 | |
95 public boolean containsKey(Object key){ | |
96 return indexOf(key) >= 0; | |
97 } | |
98 | |
99 public IMapEntry entryAt(Object key){ | |
100 int i = indexOf(key); | |
101 if(i >= 0) | |
102 return new MapEntry(array[i],array[i+1]); | |
103 return null; | |
104 } | |
105 | |
106 public IPersistentMap assocEx(Object key, Object val) throws Exception{ | |
107 int i = indexOf(key); | |
108 Object[] newArray; | |
109 if(i >= 0) | |
110 { | |
111 throw new Exception("Key already present"); | |
112 } | |
113 else //didn't have key, grow | |
114 { | |
115 if(array.length > HASHTABLE_THRESHOLD) | |
116 return createHT(array).assocEx(key, val); | |
117 newArray = new Object[array.length + 2]; | |
118 if(array.length > 0) | |
119 System.arraycopy(array, 0, newArray, 2, array.length); | |
120 newArray[0] = key; | |
121 newArray[1] = val; | |
122 } | |
123 return create(newArray); | |
124 } | |
125 | |
126 public IPersistentMap assoc(Object key, Object val){ | |
127 int i = indexOf(key); | |
128 Object[] newArray; | |
129 if(i >= 0) //already have key, same-sized replacement | |
130 { | |
131 if(array[i + 1] == val) //no change, no op | |
132 return this; | |
133 newArray = array.clone(); | |
134 newArray[i + 1] = val; | |
135 } | |
136 else //didn't have key, grow | |
137 { | |
138 if(array.length > HASHTABLE_THRESHOLD) | |
139 return createHT(array).assoc(key, val); | |
140 newArray = new Object[array.length + 2]; | |
141 if(array.length > 0) | |
142 System.arraycopy(array, 0, newArray, 2, array.length); | |
143 newArray[0] = key; | |
144 newArray[1] = val; | |
145 } | |
146 return create(newArray); | |
147 } | |
148 | |
149 public IPersistentMap without(Object key){ | |
150 int i = indexOf(key); | |
151 if(i >= 0) //have key, will remove | |
152 { | |
153 int newlen = array.length - 2; | |
154 if(newlen == 0) | |
155 return empty(); | |
156 Object[] newArray = new Object[newlen]; | |
157 for(int s = 0, d = 0; s < array.length; s += 2) | |
158 { | |
159 if(!equalKey(array[s], key)) //skip removal key | |
160 { | |
161 newArray[d] = array[s]; | |
162 newArray[d + 1] = array[s + 1]; | |
163 d += 2; | |
164 } | |
165 } | |
166 return create(newArray); | |
167 } | |
168 //don't have key, no op | |
169 return this; | |
170 } | |
171 | |
172 public IPersistentMap empty(){ | |
173 return (IPersistentMap) EMPTY.withMeta(meta()); | |
174 } | |
175 | |
176 final public Object valAt(Object key, Object notFound){ | |
177 int i = indexOf(key); | |
178 if(i >= 0) | |
179 return array[i + 1]; | |
180 return notFound; | |
181 } | |
182 | |
183 public Object valAt(Object key){ | |
184 return valAt(key, null); | |
185 } | |
186 | |
187 public int capacity(){ | |
188 return count(); | |
189 } | |
190 | |
191 private int indexOf(Object key){ | |
192 for(int i = 0; i < array.length; i += 2) | |
193 { | |
194 if(equalKey(array[i], key)) | |
195 return i; | |
196 } | |
197 return -1; | |
198 } | |
199 | |
200 static boolean equalKey(Object k1, Object k2){ | |
201 if(k1 == null) | |
202 return k2 == null; | |
203 return k1.equals(k2); | |
204 } | |
205 | |
206 public Iterator iterator(){ | |
207 return new Iter(array); | |
208 } | |
209 | |
210 public ISeq seq(){ | |
211 if(array.length > 0) | |
212 return new Seq(array, 0); | |
213 return null; | |
214 } | |
215 | |
216 public IPersistentMap meta(){ | |
217 return _meta; | |
218 } | |
219 | |
220 static class Seq extends ASeq implements Counted{ | |
221 final Object[] array; | |
222 final int i; | |
223 | |
224 Seq(Object[] array, int i){ | |
225 this.array = array; | |
226 this.i = i; | |
227 } | |
228 | |
229 public Seq(IPersistentMap meta, Object[] array, int i){ | |
230 super(meta); | |
231 this.array = array; | |
232 this.i = i; | |
233 } | |
234 | |
235 public Object first(){ | |
236 return new MapEntry(array[i],array[i+1]); | |
237 } | |
238 | |
239 public ISeq next(){ | |
240 if(i + 2 < array.length) | |
241 return new Seq(array, i + 2); | |
242 return null; | |
243 } | |
244 | |
245 public int count(){ | |
246 return (array.length - i) / 2; | |
247 } | |
248 | |
249 public Obj withMeta(IPersistentMap meta){ | |
250 return new Seq(meta, array, i); | |
251 } | |
252 } | |
253 | |
254 static class Iter implements Iterator{ | |
255 Object[] array; | |
256 int i; | |
257 | |
258 //for iterator | |
259 Iter(Object[] array){ | |
260 this(array, -2); | |
261 } | |
262 | |
263 //for entryAt | |
264 Iter(Object[] array, int i){ | |
265 this.array = array; | |
266 this.i = i; | |
267 } | |
268 | |
269 public boolean hasNext(){ | |
270 return i < array.length - 2; | |
271 } | |
272 | |
273 public Object next(){ | |
274 i += 2; | |
275 return new MapEntry(array[i],array[i+1]); | |
276 } | |
277 | |
278 public void remove(){ | |
279 throw new UnsupportedOperationException(); | |
280 } | |
281 | |
282 } | |
283 | |
284 public ITransientMap asTransient(){ | |
285 return new TransientArrayMap(array); | |
286 } | |
287 | |
288 static final class TransientArrayMap extends ATransientMap { | |
289 int len; | |
290 final Object[] array; | |
291 Thread owner; | |
292 | |
293 public TransientArrayMap(Object[] array){ | |
294 this.owner = Thread.currentThread(); | |
295 this.array = new Object[Math.max(HASHTABLE_THRESHOLD, array.length)]; | |
296 System.arraycopy(array, 0, this.array, 0, array.length); | |
297 this.len = array.length; | |
298 } | |
299 | |
300 private int indexOf(Object key){ | |
301 for(int i = 0; i < len; i += 2) | |
302 { | |
303 if(equalKey(array[i], key)) | |
304 return i; | |
305 } | |
306 return -1; | |
307 } | |
308 | |
309 ITransientMap doAssoc(Object key, Object val){ | |
310 int i = indexOf(key); | |
311 if(i >= 0) //already have key, | |
312 { | |
313 if(array[i + 1] != val) //no change, no op | |
314 array[i + 1] = val; | |
315 } | |
316 else //didn't have key, grow | |
317 { | |
318 if(len >= array.length) | |
319 return PersistentHashMap.create(array).asTransient().assoc(key, val); | |
320 array[len++] = key; | |
321 array[len++] = val; | |
322 } | |
323 return this; | |
324 } | |
325 | |
326 ITransientMap doWithout(Object key) { | |
327 int i = indexOf(key); | |
328 if(i >= 0) //have key, will remove | |
329 { | |
330 if (len >= 2) | |
331 { | |
332 array[i] = array[len - 2]; | |
333 array[i + 1] = array[len - 1]; | |
334 } | |
335 len -= 2; | |
336 } | |
337 return this; | |
338 } | |
339 | |
340 Object doValAt(Object key, Object notFound) { | |
341 int i = indexOf(key); | |
342 if (i >= 0) | |
343 return array[i + 1]; | |
344 return notFound; | |
345 } | |
346 | |
347 int doCount() { | |
348 return len / 2; | |
349 } | |
350 | |
351 IPersistentMap doPersistent(){ | |
352 ensureEditable(); | |
353 owner = null; | |
354 Object[] a = new Object[len]; | |
355 System.arraycopy(array,0,a,0,len); | |
356 return new PersistentArrayMap(a); | |
357 } | |
358 | |
359 void ensureEditable(){ | |
360 if(owner == Thread.currentThread()) | |
361 return; | |
362 if(owner != null) | |
363 throw new IllegalAccessError("Transient used by non-owner thread"); | |
364 throw new IllegalAccessError("Transient used after persistent! call"); | |
365 } | |
366 } | |
367 } |