Mercurial > lasercutter

annotate src/clojure/lang/PersistentArrayMap.java @ 10:ef7dbbd6452c

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