Generic/sortedlist.lua

   1 -- An array that keeps itself sorted.
   2 local create = QuestHelper.create
   3 local insert = table.insert
   4 local erase = table.remove
   5 local floor = math.floor
   6 local sort = table.sort
   7
   8 -- The metatable for SortedList objects.
   9 local SortedList = {}
  10
  11 function SortedList:onCreate(cmp)
  12   assert(type(cmp) == "function", "Expected function to perform less than comparisons.")
  13   rawset(self, "cmp", cmp)
  14 end
  15
  16 -- Resorts the list.
  17 function SortedList:sort()
  18   sort(self, rawget(self, "cmp"))
  19 end
  20
  21 -- Inserts a value into the table.
  22 -- Will try to insert as close to the back of the list as possible, to reduce the number of values
  23 -- that need to be shifted.
  24 -- Returns the index the value was inserted at.
  25 function SortedList:insert(value)
  26   local cmp = rawget(self, "cmp")
  27   local mn, mx = 1, #self+1
  28
  29   while mn ~= mx do
  30     local m = floor((mn+mx)*0.5)
  31
  32     if cmp(value, rawget(self, m)) then
  33       mx = m
  34     else
  35       mn = m+1
  36     end
  37   end
  38
  39   insert(self, mn, value)
  40   return mn
  41 end
  42
  43 -- Inserts a value into the table, searching the indexes [mn,mx).
  44 -- The inserted value must be greater or equal to the value at index mn, and less than the value at mx.
  45 -- mx should be the a valid index, or one past the last valid.
  46 -- Will try to insert as close to mx as possible, to reduce the number of values
  47 -- that need to be shifted.
  48 -- Returns the index the value was inserted at.
  49 function SortedList:insert2(value, mn, mx)
  50   local cmp = rawget(self, "cmp")
  51
  52   while mn ~= mx do
  53     local m = floor((mn+mx)*0.5)
  54
  55     if cmp(value, rawget(self, m)) then
  56       mx = m
  57     else
  58       mn = m+1
  59     end
  60   end
  61
  62   insert(self, mn, value)
  63   return mn
  64 end
  65
  66 -- Erases a value from the table.
  67 -- The thing you're erasing must exist.
  68 -- Care is taken to remove the actual value and not mearly something equal to it.
  69 -- Returns the upper bound of value, which you can use for reference if you intend to reinsert the value later.
  70 function SortedList:erase(value)
  71   local cmp = rawget(self, "cmp")
  72   local mn, mx = 1, #self+1
  73
  74   while mn ~= mx do
  75     local m = floor((mn+mx)*0.5)
  76
  77     if cmp(value, rawget(self, m)) then
  78       mx = m
  79     else
  80       mn = m+1
  81     end
  82   end
  83
  84   -- Subtracting 1, because it will be shifted by calling erase.
  85   local upper = mn-1
  86
  87   while true do
  88     local k = rawget(self, mn)
  89     if k == value then
  90       erase(self, mn)
  91       return upper
  92     end
  93
  94     assert(k, "Value should exist.")
  95     mn = mn - 1
  96   end
  97 end
  98
  99 -- Returns lower and upper bound for value.
 100 -- Lower bound is the first occurance of the variable, if it exists in the list.
 101 -- Upper bound is the index of the lowest value greater than value.
 102 -- If the lower and upper bound are equal, then value doesn't exist in the list.
 103 function SortedList:find(value)
 104   local cmp = rawget(self, "cmp")
 105   local lmn, lmx = 1, #self+1
 106   local hmn, hmx = lmn, lmx
 107
 108   while lmn ~= lmx do
 109     local m = floor((lmn+lmx)*0.5)
 110     local v = rawget(self, m)
 111
 112     if cmp(v, value) then
 113       lmn = m+1
 114       hmn = lmn
 115     elseif cmp(value, v) then
 116       lmx = m
 117       hmx = m
 118     else
 119       lmx = m
 120       hmn = m+1
 121
 122       while lmn ~= lmx do
 123         local m = floor((lmn+lmx)*0.5)
 124         local v = rawget(self, m)
 125
 126         if cmp(rawget(self, m), value) then
 127           lmn = m+1
 128         else
 129           lmx = m
 130
 131         end
 132       end
 133
 134       while hmn ~= hmx do
 135         local m = floor((hmn+hmx)*0.5)
 136
 137         if cmp(value, rawget(self, m)) then
 138           hmx = m
 139         else
 140           hmn = m+1
 141         end
 142       end
 143
 144       return lmn, hmx
 145     end
 146   end
 147 end
 148
 149 -- Returns lower bound for value. If value exists in the list, returned index will be its first occurance.
 150 function SortedList:lower(value)
 151   local cmp = rawget(self, "cmp")
 152   local mn, mx = 1, #self+1
 153
 154   while mn ~= mx do
 155     local m = floor((mn+mx)*0.5)
 156
 157     if cmp(rawget(self, m), value) then
 158       mn = m+1
 159     else
 160       mx = m
 161     end
 162   end
 163
 164   return mn
 165 end
 166
 167 -- Returns upper bound for value. If values exists, it will be the index directly before this one.
 168 function SortedList:upper(value)
 169   local cmp = rawget(self, "cmp")
 170   local mn, mx = 1, #self+1
 171
 172   while mn ~= mx do
 173     local m = floor((mn+mx)*0.5)
 174
 175     if cmp(value, rawget(self, m)) then
 176       mx = m
 177     else
 178       mn = m+1
 179     end
 180   end
 181
 182   return mn
 183 end
 184
 185 SortedList.__index = function(list, key)
 186   return rawget(list, key) or rawget(SortedList, key)
 187 end
 188
 189 local function createSortedList(cmp)
 190   return create(SortedList, cmp)
 191 end
 192
 193 QuestHelper.createSortedList = createSortedList