| 31 | |
| 32 | |
| 33 | class Node: |
| 34 | def __init__(self, childs): |
| 35 | assert childs |
| 36 | self.data = tuple(childs) |
| 37 | self.key = childs[0].key |
| 38 | |
| 39 | def split(self): |
| 40 | l = self.data |
| 41 | if len(l)<nmax: |
| 42 | return (self,) |
| 43 | n = nmax/2 |
| 44 | r = [] |
| 45 | while l: |
| 46 | r.append(Node(l[:n])) |
| 47 | l = l[n:] |
| 48 | return tuple(r) |
| 49 | |
| 50 | def insert(self, key, value): |
| 51 | last = None |
| 52 | for i, child in enumerate(self.data): |
| 53 | if key<child.key: |
| 54 | if last is not None: |
| 55 | l = self.data[:i-1]+last.insert(key, value).split()+self.data[i:] |
| 56 | else: |
| 57 | l = child.insert(key, value).split()+self.data[1:] |
| 58 | return Node(l) |
| 59 | last = child |
| 60 | l = self.data[:-1]+last.insert(key, value).split() |
| 61 | return Node(l) |
| 62 | |