subread/cues.lua (4736 bytes)
1 --[[-- 2 Cue index for SubRead. 3 4 Pure Lua. No KOReader dependency, so it can be unit tested on a PC. 5 6 The index holds the cues in start order and answers three questions: 7 * which cue is on at time t, 8 * which cue starts next after time t, 9 * which cue holds a piece of text. 10 --]]-- 11 12 local Text = require("subread.text") 13 14 local Cues = {} 15 Cues.__index = Cues 16 17 --- Builds an index from a cue array. The array must be sorted by start time. 18 function Cues.new(list) 19 local self = setmetatable({}, Cues) 20 self.list = list or {} 21 self.max_duration = 0 22 for _, cue in ipairs(self.list) do 23 local duration = cue.stop - cue.start 24 if duration > self.max_duration then 25 self.max_duration = duration 26 end 27 end 28 return self 29 end 30 31 function Cues:count() 32 return #self.list 33 end 34 35 function Cues:get(index) 36 return self.list[index] 37 end 38 39 --- Returns the index of the last cue that starts at or before t. 40 -- Returns 0 when every cue starts after t. 41 function Cues:lastStartedAt(t) 42 local low, high, answer = 1, #self.list, 0 43 while low <= high do 44 local mid = math.floor((low + high) / 2) 45 if self.list[mid].start <= t then 46 answer = mid 47 low = mid + 1 48 else 49 high = mid - 1 50 end 51 end 52 return answer 53 end 54 55 --- Returns the index of the cue that is on at time t, or nil. 56 -- Cues can overlap. The latest cue that is still on wins. 57 -- The walk back stops after the longest cue in the file, so the cost is bound. 58 function Cues:findByTime(t) 59 local index = self:lastStartedAt(t) 60 while index >= 1 do 61 local cue = self.list[index] 62 if t - cue.start > self.max_duration then break end 63 if cue.stop > t then return index end 64 index = index - 1 65 end 66 return nil 67 end 68 69 --- Returns the index of the first cue that starts after t, or nil. 70 function Cues:nextAfter(t) 71 local index = self:lastStartedAt(t) + 1 72 -- Cues with the same start time can follow the one that lastStartedAt 73 -- found, so step over every cue that does not start after t. 74 while self.list[index] and self.list[index].start <= t do 75 index = index + 1 76 end 77 if self.list[index] then return index end 78 return nil 79 end 80 81 --- Returns the index of the cue that is on at t, or of the nearest cue. 82 -- Use it to choose a start time. Returns nil for an empty index. 83 function Cues:findNearest(t) 84 if #self.list == 0 then return nil end 85 local on = self:findByTime(t) 86 if on then return on end 87 local before = self:lastStartedAt(t) 88 local after = before + 1 89 if before < 1 then return 1 end 90 if not self.list[after] then return before end 91 local gap_before = t - self.list[before].stop 92 local gap_after = self.list[after].start - t 93 if gap_after < gap_before then return after end 94 return before 95 end 96 97 --- Returns the index of the first cue whose text holds the needle, or nil. 98 -- The needle must already be normalised. The search is a plain substring 99 -- search, not a pattern match. 100 -- @int from optional first index to look at (default 1) 101 function Cues:findIndexContaining(needle, from) 102 if not needle or needle == "" then return nil end 103 for index = from or 1, #self.list do 104 if self.list[index].norm:find(needle, 1, true) then 105 return index 106 end 107 end 108 return nil 109 end 110 111 -- Lengths, in characters, of the needles cut out of a page of the book. 112 -- The long needle comes first, because a long match is more sure. The short 113 -- needle is the fallback for a cue that is shorter than the long needle. 114 Cues.NEEDLE_LENGTHS = { 12, 6 } 115 -- Number of needles tried for each length. A needle can fail because the book 116 -- text holds ruby text or a running head that the cue text does not hold. 117 Cues.NEEDLE_TRIES = 8 118 -- Distance, in characters, between two needles. 119 Cues.NEEDLE_STEP = 8 120 121 --- Returns the index of the first cue that holds a piece of the given text. 122 -- Use it to answer "which cue does this page start with?". 123 -- @string haystack book text, not yet normalised 124 function Cues:findIndexForText(haystack) 125 local norm = Text.normalize(haystack) 126 local count = Text.len(norm) 127 if count == 0 then return nil end 128 for _, length in ipairs(Cues.NEEDLE_LENGTHS) do 129 for try = 0, Cues.NEEDLE_TRIES - 1 do 130 local first = 1 + try * Cues.NEEDLE_STEP 131 if first > count then break end 132 local last = first + length - 1 133 if last > count then last = count end 134 if last - first + 1 >= length then 135 local index = self:findIndexContaining(Text.sub(norm, first, last)) 136 if index then return index end 137 end 138 end 139 end 140 return nil 141 end 142 143 return Cues