Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- }
Add Comment
Please, Sign In to add comment