 class Cassette
   constructor: (@record, @key) ->
 
-# Are we able to jump in, lock exclusive, or do we really need to go hand over
-# hand. Here are some properties. There is only one thread of execution that is
-# going to mutate branch pages, the same that does merges.
-#
-# We make a plan, moving from left to right, to merge. or else to split. Merges
-# require
-#
-# We have a deleted page, and that page gets the deleted pages added to it. It
-# is rewritten just as any other leaf page is rewritten. We rewrite. If you want
-# to have that go very, very fast, then create small branch pages, and huge leaf
-# pages.
-#
-# Leaning toward making a requirement that keys are unique. Duplicate keys can
-# be a combination of system time and an offset, descent count. Maybe, maybe
-# not.
-#
-# Degenerate case for all this is that we have someone inserting and deleting
-# faster than we can balance, creating live lock. There are constant balance
-# operations, not completing, and a back log of unbalanced pages. This may be an
-# imagined problem.
-#
-# We track sizes using json length. A calcualated length, based on the JSON
-# respesentation. When we reach a particular size, we purge the cache. We also
-# have items that have no length, pages that we've cached for sizes for the sake
-# of merge. We don't purge those pages if they are being used to calculate
-# balance. We keep a reference count. We also only purge at balance time, so
-# that we don't purge cached size data when it is needed.
-# 
-# When we delete an item, if it is the first record, we leave the item in place,
-# to act as a key. We need to fix this during balance. When we delete the first
-# item, we mark the item. How? Well, somehow, there is a flag that says that
-# this item has been deleted, but still exists. In fact, it is the second item
-# to the delete object, a boolean, true for retained false for destroyed. We put
-# in a second one to delete it for good.
-#
-# During balance, 
-#
-# Our binary search will skip it during search.
-#
-# When we balance, if 
-
-#              
 class Descent
   # The constructor always felt like a dangerous place to be doing anything
   # meaningful in C++ or Java.


    cursor

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

    positions = leaf.positions

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

    # Since we need to fsync anyway, we open the file and and close the file
    # when we append a JSON object to it.  Because no file handles are kept
    # open, the b-tree object can simply be reaped by the garbage collection.
    filename = @io.filename leaf.address
    fd = fs.open filename, "a", 0644, _
    position = @io.writeInsert fd, leaf, @object, i, _
    fs.close fd, _

    positions.splice i, 0, position

    if positions.length > @options.leafSize and not @homogenous(leaf, _)
      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 Descent(@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: (leaf, _) ->
    first = @_key leaf, 0, _
    last = @_key leaf, page.positions.length - 1, _
    @comparator(first, last) is 0

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

  splitLeaf: (parent, child, _) ->
    branch = @find child, @key, _
    @exclusive.push leaves = @io.lock child.addresses[branch], true, 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
class exports.Strata
  # Construct the Strata from the options.
  constructor: (options) ->

    @io         = @strata._io
    @options    = @strata._io.options

    { @extractor, @comparator } = @options

    @key        = @extractor @object if @object? and not @key?

  # 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.

  cursor: (exclusive, _) ->
    @shared.push page = @io.lock 0, false, false, _
