local sequence = require 'sequence'

local maxLevels = 20 --Maximum depth of tree.
local baseIdx = 1 --Base index of implicit tree. Is it a 0-based or 1-based array?
local tree = {}

local function insert( aTree, aSeq, aVals, bTree, bSeq, bVals )

  --print( "INSERTING" )
  local treeIdx = 1 --Pointer into implicit binary tree.
  local aIdx, bIdx = aSeq.cmin, bSeq.cmin --First elements of a and b outside the support of the sequence
  local aVal, bVal = aVals[aIdx], bVals[bIdx]
  local aTest, bTest

  --Search for appropriate bIdx.
  --Sentinel value.
  local newCandidate = false
  while aTree[treeIdx] do
    if newCandidate then
      newCandidate = false
      treeIdx = 1
      repeat bIdx = bIdx + 1 until ( not bSeq[bIdx] )
      bVal = bVals[bIdx]
    end

    --invariants guarantee these aren't empty:
    --loop invariant, that aTree[treeIdx] is nonempty
    --struct invariant, that bTree and aTree have identical support
    aTest, bTest = aTree[treeIdx], bTree[treeIdx] 
    --Go left if bounded above, go right if bounded below,
    --if there is a discrepancy then start over with the next bIdx
    --print( "VALUES:", "A[[", aVal, aTest, "B[[", bVal, bTest )
    if ( aVal < aTest ) then
      if ( bVal < bTest ) then 
        --print( "A LEFT B LEFT", aVal, aTest, bVal, bTest ) --debug
        treeIdx = 2 * treeIdx
      else
        --print( "A LEFT B RIGHT", aVal, aTest, bVal, bTest ) --debug
        newCandidate = true
      end
    elseif ( bVal > bTest ) then 
      --print( "A RIGHT B RIGHT", aVal, aTest, bVal, bTest ) --debug
      treeIdx = 2 * treeIdx + 1 
    else 
      --print( "A RIGHT B LEFT", aVal, aTest, bVal, bTest ) --debug
      newCandidate = true
    end
  end
  
  --print( "Inserting element in tree:", aIdx, aVal, bIdx, bVal )

  --Insert elements into tree.
  aTree[treeIdx], bTree[treeIdx] = aVal, bVal

  --Insert indices into sequence.
  aSeq:insert( aIdx, bIdx )
  bSeq:insert( bIdx, aIdx )

end

--In-order traversal of the tree. 
--Returns points of twin-tree, sorted and interlaced, for graphing.
-- { a_min, b_min, a_next, b_next, ...}
do
  local a, b, n, result
  local function flat( idx )
    if a[ 2 * idx ] then flat( 2 * idx ) end
    result[ n ], result[ n + 1 ], n = a[idx], b[idx], n + 2
    if a[ 2 * idx + 1 ] then flat( 2 * idx + 1 ) end
  end

  function tree.flat( aTree, bTree, t )
    result = t or {}
    a, b = aTree, bTree
    n = 1
    flat( 1 )
    for i = n + 1, #result do result[i] = nil end
    return result
  end
end

function tree.build( n, av, bv )
  local at, bt = {}, {}
  local as, bs = sequence.new 'a', sequence.new 'b'
  for i = 1, n do
    insert( at, as, av, bt, bs, bv ) --Forward map.
    insert( bt, bs, bv, at, as, av ) --Backward map.
  end
  return at, bt
end

do
  local yield = assert( coroutine.yield )
  function tree.buildIncremental( av, bv )
    local at, bt = {}, {}
    local as, bs = sequence.new 'a', sequence.new 'b'
    local flattened = {}
    repeat
      insert( at, as, av, bt, bs, bv ) --Forward map.
      insert( bt, bs, bv, at, as, av ) --Backward map.
    until yield( tree.flat( at, bt, flattened ) ) and false
  end
end

return tree