Subversion Repositories svnkaklik

Rev

Details | Last modification | View Log

Rev Author Line No. Line
36 kaklik 1 
# Written by Bram Cohen, Uoti Urpala, and John Hoffman
2 
# see LICENSE.txt for license information
3 
 
4 
try:
5 
    True
6 
except:
7 
    True = 1
8 
    False = 0
9 
    bool = lambda x: not not x
10 
 
11 
try:
12 
    sum([1])
13 
    negsum = lambda a: len(a)-sum(a)
14 
except:
15 
    negsum = lambda a: reduce(lambda x,y: x+(not y), a, 0)
16 
 
17 
def _int_to_booleans(x):
18 
    r = []
19 
    for i in range(8):
20 
        r.append(bool(x & 0x80))
21 
        x <<= 1
22 
    return tuple(r)
23 
 
24 
lookup_table = []
25 
reverse_lookup_table = {}
26 
for i in xrange(256):
27 
    x = _int_to_booleans(i)
28 
    lookup_table.append(x)
29 
    reverse_lookup_table[x] = chr(i)
30 
 
31 
 
32 
class Bitfield:
33 
    def __init__(self, length = None, bitstring = None, copyfrom = None):
34 
        if copyfrom is not None:
35 
            self.length = copyfrom.length
36 
            self.array = copyfrom.array[:]
37 
            self.numfalse = copyfrom.numfalse
38 
            return
39 
        if length is None:
40 
            raise ValueError, "length must be provided unless copying from another array"
41 
        self.length = length
42 
        if bitstring is not None:
43 
            extra = len(bitstring) * 8 - length
44 
            if extra < 0 or extra >= 8:
45 
                raise ValueError
46 
            t = lookup_table
47 
            r = []
48 
            for c in bitstring:
49 
                r.extend(t[ord(c)])
50 
            if extra > 0:
51 
                if r[-extra:] != [0] * extra:
52 
                    raise ValueError
53 
                del r[-extra:]
54 
            self.array = r
55 
            self.numfalse = negsum(r)
56 
        else:
57 
            self.array = [False] * length
58 
            self.numfalse = length
59 
 
60 
    def __setitem__(self, index, val):
61 
        val = bool(val)
62 
        self.numfalse += self.array[index]-val
63 
        self.array[index] = val
64 
 
65 
    def __getitem__(self, index):
66 
        return self.array[index]
67 
 
68 
    def __len__(self):
69 
        return self.length
70 
 
71 
    def tostring(self):
72 
        booleans = self.array
73 
        t = reverse_lookup_table
74 
        s = len(booleans) % 8
75 
        r = [ t[tuple(booleans[x:x+8])] for x in xrange(0, len(booleans)-s, 8) ]
76 
        if s:
77 
            r += t[tuple(booleans[-s:] + ([0] * (8-s)))]
78 
        return ''.join(r)
79 
 
80 
    def complete(self):
81 
        return not self.numfalse
82 
 
83 
 
84 
def test_bitfield():
85 
    try:
86 
        x = Bitfield(7, 'ab')
87 
        assert False
88 
    except ValueError:
89 
        pass
90 
    try:
91 
        x = Bitfield(7, 'ab')
92 
        assert False
93 
    except ValueError:
94 
        pass
95 
    try:
96 
        x = Bitfield(9, 'abc')
97 
        assert False
98 
    except ValueError:
99 
        pass
100 
    try:
101 
        x = Bitfield(0, 'a')
102 
        assert False
103 
    except ValueError:
104 
        pass
105 
    try:
106 
        x = Bitfield(1, '')
107 
        assert False
108 
    except ValueError:
109 
        pass
110 
    try:
111 
        x = Bitfield(7, '')
112 
        assert False
113 
    except ValueError:
114 
        pass
115 
    try:
116 
        x = Bitfield(8, '')
117 
        assert False
118 
    except ValueError:
119 
        pass
120 
    try:
121 
        x = Bitfield(9, 'a')
122 
        assert False
123 
    except ValueError:
124 
        pass
125 
    try:
126 
        x = Bitfield(7, chr(1))
127 
        assert False
128 
    except ValueError:
129 
        pass
130 
    try:
131 
        x = Bitfield(9, chr(0) + chr(0x40))
132 
        assert False
133 
    except ValueError:
134 
        pass
135 
    assert Bitfield(0, '').tostring() == ''
136 
    assert Bitfield(1, chr(0x80)).tostring() == chr(0x80)
137 
    assert Bitfield(7, chr(0x02)).tostring() == chr(0x02)
138 
    assert Bitfield(8, chr(0xFF)).tostring() == chr(0xFF)
139 
    assert Bitfield(9, chr(0) + chr(0x80)).tostring() == chr(0) + chr(0x80)
140 
    x = Bitfield(1)
141 
    assert x.numfalse == 1
142 
    x[0] = 1
143 
    assert x.numfalse == 0
144 
    x[0] = 1
145 
    assert x.numfalse == 0
146 
    assert x.tostring() == chr(0x80)
147 
    x = Bitfield(7)
148 
    assert len(x) == 7
149 
    x[6] = 1
150 
    assert x.numfalse == 6
151 
    assert x.tostring() == chr(0x02)
152 
    x = Bitfield(8)
153 
    x[7] = 1
154 
    assert x.tostring() == chr(1)
155 
    x = Bitfield(9)
156 
    x[8] = 1
157 
    assert x.numfalse == 8
158 
    assert x.tostring() == chr(0) + chr(0x80)
159 
    x = Bitfield(8, chr(0xC4))
160 
    assert len(x) == 8
161 
    assert x.numfalse == 5
162 
    assert x.tostring() == chr(0xC4)