PyStringMap


1   // Copyright (c) Corporation for National Research Initiatives
2   package org.python.core;
3   
4   /**
5    * A faster Dictionary where the keys have to be strings.
6    * <p>
7    * This is the default for all __dict__ instances.
8    */
9   
10  public class PyStringMap extends PyObject
11  {
12      //Table of primes to cycle through
13      private static final int[] primes = {
14          7, 13, 31, 61, 127, 251, 509, 1021, 2017, 4093,
15          5987, 9551, 15683, 19609, 31397,
16          65521, 131071, 262139, 524287, 1048573, 2097143,
17          4194301, 8388593, 16777213, 33554393, 67108859,
18          134217689, 268435399, 536870909, 1073741789,};
19  
20      private transient String  [] keys;
21      private transient PyObject[] values;
22      private int size;
23      private transient int filled;
24      private transient int prime;
25      private transient int popfinger;
26  
27      /* Override serialization behavior */
28      private void writeObject(java.io.ObjectOutputStream   out)
29          throws java.io.IOException  
30      {
31          out.defaultWriteObject();
32  
33          String  [] keyTable = keys;
34          PyObject[] valueTable = values;
35          int n = keyTable.length;
36  
37          for (int i=0; i<n; i++) {
38              //String key = keyTable[i];
39              PyObject value = valueTable[i];
40              if (value == null)
41                  continue;
42              out.writeUTF(keys[i]);
43              out.writeObject(values[i]);
44          }
45      }
46  
47      private void readObject(java.io.ObjectInputStream   in)
48          throws java.io.IOException  , ClassNotFoundException  
49      {
50          in.defaultReadObject();
51  
52          prime = 1;
53          keys = null;
54          values = null;
55          int n = size;
56  
57          resize(n);
58  
59          for (int i=0; i<n; i++) {
60              String   key = in.readUTF().intern();
61              insertkey(key, (PyObject)in.readObject());
62          }
63      }
64      public PyStringMap(int capacity) {
65          prime = 0;
66          keys = null;
67          values = null;
68          resize(capacity);
69      }
70  
71      public PyStringMap() {
72          this(4);
73      }
74  
75      public PyStringMap(PyObject elements[]) {
76          this(elements.length);
77          for (int i=0; i<elements.length; i+=2) {
78              __setitem__(elements[i], elements[i+1]);
79          }
80      }
81  
82      public synchronized int __len__() {
83          return size;
84      }
85  
86      public synchronized boolean __nonzero__() {
87          return size != 0;
88      }
89  
90      public synchronized PyObject __finditem__(String   key) {
91          String  [] table = keys;
92          int maxindex = table.length;
93          int index = (System.identityHashCode(key) & 0x7fffffff) % maxindex;
94  
95          // Fairly aribtrary choice for stepsize...
96          int stepsize = maxindex / 5;
97  
98          // Cycle through possible positions for the key;
99          //int collisions = 0;
100         while (true) {
101             String   tkey = table[index];
102             if (tkey == key) {
103                 //if (collisions > 0) {
104                 //    System.err.println("key: "+key+", "+collisions+", "+
105                 //               maxindex+", "+System.identityHashCode(key));
106                 //}
107                 return values[index];
108             }
109             if (tkey == null)
110                 return values[index];
111 
112             //collisions++;
113             index = (index+stepsize) % maxindex;
114         }
115     }
116 
117     public PyObject __finditem__(PyObject key) {
118         //System.err.println("oops: "+key);
119         if (key instanceof PyString) {
120             return __finditem__(((PyString)key).internedString());
121         } else {
122             return null;
123         }
124     }
125 
126     public PyObject __iter__() {
127         return new PyStringMapIter(keys, values);
128     }
129 
130     private final void insertkey(String   key, PyObject value) {
131         String  [] table = keys;
132         int maxindex = table.length;
133         int index = (System.identityHashCode(key) & 0x7fffffff) % maxindex;
134 
135         // Fairly aribtrary choice for stepsize...
136         int stepsize = maxindex / 5;
137  
138         int free_index = -1;
139 
140         // Cycle through possible positions for the key;
141         while (true) {
142             String   tkey = table[index];
143             if (tkey == null) {
144                 if (free_index == -1 ) {
145                     filled++;
146                     free_index = index;
147                 }
148                 break;
149             } else if (tkey == key) {
150                 values[index] = value;
151                 return;
152             } else if (tkey == "<deleted key>" && free_index == -1) {
153                 free_index = index;
154             }
155             index = (index+stepsize) % maxindex;
156         }
157         table[free_index] = key;
158         values[free_index] = value;
159         size++;
160         return;        
161     }
162 
163     private synchronized final void resize(int capacity) {
164         int p = prime;
165         for (; p<primes.length; p++) {
166             if (primes[p] >= capacity)
167                 break;
168         }
169         if (primes[p] < capacity) {
170             throw Py.ValueError("can't make hashtable of size: "+capacity);
171         }
172         //System.err.println("resize: "+(keys != null ? keys.length : -1)+
173         //                   ", "+primes[p]);
174         capacity = primes[p];
175         prime = p;
176 
177         String  [] oldKeys = keys;
178         PyObject[] oldValues = values;
179 
180         keys = new String  [capacity];
181         values = new PyObject[capacity];
182         size = 0;
183         filled = 0;
184 
185         if (oldValues != null) {
186             int n = oldValues.length;
187 
188             for (int i=0; i<n; i++) {
189                 PyObject value = oldValues[i];
190                 if (value == null)
191                     continue;
192                 insertkey(oldKeys[i], value);
193             }
194         }
195     }
196 
197     public synchronized void __setitem__(String   key, PyObject value) {
198         if (2*filled > keys.length)
199             resize(keys.length+1);
200         insertkey(key, value);
201     }
202 
203     public void __setitem__(PyObject key, PyObject value) {
204         if (key instanceof PyString) {
205             __setitem__(((PyString)key).internedString(), value);
206         } else {
207             throw Py.TypeError("keys in namespace must be strings");
208         }
209     }
210 
211     public synchronized void __delitem__(String   key) {
212         String  [] table = keys;
213         int maxindex = table.length;
214         int index = (System.identityHashCode(key) & 0x7fffffff) % maxindex;
215 
216         // Fairly aribtrary choice for stepsize...
217         int stepsize = maxindex / 5;
218 
219         // Cycle through possible positions for the key;
220         while (true) {
221             String   tkey = table[index];
222             if (tkey == null) {
223                 throw Py.KeyError(key);
224             }
225             if (tkey == key) {
226                 table[index] = "<deleted key>";
227                 values[index] = null;
228                 size--;
229                 break;
230             }
231             index = (index+stepsize) % maxindex;
232         }
233     }
234 
235     public void __delitem__(PyObject key) {
236         if (key instanceof PyString) {
237             __delitem__(((PyString)key).internedString());
238         } else {
239             throw Py.KeyError(key.toString());
240         }
241     }
242 
243     /**
244      * Remove all items from the dictionary.
245      */
246     public synchronized void clear() {
247         for (int i=0; i<keys.length; i++) {
248             keys[i] = null;
249             values[i] = null;
250         }
251         size = 0;
252     }
253 
254 
255     public synchronized String   toString() {
256         ThreadState ts = Py.getThreadState();
257         if (!ts.enterRepr(this)) {
258             return "{...}";
259         }
260 
261         String  [] keyTable = keys;
262         PyObject[] valueTable = values;
263         int n = keyTable.length;
264 
265         StringBuffer   buf = new StringBuffer  ("{");
266 
267         for (int i=0; i<n; i++) {
268             //String key = keyTable[i];
269             PyObject value = valueTable[i];
270             if (value == null)
271                 continue;
272             buf.append("'");
273             buf.append(keyTable[i]);
274             buf.append("': ");
275             buf.append(value.__repr__().toString());
276             buf.append(", ");
277         }
278 
279         // A hack to remove the final ", " from the string repr
280         int len = buf.length();
281         if (len > 4) {
282             buf.setLength(len-2);
283         }
284 
285         buf.append("}");
286         ts.exitRepr(this);
287         return buf.toString();
288     }
289   
290     public synchronized int __cmp__(PyObject other) {
291         if (!(other instanceof PyStringMap ||
292                   other instanceof PyDictionary)) {
293             return -2;
294         }
295         int an = __len__();
296         int bn = other.__len__();
297         if (an < bn) return -1;
298         if (an > bn) return 1;
299 
300         PyList akeys = keys();
301         PyList bkeys = null;
302         if (other instanceof PyStringMap) {
303             bkeys = ((PyStringMap)other).keys();
304         } else {
305             bkeys = ((PyDictionary)other).keys();
306         }
307         akeys.sort();
308         bkeys.sort();
309 
310         for (int i=0; i<bn; i++) {
311             PyObject akey = akeys.pyget(i);
312             PyObject bkey = bkeys.pyget(i);
313             int c = akey._cmp(bkey);
314             if (c != 0)
315                 return c;
316 
317             PyObject avalue = __finditem__(akey);
318             PyObject bvalue = other.__finditem__(bkey);
319             c = avalue._cmp(bvalue);
320             if (c != 0)
321                 return c;
322         }
323         return 0;
324     }
325 
326     /**
327      * Return true if the key exist in the dictionary.
328      */
329     public boolean has_key(PyObject key) {
330         return __finditem__(key) != null;
331     }
332 
333     /**
334      * Return this[key] if the key exists in the mapping, default_object
335      * is returned otherwise.
336      *
337      * @param key            the key to lookup in the mapping.
338      * @param default_object the value to return if the key does not
339      *                       exists in the mapping.
340      */
341     public PyObject get(PyObject key, PyObject default_object) {
342         PyObject o = __finditem__(key);
343         if (o == null)
344             return default_object;
345         else
346             return o;
347     }
348 
349     /**
350      * Return this[key] if the key exists in the mapping, None
351      * is returned otherwise.
352      *
353      * @param key  the key to lookup in the mapping.
354      */
355     public PyObject get(PyObject key) {
356         return get(key, Py.None);
357     }
358 
359     /**
360      * Return a shallow copy of the dictionary.
361      */
362     public synchronized PyStringMap copy() {
363         int n = keys.length;
364 
365         PyStringMap map = new PyStringMap(n);
366         System.arraycopy(keys, 0, map.keys, 0, n);
367         System.arraycopy(values, 0, map.values, 0, n);
368 
369         map.filled = filled;
370         map.size = size;
371         map.prime = prime;
372 
373         return map;
374     }
375 
376     /**
377      * Insert all the key:value pairs from <code>map</code> into
378      * this mapping.
379      */
380     public synchronized void update(PyStringMap map) {
381         String  [] keyTable = map.keys;
382         PyObject[] valueTable = map.values;
383         int n = keyTable.length;
384 
385         if (2*filled+n > keys.length)
386             resize(2*filled+n);
387 
388         for (int i=0; i<n; i++) {
389             String   key = keyTable[i];
390             if (key == null || key == "<deleted key>")
391                 continue;
392             insertkey(key, valueTable[i]);
393         }
394     }
395 
396     /**
397      * Insert all the key:value pairs from <code>dict</code> into
398      * this mapping.
399      */
400     public void update(PyDictionary dict) {
401         java.util.Hashtable   table = dict.table;
402 
403         java.util.Enumeration   ek = table.keys();
404         java.util.Enumeration   ev = table.elements();
405         int n = table.size();
406 
407         for(int i=0; i<n; i++) {
408             __setitem__((PyObject)ek.nextElement(),
409                         (PyObject)ev.nextElement());
410         }
411     }
412 
413     /**
414      * Return this[key] if the key exist, otherwise insert key with
415      * a None value and return None.
416      *
417      * @param key   the key to lookup in the mapping.
418      */
419     public PyObject setdefault(PyObject key) {
420         return setdefault(key, Py.None);
421     }
422 
423     /**
424      * Return this[key] if the key exist, otherwise insert key with
425      * the value of failobj and return failobj
426      *
427      * @param key     the key to lookup in the mapping.
428      * @param failobj the default value to insert in the mapping
429      *                if key does not already exist.
430      */
431     public PyObject setdefault(PyObject key, PyObject failobj) {
432         PyObject o = __finditem__(key);
433         if (o == null)
434             __setitem__(key, o = failobj);
435         return o;
436     }
437 
438     /**
439      * Return a random (key, value) tuple pair and remove the pair
440      * from the mapping.
441      */
442     public synchronized PyObject popitem() {
443         if (size == 0)
444             throw Py.KeyError("popitem(): dictionary is empty");
445 
446         String  [] table = keys;
447         int maxindex = table.length;
448         int index = popfinger;
449 
450         if (index >= maxindex || index < 0)
451             index = 1;
452         while (true) {
453             String   tKey = table[index];
454             if (tKey != null && tKey != "<deleted key>")
455                 break;
456             index++;
457             if (index >= maxindex)
458                index = 0;
459         }
460 
461         popfinger = index + 1;
462         PyObject key = Py.newString(table[index]);
463         PyObject val = (PyObject) values[index];
464 
465         table[index] = "<deleted key>";
466         values[index] = null;
467         size--;
468 
469         return new PyTuple(new PyObject[] { key, val });
470     }
471 
472     /**
473      * Return a copy of the mappings list of (key, value) tuple
474      * pairs.
475      */
476     public synchronized PyList items() {
477         String  [] keyTable = keys;
478         PyObject[] valueTable = values;
479         int n = keyTable.length;
480 
481         PyList l = new PyList();
482         for (int i=0; i<n; i++) {
483             String   key = keyTable[i];
484             if (key == null || key == "<deleted key>" || values[i] == null)
485                 continue;
486             l.append(new PyTuple(new PyObject[] {
487                 new PyString(key), valueTable[i]
488             }));
489         }
490         return l;
491     }
492 
493 
494     synchronized String  [] jkeys() {
495         String  [] keyTable = keys;
496         //PyObject[] valueTable = values;
497         int n = keyTable.length;
498 
499         String  [] newKeys = new String  [size];
500         int j=0;
501 
502         for (int i=0; i<n; i++) {
503             String   key = keyTable[i];
504             if (key == null || key == "<deleted key>")
505                 continue;
506             newKeys[j++] = key;
507         }
508         return newKeys;
509     }
510 
511 
512     /**
513      * Return a copy of the mappings list of keys.
514      */
515     public synchronized PyList keys() {
516         String  [] keyTable = keys;
517         //PyObject[] valueTable = values;
518         int n = keyTable.length;
519 
520         PyList l = new PyList();
521         for (int i=0; i<n; i++) {
522             String   key = keyTable[i];
523             if (key == null || key == "<deleted key>" || values[i] == null)
524                 continue;
525             l.append(new PyString(key));
526         }
527         return l;
528     }
529 
530     /**
531      * Return a copy of the mappings list of values.
532      */
533     public synchronized PyList values() {
534         PyObject[] valueTable = values;
535         int n = valueTable.length;
536 
537         PyList l = new PyList();
538         for (int i=0; i<n; i++) {
539             PyObject value = valueTable[i];
540             if (value == null)
541                 continue;
542             l.append(value);
543         }
544         return l;
545     }
546 }
547 
548 class PyStringMapIter extends PyIterator {
549     String  [] keyTable;
550     PyObject[] valTable;
551     private int idx;
552 
553     public PyStringMapIter(String  [] keys, PyObject[] values) {
554         this.keyTable = keys;
555         this.valTable = values;
556         this.idx = 0;
557     }
558 
559     public PyObject __iternext__() {
560         int n = keyTable.length;
561 
562         for (; idx < n; idx++) {
563             String   key = keyTable[idx];
564             if (key == null || key == "<deleted key>" || valTable[idx] == null)
565                 continue;
566             idx++;
567             return Py.newString(key);
568         }
569         return null;
570     }
571 
572 }
573 
574 
575
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags