 # You must not remove this notice, or any other, from this software.
 # --------------------------------------------------------------------
 
-
 if typeof(require) == 'function'
   require 'underscore'
   util = require 'hash_util'

  toString: -> "LeafNode(#{@key}, #{@value})"


# A collision node contains several key-value pairs in which all keys
# have a common hash value, which is cached. The key-value pairs are
# stored in an array @bucket.
class CollisionNode
  constructor: (@hash, @bucket) ->
    @bucket = [] unless @bucket?
    @size = @bucket.length

  each: (func) ->
    for item in @bucket
      func(item)

  get: (shift, hash, key) ->
    pair[1] if (pair = _.detect @bucket, (pair) -> util.equal(pair[0], key))?

  with: (shift, hash, leaf) ->
    if hash != @hash
      new BitmapIndexedNode().with(shift, @hash, this).with(shift, hash, leaf)
    else
      newBucket = this.bucketWithout(leaf.key).concat([[leaf.key, leaf.value]])
      new CollisionNode(hash, newBucket)

  without: (shift, hash, key) ->
    newBucket = this.bucketWithout key
    if newBucket.length < 2
      new LeafNode(hash, _.first(newBucket)...)
    else
      new CollisionNode(hash, newBucket)

  toString: -> "CollisionNode(#{@bucket.join(", ")})"

  bucketWithout: (key) ->
    item for item in @bucket when not util.equal(item[0], key)


# A sparse interior node using a bitmap to indicate which of the

      else
        new ArrayNode(@table, i, null, @size - 1)

  toString: -> "ArrayNode(#{(x for x in @table when x?).join(", ")})"


# -- exporting
