Class: Ferret::Search::Spans::NearSpansEnum

Inherits:
SpansEnum
  • Object
show all
Defined in:
lib/ferret/search/spans/near_spans_enum.rb

Defined Under Namespace

Classes: CellQueue, SpansCell

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(query, reader) ⇒ NearSpansEnum

Returns a new instance of NearSpansEnum.



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 83

def initialize(query, reader)
  @ordered = []         # spans in query order

  @first = nil          # linked list of spans
  @last = nil           # sorted by doc only

  @total_length = 0     # sum of current lengths

  @queue = nil          # sorted queue of spans
  @max = nil            # max element in queue

  @more = true          # true iff not done
  @first_time = true    # true before first next?

 
  @query = query
  @slop = query.slop
  @in_order = query.in_order?

  clauses = query.clauses # initialize spans & list
  @queue = CellQueue.new(clauses.length)
  clauses.length.times do |i|
    # construct clause spans
    cell = SpansCell.new(self, clauses[i].spans(reader), i)
    @ordered << cell    # add to ordered
  end
end

Instance Attribute Details

#max ⇒ Object

Returns the value of attribute max.



81
82
83
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 81

def max
  @max
end

#total_length ⇒ Object

Returns the value of attribute total_length.



81
82
83
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 81

def total_length
  @total_length
end

Instance Method Details

#add_to_list(cell) ⇒ Object 



229
230
231
232
233
234
235
236
237
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 229

def add_to_list(cell) 
  if (@last != nil) # add next to end of list
    @last.next = cell
  else
    @first = cell
  end
  @last = cell
  cell.next = nil
end

#at_match? ⇒ Boolean

Returns:

  • (Boolean) 


284
285
286
287
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 284

def at_match?() 
  return ((min().doc() == @max.doc()) and check_slop?() and
          (not @in_order or match_is_ordered?()))
end

#check_slop? ⇒ Boolean

Returns:

  • (Boolean) 


289
290
291
292
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 289

def check_slop?() 
  match_length = @max.finish() - min.start()
  return ((match_length - @total_length) <= @slop)
end

#doc ⇒ Object 



203
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 203

def doc() min().doc() end

#each ⇒ Object 



165
166
167
168
169
170
171
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 165

def each()
  cell = @first
  while (cell)
    yield cell
    cell=cell.next
  end
end

#finish ⇒ Object 



205
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 205

def finish() @max.finish() end

#first_non_ordered_next_to_partial_list ⇒ Object

Raises:

  • (RuntimeException) 


253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 253

def first_non_ordered_next_to_partial_list()
  # Creates a partial list consisting of first non ordered and earlier.
  # Returns first non ordered .next?.
  @last = @first = nil
  ordered_index = 0
  while (@queue.top() != nil) 
    cell = @queue.pop()
    add_to_list(cell)
    if (cell.index == ordered_index) 
      ordered_index += 1
    else 
      return cell.next?()
      # FIXME: continue here, rename to eg. checkOrderedMatch():
      # when check_slop?() and not ordered, repeat cell.next?().
      # when check_slop?() and ordered, add to list and repeat queue.pop()
      # without check_slop?(): no match, rebuild the queue from the partial list.
      # When queue is empty and check_slop?() and ordered there is a match.
    end
  end
  raise RuntimeException, "Unexpected: ordered"
end

#first_to_last ⇒ Object 



239
240
241
242
243
244
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 239

def first_to_last() 
  @last.next = @first # move first to end of list
  @last = @first
  @first = @first.next
  @last.next = nil
end

#init_list(nxt) ⇒ Object 



218
219
220
221
222
223
224
225
226
227
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 218

def init_list(nxt)
  @ordered.each do |cell|
    @more = cell.next? if nxt
    if @more
      add_to_list(cell) # add to list
    else
      break
    end
  end
end

#list_to_queue ⇒ Object 



275
276
277
278
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 275

def list_to_queue() 
  @queue.clear() # rebuild queue
  partial_list_to_queue()
end

#match_is_ordered? ⇒ Boolean

Returns:

  • (Boolean) 


294
295
296
297
298
299
300
301
302
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 294

def match_is_ordered?() 
  last_start = -1
  @ordered.each do |cell|
    start = cell.start
    return false if start <= last_start
    last_start = start
  end
  return true
end

#min ⇒ Object 



201
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 201

def min() @queue.top() end

#next? ⇒ Boolean

Returns:

  • (Boolean) 


111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 111

def next?()
  if (@first_time) 
    init_list(true)
    list_to_queue()                # initialize queue
    @first_time = false
  elsif (@more) 
    @more = min().next?            # trigger further scanning
    @queue.adjust_top() if (@more) # maintain queue 
  end

  while (@more) 
    queue_stale = false

    if (min().doc != @max.doc)     # maintain list
      queue_to_list()
      queue_stale = true
    end

    # skip to doc w/ all clauses

    while (@more and @first.doc < @last.doc) 
      @more = @first.skip_to(@last.doc) # skip first upto last
      first_to_last()              # and move it to the end
      queue_stale = true
    end

    return false if not @more

    # found doc w/ all clauses

    if (queue_stale) # maintain the queue
      list_to_queue()
      queue_stale = false
    end

    return true if at_match?
    
    # trigger further scanning
    if (@in_order and check_slop?()) 
      # There is a non ordered match within slop and an ordered match is needed. 
      @more = first_non_ordered_next_to_partial_list()
      if (@more) 
        partial_list_to_queue()
      end
    else 
      @more = min().next?()
      if (@more) 
        @queue.adjust_top()        # maintain queue
      end
    end
  end
  return false                     # no more matches
end

#partial_list_to_queue ⇒ Object 



280
281
282
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 280

def partial_list_to_queue() 
  each() { |cell| @queue.push(cell) } # add to queue from list
end

#queue_to_list ⇒ Object 



246
247
248
249
250
251
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 246

def queue_to_list() 
  @last = @first = nil
  while (@queue.top() != nil) 
    add_to_list(@queue.pop())
  end
end

#skip_to(target) ⇒ Object 



173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 173

def skip_to(target)
  if (@first_time) # initialize
    init_list(false)
    each() do |cell|
      @more = cell.skip_to(target) # skip all
      break if not @more
    end

    if (@more) 
      list_to_queue()
    end
    @first_time = false

  else # normal case
    while (@more and min().doc < target) # skip as needed
      @more = min().skip_to(target)
      @queue.adjust_top() if (@more)
    end
  end

  if (@more) 
    return true if (at_match?())              # at a match?
    return next?                              # no, scan
  end

  return false
end

#start ⇒ Object 



204
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 204

def start() min().start() end

#to_s ⇒ Object 



208
209
210
211
212
213
214
215
216
 
# File 'lib/ferret/search/spans/near_spans_enum.rb', line 208

def to_s() 
  buffer = "spans(#{@query})@"
  if @first_time
    buffer << "START"
  else
    buffer << (@queue.size>0 ? ("#{doc}:#{start()}-#{finish}") : "END")
  end
  return buffer
end