main.nim

template `as` (a, b: untyped): untyped = ((b)a)

type
  BSPNode[T] = ref object of RootObj
    parent: BSPNode[T]
  ParentNode[T] = ref object of BSPNode[T]
    forward, backward: BSPNode[T]
    position: float
  Leaf[T]= ref object of BSPNode[T]
    content: T
    left, top, right, bottom: int
  HSplit[T] = ref object of ParentNode[T]
  VSplit[T] = ref object of ParentNode[T]
  BSPTree[T] = ref object
    root: BSPNode[T]
    leaves: seq[BSPNode[T]]

proc newLeaf[T](content: T, left, top, right, bottom: int, parent: BSPNode[T] = nil): Leaf[T] =
  result = new(Leaf[T])
  result.parent = parent
  result.content = content
  result.left = left
  result.top = top
  result.right = right
  result.bottom = bottom

proc newBSPTree[T](content: T, left, top, right, bottom: int): BSPTree[T] =
  result = new(BSPTree[T])
  result.root = newLeaf(content, left, top, right, bottom)
  result.leaves = @[result.root]

proc midpoint[T](self:VSplit[T], target: Leaf): int =
  let width = target.right - target.left
  result = target.left + int(self.position * width.float)

proc midpoint[T](self:HSplit[T], target: Leaf): int =
  let height = target.bottom - target.top
  result = target.top + int(self.position * height.float)

proc adjustSource[T](self: VSplit[T], target: Leaf, midpoint: int) =
  target.right = midpoint
  target.parent = self

proc adjustSource[T](self: HSplit[T], target: Leaf, midpoint: int) =
  target.bottom = midpoint
  target.parent = self

proc newSibling[T](self: VSplit[T], target: Leaf, midpoint: int): Leaf =
  newLeaf[T](nil, midpoint, target.top, target.right, target.bottom, self)

proc newSibling[T](self: HSplit[T], target: Leaf, midpoint: int): Leaf =
  newLeaf[T](nil, target.left, midpoint, target.right, target.bottom, self)

proc newParent[T, K](self: BSPTree[T], parent: BSPNode[T], position: float): K =
  result = new(K)
  result.parent = parent
  result.position = position

  if isNil(parent):
    self.root = result

proc split[T, K](self: BSPTree[T], target: Leaf, parent: K): Leaf[T] =
  let mp = parent.midpoint(target)
  parent.backward = target
  parent.forward = parent.newSibling(target, mp)
  parent.adjustSource(target, mp)
  return (parent.forward as Leaf)

proc vsplit[T](self: BSPTree[T], target:Leaf, position: float): Leaf[T] =
  var parent = newParent[T, VSplit[T]](self, target.parent, position)
  return self.split(target, parent)

proc hsplit[T](self: BSPTree[T], target:Leaf, position: float): Leaf[T] =
  var parent = newParent[T, HSplit[T]](self, target.parent, position)
  return self.split(target, parent)

proc delete[T](self: BSPTree[T], target:Leaf): Leaf[T] =
  # return target if it is the root node
  if self.root == target:
    return target

  var parent = (target.parent as ParentNode[T])

  # determine correct sibling
  if target == (parent.forward as Leaf):
    result = (parent.backward as Leaf)
  else:
    result = (parent.forward as Leaf)

  # if target's parent is root
  if self.root == target.parent:
    self.root = result
    return result

  if isNil(parent.parent):
    return result

  var grandparent = (parent.parent as ParentNode[T])

  # if target's parent is a split
  if parent == (grandparent.forward as ParentNode[T]):
    grandparent.forward = result
  else:
    grandparent.backward = result

test.nim

import unittest

include main

type
  sLeaf = Leaf[string]
  sHSplit = HSplit[string]
  sVSplit = VSplit[string]

suite "bsp tree":
  setup:
    var
      content = "Hello World"
      bsp = newBSPTree(content, 0, 0, 100, 100)
      root = (bsp.root as sLeaf)

  test "creation":
    check:
      bsp.root of sLeaf
      isNil(root.parent)
      root.left == 0
      root.top == 0
      root.right == 100
      root.bottom == 100
      root in bsp.leaves
      root.content == content

  test "horizontal split":
    var
      sib = bsp.hsplit(root, 0.5)
      split = (bsp.root as sHSplit)

    check:
      bsp.root == sib.parent
      sib.parent of sHSplit
      sib == (split.forward as sLeaf)
      root == (split.backward as sLeaf)
      root.top == 0
      root.bottom == 50
      sib.top == 50
      sib.bottom == 100

  test "vertical split":
    var
      sib = bsp.vsplit(root, 0.5)
      split = (bsp.root as sVSplit)

    check:
      bsp.root == sib.parent
      sib.parent of sVSplit
      sib == (split.forward as sLeaf)
      root == (split.backward as sLeaf)
      root.left == 0
      root.right == 50
      sib.left == 50
      sib.right == 100


  test "deletion":
    var
      sib = bsp.vsplit(root, 0.5)
      split = (bsp.root as sVSplit)
      newRoot = bsp.delete(root)

    check:
      bsp.root == newRoot