--[[-------------------------------------------------------------------- Ovale Spell Priority Copyright (C) 2013 Johnny C. Lam This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License in the LICENSE file accompanying this program. --]]-------------------------------------------------------------------- --[[ Time spans are continuous open intervals (start, ending) that are subsets of (0, infinity). Infinity is represented by math.huge. Point sets are considered empty. "nil" time spans are considered empty. This module supports the following operations on time spans: Complement Union (code kindly contributed by Qrux) Intersection --]] local _, Ovale = ... local OvaleTimeSpan = {} Ovale.OvaleTimeSpan = OvaleTimeSpan --<private-static-properties> --local debugprint = print local setmetatable = setmetatable local strformat = string.format local tconcat = table.concat local wipe = table.wipe --</private-static-properties> --<public-static-properties> OvaleTimeSpan.__index = OvaleTimeSpan do -- Class constructor setmetatable(OvaleTimeSpan, { __call = function(self, ...) return self:New(...) end }) end --</public-static-properties> --<private-static-methods> local function CompareIntervals(startA, endA, startB, endB) --debugprint(string.format(" comparing (%s, %s) with (%s, %s)", startA, endA, startB, endB)) if startA == startB and endA == endB then -- same (0) return 0 elseif startA < startB and endA >= startB and endA <= endB then -- overlap, A comes-before B (-1) return -1 elseif startB < startA and endB >= startA and endB <= endA then -- overlap, B comes-before A (1) return 1 elseif (startA == startB and endA > endB) or (startA < startB and endA == endB) or (startA < startB and endA > endB) then -- A contains B (-2) return -2 elseif (startB == startA and endB > endA) or (startB < startA and endB == endA) or (startB < startA and endB > endA) then -- B contains A (3) return 2 elseif endA <= startB then -- A before B (-3) return -3 elseif endB <= startA then -- B before A (3) return 3 end -- Fail; unreachable (99) return 99 end --</private-static-methods> --<public-static-methods> function OvaleTimeSpan:New(...) local A = ... if type(A) == "table" then return setmetatable(A, self) else return setmetatable({ ... }, self) end end function OvaleTimeSpan:__tostring() if not self or #self == 0 then return "empty set" else return strformat("(%s)", tconcat(self, ", ")) end end function OvaleTimeSpan:Clone() if not self then return OvaleTimeSpan() end return self:CopyTo( {} ) end function OvaleTimeSpan:CopyTo(result) if not self then return OvaleTimeSpan(result) end for i = 1, #self do result[i] = self[i] end return OvaleTimeSpan(result) end function OvaleTimeSpan:Reset(template) if self then wipe(self) if template then return template:CopyTo(self) else return OvaleTimeSpan(self) end end end function OvaleTimeSpan:IsEmpty() return (not self or #self == 0) end function OvaleTimeSpan:Equals(B) local A = self local countA = A and #A or 0 local countB = B and #B or 0 if countA ~= countB then return false end for k = 1, countA do if A[k] ~= B[k] then return false end end return true end function OvaleTimeSpan:HasTime(atTime) local A = self local countA = A and #A or 0 for i = 1, countA, 2 do if A[i] <= atTime and atTime <= A[i+1] then return true end end return false end function OvaleTimeSpan:NextTime(atTime) local A = self local countA = A and #A or 0 for i = 1, countA, 2 do if atTime < A[i] then return A[i] elseif A[i] <= atTime and atTime <= A[i+1] then return atTime end end end function OvaleTimeSpan:Measure() local A = self local countA = A and #A or 0 local measure = 0 for i = 1, countA, 2 do measure = measure + (A[i+1] - A[i]) end return measure end function OvaleTimeSpan:Complement(result) local A = self local countA = A and #A or 0 result = result or {} if countA == 0 then result[1], result[2] = 0, math.huge return OvaleTimeSpan(result) end local i, k = 1, 1 if A[i] == 0 then i = i + 1 else result[k] = 0 k = k + 1 end while i < countA do result[k] = A[i] i, k = i + 1, k + 1 end if A[i] < math.huge then result[k], result[k+1] = A[i], math.huge end return OvaleTimeSpan(result) end function OvaleTimeSpan:IntersectInterval(startB, endB, result) local A = self local countA = A and #A or 0 result = result or {} -- If A is empty, then the intersection is empty. if countA == 0 or not startB or not endB then return OvaleTimeSpan(result) end local i, k = 1, 1 while true do if i > countA then break end local startA, endA = A[i], A[i+1] local compare = CompareIntervals(startA, endA, startB, endB) if compare == 0 then -- Same; output, exit. result[k], result[k+1] = startA, endA break elseif compare == -1 then -- Overlap; A comes before B, output, advance A. if endA > startB then result[k], result[k+1] = startB, endA i, k = i + 2, k + 2 else i = i + 2 end elseif compare == 1 then -- Overlap; B comes before A, output, exit. if endB > startA then result[k], result[k+1] = startA, endB end break elseif compare == -2 then -- A contains B; output, exist. result[k], result[k+1] = startB, endB break elseif compare == 2 then -- B contains A; output, advance A. result[k], result[k+1] = startA, endA i, k = i + 2, k + 2 elseif compare == -3 then -- A before B i = i + 2 elseif compare == 3 then -- B before A break end end return OvaleTimeSpan(result) end function OvaleTimeSpan:Intersect(B, result) local A = self local countA = A and #A or 0 local countB = B and #B or 0 result = result or {} -- If either A or B are empty, then the intersection is empty. if countA == 0 or countB == 0 then return OvaleTimeSpan(result) end local i, j, k = 1, 1, 1 while true do if i > countA or j > countB then break end local startA, endA = A[i], A[i+1] local startB, endB = B[j], B[j+1] --debugprint(string.format(" A: (%s, %s)", tostring(startA), tostring(endA))) --debugprint(string.format(" B: (%s, %s)", tostring(startB), tostring(endB))) local compare = CompareIntervals(startA, endA, startB, endB) --debugprint(" overlap?", compare) if compare == 0 then -- Same; output, advance both. result[k], result[k+1] = startA, endA i, j, k = i + 2, j + 2, k + 2 --debugprint(" ADV(A)") --debugprint(" ADV(B)") elseif compare == -1 then -- Overlap; A comes before B, output, advance A. if endA > startB then result[k], result[k+1] = startB, endA i, k = i + 2, k + 2 else i = i + 2 end --debugprint(" ADV(A)") elseif compare == 1 then -- Overlap; B comes before A, output, advance B. if endB > startA then result[k], result[k+1] = startA, endB j, k = j + 2, k + 2 else j = j + 2 end --debugprint(" ADV(B)") elseif compare == -2 then -- A contains B; output, advance B. result[k], result[k+1] = startB, endB j, k = j + 2, k + 2 --debugprint(" ADV(B)") elseif compare == 2 then -- B contains A; output, advance A. result[k], result[k+1] = startA, endA i, k = i + 2, k + 2 --debugprint(" ADV(A)") elseif compare == -3 then -- A before B i = i + 2 --debugprint(" ADV(A)") elseif compare == 3 then -- B before A j = j + 2 --debugprint(" ADV(B)") else --debugprint("WTF--can't happen; ABORT NAO!") i = i + 2 j = j + 2 end end return OvaleTimeSpan(result) end function OvaleTimeSpan:Union(B, result) local A = self local countA = A and #A or 0 local countB = B and #B or 0 result = result or {} -- If either A or B are empty, then return the other one. if countA == 0 and countB == 0 then return OvaleTimeSpan(result) elseif countA == 0 then return not B and OvaleTimeSpan(result) or B:CopyTo(result) elseif countB == 0 then return not A and OvaleTimeSpan(result) or A:CopyTo(result) end local i, j, k = 1, 1, 1 local startTemp, endTemp = A[i], A[i+1] local holdingA = true local scanningA = false while true do local startA, endA, startB, endB if i > countA and j > countB then -- Write the final temp to output. result[k], result[k+1] = startTemp, endTemp break end if scanningA and i > countA then -- Past the end of A; Flip-scan; Flip-hold. holdingA = not holdingA scanningA = not scanningA else -- Normal; not past the end of A. startA, endA = A[i], A[i+1] end if not scanningA and j > countB then -- Past the end of B; Flip-scan; Flip-hold. holdingA = not holdingA scanningA = not scanningA else -- Normal; not past the end of B. startB, endB = B[j], B[j+1] end local startCurrent = scanningA and startA or startB local endCurrent = scanningA and endA or endB --debugprint(string.format(" temp: (%s, %s)", tostring(startTemp), tostring(endTemp))) --debugprint(string.format(" A: (%s, %s)", tostring(startA), tostring(endA))) --debugprint(string.format(" B: (%s, %s)", tostring(startB), tostring(endB))) --debugprint(string.format("current: (%s, %s)", tostring(startCurrent), tostring(endCurrent))) --debugprint(" holdA", holdingA) --debugprint(" scanA", scanningA) --[[ Comparing pairs (temp, current): 0 is (2, 3) - (2, 3) (temp equals current) - Advance-scan. -2 is (1, 5) - (2, 4) (temp contains current) - Advance-scan. -1 is (1, 3) - (2, 5) (temp starts-before current) - Update temp-end (to cur2); advance-scan. 1 is (2, 5) - (1, 3) (current starts-before temp ) - Update temp-start (to cur1); advance-scan. 2 is (1, 5) - (2, 4) (current contains temp ) - Reset-temp (to cur); Flip-scan; Flip-hold. -3 is (1, 2) - (3, 4) (temp is-before current) - Flip-scan; advance-cur. 3 is (3, 4) - (1, 2) (current is-before temp ) - Reset-temp (to cur); Flip-scan; Flip-hold. --]] local compare = CompareIntervals(startTemp, endTemp, startCurrent, endCurrent) --debugprint(" overlap?", compare) if compare == 0 then -- Skip. if scanningA then i = i + 2 else j = j + 2 end elseif compare == -2 then -- Simplest cases; advance input-currently-being-scanned. if scanningA then i = i + 2 else j = j + 2 end elseif compare == -1 then -- Update temp-END, advance. endTemp = endCurrent if scanningA then i = i + 2 else j = j + 2 end elseif compare == 1 then -- update temp-START, advance. startTemp = startCurrent if scanningA then i = i + 2 else j = j + 2 end elseif compare == 2 then -- We need to flip the side we're scanning (and holding), because the other side contains this side. startTemp, endTemp = startCurrent, endCurrent holdingA = not holdingA scanningA = not scanningA if scanningA then i = i + 2 else j = j + 2 end elseif compare == -3 then -- This (and 3) are the only situations where we capture the output. --debugprint(" (-3) holdA", holdingA) --debugprint(" (-3) scanA", scanningA) if holdingA == scanningA then result[k], result[k+1] = startTemp, endTemp startTemp, endTemp = startCurrent, endCurrent scanningA = not scanningA k = k + 2 else scanningA = not scanningA if scanningA then i = i + 2 --debugprint(" ADV(A)") else j = j + 2 --debugprint(" ADV(B)") end end elseif compare == 3 then -- This (and -3) are the only situations where we capture the output. startTemp, endTemp = startCurrent, endCurrent holdingA = not holdingA scanningA = not scanningA else --debugprint("WTF--can't happen; ABORT NAO!") i = i + 2 j = j + 2 end end return OvaleTimeSpan(result) end --</public-static-methods>