oaktree.py

def sbin(toPrint):
    return "{:0b}".format(toPrint)

class OctNode:
    def __init__(self, parentNode, data):
        self.parentNode = parentNode
        #self.position = position
        self.data = data

        self.leaf = True
        self.branches = {}

    def branch(self):
        self.leaf = False
        self.branches = {}

        for i in xrange(8):
            self.branches[i] = OctNode(self, None)

    def debug(self):
        print "Data: " + str(data)

        if self.leaf:
            print "Leaf!"
        else:
            for i in xrange(8):
                self.branches[i].debug()

class Octree:
    def __init__(self):
        self.root = OctNode(None, None)

    def set(self, position, data):
        self.get(position).data = data

    def get(self, position):
        length = len(sbin(position[0]))
        currNode = self.root

        for i in xrange(length):
            x = (position[0] >> i) & 1
            y = (position[1] >> i) & 1
            z = (position[2] >> i) & 1

            #print int(sbin(x) + sbin(y) + sbin(z),2)

            i = (x << 2) | (y << 1) | z

            #print int(sbin(i),2)

            #print "--"

            if currNode.leaf:
                currNode.branch()

            currNode = currNode.branches[i]

        return currNode

    def debug(self):
        self.root.debug()

import datetime, random
octree = Octree()

for i in xrange(2000):
    x = random.randint(0, 1000000)
    y = random.randint(0, 1000000)
    z = random.randint(0, 1000000)

    octree.set((x, y, z), "test")


#octree.get((x, y, z)).data