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"

Binary Insert

Insert a Value Directly into a Sorted Table

See Also