A simple binary search tree in coffeescript Uses djb hash on string keys

binary-search-tree.coffee

class Tree
    constructor: ->
        throw new Error "Tree is an abstract class"

    hasKey: (key) ->
        (@lookup key).length is 1

    get: (key, _default=null) ->
        result = @lookup key
        if result.length is 0
            _default
        else
            result[0]

    validate: ->
        validate = (tree, min, max) ->
            if tree instanceof EmptyTree
                true
            else
                {left, right, pair: {key}} = tree
                (min < key && key < max) &&
                (validate left, min, key) &&
                (validate right, key, max)

        validate this, -Infinity, Infinity

    add: (key, value) ->
        @addHashedKey (@hash key), value

    hash: (str) ->
        Tree.djbHashString str

    @fromObject: (obj) ->
        tree = new EmptyTree

        for k, v of obj
            tree = tree.add k, v

        tree

    @fromPairsArray: (arr) ->
        tree = new EmptyTree

        for [k, v] in arr
            tree = tree.add k, v

        tree

    @djbHashString: (str) ->
        # using djb hash
        hash = 5381
        i = str.length

        while i--
            hash = ((hash << 5) + hash) + (str.charCodeAt i)
        
        hash


class Node extends Tree
    constructor: (@pair, @left, @right) ->

    LESS_THAN = -1
    GREATER_THAN = 1
    EQUAL = 0


    addHashedKey: (key, value) ->
        switch @compare key, @pair.key
            when EQUAL
                kv = (new KeyValuePair key, value)
                new Node kv, @left, @right

            when LESS_THAN
                new Node @pair, (@left.addHashedKey key, value), @right

            when GREATER_THAN
                new Node @pair, @left, (@right.addHashedKey key, value) 

    compare: (a, b) ->
        if a < b 
            LESS_THAN
        else if a > b
            GREATER_THAN
        else
            EQUAL

    lookup: (key) -> 
        @lookupHashedKey (@hash key)

    lookupHashedKey: (key) ->
        switch @compare key, @pair.key
            when EQUAL
                [ @pair.value ]

            when LESS_THAN
                @left.lookupHashedKey key

            when GREATER_THAN
                @right.lookupHashedKey key

    merge: (tree) ->
        merge = (a, b) ->
            if a instanceof EmptyTree
                return b

            if b instanceof EmptyTree
                return a

            {key, value} = a.pair

            tree = b.addHashedKey key, value
            tree = merge a.left, tree
            merge a.right, tree

        merge tree, this



class EmptyTree extends Tree
    constructor: ->

    addHashedKey: (key, value) ->
        kv = new KeyValuePair key, value
        new Node kv, (new EmptyTree), (new EmptyTree)

    lookupHashedKey: (key) -> []

    merge: (tree) -> tree

    clone: -> new EmptyTree

class KeyValuePair
    constructor: (@key, @value) ->

exports.Tree = Tree

do ->
    assert = require 'assert'
    tree = Tree.fromObject
        'poop': 'fart',
        'alpha': 'beta',
        'cat': 'pizza',
        'pizza': 'cat',
        'elephant': 'time'

    assert.equal (tree.get 'apple'), null
    assert.equal (tree.get 'apple', 'pie'), 'pie'

    assert.equal (tree.get 'poop'), 'fart'
    assert.equal (tree.get 'elephant'), 'time'

    tree2 = Tree.fromObject
        'poop': 'pee',
        'booze': 'vodka'

    tree3 = tree.merge tree2

    assert.equal (tree3.get 'apple'), null
    assert.equal (tree3.get 'pizza'), 'cat'
    assert.equal (tree3.get 'poop'), 'pee'

    assert.ok do tree.validate
    assert.ok do tree2.validate
    assert.ok do tree3.validate

    # Make a bad tree where there is an
    # key of Infinity to the left of center
    tree.left.right.pair.key = Infinity
    assert.ok !do tree.validate