Permalink
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Mar 25, 2015
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Dec 31, 2014
Dec 31, 2014
Mar 25, 2015
Dec 31, 2014
Dec 31, 2014
Dec 31, 2014
Mar 28, 2015
Dec 31, 2014
Mar 25, 2015
Dec 31, 2014
Jan 9, 2015
Dec 31, 2014
Jan 9, 2015
Sep 5, 2014
Jan 1, 2015
Sep 5, 2014
Jan 1, 2015
Jan 3, 2015
Mar 25, 2015
Sep 5, 2014
Mar 28, 2015
Dec 31, 2014
Sep 5, 2014
Jan 1, 2015
Jan 3, 2015
Mar 25, 2015
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Mar 28, 2015
Sep 5, 2014
Sep 5, 2014
Mar 28, 2015
Jan 18, 2015
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Mar 1, 2015
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Mar 28, 2015
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Jan 18, 2015
Jan 11, 2015
Sep 5, 2014
Sep 5, 2014
Jan 1, 2015
Jan 3, 2015
Mar 25, 2015
Sep 5, 2014
Mar 25, 2015
Sep 5, 2014
Sep 5, 2014
Jan 1, 2015
Sep 5, 2014
Mar 25, 2015
Sep 5, 2014
Sep 5, 2014
Jan 9, 2015
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Sep 5, 2014
Sep 5, 2014
Jan 19, 2015
Mar 25, 2015
Sep 5, 2014
Sep 5, 2014
Mar 27, 2015
Mar 28, 2015
Sep 5, 2014
Mar 27, 2015
Sep 5, 2014
Sep 5, 2014
Dec 31, 2014
Nov 11, 2014
Nov 11, 2014
Nov 12, 2014
Jan 24, 2015
Mar 16, 2015
Nov 11, 2014
Sep 5, 2014
Newer
100644
680 lines (585 sloc)
18.5 KB
1
;(function($B){
2
5
var $ObjectDict = _b_.object.$dict
6
9
// dictionary
10
function $DictClass($keys,$values){
11
this.iter = null
12
this.__class__ = $DictDict
21
dummy = {}
22
23
// can either grow or shrink depending on actual used items
24
var $grow_dict = function(self) {
25
var new_size = $DICT_MINSIZE
26
var target_size = (self.$used < 50000? 2 : 4) * self.$used
27
while (new_size < target_size) {
28
new_size <<= 1
29
}
30
var new_data = Array($DICT_MINSIZE)
31
try {
32
var ig = new $item_generator(self)
33
while(1) {
34
var itm = ig.next()
35
var bucket = $find_empty(itm[0], new_size, new_data)
36
new_data[bucket] = itm
37
}
38
} catch (err) {
39
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
40
}
41
self.$data = new_data
42
self.$fill = self.$used
43
self.$size = new_size
44
}
45
46
var $lookup_key = function(self, key) {
47
eq = _b_.getattr(key, "__eq__")
48
size = self.$size
49
data = self.$data
50
bucket = Math.abs(_b_.hash(key) % size)
51
val = data[bucket]
52
while (val !== undefined) {
53
if (val === dummy) {
54
bucket = $next_probe(bucket, size)
55
} else {
56
k_val = val[0] // [key, value]
57
if (eq(k_val)) {
58
return bucket
59
} else {
60
bucket = $next_probe(bucket, size)
61
}
62
}
63
val = data[bucket]
64
}
65
self.$empty_bucket = bucket
66
67
return undefined
68
}
69
70
var $find_empty = function(key, size, data) {
71
bucket = Math.abs(hash(key) % size)
72
val = data[bucket]
73
while (val !== undefined) {
74
bucket = $next_probe(bucket, size)
75
val = data[bucket]
76
}
77
return bucket
78
}
79
80
var $next_probe = function(i, size) {
81
return ((i * 5) + 1) % size
82
}
83
84
var $DictDict = {__class__:$B.$type,
85
__name__ : 'dict',
88
}
89
90
var $key_iterator = function(d) {
91
this.d = d
92
this.current = 0
93
this.iter = new $item_generator(d)
94
}
96
$key_iterator.prototype.next = function() { return this.iter.next()[0] }
97
98
var $value_iterator = function(d) {
99
this.d = d
100
this.current = 0
101
this.iter = new $item_generator(d)
102
}
104
$value_iterator.prototype.next = function() { return this.iter.next()[1] }
105
106
var $item_generator = function(d) {
121
for (var i=0; i < this.data.length; i++) {
122
var _v=this.data[i]
123
if (_v === undefined || _v === dummy) continue
134
}
135
throw _b_.StopIteration("StopIteration")
136
}
137
$item_generator.prototype.as_list = function() {
139
}
140
141
var $item_iterator = function(d) {
142
this.d = d
143
this.current = 0
144
this.iter = new $item_generator(d)
145
}
147
$item_iterator.prototype.next = function() { return _b_.tuple(this.iter.next()) }
148
149
var $copy_dict = function(left, right) {
150
var _l=new $item_generator(right).as_list()
151
var si=$DictDict.__setitem__
152
for (var i=0; i < _l.length; i++) si(left, _l[i][0], _l[i][1])
153
}
154
155
$iterator_wrapper = function(items,klass){
156
var res = {
157
__class__:klass,
160
__next__:function(){
161
//if (items.length() !== items.iter.used) {
162
// throw _b_.RuntimeError("dictionary changed size during iteration")
163
//}
164
return items.next()
165
//return items[counter++]
166
},
167
//__repr__:function(){return "<"+klass.__name__+" object>"},
168
//counter:0
175
var $dict_keysDict = $B.$iterator_class('dict_keys')
176
177
$DictDict.keys = function(self){
178
if (arguments.length > 1) {
179
var _len=arguments.length - 1
180
var _msg="keys() takes no arguments ("+_len+" given)"
181
throw _b_.TypeError(_msg)
182
}
183
return $iterator_wrapper(new $key_iterator(self),$dict_keysDict)
184
}
185
186
var $dict_valuesDict = $B.$iterator_class('dict_values')
187
188
$DictDict.values = function(self){
189
if (arguments.length > 1) {
190
var _len=arguments.length - 1
191
var _msg="values() takes no arguments ("+_len+" given)"
192
throw _b_.TypeError(_msg)
193
}
198
199
$DictDict.__contains__ = function(self,item){
200
if(self.$jsobj) return self.$jsobj[item]!==undefined
201
switch(typeof item) {
202
case 'string':
203
return self.$string_dict[item] !==undefined
208
}
209
210
$DictDict.__delitem__ = function(self,arg){
211
switch(typeof arg) {
212
case 'string':
213
if (self.$string_dict[arg] === undefined) throw KeyError(_b_.str(arg))
214
delete self.$string_dict[arg]
215
if (self.$jsobj) delete self.$jsobj[arg]
216
return
217
case 'number':
218
if (self.$numeric_dict[arg] === undefined) throw KeyError(_b_.str(arg))
219
delete self.$numeric_dict[arg]
220
if (self.$jsobj) delete self.$jsobj[arg]
221
return
224
225
var bucket = $lookup_key(self, arg)
226
if (bucket === undefined) throw KeyError(_b_.str(arg))
227
self.$data[bucket] = dummy
228
--self.$used
231
}
232
233
$DictDict.__eq__ = function(self,other){
234
if(other===undefined){ // compare self to class "dict"
235
return self===dict
236
}
241
var _l = new $item_generator(self).as_list()
242
for (var i=0; i < _l.length; i++) {
243
var key=_l[i][0]
246
var v2=$DictDict.__getitem__(other, key)
247
if (!getattr(v1, '__eq__')(v2)) return false
248
}
249
250
return true
251
}
252
253
$DictDict.__getitem__ = function(self,arg){
254
if(self.$jsobj && self.$jsobj[arg] !== undefined) return self.$jsobj[arg]
255
256
switch(typeof arg) {
257
case 'string':
258
if (self.$string_dict[arg] !== undefined) return self.$string_dict[arg]
259
break
260
case 'number':
261
if (self.$numeric_dict[arg] !== undefined) return self.$numeric_dict[arg]
265
var bucket = $lookup_key(self, arg)
266
if (bucket !== undefined) return self.$data[bucket][1]
270
throw KeyError(_b_.str(arg))
271
}
272
273
$DictDict.__hash__ = function(self) {
274
if (self === undefined) {
275
return $DictDict.__hashvalue__ || $B.$py_next_hash-- // for hash of dict type (not instance of dict)
276
}
277
throw _b_.TypeError("unhashable type: 'dict'");
278
}
279
280
$DictDict.__init__ = function(self){
281
var args = []
282
for(var i=1;i<arguments.length;i++){args.push(arguments[i])}
283
$DictDict.clear(self)
284
switch(args.length) {
285
case 0:
286
return
287
case 1:
288
var obj = args[0]
290
var i = obj.length
291
var si = $DictDict.__setitem__
292
while(i--) si(self, obj[i][0], obj[i][1])
296
return
297
}
299
if(obj.__class__===$B.JSObject.$dict){
300
// convert a JSObject into a Python dictionary
301
var si = $DictDict.__setitem__
302
for(var attr in obj.js) si(self,attr,obj.js[attr])
303
304
// Attribute $jsobj is used to update the original JS object
305
// when the dictionary is modified
307
return
308
}
311
var $ns=$B.$MakeArgs('dict',args,[],[],'args','kw')
312
var args = $ns['args']
313
var kw = $ns['kw']
316
if(isinstance(args[0],dict)){
318
return
319
}
321
// format dict([(k1,v1),(k2,v2)...])
328
}else{
329
var iterable = iter(args[0])
330
while(1){
331
try{
332
var elt = next(iterable)
333
var key = getattr(elt,'__getitem__')(0)
334
var value = getattr(elt,'__getitem__')(1)
335
$DictDict.__setitem__(self, key, value)
336
}catch(err){
337
if(err.__name__==='StopIteration'){$B.$pop_exc();break}
338
throw err
339
}
340
}
341
}
344
}
345
346
var $dict_iterator = $B.$iterator_class('dict iterator')
349
}
350
354
for (var k in self.$numeric_dict) _count++
355
for (var k in self.$string_dict) _count++
359
360
$DictDict.__mro__ = [$DictDict,$ObjectDict]
361
362
$DictDict.__ne__ = function(self,other){return !$DictDict.__eq__(self,other)}
363
364
$DictDict.__next__ = function(self){
367
}
368
try {
369
return self.$iter.next()
370
} catch (err) {
371
if (err.__name__ !== "StopIteration") { throw err } else { $B.$pop_exc() }
372
}
373
}
374
375
$DictDict.__repr__ = function(self){
376
if(self===undefined) return "<class 'dict'>"
378
var res=[]
382
if (_objs.indexOf(itm[1]) > -1 && _b_.isinstance(itm[1], [_b_.dict,_b_.list,_b_.set, _b_.tuple])) {
383
var value='?'+_b_.type(itm[1])
384
if(isinstance(itm[1], dict)) value='{...}'
385
res.push(repr(itm[0])+': '+ value)
386
} else {
390
}
392
}
393
394
$DictDict.__setitem__ = function(self,key,value){
395
switch(typeof key) {
396
case 'string':
397
self.$string_dict[key]=value
398
if(self.$jsobj) self.$jsobj[key]=value
399
return
400
case 'number':
401
self.$numeric_dict[key]=value
402
if(self.$jsobj) self.$jsobj[key]=value
403
return
407
408
// if adding new item would invoke a grow...
409
if (self.$fill + 1 > self.$size * 3 / 4) {
410
$grow_dict(self)
411
}
412
413
var bucket = $lookup_key(self, key)
414
if (bucket === undefined) {
415
bucket = self.$empty_bucket
416
++self.$fill
417
++self.$used
418
}
419
self.$data[bucket] = [key, value]
420
421
if(self.$jsobj) self.$jsobj[key]=value
422
}
423
424
$DictDict.__str__ = $DictDict.__repr__
425
426
// add "reflected" methods
427
$B.make_rmethods($DictDict)
428
429
$DictDict.clear = function(self){
430
// Remove all items from the dictionary.
431
self.$data = Array($DICT_MINSIZE)
432
self.$size = $DICT_MINSIZE
433
self.$fill = 0
434
self.$used = 0
435
439
if(self.$jsobj) self.$jsobj={}
440
}
441
442
$DictDict.copy = function(self){
443
// Return a shallow copy of the dictionary
446
return res
447
}
448
450
if (_default === undefined) _default=None
451
switch(typeof key) {
452
case 'string':
453
return self.$string_dict[key] || _default
456
}
458
var bucket = $lookup_key(self, key)
459
if(bucket !== undefined) return self.$data[bucket][1]
462
}
463
465
466
$DictDict.items = function(self){
467
if (arguments.length > 1) {
468
var _len=arguments.length - 1
469
var _msg="items() takes no arguments ("+_len+" given)"
470
throw _b_.TypeError(_msg)
471
}
473
}
474
476
// class method
478
var res = dict()
479
var keys_iter = _b_.iter(keys)
480
while(1){
481
try{
482
var key = _b_.next(keys_iter)
483
$DictDict.__setitem__(res,key,value)
484
}catch(err){
485
if($B.is_exc(err,[_b_.StopIteration])){
486
$B.$pop_exc()
487
return res
488
}
489
throw err
490
}
491
}
492
}
493
494
$DictDict.pop = function(self,key,_default){
495
try{
496
var res = $DictDict.__getitem__(self,key)
497
$DictDict.__delitem__(self,key)
498
return res
499
}catch(err){
500
$B.$pop_exc()
501
if(err.__name__==='KeyError'){
502
if(_default!==undefined) return _default
503
throw err
504
}
505
throw err
506
}
507
}
508
509
$DictDict.popitem = function(self){
510
try{
511
var itm = new $item_iterator(self).next()
512
$DictDict.__delitem__(self,itm[0])
513
return _b_.tuple(itm)
514
}catch(err) {
515
if (err.__name__ == "StopIteration") {
516
$B.$pop_exc()
517
throw KeyError("'popitem(): dictionary is empty'")
518
}
519
}
520
}
521
522
$DictDict.setdefault = function(self,key,_default){
523
try{return $DictDict.__getitem__(self,key)}
524
catch(err){
525
if(_default===undefined) _default=None
526
$DictDict.__setitem__(self,key,_default)
527
return _default
528
}
529
}
530
531
$DictDict.update = function(self){
532
var params = []
534
var $ns=$B.$MakeArgs('$DictDict.update',params,[],[],'args','kw')
535
var args = $ns['args']
536
if(args.length>0) {
537
var o=args[0]
538
if (isinstance(o,dict)){
539
$copy_dict(self, o)
540
} else if (hasattr(o, '__getitem__') && hasattr(o, 'keys')) {
541
var _keys=_b_.list(getattr(o, 'keys')())
542
for (var i=0; i < _keys.length; i++) {
543
var _value = getattr(o, '__getitem__')(_keys[i])
544
$DictDict.__setitem__(self, _keys[i], _value)
547
}
548
var kw = $ns['kw']
550
}
551
556
var res = {__class__:$DictDict,
557
$data : Array($DICT_MINSIZE),
558
$size : $DICT_MINSIZE,
559
$fill : 0,
560
$used : 0,
561
$numeric_dict : {},
562
$string_dict : {}
563
}
564
var i = args.length
567
var item=args[i]
568
switch(typeof item[0]) {
569
case 'string':
570
res.$string_dict[item[0]]=item[1]
571
break;
572
case 'number':
573
res.$numeric_dict[item[0]]=item[1]
574
break
575
default:
576
si(res, item[0], item[1])
577
}
582
// apply __init__ with arguments of dict()
583
var res = {__class__:$DictDict}
584
$DictDict.clear(res)
585
var _args = [res]
586
for(var i=0, _len_i = arguments.length; i < _len_i;i++){_args.push(arguments[i])}
587
$DictDict.__init__.apply(null,_args)
588
return res
589
}
591
dict.__class__ = $B.$factory
592
dict.$dict = $DictDict
593
$DictDict.$factory = dict
594
$DictDict.__new__ = $B.$__new__(dict)
595
596
_b_.dict = dict
598
// following are used for faster access elsewhere
599
$B.$dict_iterator = function(d) { return new $item_generator(d) }
600
$B.$dict_length = $DictDict.__len__
601
$B.$dict_getitem = $DictDict.__getitem__
602
$B.$dict_get = $DictDict.get
603
$B.$dict_set = $DictDict.__setitem__
604
$B.$dict_contains = $DictDict.__contains__
605
$B.$dict_items = function(d) { return new $item_generator(d).as_list() }
606
$B.$copy_dict = $copy_dict // copy from right to left
607
$B.$dict_get_copy = $DictDict.copy // return a shallow copy
608
614
$ObjDictDict.__delitem__ = function(self, key){
615
$DictDict.__delitem__(self, key)
616
delete self.$obj[key]
617
}
618
619
$ObjDictDict.__setitem__ = function(self, key, value){
620
$DictDict.__setitem__(self, key, value)
621
self.$obj[key] = value
622
}
623
624
$ObjDictDict.clear = function(self){
625
$DictDict.clear(self)
626
for(var key in self.$obj){delete self.$obj[key]}
627
}
628
629
$ObjDictDict.pop = function(self, key, _default){
630
$DictDict.pop(self, key, _default)
631
delete self.$obj[key]
632
return key
633
}
634
635
$ObjDictDict.popitem = function(self){
636
var res = $DictDict.popitem(self) // tuple
637
var key = res[0]
638
delete self.$obj[key]
639
return res
640
}
641
642
$ObjDictDict.update = function(self){
643
$DictDict.update.apply(null, arguments)
644
// Update attributes of underlying object by iterating on self.items()
645
var it = $DictDict.items(self)
646
while(true){
647
try{
648
var item = next(it)
649
self.$obj[item[0]] = item[1]
650
}catch(err){
651
if($B.is_exc(err,[_b_.StopIteration])){
652
$B.$pop_exc();return
653
}
654
throw err
655
}
656
}
661
if(obj.__class__===$B.$factory){
662
// For classes, use the class dictionary
663
obj = obj.$dict
664
}
670
}
671
}
672
return res
673
}
674
obj_dict.$dict = $ObjDictDict
675
obj_dict.__class__ = $B.$factory
676
$ObjDictDict.$factory = obj_dict
677
678
$B.obj_dict = obj_dict
679
680
})(__BRYTHON__)