octree.rb

class Integer
    def orBit(i, bool)
        if bool then self | (1 << i) else self end
    end
    
    def bit(i)
        mask = 1 << i
        (self & mask) / mask
    end
end

"""
    A point in space.
"""
class Point < Struct.new :x, :y, :z

    """
        Immitent descent direction at given level.
    """
    def octantAtLevel(edge)
        x.bit(edge) + y.bit(edge) * 2 + z.bit(edge) * 4
    end
    
    """
        One step of descent.
    """
    def descent(dir, edge)
        Point.new(
            x.orBit(edge, dir.bit(0).nonzero?),
            y.orBit(edge, dir.bit(1).nonzero?),
            z.orBit(edge, dir.bit(2).nonzero?),
        )
    end
    
    def inspect
        "{#{x},#{y},#{z}}"
    end
end

"""
    The shape for the volume of space.
"""
class Location < Struct.new :point, :edge

    """
        Get number of child cube to descent to get to the specified point.
    """
    def getOctant(pt)
        pt.octantAtLevel(edge / 2)
    end
    
    """
        Get a location of child cube of given number.
    """
    def descent(dir)
        half_edge = edge >> 1
        Location.new(point.descent(dir, half_edge), half_edge)
    end
    
    def atomic?
        edge == 0
    end
    
    def inspect
        "#{point.inspect}-#{edge}"
    end
end

"""
    We want to make a structure we can ask
    
    > point = Point.new x, y, z
    > space[point]
    
    and it will return a material at that point.
    
    We also want to say
    
    > space[point] = newMaterial
    
    and it will set that material at point.
    
    For start this will be enough.
"""

"""
    First case of that structure: Atom.
    
    It only knows it is made from 1 material only.
    
    So dumb it even doesn't cares about its location.
    (this is, probably, a design problem)
"""
class Atom < Struct.new :material
    def [](point)
        material
    end
    
    class SettingIntoAtom < StandardError
    end
    
    def []=(point, mat)
        raise SettingIntoAtom, {point: point, mat: mat}
    end
    
    def inspect
        material
    end
end

"""
    Second case, Split - our working horse.
    
    Eight cubes with edge N, tightly packed into one with edge 2N.
"""
class Split < Struct.new :children, :location

    """
        Basically, generates split of given material.
    """
    def self.of loc, mat
        Split.new (0..7).map { |_| Atom.new mat }, loc
    end

    """
        Retrieves material at point.
    """
    def [](point)
        dir  = location.getOctant(point)
        tree = self.descent(dir)
        tree[point]
    end

    """
        Sets given material at given point.
        
        If we're just above atoms, puts new Atom.
        Otherwise, descents into Splits and Atoms alike.
    """    
    def []=(point, mat)
        dir  = location.getOctant(point)

        if location.atomic? then
            children[dir] = Atom.new mat
        else
            tree = self.descent(dir)
            if tree.is_a? Atom then
                split         = Split.of location.descent(dir), tree.material
                children[dir] = split
                tree          = split
            end
            
            tree[point] = mat
        end
    
        tryWelding dir
    end
    
    """
        If child in given octant is a Split of equal Atoms, weld it into one Atom.
    """
    def tryWelding dir
        child = descent dir
        if child.is_a? Split and
           child.children.all? { |grandchild| grandchild.is_a? Atom } and
           child.children.map(&:material).uniq.length == 1
        then
            children[dir] = Atom.new child.children[0].material
        end
    end
    
    """
        Return child at given direction. If it is a Thunk, force it to generate.
    """
    def descent(dir)
        if children[dir].is_a? Thunk then
            children[dir] = children[dir].generate()
        end
        children[dir]
    end
    
    def inspect
        "split@#{location.inspect}:#{children}"
    end
end

"""
    Non-generated-yet volume of space.
"""
class Thunk < Struct.new :generator
    def generate
        generator.()
    end
    
    def inspect
        "?"
    end
end

"""
    Generates tree to fill the location.
    Materials generated will be numbers of lowest cubes: 0.. 7.
"""
def generate(loc)
    if loc.edge == 0 then
        Atom.new loc.point.octantAtLevel 0
    else
        Split.new (0..7).map { |dir|
            Thunk.new ->() { generate loc.descent dir }
        }, loc
    end
end

"""
    TDD saves the day, as usual.
    Todo: use rspec here.
"""
module Test

    """
        Nothing to see here, move along.
    """
    def self.describe(name, &block)
        @@tests  = []
        failures = []

        self.instance_eval &block

        print name + ' '

        @@tests.each do |test|
            case
            when test[:crashed?]
                failures << test
                putc 'E'
            else
                putc '.'
            end
        end

        if failures.empty? then
            puts ' all good.'
        else
            puts ''
            failures.each do |test|
                case
                when test[:crashed?]
                    puts "  Failed: it #{test[:name]}:\n    #{test[:error]}\n"
                end
            end
        end

        return
    end

    """
        Nothing to see here, move along.
    """
    def self.it(name)
        begin
            res = yield
            @@tests << {name: name, failed?: !res}

        rescue StandardError => e
            @@tests << {name: name, crashed?: true, error: e}
        end
    end
    
    class NotEqualError < StandardError
    end
    
    """
        Still nothing to see here, move along.
    """
    def self.equals? (x, y)
        raise NotEqualError, "#{x} =/= #{y}" if x != y
        true
    end
end

Test.describe "Point" do
    it "retrieves correct octant at level 0" do
        equals? 5, Point.new(1,0,1).octantAtLevel(0)
    end

    it "retrieves correct octant at level 1" do
        equals? 6, Point.new(1,2,3).octantAtLevel(1)
    end

    it "retrieves correct octant at level 2" do
        equals? 0, Point.new(1,2,3).octantAtLevel(2)
    end
    
    it "compares by structure" do
        equals? Point.new(1,2,3), Point.new(1,2,3)
    end
    
    it "descends correctly at level 0" do
        equals? Point.new(0,0,0).descent(5, 0), Point.new(1, 0, 1)
    end
    
    it "descends correctly at level 1" do
        equals? Point.new(0,0,0).descent(2, 1), Point.new(0, 2, 0)
    end
end

Test.describe "Integer" do
    it "retrieves correct bit#0" do
        equals? 5.bit(0), 1
    end

    it "retrieves correct bit#1" do
        equals? 5.bit(1), 0
    end
end

Test.describe "generate" do
    space = generate Location.new Point.new(0, 0, 0), 4
        
    it "generates correct tree" do
        equals? space[Point.new(0, 0, 0)], 0
    end

    it "generates correct tree" do
        equals? space[Point.new(1, 0, 1)], 5
    end

    it "the tree volume repeats itself in all directions" do
        equals? space[Point.new(1 + 4, 0 + 4, 1)], 5
    end

    it "the tree volume REALLY repeats itself in all directions" do
        equals? space[Point.new(1 + 16, 1 + 8, 1)], 7
    end

    it "the tree accepts writes" do
        space[Point.new(1, 1, 0)] = 42
        equals? space[Point.new(1, 1, 0)], 42
        equals? space[Point.new(1, 1, 1)], 7
        
        # should cause welding
        space[Point.new(1, 1, 0)] = 3
    end
end