fingertree.coffee

# @fileoverview Implementation of Finger Tree, an immutable general-purpose
#   data structure which can further be used to implement random-access
#   sequences, priority-queues, ordered sequences, interval trees, etc.
#
#   Based on:
#   Ralf Hinze and Ross Paterson,
#   "Finger trees: a simple general-purpose data structure",
#   <http://www.soi.city.ac.uk/~ross/papers/FingerTree.html>
# @author Xueqiao Xu <xueqiaoxu@gmail.com>
#
# Converted to CoffeeScript by Bill Burdick, 2015
# I converted this for people like me who prefer to read the code, rather
# than generated docs.  With this in mind, I've condensed the code to make
# it easier to see more code at a time and removed doc generation-only
# information (like @inheritDoc comments).  Also, in the name of readability
# and brevity, I have removed many micro-optimizations (like caching this.*
# in a variable) because I think most VMs will handle these anyway.  Other
# than that, I've tried to preserve the original author's intent.
#
# MIT License
#
# © 2014 Xueqiao Xu <xueqiaoxu@gmail.com>
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use, copy,
# modify, merge, publish, distribute, sublicense, and/or sell copies
# of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

'use strict'

# Placeholder for methods of interfaces / abstract base classes.
notImplemented = -> throw new Error 'Not Implemented'

# A split is a container which has 3 parts, in which the left part is the
# elements that do not satisfy the predicate, the middle part is the
# first element that satisfies the predicate and the last part is the rest
# elements.
class Split
  # @param {Array|FingerTree} left
  # @param {*} mid
  # @param {Array|FingerTree} right
  constructor: (@left, @mid, @right)->

# A digit is a measured container of one to four elements.
# @constructor
# @param {Object.<string, function>} measurer
# @param {Array.<*>} items
class Digit
  constructor: (@measurer, @items)->
    @length = @items.length
    m = @measurer.identity()
    for item in @items
      m = @measurer.sum m, @measurer.measure item, this
    # @private
    @measure_ = m;

  # Get the measure of the digit.
  measure: -> @measure_

  # Get the first element stored in the digit.
  peekFirst: -> @items[0]

  # Get the last element stored in the digit.
  peekLast: -> @items[this.items.length - 1]

  # Return a new digit with the first item removed.
  # @return {Digit}
  removeFirst: -> @slice(1)

  # Return a new digit with the first item removed.
  # @return {Digit}
  removeLast: -> @slice(0, this.length - 1)

  # Return a new digit with the items sliced.
  # @param {Number} start
  # @param {Number} end
  # @return {Digit}
  slice: (start, end)->
    if !end? then end = @length
    new Digit @measurer, @items.slice start, end

  # Split the digit into 3 parts, in which the left part is the elements
  # that does not satisfy the predicate, the middle part is the first
  # element that satisfies the predicate and the last part is the rest
  # elements.
  # @param {Function} predicate A function which returns either true or false
  #   given each stored element.
  # @param {*} initial The initial measure for the predicate
  # @return {Split}
  split: (predicate, initial)->
    measure = initial
    i = null

    if @items.length == 1 then new Split [], @items[0], []
    else
      for item, i in @items
        measure = @measurer.sum measure, @measurer.measure(item)
        if predicate measure then break
      new Split @items.slice(0, i), item, @items.slice(i + 1)

  # Return the JSON representation of the digit.
  toJSON: ->
    type: 'digit'
    items: @items
    measure: @measure()

# A node is a measured container of either 2 or 3 sub-finger-trees.
class Node
  # @param {Object.<string, function>} measurer
  # @param {Array.<FingerTree>} items
  constructor: (@measurer, @items)->
    m = @measurer.identity()
    for item in @items
      m = @measurer.sum m, @measurer.measure item
    # @private
    @measure_ = m

  # Get the measure of the node.
  measure: -> @measure_

  # Convert the node to a digit.
  # @return {Digit}
  toDigit: -> new Digit @measurer, @items

  # Return the JSON representation of the node.
  toJSON: ->
    type: 'node'
    items: @items
    measure: @measure()

# Interface of finger-tree.
# @interface
export class FingerTree
  # Get the measure of the tree.
  @measure: notImplemented

  # Force on a normal FingerTree just returns this
  force: -> this

  # Check whether the tree is empty.
  # @return {boolean} True if the tree is empty.
  isEmpty: notImplemented

  # Return a new tree with an element added to the front.
  # @param {*} v The element to add.
  # @return {FingerTree}
  addFirst: notImplemented

  # Return a new tree with an element added to the end.
  # @param {*} v The element to add.
  # @return {FingerTree} A new finger-tree with the element added.
  addLast: notImplemented

  # Return a new tree with the first element removed.
  # @return {FingerTree}
  removeFirst: notImplemented

  # Return a new tree with the last element removed.
  # @return {FingerTree}
  removeLast: notImplemented

  # Get the first element of the tree.
  # @return {*}
  peekFirst: notImplemented

  # Get the last element of the tree.
  # @return {*}
  peekLast: notImplemented

  # Concatenate this tree with another tree.
  # @param {FingerTree} other
  # @return {FingerTree} The concatenated tree.
  concat: notImplemented

  # Split the tree into two halves, where the first half is a finger-tree
  # which contains all the elements that satisfy the given predicate,
  # while the ones from the other half do not.
  # @param {function(*): boolean} predicate
  # @return {Array.<FingerTree>} An array with the first element being a
  #   finger-tree that contains all the satisfying elements and the second
  #   element being a finger-tree that contains all the other elements.
  split: notImplemented

  # Take elements from the tree until the predicate returns true.
  # @param {function(*): boolean} predicate
  # @return {FingerTree}
  takeUntil: (predicate)-> @split(predicate)[0]

  # Drop elements from the tree until the predicate returns true.
  # @param {function(*): boolean} predicate
  # @return {FingerTree}
  dropUntil: (predicate)-> @split(predicate)[1]

  # @return the JSON representation of the tree.
  toJSON: notImplemented

  # iterate over the nodes
  each: (func)->
    t = this
    while !t.isEmpty()
      func t.peekFirst()
      t = t.removeFirst()

  # iterate over the nodes
  eachReverse: (func)->
    t = this
    while !t.isEmpty()
      func t.peekLast()
      t = t.removeLast()

  toArray: ->
    a = []
    @each (n)-> a.push n
    a

# An empty finger-tree.
class Empty extends FingerTree
  constructor: (@measurer)->
    super()
    @measure_ = @measurer.identity()
  measure: -> @measure_
  addFirst: (v)-> new Single @measurer, v
  addLast: (v)-> new Single @measurer, v
  peekFirst: -> null
  peekLast: -> null
  isEmpty: -> true
  concat: (other)-> other
  split: (predicate)-> [this, this]
  toJSON: ->
    type: 'empty'
    measure: @measure()

# A finger-tree which contains exactly one element.
class Single extends FingerTree
  # @param {Object.<string, function>} measurer
  # @param {*} value
  constructor: (@measurer, @value)->
    super()
    @measure_ = @measurer.measure(@value)

  measure: -> @measure_

  addFirst: (v)->
    new Deep @measurer,
      new Digit(@measurer, [v]),
      new Empty(makeNodeMeasurer @measurer),
      new Digit(@measurer, [@value])

  addLast: (v)->
    new Deep @measurer,
      new Digit(@measurer, [@value]),
      new Empty(makeNodeMeasurer @measurer),
      new Digit(@measurer, [v])

  removeFirst:-> new Empty @measurer

  removeLast: -> new Empty @measurer

  peekFirst: -> @value

  peekLast: -> @value

  isEmpty: -> false

  concat: (other)-> other.addFirst @value

  # Helper function to split the tree into 3 parts.
  # @private
  # @param {function(*): boolean} predicate
  # @param {*} initial The initial measurement for reducing
  # @return {Split}
  splitTree: (predicate, initial)->
    new Split new Empty(@measurer),
      @value,
      new Empty(@measurer)

  split: (predicate)->
    if predicate @measure() then [new Empty(@measurer), this]
    else [this, new Empty @measurer]

  toJSON: ->
    type: 'single'
    value: @value
    measure: @measure()

# A finger-tree which contains two or more elements.
class Deep extends FingerTree
  # @param {Object.<string, function>} measurer
  # @param {Digit} left
  # @param {FingerTree} mid
  # @param {Digit} right
  constructor: (@measurer, @left, @mid, @right)->
    # @private
    super()
    @measure_ = null

  measure: ->
    if @measure_ == null
      @measure_ = @measurer.sum(
        @measurer.sum(@left.measure(), @mid.measure()),
        @right.measure())
    @measure_

  addFirst: (v)->
    leftItems = @left.items
    if @left.length == 4 then new Deep @measurer,
      new Digit(@measurer, [v, leftItems[0]]),
      @mid.addFirst(new Node(@measurer,
        [leftItems[1],
         leftItems[2],
         leftItems[3]])),
      @right
    else new Deep @measurer,
      new Digit(@measurer, [v].concat(leftItems)),
      @mid,
      @right

  addLast: (v)->
    rightItems = @right.items
    if @right.length == 4 then new Deep @measurer,
      @left,
      @mid.addLast(new Node(@measurer,
        [rightItems[0],
         rightItems[1],
         rightItems[2]])),
      new Digit(@measurer, [rightItems[3], v])
    else new Deep @measurer,
      @left,
      @mid,
      new Digit(@measurer, rightItems.concat([v]))

  removeFirst: ->
    if @left.length > 1
      new Deep @measurer, @left.removeFirst(), @mid, @right
    else if !@mid.isEmpty()
      newMid = new DelayedFingerTree => @mid.removeFirst()
      new Deep @measurer, @mid.peekFirst().toDigit(), newMid, @right
    else if @right.length == 1 then new Single @measurer, @right.items[0]
    else new Deep @measurer, @right.slice(0, 1), @mid, @right.slice(1)

  removeLast: ->
    if @right.length > 1
      new Deep @measurer, @left, @mid, @right.removeLast()
    else if !@mid.isEmpty()
      newMid = new DelayedFingerTree => @mid.removeLast()
      new Deep @measurer, @left, newMid, @mid.peekLast().toDigit()
    else if @left.length == 1 then new Single @measurer, @left.items[0]
    else new Deep @measurer, @left.slice(0, -1), @mid, @left.slice(-1)

  peekFirst: -> @left.peekFirst()

  peekLast: -> @right.peekLast()

  isEmpty: -> false

  concat: (other)->
    other = other.force()
    if other instanceof Empty then this
    else if other instanceof Single then @addLast(other.value)
    else app3 this, [], other

  # Helper function to split the tree into 3 parts.
  # @private
  # @param {function(*): boolean} predicate
  # @param {*} initial The initial measurement for reducing
  # @return {Split}
  splitTree: (predicate, initial)->
    # see if the split point is inside the left tree
    leftMeasure = @measurer.sum initial, @left.measure()
    if predicate leftMeasure
      split = @left.split predicate, initial
      new Split fromArray(split.left, @measurer),
        split.mid,
        deepLeft(@measurer, split.right, @mid, @right)
    else
      # see if the split point is inside the mid tree
      midMeasure = @measurer.sum leftMeasure, @mid.measure()
      if predicate midMeasure
        midSplit = @mid.splitTree predicate, leftMeasure
        split = midSplit.mid.toDigit().split predicate, @measurer.sum(leftMeasure, midSplit.left.measure())
        new Split deepRight(@measurer, @left, midSplit.left, split.left),
          split.mid,
          deepLeft(@measurer, split.right, midSplit.right, @right)
      else
        # the split point is in the right tree
        split = @right.split predicate, midMeasure
        new Split deepRight(@measurer, @left, @mid, split.left),
          split.mid,
          fromArray(split.right, @measurer)

  split: (predicate)->
    if predicate @measure()
      split = @splitTree predicate, @measurer.identity()
      [split.left, split.right.addFirst split.mid]
    else [this, new Empty @measurer]

  toJSON: ->
    type: 'deep',
    left: @left
    mid: @mid
    right: @right
    measure: @measure()

# A lazy-evaluted finger-tree.
class DelayedFingerTree
  # @param {function(): FingerTree} thunk A function, which when called, will
  constructor: (@thunk)-> @tree = null
  # Evaluate the thunk and return the finger-tree.
  # @return {FingerTree}
  force: ->
    if @tree == null then @tree = this.thunk()
    @tree
  isEmpty: (v)-> @force().isEmpty()
  measure: -> @force().measure()
  peekFirst: -> @force().peekFirst()
  peekLast: -> @force().peekLast()
  addFirst: (v)-> @force().addFirst(v)
  addLast: (v)-> @force().addLast(v)
  removeFirst: -> @force().removeFirst()
  removeLast: -> @force().removeLast()
  concat: (other)-> @force().concat other
  splitTree: (predicate, initial)-> @force().splitTree(predicate, initial)
  split: (predicate)-> @force().split(predicate)
  takeUntil: (predicate)-> @force().takeUntil other
  dropUntil: (predicate)-> @force().dropUntil other
  toJSON: -> @force().toJSON()
  toArray: -> @force().toArray()

# @param {Array} left
# @param {FingerTree} mid
# @param {Digit} right
deepLeft = (measurer, left, mid, right)->
  if !left.length
    if mid.isEmpty() then fromArray right.items, measurer
    else new DelayedFingerTree -> new Deep measurer,
       mid.peekFirst().toDigit(),
       mid.removeFirst(),
       right
  else new Deep measurer, new Digit(measurer, left), mid, right

# @param {Digit} left
# @param {FingerTree} mid
# @param {Array} right
deepRight = (measurer, left, mid, right)->
  if !right.length
    if mid.isEmpty() then fromArray left.items, measurer
    else new DelayedFingerTree -> new Deep measurer,
       left,
       mid.removeLast(),
       mid.peekLast().toDigit()
  else new Deep measurer, left, mid, new Digit measurer, right

# Helper function to concatenate two finger-trees with additional elements
# in between.
# @param {FingerTree} t1 Left finger-tree
# @param {Array} ts An array of elements in between the two finger-trees
# @param {FingerTree} t2 Right finger-tree
# @return {FingerTree}
app3 = (t1, ts, t2)->
  t1 = t1.force()
  t2 = t2.force()
  if t1 instanceof Empty then prepend t2, ts
  else if t2 instanceof Empty then append t1, ts
  else if t1 instanceof Single then prepend(t2, ts).addFirst t1.value
  else if t2 instanceof Single then append(t1, ts).addLast t2.value
  else new Deep t1.measurer,
    t1.left,
    new DelayedFingerTree(-> app3 t1.mid,
      nodes(t1.measurer,
        t1.right.items
          .concat(ts)
          .concat(t2.left.items)),
      t2.mid),
    t2.right

# Helper function to group an array of elements into an array of nodes.
# @param {Object.<string, function>} m Measurer
# @param {Array} xs
# @return {Array}
nodes = (m, xs, res)->
  res = res ? []
  switch xs.length
    when 2 then res.push new Node(m, xs)
    when 3 then res.push new Node(m, xs)
    when 4 then res.push new Node(m, [xs[0], xs[1]]), new Node(m, [xs[2], xs[3]])
    else
      res.push new Node m, [xs[0], xs[1], xs[2]]
      nodes m, xs.slice(3), res
  res

# Construct a derived measurer which will return the memoized
# measurement of a node instead of evaluting the node.
# @param {Object.<string, function>} measurer
# @return {Object.<string, function>}
makeNodeMeasurer = (measurer)->
  identity: measurer.identity
  measure: (n)-> n.measure()
  sum: measurer.sum

# Prepend an array of elements to the left of a tree.
# Returns a new tree with the original one unmodified.
# @param {FingerTree} tree
# @param {Array} xs
# @return {FingerTree}
prepend = (tree, xs)->
  for i in [xs.length - 1 .. 0] by -1
    tree = tree.addFirst(xs[i])
  tree

# Append an array of elements to the right of a tree.
# Returns a new tree with the original one unmodified.
# @param {FingerTree} tree
# @param {Array} xs
# @return {FingerTree}
append = (tree, xs)->
  for x in xs
    tree = tree.addLast x
  tree

# Construct a fingertree from an array.
# @param {Array} xs An array of elements.
# @param {Object.<string, function>} measurer
# @return {FingerTree}
fromArray = (xs, measurer)->
  measurer = measurer ||
    identity: -> 0
    measure: (v)-> 1
    sum: (a, b)-> a + b
  prepend new Empty(measurer), xs

FingerTree.fromArray = fromArray