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")
