aob.js

const toString = require('tree-to-string')
const util = require('util')

module.exports = BTree

function BTree () {
  this.feed = []
}

BTree.prototype.put = function (key, value) {
  this.insert({key, value})
}

BTree.prototype.insert = function (val) {
  if (!this.feed.length) {
    const node = new Node()
    node.values.push(val)
    node.seq = 0
    this.feed.push(node)
    return
  }

  // find leaf
  var i
  var node = this.feed[this.feed.length - 1]
  var next
  var tick = this.feed.length

  const stack = []
  const batch = []
  const seqs = []

  while (node.children.length) {
    next = node.children[node.children.length - 1]

    for (i = 0; i < node.values.length; i++) {
      const v = node.values[i]
      const c = cmp(v, val)

      if (c === 0) {
        var o = node
        node = node.clone()
        node.values[i] = v
        node.seq = tick++
        batch.push(node)
        this.commit(batch, tick, node, stack, seqs)
        return
      }
      if (c > 0) {
        next = node.children[i]
        break
      }
    }

    stack.push(node)
    seqs.push(node.children.indexOf(next))
    node = this.feed[next]
  }

  for (i = 0; i < node.values.length; i++) {
    const v = node.values[i]
    const c = cmp(v, val)

    if (c === 0) {
      node = node.clone()
      node.seq = tick++
      node.values[i] = val
      batch.push(node)
      this.commit(batch, tick, node, stack, seqs)
      return
    }
    if (c > 0) break
  }

  node = node.clone()
  node.values.splice(i, 0, val)

  if (node.values.length <= 2) {
    node.seq = tick++
    batch.push(node)
  }

  while (node.values.length > 2) {
    const parent = (stack.pop() || new Node()).clone()
    seqs.pop()

    const left = node.clone()
    const right = new Node()

    right.values.push(left.values.pop())
    const mid = left.values.pop()

    if (left.children.length) {
      const b = left.children.pop()
      const a = left.children.pop()
      right.children.push(a)
      right.children.push(b)
    }

    left.seq = tick++
    right.seq = tick++
    batch.push(left, right)

    for (i = 0; i < parent.values.length; i++) {
      const v = parent.values[i]
      if (cmp(v, mid) > 0) break
    }

    parent.values.splice(i, 0, mid)
    parent.children.splice(i, 0, 0)
    parent.children[i] = left.seq
    parent.children[i + 1] = right.seq
 
    node = parent
    if (node.values.length <= 2) {
      node.seq = tick++
      batch.push(node)
    }
  }

  this.commit(batch, tick, node, stack, seqs)
}

BTree.prototype.commit = function (batch, tick, node, stack, seqs) {
  while (stack.length) {
    const parent = stack.pop().clone()
    const seq = seqs.pop()
    parent.children[seq] = node.seq
    parent.seq = tick++
    batch.push(parent)
    node = parent
  }

  for (var i= 0 ; i < batch.length; i++) this.feed.push(batch[i])
}

BTree.prototype.toString = function () {
  var self = this

  return toString(map(this.feed[this.feed.length - 1]), format)

  function map (node) {
    return {
      values: node.values,
      children: node.children.map(seq => self.feed[seq]).map(map)
    }
  }
}

function cmp (a, b) {
  return a.key < b.key ? -1 : a.key > b.key ? 1 : 0
}

function Node () {
  this.seq = 0
  this.values = []
  this.children = []
}

Node.prototype.clone = function () {
  const node = new Node()
  node.seq = this.seq
  node.values = this.values.slice(0)
  node.children = this.children.slice(0)
  return node
}

function format (nodes) {
  var start = ''
  for (var i = 0; i < nodes.length; i++) {
    if (i) start += '\n'
    start += util.inspect(nodes[i].key) + ' => ' + util.inspect(nodes[i].value)
  }
  return start
}