Binary Insert

wiki

Insert a Value Directly into a Sorted Table

This function inserts a value into a sorted table via a binary search algorithm. It is faster than doing a regular table.insert(table, value) followed by a table.sort(table [, comp]).

Files:wiki_insecure/users/chill/table.binsearch-0.3.lua

--[[
   table.bininsert( table, value [, comp] )
   
   Inserts a given value through BinaryInsert into the table sorted by [, comp].
   
   If 'comp' is given, then it must be a function that receives
   two table elements, and returns true when the first is less
   than the second, e.g. comp = function(a, b) return a > b end,
   will give a sorted table, with the biggest value on position 1.
   [, comp] behaves as in table.sort(table, value [, comp])
   returns the index where 'value' was inserted
]]--
do
   -- Avoid heap allocs for performance
   local fcomp_default = function( a,b ) return a < b end
   function table.bininsert(t, value, fcomp)
      -- Initialise compare function
      local fcomp = fcomp or fcomp_default
      --  Initialise numbers
      local iStart,iEnd,iMid,iState = 1,#t,1,0
      -- Get insert position
      while iStart <= iEnd do
         -- calculate middle
         iMid = math.floor( (iStart+iEnd)/2 )
         -- compare
         if fcomp( value,t[iMid] ) then
            iEnd,iState = iMid - 1,0
         else
            iStart,iState = iMid + 1,1
         end
      end
      table.insert( t,(iMid+iState),value )
      return (iMid+iState)
   end
end
-- CHILLCODE™

Test suite:

-- test: typical usage, with duplicates
t = {}
table.bininsert(t,  5)
assert(table.concat(t) == "5")
table.bininsert(t,  4)
assert(table.concat(t) == "45")
table.bininsert(t,  6)
assert(table.concat(t) == "456")
table.bininsert(t,  5)
assert(table.concat(t) == "4556")
table.bininsert(t,  6)
assert(table.concat(t) == "45566")
table.bininsert(t,  4)
assert(table.concat(t) == "445566")
table.bininsert(t,  0)
assert(table.concat(t) == "0445566")

-- test: fcomp
fcomp = function(a, b) return (a%3) < (b%3) end
t = {}
table.bininsert(t, 9, fcomp)
assert(table.concat(t) == "9")
table.bininsert(t, 3, fcomp)
assert(table.concat(t) == "93")
table.bininsert(t, 6, fcomp)
assert(table.concat(t) == "936")
table.bininsert(t, 2, fcomp)
assert(table.concat(t) == "9362")
table.bininsert(t, 7, fcomp)
assert(table.concat(t) == "93672")
table.bininsert(t, 1, fcomp)
assert(table.concat(t) == "936712")
table.bininsert(t, 5, fcomp)
assert(table.concat(t) == "9367125")
table.bininsert(t, 8, fcomp)
assert(table.concat(t) == "93671258")
table.bininsert(t, 4, fcomp)
assert(table.concat(t) == "936714258")
print "DONE"

See Also

• BinarySearch - searches for a value in a sorted table via a binary search algorithm