Search Algorithms in Python

Below are some popular implementations of searching algorithms.

#!/usr/bin/env python

class SequentialSearchDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.next = None
    
    def __init__(self):
        self.first = None
        self.size = 0
       
    def put(self, key, value):
        self._put(key, value)
    
    def _put(self, key, value):
        n = self._get(key)
        if n:
            n.value = value
            return 0
        else:
            # add the new node into the first
            tmp = self.first
            self.first = SequentialSearchDict.Node(key, value)
            self.first.next = tmp
            self.size += 1
            return 1
   
    def _get(self, key):
        n = self.first
        while n:
            if n.key == key: return n
            n = n.next
        return None
   
    def get(self, key):
        n = self._get(key)
        if n: return n.value
        return n
   
class BinarySearchDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
    
    def __init__(self):
        self.size = 0
        self.l = []
       
    def put(self, key, value):
        # the elements must be kept sorted for the binary search to work
        index = self._get(key)
        if index < 0:
            self.l.append(BinarySearchDict.Node(key, value))
            self.size += 1
            return
        n = self.l[index]
        if n.key == key:
            n.value = value
        else:
            self.l.append(BinarySearchDict.Node(key, value))
            # shift all the elements to the right
            if (index+1) < (len(self.l)-1):
                for i in xrange(len(self.l)-1, index, -1):
                    self.l[i] = self.l[i-1]
            self.size += 1
           
    def get(self, key):
        # search using binary search
        index = self._get(key)
        if index < 0: return None
        n = self.l[index]
        if n.key == key: return n.value
        return None
       
    def _get(self, key):
        lo = 0
        hi = len(self.l) - 1
        mid = (lo + hi) / 2
        while lo <= mid and hi >= mid:
            if self.l[mid].key > key:
                hi = mid - 1
                mid = (lo + hi) / 2
            elif self.l[mid].key == key:
                return mid
            elif self.l[mid].key < key:
                lo = mid + 1
                mid = (lo + hi) / 2
        return mid
       
class BinarySearchTreeDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            
    def __init__(self):
        self.size = 0
        self.root = None
       
    def put(self, key, value):
        self.root = self._put(key, value, self.root)
   
    def get(self, key):
        return self._get(key, self.root)
        
    def _put(self, key, value, node):
        if node == None:
            self.size += 1
            return BinarySearchTreeDict.Node(key, value)
        if node.key == key:
            node.value = value
            return node
        elif node.key < key: node.left = self._put(key, value, node.left)
        else: node.right = self._put(key, value, node.right)
        return node
        
    def _get(self, key, node):
        if node == None: return None
        if node.key == key: return node.value
        elif node.key < key: return self._get(key, node.left)
        else: return self._get(key, node.right)
   
class BalancedSearchTreeDict(object):
    class Node(object):
        RED = True
        BLACK = False
        
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            self.color = BalancedSearchTreeDict.Node.RED
            
        def is_red(self, node):
            if node == None: return False
            return node.color == BalancedSearchTreeDict.Node.RED
        
        def rotate_left(self, node):
            x = node.right
            node.right = x.left
            x.left = node
            node.color = BalancedSearchTreeDict.Node.RED
            return x 
        
        def rotate_right(self, node):
            x = node.left
            node.left = x.right
            x.right = node
            node.color = BalancedSearchTreeDict.Node.RED
            return x
        
        def flip_colors(self, node):
            node.color = BalancedSearchTreeDict.Node.RED
            node.left.color = BalancedSearchTreeDict.Node.BLACK
            node.right.color = BalancedSearchTreeDict.Node.BLACK
            
    def __init__(self):
        self.size = 0
        self.root = None
       
    def put(self, key, value):
        self.root = self._put(key, value, self.root)
        self.root.color = BalancedSearchTreeDict.Node.BLACK
   
    def _put(self, key, value, node):
        if node == None:
            self.size += 1
            return BalancedSearchTreeDict.Node(key, value)
        if node.key == key:
            node.value = value
            return node
        elif node.key < key: node.left = self._put(key, value, node.left)
        else: node.right = self._put(key, value, node.right)
        
        # these are the properties of Red-Black tree for balancing
        # the tree
        if node.is_red(node.right) and not node.is_red(node.left):
            node = node.rotate_left(node);
        if node.is_red(node.left) and node.is_red(node.left.left):
            node = node.rotate_right(node);
        if node.is_red(node.left) and node.is_red(node.right):
            node.flip_colors(node);
      
        return node
        
    def get(self, key):
        return self._get(key, self.root)
    
    def _get(self, key, node):
        if node == None: return None
        if node.key == key: return node.value
        elif node.key < key: return self._get(key, node.left)
        else: return self._get(key, node.right)
   
class HashDict(object):
    # choose this M to be a prime number
    M = 977
    
    def __init__(self, n=M):
        self.size = 0
        self.l = []
        for i in xrange(0, n):
            self.l.append(SequentialSearchDict())
            
    def _hash(self, key):
        return (hash(key) & 0x7ffffff) % HashDict.M
    
    def put(self, key, value):
        d = self.l[self._hash(key)]
        n = d._put(key, value)
        self.size += n
   
    def get(self, key):
        return self.l[self._hash(key)].get(key)
 
if __name__ == "__main__":
    searches = [SequentialSearchDict(),
                BinarySearchDict(),
                BinarySearchTreeDict(),
                BalancedSearchTreeDict(),
                HashDict()]
    for s in searches:                                                                                                                                                                                                                  
        assert None == s.get("foo")
        s.put("1", "a")
        s.put("2", "b")
        s.put("3", "c")
        assert 3 == s.size
        assert "b" == s.get("2")
        assert "c" == s.get("3")
        assert "a" == s.get("1")
        s.put("3", "d")
        assert 3 == s.size
        assert "d" == s.get("3")
        assert "b" == s.get("2")
        assert "a" == s.get("1")
        assert None == s.get("bar")