language-lua2 0.1.0.4 → 0.1.0.5
raw patch · 3 files changed
+1116/−1 lines, 3 files
Files
- language-lua2.cabal +3/−1
- test/samples/1.lua +947/−0
- test/samples/2.lua +166/−0
language-lua2.cabal view
@@ -1,5 +1,5 @@ name: language-lua2-version: 0.1.0.4+version: 0.1.0.5 synopsis: Lua parser and pretty printer description: Lua parser and pretty printer homepage: http://github.com/mitchellwrosen/language-lua2@@ -10,6 +10,8 @@ category: Language build-type: Simple cabal-version: >=1.10+extra-source-files: test/samples/1.lua+ , test/samples/2.lua Flag exes Description: "Build debug executables"
+ test/samples/1.lua view
@@ -0,0 +1,947 @@+--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™++--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™++--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™++--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™++--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™++--[[+ Interpolating Search on a String++ LUA 5.1 compatible++ Can only search sorted tables with value string++ table.intsearchstr( table, value ), for searching a normal sorted table+ table.intsearchstrrev( table, value ), for searching a reversed sorted table++ If the value is found:+ it returns a table holding all the matching indices (e.g. { startindice,endindice } )+ endindice may be the same as startindice if only one matching indice was found+ Return value:+ on success: a table holding matching indices (e.g. { startindice,endindice } )+ on failure: nil+]]--+do+ -- Avoid heap allocs for performance+ local getbytevalue = function( value )+ if value then+ local num,mul = 0,1+ -- set bytedept, 4 or 5 seems appropriate+ for i = 4,1,-1 do+ local byte = string.byte( string.sub( value,i,i ) ) or -1+ byte,num,mul = byte + 1,num + mul*byte,mul*257+ end+ return num+ end+ end+ -- Load the optimised binary function+ -- Avoid heap allocs for performance+ local fcompf = function( a,b ) return a < b end+ local fcompr = function( a,b ) return a > b end+ local function tablebinsearch( t,value,reversed,iStart,iEnd )+ -- Initialise functions+ local fcomp = reversed and fcompr or fcompf+ -- Initialise numbers+ local iStart,iEnd,iMid = iStart or 1,iEnd or #t,0+ -- Binary Search+ while iStart <= iEnd do+ -- calculate middle+ iMid = math.floor( (iStart+iEnd)/2 )+ -- get compare value+ local value2 = t[iMid]+ -- get all values that match+ if value == value2 then+ local tfound,num = { iMid,iMid },iMid - 1+ while value == t[num] do+ tfound[1],num = num,num - 1+ end+ num = iMid + 1+ while value == t[num] do+ tfound[2],num = num,num + 1+ end+ return tfound+ -- keep searching+ elseif fcomp( value,value2 ) then+ iEnd = iMid - 1+ else+ iStart = iMid + 1+ end+ end+ end++ -- The interpolationg Search Function on a String+ function table.intsearchstr( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow < _ihigh do+ -- get interpolated position+ local pos = math.floor( (_value-_ilow)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value < t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,_,ilow,ihigh )+ end+ -- The interpolationg Search Function on a String+ function table.intsearchstrrev( t,value )+ -- Inistialise numbers+ local ilow,ihigh = 1,#t+ -- return on empty table+ if not t[ilow] then return end+ -- get byte values values of indices and searched value+ local _ilow,_ihigh,_value = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),getbytevalue(value)+ local oldpos = -1+ -- make sure slope cannot become 0+ while _ilow and _ilow > _ihigh do+ -- get interpolated position+ local pos = math.floor( (_ihigh-_value)*(ihigh-ilow)/(_ihigh-_ilow) ) + ilow+ -- check for out of range+ if pos < ilow or pos > ihigh then return end+ -- check for real match+ if value == t[pos] then+ -- insert found position+ local tfound,num = { pos,pos },pos-1+ -- get all values that match+ while value == t[num] do+ tfound[1],num = num,num-1+ end+ num = pos+1+ while value == t[num] do+ tfound[2],num = num,num+1+ end+ return tfound+ -- keep searching,+ -- left part of the table,check for real lower+ elseif value > t[pos] then+ ihigh = pos-1+ else+ ilow = pos+1+ end+ -- check if new position is further than 1 away+ if oldpos+1 == pos or oldpos-1 == pos then+ -- start binary search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+ _ilow,_ihigh,oldpos = getbytevalue(t[ilow]),getbytevalue(t[ihigh]),pos+ end+ -- initiate binary seach function here since we could be in a flat for the interpolating search+ return tablebinsearch( t,value,1,ilow,ihigh )+ end+end+-- CHILLCODE™
+ test/samples/2.lua view
@@ -0,0 +1,166 @@+-- The constructor makes a tuple definition, which has its own intern table+-- tuples may have an optional binding to alias a key to a given tuple index++--[[+Tuples are immutable lists that can be used as table keys because they have+value semantics, that is, the tuple constructor returns the same identity for+the exact same list of identities++tuples are composed of only immutable values++TODO allow tuples to contain other tuples?+]]++local tuple = {}++local NAN = setmetatable({}, {__tostring = function() return "NAN" end})+local NIL = setmetatable({}, {__tostring = function() return "NIL" end})++local allowed_primitive_types = {+ number = true,+ string = true,+ ["nil"] = true,+}+++local function value_to_key(value)+ if value == nil then+ return NIL+ end++ -- We rely on the property that NaN is the only value that doesn't equal itself+ if value ~= value then+ return NAN+ end++ return value+end++-- use a weak table?+local function create_index()+ return {}+end++local function insert_tuple(tuple_def, index, raw_tuple)+ local tuple = setmetatable({}, tuple_def.tuple_mt)+ tuple_def.tuples[index] = tuple+ tuple_def.raw_tuples[tuple] = raw_tuple+ return tuple+end++local function get_tuple(values, index)+ return values[index]+end++local function find_tuple_n(values, cur_index, count, value, ...)+ if count == 0 then+ return get_tuple(values, cur_index)+ end++ local key = value_to_key(value)+ cur_index = cur_index[key]+ if not cur_index then+ return nil+ end++ return find_tuple_n(values, cur_index, count - 1, ...)+end++local function find_tuple(tuple_def, ...)+ local cur_index = tuple_def.index+ local values = tuple_def.tuples+ local count = select('#', ...)+ assert(count <= tuple_def.size)+ return find_tuple_n(values, cur_index, count, ...)+end++++local function new_tuple_n(tuple_def, cur_index, raw_tuple, count, value, ...)+ if count == 0 then+ return insert_tuple(tuple_def, cur_index, raw_tuple)+ end++ local key = value_to_key(value)+ local next_index = cur_index[key]+ if not next_index then+ next_index = create_index()+ cur_index[key] = next_index+ end++ local ndx = #raw_tuple + 1++ local value_type = type(value)+ assertf(allowed_primitive_types[value_type] or tuple.is_a(value),+ "invalid tuple value %s (at position %d)", tostring(value), ndx)+ raw_tuple[ndx] = value++ return new_tuple_n(tuple_def, next_index, raw_tuple, count - 1, ...)+end++local function new_tuple(tuple_def, ...)+ local cur_index = tuple_def.index+ assert(select('#', ...) == tuple_def.size)+ local raw_tuple = {}+ return new_tuple_n(tuple_def, cur_index, raw_tuple, tuple_def.size, ...)+end++local function tuple_to_string(tuple_def, tuple)+ local tuple_strs = {}+ for i=1,#tuple_def.raw_tuples[tuple] do+ tuple_strs[i] = tostring(tuple_def.raw_tuples[tuple][i])+ end+ -- TODO memoize this value in the tuple?+ local tuple_content = table.concat(tuple_strs, ",")+ return ("%s<%s>"):format(tuple_def.data_type, tuple_content)+end++function tuple.is_a(inst)+ local mt = getmetatable(inst)+ return mt and mt.__tuple+end++--- define a tuple+-- @tparam number size number of elements in the tuple+-- @tparam table binding list of keys to use as an alias for the tuple index+function tuple.define(data_type, size, binding)+ local wrapper = {}+ binding = binding or {}+ assert(#binding == 0 or #binding == size)+ for tuple_ndx, alias_key in ipairs(binding) do+ assert(type(alias_key) == "string")+ wrapper[alias_key] = tuple_ndx+ end++ local tuple_def = {+ data_type = data_type,+ size = size,+ raw_tuples = {}, -- tuple lookup to raw tuple+ tuples = {}, -- element N (last X) lookup to tuple+ index = {}, -- element X lookup to element X + 1+ lookup_alias = wrapper,+ }++ -- use the same metatable for all tuples+ tuple_def.tuple_mt = {+ __index = function(t, k)+ local raw = tuple_def.raw_tuples[t]+ return raw[k] or raw[tuple_def.lookup_alias[k]]+ end,+ __data_type = tuple_def.data_type,+ __tuple = true,+ __newindex = false,+ __tostring = function(t)+ return tuple_to_string(tuple_def, t)+ end+ }++ return tuple_def+end++--- create an instance of `tuple_def` populated from the vararg+function tuple.new(tuple_def, ...)+ return find_tuple(tuple_def, ...) or new_tuple(tuple_def, ...)+end++return tuple