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

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

  toString: -> "ArrayNode(#{_.compact(@table).join(", ")})"


# -- exporting

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


# A collision node contains several leaf nodes, stored in an array
# @bucket, in which all keys share a common hash value.
class CollisionNode
  constructor: (@hash, @bucket) ->
    @bucket = [] unless @bucket?
    @size = @bucket.length

  each: (func) ->
    for node in @bucket
      node.each(func)

  get: (shift, hash, key) ->
    leaf = _.detect @bucket, (v) -> util.equal(v.key, key)
    leaf.get(shift, hash, key) if leaf?

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

  without: (shift, hash, key) ->
    switch @bucket.length
      when 0, 1 then null
      when 2    then _.detect @bucket, (v) -> not util.equal(v.key, key)
      else           new CollisionNode(hash, this.bucketWithout(key))

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

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


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