B+-tree実装終了

とりあえずらしきものは出来上がった。

class BalancedPlusTree:
    """B+-tree.
    データはエッジノード(leaf)にのみ存在。"""
    class _leaf:
        """B+-treeのleaf.
        データを持つ"""
        def __init__(self,parent,prev=None,next=None):
            self.index=[]
            self.value=[]
            self.parent=parent
            self.prev=prev
            self.next=next
        def length(self):
            return len(self.index)
        def divide(self):
            """leafを2つに分割する."""
            ret=BalancedPlusTree._leaf(self,self.parent,self.next)
            if self.next:
                self.next.prev=ret
                self.next=ret
            index=len(self.index)/2
            ret.index=self.index[index:]
            ret.value=self.value[index:]
            tmp=self.index[index]
            self.index=self.index[:index]
            self.value=self.value[:index]
            self.next=ret
            return (tmp,ret)
        def merge(self):
            """隣のノードとマージする"""
            if self.next and self.parent==self.next.parent:
                self.next.index=self.index+self.next.index
                self.next.value=self.value+self.next.value
                self.next.prev=self.prev
                if self.prev:
                    self.prev.next=self.next
            elif self.prev and self.parent==self.prev.parent:
                self.prev.index=self.prev.index+self.index
                self.prev.value=self.prev.value+self.value
                self.prev.next=self.next
            else:
                #マージ対象がない
                raise Exception()
        def append(self,index,value):
            if self.index:
                for i in range(len(self.index)):
                    if self.index[i]>=index:
                        break
                if self.index[i]==index:
                    self.value[i]=value
                elif self.index[i]>index:
                    self.index=self.index[:i]+[index]+self.index[i:]
                    self.value=self.value[:i]+[value]+self.value[i:]
                elif self.next and self.next.index[0]>index:
                    self.index.append(index)
                    self.value.append(value)
                else:
                    self.index.append(index)
                    self.value.append(value)
            else:
                self.index=[index]
                self.value=[value]
            return len(self.index)
        def remove(self,index):
            ret=None
            for i in range(len(self.index)):
                if self.index[i]>=index:
                    break
            if self.index[i]==index:
                ret=self.value[i]
                self.index=self.index[:i]+self.index[i+1:]
                self.value=self.value[:i]+self.value[i+1:]
            return ret
        def get(self,index):
            ret=None
            if self.index:
                for i in range(len(self.index)):
                    if self.index[i]>=index:
                        break
                if self.index[i]==index:
                    ret=self.value[i]
            return ret
    class _node:
        """B+-treeのnode"""
        def __init__(self,max_n,parent=None):
            self.N=(max_n/2)*2
            self.parent=parent
            self.index=[]
            self.link=[]
        def append(self,index,value):
            if self.index:
                if self.index[0]>index:
                    self.index[0]=index
                    i=0
                else:
                    for i in range(len(self.index)):
                        if self.index[i]>index:
                            i=i-1
                            break
                if self.link[i].append(index,value)>self.N:
                    newindex,newnode=self.link[i].divide()
                    self.index=self.index[:i+1]+[newindex]+self.index[i+1:]
                    self.link=self.link[:i+1]+[newnode]+self.link[i+1:]
            else:
                self.index=[index]
                ge=BalancedPlusTree._leaf(self)
                self.link=[ge]
                ge.append(index,value)
            return len(self.index)
        def divide(self):
            ret=BalancedPlusTree._node(self.N,self.parent)
            index=len(self.index)/2
            ret.index=self.index[index:]
            ret.link=self.link[index:]
            self.index=self.index[:index]
            self.link=self.link[:index]
            return ret.index[0],ret
        def remove(self,index):
            if self.index:
                for i in range(len(self.index)):
                    if self.index[i]>index:
                        i=i-1
                        break
                ret=self.link[i].remove(index)
                if self.link[i]==0:
                    self.index=self.index[:i]+self.index[i+1:]
                    self.link=self.link[:i]+self.link[i+1:]
                return ret
            else:
                return None
        def get(self,index):
            for i in range(len(self.index)):
                if self.index[i]>index:
                    i=i-1
                    break
            return self.link[i].get(index)
        def length(self):
            return len(self.index)
    def __init__(self,max_n):
        self.N=(max_n/2)*2
        self.top=BalancedPlusTree._node(self.N)
        self.data=None
    def append(self,index,value):
        tmp=self.top.append(index,value)
        if not self.data:
            self.data=self.top.link[0]
        if tmp>self.N:
            tmpnode=BalancedPlusTree._node(self.N)
            self.top.parent=tmpnode
            newindex,newnode=self.top.divide()
            tmpnode.index=[self.top.index[0],newindex]
            tmpnode.link=[self.top,newnode]
            self.top=tmpnode
    def remove(self,index):
        return self.top.remove(index)
    def get(self,index):
        return self.top.get(index)

以下のところでも公開している。
http://www.masahase.mydns.jp/hg/lib-study/