Permalink
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Nov 11, 2014
Nov 11, 2014
Nov 12, 2014
Dec 31, 2014
Dec 31, 2014
Nov 11, 2014
Sep 5, 2014
Newer
100644
556 lines (476 sloc)
14.5 KB
1
;(function($B){
2
3
var _b_ = $B.builtins
4
var $s=[]
5
for(var $b in _b_) $s.push('var ' + $b +'=_b_["'+$b+'"]')
6
eval($s.join(';'))
8
var $ObjectDict = _b_.object.$dict
9
12
// dictionary
13
function $DictClass($keys,$values){
14
this.iter = null
15
this.__class__ = $DictDict
16
$DictDict.clear(this)
17
18
for (var i = 0; i < $keys.length; ++i) {
19
$DictDict.__setitem__($keys[i], $values[i])
20
}
21
}
22
23
dummy = {}
24
25
// can either grow or shrink depending on actual used items
26
var $grow_dict = function(self) {
27
var new_size = $DICT_MINSIZE
28
var target_size = (self.$used < 50000? 2 : 4) * self.$used
29
while (new_size < target_size) {
30
new_size <<= 1
31
}
32
var new_data = Array($DICT_MINSIZE)
33
try {
34
var ig = new $item_generator(self)
35
while(1) {
36
var itm = ig.next()
37
var bucket = $find_empty(itm[0], new_size, new_data)
38
new_data[bucket] = itm
39
}
40
} catch (err) {
41
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
42
}
43
self.$data = new_data
44
self.$fill = self.$used
45
self.$size = new_size
46
}
47
48
var $lookup_key = function(self, key) {
49
eq = _b_.getattr(key, "__eq__")
50
size = self.$size
51
data = self.$data
52
bucket = Math.abs(_b_.hash(key) % size)
53
val = data[bucket]
54
while (val !== undefined) {
55
if (val === dummy) {
56
bucket = $next_probe(bucket, size)
57
} else {
58
k_val = val[0] // [key, value]
59
if (eq(k_val)) {
60
return bucket
61
} else {
62
bucket = $next_probe(bucket, size)
63
}
64
}
65
val = data[bucket]
66
}
67
self.$empty_bucket = bucket
68
69
return undefined
70
}
71
72
var $find_empty = function(key, size, data) {
73
bucket = Math.abs(hash(key) % size)
74
val = data[bucket]
75
while (val !== undefined) {
76
bucket = $next_probe(bucket, size)
77
val = data[bucket]
78
}
79
return bucket
80
}
81
82
var $next_probe = function(i, size) {
83
return ((i * 5) + 1) % size
84
}
85
86
var $DictDict = {__class__:$B.$type,
87
__name__ : 'dict',
88
$native:true
89
}
90
91
var $key_iterator = function(d) {
92
this.d = d
93
this.current = 0
94
this.iter = new $item_generator(d)
95
}
96
$key_iterator.prototype.length = function() { return this.d.$used }
97
$key_iterator.prototype.next = function() { return this.iter.next()[0] }
98
99
var $value_iterator = function(d) {
100
this.d = d
101
this.current = 0
102
this.iter = new $item_generator(d)
103
}
104
$value_iterator.prototype.length = function() { return this.d.$used }
105
$value_iterator.prototype.next = function() { return this.iter.next()[1] }
106
107
var $item_generator = function(d) {
108
this.i = -1
109
this.data = d.$data
110
this.size = d.$size
111
this.used = d.$used
112
}
113
$item_generator.prototype.next = function() {
114
do {
115
val = this.data[++this.i]
116
} while ((val === undefined || val === dummy) && this.i < this.size)
117
if (this.i < this.size) {
118
return val
119
}
120
this.i--
121
throw _b_.StopIteration("StopIteration")
122
}
123
$item_generator.prototype.as_list = function() {
124
ret = []
125
j = 0
126
try {
127
while(1) ret[j++] = this.next()
128
} catch (err) {
129
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
130
}
131
return ret
132
}
133
134
var $item_iterator = function(d) {
135
this.d = d
136
this.current = 0
137
this.iter = new $item_generator(d)
138
}
139
$item_iterator.prototype.length = function() { return this.d.$used }
140
$item_iterator.prototype.next = function() { return _b_.tuple(this.iter.next()) }
141
142
var $copy_dict = function(left, right) {
143
var gen = new $item_generator(right)
144
try {
145
while(1) {
146
var item = gen.next()
147
$DictDict.__setitem__(left, item[0], item[1])
148
}
149
} catch (err) {
150
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
151
}
152
}
153
154
$iterator_wrapper = function(items,klass){
155
var res = {
156
__class__:klass,
157
__iter__:function(){return res},
158
__len__:function(){return items.length()},
159
__next__:function(){
160
if (items.length() !== items.iter.used) {
161
throw _b_.RuntimeError("dictionary changed size during iteration")
162
}
163
return items.next()
164
},
165
__repr__:function(){return "<"+klass.__name__+" object>"},
166
counter:-1
167
}
168
res.__str__ = res.toString = res.__repr__
169
return res
170
}
171
172
var $dict_keysDict = $B.$iterator_class('dict_keys')
173
174
$DictDict.keys = function(self){
175
return $iterator_wrapper(new $key_iterator(self),$dict_keysDict)
176
}
177
178
var $dict_valuesDict = $B.$iterator_class('dict_values')
179
180
$DictDict.values = function(self){
181
return $iterator_wrapper(new $value_iterator(self), $dict_valuesDict)
182
}
183
184
$DictDict.__bool__ = function (self) {
185
return self.count > 0
186
}
187
188
$DictDict.__contains__ = function(self,item){
189
if(self.$jsobj) return self.$jsobj[item]!==undefined
191
}
192
193
$DictDict.__delitem__ = function(self,arg){
194
var bucket = $lookup_key(self, arg)
195
if (bucket === undefined) throw KeyError(_b_.str(arg))
196
self.$data[bucket] = dummy
197
--self.$used
198
199
if(self.$jsobj) delete self.$jsobj[arg]
200
}
201
202
$DictDict.__eq__ = function(self,other){
203
if(other===undefined){ // compare self to class "dict"
204
return self===dict
205
}
206
if(!isinstance(other,dict)) return False
207
208
if ($DictDict.__len__(self) != $DictDict.__len__(other)) return false
209
210
var gen = new $item_generator(self)
211
var keys1=[]
212
try {
213
while(1) keys1.push(gen.next()[0])
214
} catch (err) {
215
216
}
217
218
for (var i=0; i < keys1.length; i++) {
219
var key=keys1[i]
220
if (!$DictDict.__contains__(other, key)) return false
221
var v1=$DictDict.__getitem__(self, key)
222
var v2=$DictDict.__getitem__(other, key)
223
if (!getattr(v1, '__eq__')(v2)) return false
224
}
225
226
return true
227
}
228
229
$DictDict.__getitem__ = function(self,arg){
230
var bucket = $lookup_key(self, arg)
231
if (bucket !== undefined) return self.$data[bucket][1]
232
throw KeyError(_b_.str(arg))
233
}
234
235
$DictDict.__hash__ = function(self) {
236
if (self === undefined) {
237
return $DictDict.__hashvalue__ || $B.$py_next_hash-- // for hash of dict type (not instance of dict)
238
}
239
throw _b_.TypeError("unhashable type: 'dict'");
240
}
241
242
$DictDict.__init__ = function(self){
243
var args = []
244
for(var i=1;i<arguments.length;i++){args.push(arguments[i])}
245
$DictDict.clear(self)
246
switch(args.length) {
247
case 0:
248
return
249
case 1:
250
var obj = args[0]
251
if(isinstance(obj,dict)){
253
return
254
}
256
if(obj.__class__===$B.JSObject.$dict){
257
// convert a JSObject into a Python dictionary
258
var res = new $DictClass([],[])
259
for(var attr in obj.js){
260
$DictDict.__setitem__(res,attr,obj.js[attr])
261
}
262
263
self.$data = res.$data
264
self.$size = res.$size
265
self.$used = res.$used
266
267
self.$jsobj = obj.js
268
269
//for(var attr in obj.js){
270
// $DictDict.__setitem__(self, $B.JSObject(attr), $B.JSObject(obj.js[attr]))
271
//}
272
return
273
}
276
var $ns=$B.$MakeArgs('dict',args,[],[],'args','kw')
277
var args = $ns['args']
278
var kw = $ns['kw']
281
if(isinstance(args[0],dict)){
283
return
284
}
286
// format dict([(k1,v1),(k2,v2)...])
287
var iterable = iter(args[0])
288
while(1){
289
try{
290
var elt = next(iterable)
291
var key = getattr(elt,'__getitem__')(0)
292
var value = getattr(elt,'__getitem__')(1)
293
$DictDict.__setitem__(self, key, value)
294
}catch(err){
295
if(err.__name__==='StopIteration'){$B.$pop_exc();break}
296
throw err
297
}
298
}
299
}//if
300
if(kw.$used>0){ // format dict(k1=v1,k2=v2...)
301
for (var k in kw.$data) {
302
$DictDict.__setitem__(self, kw.$data[k][0], kw.$data[k][1])
303
}
304
}
306
}
307
308
var $dict_iterator = $B.$iterator_class('dict iterator')
311
}
312
314
315
$DictDict.__mro__ = [$DictDict,$ObjectDict]
316
317
$DictDict.__ne__ = function(self,other){return !$DictDict.__eq__(self,other)}
318
319
$DictDict.__next__ = function(self){
320
if(self.$iter==null){
321
self.$iter = new $item_generator(self.$data)
322
}
323
try {
324
return self.$iter.next()
325
} catch (err) {
326
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
327
}
328
}
329
330
$DictDict.__repr__ = function(self){
331
if(self===undefined) return "<class 'dict'>"
332
var res=[]
333
var items = new $item_generator(self).as_list()
334
for(var idx in items) {
335
var itm = items[idx]
336
res.push(repr(itm[0])+':'+repr(itm[1]))
337
}
338
return '{'+ res.join(',') +'}'
339
}
340
341
$DictDict.__setitem__ = function(self,key,value){
342
// if adding new item would invoke a grow...
343
if (self.$fill + 1 > self.$size * 3 / 4) {
344
$grow_dict(self)
345
}
346
347
var bucket = $lookup_key(self, key)
348
if (bucket === undefined) {
349
bucket = self.$empty_bucket
350
++self.$fill
351
++self.$used
352
}
353
self.$data[bucket] = [key, value]
354
355
// if dict wraps a JS Object, set its attribute (think sys.modules)
356
if(self.$jsobj) self.$jsobj[key]=value
357
}
358
359
$DictDict.__str__ = $DictDict.__repr__
360
361
// add "reflected" methods
362
$B.make_rmethods($DictDict)
363
364
$DictDict.clear = function(self){
365
// Remove all items from the dictionary.
366
self.$data = Array($DICT_MINSIZE)
367
self.$size = $DICT_MINSIZE
368
self.$fill = 0
369
self.$used = 0
370
371
if(self.$jsobj) self.$jsobj={}
372
}
373
374
$DictDict.copy = function(self){
375
// Return a shallow copy of the dictionary
378
return res
379
}
380
381
$DictDict.get = function(self, key, _default){
382
var bucket = $lookup_key(self, key)
383
if (bucket !== undefined) {
384
return self.$data[bucket][1]
385
}
388
}
389
390
var $dict_itemsDict = $B.$iterator_class('dict_itemiterator')
391
392
$DictDict.items = function(self){
394
}
395
396
$DictDict.fromkeys = function(keys,value){
397
// class method
398
if(value===undefined) value=_b_.None
399
var res = dict()
400
var keys_iter = _b_.iter(keys)
401
while(1){
402
try{
403
var key = _b_.next(keys_iter)
404
$DictDict.__setitem__(res,key,value)
405
}catch(err){
406
if($B.is_exc(err,[_b_.StopIteration])){
407
$B.$pop_exc()
408
return res
409
}
410
throw err
411
}
412
}
413
}
414
415
$DictDict.pop = function(self,key,_default){
416
try{
417
var res = $DictDict.__getitem__(self,key)
418
$DictDict.__delitem__(self,key)
419
return res
420
}catch(err){
421
$B.$pop_exc()
422
if(err.__name__==='KeyError'){
423
if(_default!==undefined) return _default
424
throw err
425
}
426
throw err
427
}
428
}
429
430
$DictDict.popitem = function(self){
431
try{
432
var itm = new $item_iterator(self).next()
433
$DictDict.__delitem__(self,itm[0])
434
return _b_.tuple(itm)
435
}catch(err) {
436
if (err.__name__ == "StopIteration") {
437
$B.$pop_exc()
438
throw KeyError("'popitem(): dictionary is empty'")
439
}
440
}
441
}
442
443
$DictDict.setdefault = function(self,key,_default){
444
try{return $DictDict.__getitem__(self,key)}
445
catch(err){
446
if(_default===undefined) _default=None
447
$DictDict.__setitem__(self,key,_default)
448
return _default
449
}
450
}
451
452
$DictDict.update = function(self){
453
var params = []
455
var $ns=$B.$MakeArgs('$DictDict.update',params,[],[],'args','kw')
456
var args = $ns['args']
457
if(args.length>0 && isinstance(args[0],dict)){
458
var other = args[0]
460
}
461
var kw = $ns['kw']
463
}
464
465
function dict(){
466
var res = {__class__:$DictDict}
467
// apply __init__ with arguments of dict()
468
var args = [res]
470
$DictDict.__init__.apply(null,args)
471
return res
472
}
474
$B.$dict = dict // used for dict literals : "x={}" is translated to "x=__BRYTHON__.$dict()",
475
// not to "x=dict()"
476
// otherwise this would fail :
477
// def foo(dict=None):
478
// x = {}
479
// because inside the function, 'dict' has beeen set to the
480
// value of argument 'dict'
481
dict.__class__ = $B.$factory
482
dict.$dict = $DictDict
483
$DictDict.$factory = dict
484
$DictDict.__new__ = $B.$__new__(dict)
485
486
_b_.dict = dict
488
// following are used for faster access elsewhere
489
$B.$dict_iterator = function(d) { return new $item_generator(d) }
490
$B.$dict_length = $DictDict.__len__
491
$B.$dict_getitem = $DictDict.__getitem__
492
$B.$dict_get = $DictDict.get
493
$B.$dict_set = $DictDict.__setitem__
494
$B.$dict_contains = $DictDict.__contains__
495
$B.$dict_items = function(d) { return new $item_generator(d).as_list() }
496
$B.$copy_dict = $copy_dict // copy from right to left
497
$B.$dict_get_copy = $DictDict.copy // return a shallow copy
498
505
$ObjDictDict.__delitem__ = function(self, key){
506
$DictDict.__delitem__(self, key)
507
delete self.$obj[key]
508
}
509
510
$ObjDictDict.__setitem__ = function(self, key, value){
511
$DictDict.__setitem__(self, key, value)
512
self.$obj[key] = value
513
}
514
515
$ObjDictDict.clear = function(self){
516
$DictDict.clear(self)
517
for(var key in self.$obj){delete self.$obj[key]}
518
}
519
520
$ObjDictDict.pop = function(self, key, _default){
521
$DictDict.pop(self, key, _default)
522
delete self.$obj[key]
523
return key
524
}
525
526
$ObjDictDict.popitem = function(self){
527
var res = $DictDict.popitem(self) // tuple
528
var key = res[0]
529
delete self.$obj[key]
530
return res
531
}
532
533
$ObjDictDict.update = function(self, other){
534
$DictDict.update(self, other)
539
// not sure what res should be?
540
var res = {__class__:$ObjDictDict,$obj:obj}
541
$DictDict.clear(res)
544
//this causes my browser to freeze..
545
$DictDict.__setitem__(res, attr, obj[attr])
546
}
547
}
548
return res
549
}
550
obj_dict.$dict = $ObjDictDict
551
obj_dict.__class__ = $B.$factory
552
$ObjDictDict.$factory = obj_dict
553
554
$B.obj_dict = obj_dict
555
556
})(__BRYTHON__)