105 lines
3.1 KiB
Lua
105 lines
3.1 KiB
Lua
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 |