Source Code for Module envi.bintree

 1  import envi.bits as e_bits 
 2  
 
 3 -class BinaryTree: 
 4      '''
 
 5      A simple binary search tree capable of using integers
 
 6      or string representations of binary integers as inputs.
 
 7  
 
 8      NOTE: the lookup routines assume once a node is found which
 
 9      has nodeinfo, we have matched.  It does *not* need to walk
 
10      the rest of the values...
 
11      ''' 
12 -    def __init__(self): 
13          self.basenode = [None, None, None] 
14  
 
15 -    def addInt(self, intval, width, nodeinfo): 
16          node = self.basenode 
17          for sh in xrange(width-1, -1, -1): 
18              choice = (intval >> sh) & 1 
19              if node[choice] == None: 
20                  node[choice] = [None, None, None] 
21              node = node[choice] 
22          node[2] = nodeinfo 
23  
 
24 -    def addBinstr(self, binstr, nodeinfo): 
25          bval = e_bits.binary(binstr) 
26          return self.addInt(bval, len(binstr), nodeinfo) 
27  
 
28      #def addString(self, charstr, nodeinfo):
 
29      # e_bits the whole string to a huge int?
 
30  
 
31 -    def getInt(self, intval, width): 
32          '''
 
33          Get an element back out of the tree.
 
34  
 
35          width is in bits...
 
36          ''' 
37          node = self.basenode 
38          for sh in xrange(width-1, -1, -1): 
39              choice = (intval >> sh) & 1 
40              node = node[choice] 
41              ninfo = node[2] 
42              if ninfo != None: 
43                  return ninfo 
44          return node[2] 
45  
 
46 -    def getBinstr(self, binstr): 
47          bval = e_bits.binary(binstr) 
48          return self.getInt(bval, len(bstr)) 
49