nmax = 20 # max number of branches per node
class Values:
key = None
def __init__(self, data):
self.data = tuple(data)
if len(data):
self.key = data[0][0]
def split(self):
l = self.data
if len(l)<nmax:
return (self,)
n = nmax/2
r = []
while l:
r.append(Values(l[:n]))
l = l[n:]
return tuple(r)
def insert(self, key, value):
for i, (k, v) in enumerate(self.data):
if key<k:
l = self.data[:i]+((key, value),)+self.data[i:]
return Values(l)
elif key == k:
l = self.data[:i]+((key, value),)+self.data[i+1:]
return Values(l)
l = self.data+((key, value),)
return Values(l)
class Node:
def __init__(self, childs):
assert childs
self.data = tuple(childs)
self.key = childs[0].key
def split(self):
l = self.data
if len(l)<nmax:
return (self,)
n = nmax/2
r = []
while l:
r.append(Node(l[:n]))
l = l[n:]
return tuple(r)
def insert(self, key, value):
last = None
for i, child in enumerate(self.data):
if key<child.key:
if last is not None:
l = self.data[:i-1]+last.insert(key, value).split()+self.data[i:]
else:
l = child.insert(key, value).split()+self.data[1:]
return Node(l)
last = child
l = self.data[:-1]+last.insert(key, value).split()
return Node(l)
Diff to Previous Revision
--- revision 1 2014-05-14 18:26:49
+++ revision 2 2014-05-14 19:16:04
@@ -1,4 +1,4 @@
-nmax = 20
+nmax = 20 # max number of branches per node
class Values:
key = None
