 # TK move. Until the root branch page is split, it is both the root branch page
 # and a penultimate branch page.
 #
-# ##### Penultimate Pages
+# #### Penultimate Branch Pages
 #
 # A penultimate branch page is a branch page whose children are leaf pages. If a
 # branch page is not penultimate, then its children are branch pages.

# Default extractor returns the value as hole, i.e. tree of integers.
extractor = (a) -> a

# Glossary:
# 
#  * Descent - What we call an attempt to move from a parent node to a child
#              node in  the tree, which may be paused because it encounters a
#              lock on a tier.
#  * Record - A JSON object stored in the b-tree.
#  * Object - JavaScript objects are referred to as objects in this
#             documentation and are not to be confused with actual records.

#              
class Mutation
  # The constructor always felt like a dangerous place to be doing anything
  # meaningful in C++ or Java.
  constructor: (@strata, @object, @key, @operation) ->
    @io         = @strata._io
    @options    = @strata._options

    @parent     = { operations: [], locks: [] }
    @child      = { operations: [], locks: [] }
    @exclusive  = []
    @shared     = []
    @pivots     = []

    { @extractor, @comparator } = @options

    @key        = @extractor @object if @object? and not key?
  
  # Descend the tree, optionally starting an exclusive descent. Once the descent
  # is exclusive, all subsequent descents are exclusive.

  # `mutation.descend(exclusive)` 
  descend: (exclusive) ->
    # Add a new level to the plan.
    @plan.unshift { operations: [], addresses: [] }

    # Two or more exclusive levels mean that the parent is exclusive.
    if @exclusive.length < 1
      @strata._release @parent

    # Any items in the exclusive level array means we are now locking exclusive.
    exclusive or= @exclusive.length > 0

    # Make child a parent.
    @parent = @child
    @child = { operations: [], locks: [], exclusive }

    # Add the new child to the list of exclusive levels.
    if exclusive
      @exclusive.push(@child)

  # Search for a value in a tier, returning the  index of the value or else
  # where it should be inserted.
  #
  # There is some magic here, long forgotten at the time of documentation. The
  # tree beneath each branch in an inner tier contains records whose value is
  # equal to or greater than the pivot. Thus, the pivot of the first record on
  # an inner tier is null, indicating that that is the branch for all values
  # less than the value of the first branch with a real pivot.
  #
  # TODO: Reading through the code, this does not take this into account, and
  # will problably send items that belong in the least value tree into the three
  # that follows it. I'll clean this up with unit testing.

  # `mutation.find(tier, key, callback)`
  find: (tier, key, _) ->
    size = tier.addresses.length
    if tier.leaf
      [ low, high, leaf ] = [ 0, size - 1, true ]
    else if size is 1
      return 0
    else
      [ low, high ] = [ 1, size - 1 ]
    { comparator, io } = @
    loop
      mid = (low + high) >>> 1
      compare = comparator key, io.key(tier, mid, _)
      if compare is 0
        break
      if compare > 0
        low = mid + 1
      else
        high = mid - 1
    if compare is 0
      if leaf
        while mid != 0 && comparator(key, io.key(tier, mid - 1, _)) == 0
          mid--
      mid
    else if branches
      mid - 1
    else
      mid

  hasKey: (tier, _) ->
    for key in @operation.keys or []
      die { key }
      branch = @find(tier, key, _)
      if tier.cache[branch] is key
        return true
    false

  # TODO: We are always allowed to get a shared lock on any leaf page and read a
  # value, as long as we let go of it immediately. This allows us to read from
  # leaf pages to get branch values.
  # TODO: Rename this descend.

  # `mutation.mutate(callback)`
  mutate: (_) ->
    parent = null

    @shared.push child = @io.lock false, 0, false, _
    if @operation.keys and (child.addresses.length is 1 or @hasKey(child, _))
      @exclusive.push @io.upgrade @shared.pop(), _

    # TODO: Flag for go left.
    while not child.penultimate or child.address is @soughtAddress
      process.exit 1

    # TODO: Flag for shared or exclusive. If exclusive, leave parent locked, if
    # shared, then unlock parent.

    mutation = @[@operation.method].call this, parent, child, _

    @io.release tier for tier in @shared
    @io.release tier for tier in @exclusive

    mutation.mutate _ if mutation

  insertSorted: (parent, child, _) ->
    branch = @find child, @key, _
    @exclusive.push leaves = @io.lock true, child.addresses[branch], true, _

    addresses = leaves.addresses

    # Insert the object value sorted.
    for i in [0...addresses.length]
      key = @io.key(leaves, i, _)
      if @comparator(@key, key) <= 0
        break

    address = leaves.io.writeInsert @object, i, _
    addresses.splice i, 0, address

    if addresses.length > @options.leafSize and not @homogenous(leaves, _)
      keys = []
      process.nextTick _
      # Opportunity to deadlock.
      keys.push key = @io.key leaves, 0, _
      if leaves.right
        keys.push @io.key leaves.right, 0, _
      operation =
        method: "splitLeaf"
        keys: keys
      new Mutation(@strata, null, key, operation)
  
  # If the leaf tier is now at the maximum size, we test to see if the leaf tier
  # is filled with an identical key value, and if not, we split the leaf tier.
  homogenous: (tier, _) ->
    { io, comparator } = @
    first = io.key(tier, 0, _)
    last = io.key(tier, tier.addresses.length - 1, _)
    comparator(first, last) is 0

  get: (parent, child, _) ->
    branch = @find child, @key, _
    @shared.push leaves = @io.lock false, child.addresses[branch], true, _
    address = @find leaves, @key, _
    leaves.cache[leaves.addresses[address]]

  splitLeaf: (parent, child, _) ->
    branch = @find child, @key, _
    @exclusive.push leaves = @io.lock true, child.addresses[branch], true, _

    # See that nothing has changed since we last descended.
    { comparator: c, io, options: { leafSize: length } } = @
    return if c(io.key(leaves, 0, _), @key) isnt 0
    return if @homogenous(leaves, _)
    return if leaves.addresses.length < @options.leafSize

    # We might have let things go for so long, that we're going to have to split
    # the page into more than two pages.
    partitions = Math.floor leaves.addresses.length / @options.leafSize
    while (partitions * @options.leafSize) <= leaves.addresses.length
      # Find a partition.
      mid = Math.floor leaves.addresses.length / (partitions + 1)
      key = io.key leaves, mid, _
      [ before, after ] = [ mid - 1, mid + 1 ]
      while not partition
        if before > 0 and c(io.key(leaves, before, _), key) isnt 0
          partition = before + 1
        else if after <= length and c(io.key(leaves, after, _)) isnt 0
          partition = after
        else
          --before
          ++after

      key = io.key leaves, partition, _
      pivot = @find(child, key, _) + 1

      addresses = leaves.addresses.splice(partition)
      right = io.allocateLeaves(addresses, leaves.right)

      leaves.right = right.address

      child.addresses.splice(pivot, 0, right.address)

      # Append an operation indciator. This would be a record that describes all
      # the participants in the rewrite, in the order in which they are supposed
      # to be rewritten. When found, we look at the last item in the list, then
      # load that, and ensure that the last record is a complete operation
      # record. If it is, we know that all of the temporary pages were written.
      @io.rewriteLeaves(leaves, _)
      @io.rewriteLeaves(right, _)

      @io.rewriteBranches(child, _)

      @io.relink(right, _)
      @io.relink(leaves, _)
      @io.relink(child, _)

      --paritions

  mergeLeaf: (parent, child, _) ->
    [ key, rightKey ] = @operation.keys
    compare = @comparator(full, leftKey = @io.key(child, 0, _))
    if compare is 0
      return if leftKey isnt key

class Level
  # Construct a new level. The `exclusive` pararameter determines how this level
  # locks tiers when asked to lock tiers.
  constructor: (@exclusive) ->
    @operations = []
    @locks = []

  # Convert lock to read lock and tell anyone waiting that they can go ahead.
  #
  # We give the next tick a copy of just the continuations to fire, excluding
  # our own continuation which we're about to add. (TODO rename continuations?) 
  #
  # If you're wondering, no, you're not going to fire the continuations twice.
  # They are only ever fired by the decent that holds the exclusive lock. This
  # level will be removed from the level list, so we won't grab at it when the
  # operations are over.
  downgrade: (strata) ->
    if @exclusive
      while @locks.length
        lock = @locks.shift()
        locks = strata.locks[lock.address]
        throw "not locked by me" if locks[0][0] isnt lock
        locks.shift()
        @_resume strata, locks[0].slice(0)
        locks[0].push lock
      @exclusive = false
  
  # Unused.
  advance: (strata) ->
    locks = strata.locks[@tier.id]
    if locks[0].length is 0 and locks.length isnt 1
      locks.shift()
      true
    false

# ### B-Tree Structure
#
# We call page of the b-tree, ah, maybe we stop using the word tier, start using
# the word page, because we're not going to have to reduce the ambiguity with
# some sort of subdivided binary file structure.
#
# NOTE Come back and look at this. It is succinct.
#
# There are two types of pages. Branch pages and leaf pages.
#
# Leaf pages store the records. They maintain the collation
#
# Leaf pages are all uniformly the same.
#
# ### Leaf Tier Files
#
# A leaf tier maintains an array of file positions called an address array. A
# file position in the address array references a record in the leaf tier file
# by its file position. The addresses in the address array are sorted by the
# the sort order of the referenced records according to the sort order of the
# b-tree.
#
# A leaf tier file contains JSON objects, one object on each line.
#
# There are three types of objects in a leaf tier file, insert objects, delete
# objects, and address array objects.
#
# An insert object contains a *record* and the index in the address array where
# the record's address would be inserted to preserve the sort order of the
# address array.
#
# Beginning with an empty array and reading from the start of the file, the leaf
# tier address array is reconstituted by reading the object at the current
# position in the file, then inserting the position of the current object into
# the address array at the index in the insert object.
#
# We record a deletion by appending a delete object. A delete object contains
# an index in the address array that should be deleted. When reading the leaf
# tier from the start of the file, we insert an address into the address array
# when we encounter an insert object, and we delete an address when we encounter
# a delete object.
#
# On occasion, we can store an address array object, An address array object
# contains the address array itself.  We store a copy of a constructed address
# array object in the leaf tier file so that we can read a large leaf tier file
# quickly.
#
# When we read a leaf tier file, if we read from the back of the file toward the
# front, we can read backward until we find an address array object. Then we can
# read forward to the end of the file, applying the inserts and deletes that
# occured after we wrote the address array object. 
# 
# When a leaf tier file is large, stashing the constructed address array at the
# end means that the leaf tier can be loaded quickly, because we will only have
# to read backwards a few entries to find a mostly completed address array. We
# can then read forward from the array to amend the address array with the
# inserts and deletes that occured after it was written.
#
# Not all of the records will be loaded when we go backwards, but we have their
# file position from the address array, so we can jump to them and load them as
# we need them. That is, if we need them, because owing to binary search, we
# might only need a few records out of a great many records to find the record
# we're looking for.
#
# Over time, a leaf tier file can grow fat with deleted records &mdash; an
# insert object and a subsequent delete object. We vacuum a leaf tier file by
# writing it to a new leaf tier file.

# `LeafIO` &mdash; Keeps track of a file descriptor opened for append, and the
# append file position. The `LeafIO` class does *not* contain all methods
# relating to leaf tier file I/O. You can find more leaf tier file methods in
# the `IO` class below.
#
# TODO Rename `RecordIO`.
class LeafIO
  # Construct a leaf file tier writer for the given file name.
  constructor: (@filename) ->
    @length = 1024

  # #### Leaf Tier File Object Format
  #
  # Each leaf tier object is a JSON array. The first element of the array is an
  # integer.
  #
  # If the integer is greater than zero, it indicates an insert object.  The
  # integer is the one based index into the zero based address array, indicating
  # the index where the position of the current insert object should be
  # inserted. The second element of the leaf tier object array is the record
  # object.

  # Write an insert object.
  writeInsert: (object, index, _) ->
    @_writeJSON [ index + 1, object ], _

  # If the integer is less than zero, it indicates a delete object. The absolute
  # value of the integer is the one based index into the zero based addrss
  # array, indicating the index of address array element that should be deleted.
  # There are no other elements in the leaf tier object array.

  # Write a delete object.
  writeDelete: (index, _) ->
    @_writeJSON [ -(index + 1) ], _
  
  # If the integer is zero, it indicates an address array object. The integer
  # value of zero is used only as an indicator. The second element is the
  # address of the leaf tier to the right of current leaf tier. The third
  # element of the leaf tier object array is the address array.

  # Write an address array object.
  writeAddresses: (right, addresses, _) ->
    @_writeJSON [ 0, right, addresses ], _

  # Append an object to the leaf tier file as a single line of JSON.
  _writeJSON: (object, _) ->
    @fd           or= fs.open @filename, "a+", 0644, _
    @position     or= fs.stat(@filename, _).size

    json            = JSON.stringify object
    position        = @position
    length          = Buffer.byteLength(json, "utf8")
    buffer          = new Buffer(length + 1)
    offset          = 0

    # Write JSON and newline.
    buffer.write json
    buffer[length] = 0x0A

    # Write may be interrupted by a signal, so we keep track of how many bytes
    # are actually written and write the difference if we come up short.
    while offset != buffer.length
      count = buffer.length - offset
      written = fs.write @fd, buffer, offset, count, @position, _
      @position += written
      offset += written

    # What's the point if it doesn't make it to disk?
    fs.fsync @fd, _

    # Return the file position of the inserted record.
    position

  # Each line is terminated by a newline. In case your concerned that this
  # simple search will mistake a byte inside a multi-byte character for a
  # newline, have a look at
  # [UTF-8](http://en.wikipedia.org/wiki/UTF-8#Description). All bytes
  # participating in a multi-byte character have their leading bit set, all
  # single-byte characters have their leading bit unset.

  # Search for the newline that separates JSON records.
  _readJSON: (buffer, read) ->
    for offset in [0...read]
      if buffer[offset] is 0x0A
        return JSON.parse buffer.toString("utf8", 0, offset + 1)

  # Jump to a position in the file and read a specific object. Because objects
  # are cached in memory by a leaf tier, we're not going to get a request to
  # read an object that has been written to the current write stream. When we
  # read in a leaf tier, we'll cache any objects we encounter prior to read the
  # ordering array.
  #
  # Note how we allow we keep track of the minimum buffer size that will
  # accommodate the largest possible buffer.
  readObject: (address, _) ->
    @fd or= fs.open @filename, "a+", _
    @position or= fs.stat(@filename, _).size
    loop
      buffer = new Buffer(@length)
      read = fs.read @in, buffer, 0, buffer.length, address, _
      if json = @_readJSON(buffer, read)
        break
      if @length > @position - address
        throw new Error "cannot find end of record."
      @length += @length >>> 1
    json.pop()

  # Close the file descriptor if it is open and reset the file descriptor and
  # append position.
  close: (_) ->
    fs.close(@fd, _) if @fd
    @position = @fd = null

# ### Tier File Storage
#
# Tiers are identified by a number tier address. The tier address is a number
# that is incremented as new tier are created. A branch tier file has a file
# name that includes the tier address. The file name is derived from the tier
# address. When we load a tier, we first derive the file name from the tier
# address, then we load the file.
#
# The leaf tier file contains insert objects, delete objects and address array
# objects, stored as JSON, one object per line, as described above.
#
# The branch tier file contains a single object that includes the array of
# tier addresses. The tier addresses reference leaf tier files. The tier
# addresses are sorted according to the value of the objects in leaf tiers they
# reference. The addresses are sorted by the tree collation using the record
# from the referenced leaf tier that has the least value according to the tree
# collation.
#
# Put another way, each branch element in a branch tier represents a leaf tier.
# The leaf tiers are sorted by the tree collation. The object value used to sort
# the branch tier is first element in the sorted leaf tier.
#
# TODO Okay, what? I'm forgetting that I need the addresses to inner tiers as
# well as to leaf tiers, both, when the tier is not penultimate. Descending is
# not going to work, that is going to load the entire tree into memory quickly.
#
# Hmm... Maybe not. Tree four deep means loading only a particular path. It
# ensures that we read lock our way down the tree to get our record. Although, I
# believe I thought long and hard about this, and jumping down to the leaves
# wasn't a problem.
#
# We only need to store the sorted array of the leaf tier addresses in our
# branch tier, since we can obtain the object used to collate the address

#
class IO
  # Set directory and extractor. Initialze cache and MRU list.
  constructor: (@directory, @extractor) ->
    @cache          = {}
    @head           = { address: -1 }

# [B-trees](http://en.wikipedia.org/wiki/B-tree) and
# [B+trees](http://en.wikipedia.org/wiki/B%2B_tree). 
#
# ## What flavor of b-tree is this?
#
# Strata is a b-tree with leaf pages that contain records ordered by the
# collation order of the tree, indexed for retrieval in constant time, so that
