PyMultiThread/binList.py at master · StephDC/PyMultiThread · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#! /usr/bin/env python3
# Binary list with chaining that would allow
# storing a list of bool with minimum memory

maxLength=63

classbinList():

def__init__(self):
self.length=0
self.totalLength=0
self.data=0
self.nextdata=None

def__str__(self):
result= []
foriinself:
result.append(i)
returnstr(result)

def__repr__(self):
returnstr(self)

def__iter__(self):
returnbinListIter(self)

def__len__(self):
returnself.totalLength

def__getitem__(self,index):
ifself.totalLength<=index:
raiseIndexError("list index "+str(index)+" out of range")
elifself.length<=index:
returnself.nextdata[index-self.length]
else:
returnbool(self.data&1<<index)

def__setitem__(self,index,value):
ifself.totalLength<index:
raiseIndexError("list index out of range")
elifself.totalLength==index:
self.pushBack(value)
elif (self.__getitem__(index) !=value):
ifself.length<=index:
self.nextdata.__setitem__(index-self.length,value)
else:
ifvalue:
self.data+=1<<index
else:
self.data-=1<<index

def__delitem__(self,index):
ifself.length<=index:
raiseIndexError("list index out of range")
else:
self.data=self.data%(1<<index)+(self.data>>(1+index)<<index)
self.length-=1
self.totalLength-=1

defattachList(self):
ifself.nextdataisNone:
self.nextdata=binList()
else:
self.nextdata.attachList()

defpushBack(self,value):
ifself.length<=maxLength:
ifvalue:
self.data+= (1<<self.length)
self.length+=1
self.totalLength+=1
else:
self.totalLength+=1
ifself.nextdataisNone:
self.attachList()
self.nextdata.pushBack(value)

defpopFront(self):
ifself.length<1:
raiseIndexError("list index out of range")
else:
result=__getitem__(0)
self.data= (self.data>>1)
self.length-=1
self.totalLength-=1
returnresult

defremItem(self,index):
self.__delitem__(index)

defappend(self,value):
self.pushBack(value)

defpop(self):
returnself.popFront(self)

classbinListIter():
def__init__(self,list):
self.i=0
self.d=list

def__iter__(self):
returnself

def__next__(self):
ifself.i<len(self.d):
result=self.d[self.i]
self.i+=1
returnresult
elifself.d.nextdataisnotNone:
self.i=0
self.d=self.d.nextdata
returnself.__next__()
else:
raiseStopIteration()