Class: MSlinnBinarySearch

Inherits:
Object
  • Object
show all
Defined in:
lib/util/mslinn_binary_search.rb

Overview

Ruby’s binary search is unsuitable because the value to be searched for changes the required ordering for String compares

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(accessor_chain) ⇒ MSlinnBinarySearch

Returns a new instance of MSlinnBinarySearch.



10
11
12
13
 
# File 'lib/util/mslinn_binary_search.rb', line 10

def initialize(accessor_chain)
  @array = SortedSet.new # [LruFile] Ordered highest to lowest
  @accessor_chain = accessor_chain
end

Instance Attribute Details

#accessor_chain ⇒ Object (readonly)

For testing only



8
9
10
 
# File 'lib/util/mslinn_binary_search.rb', line 8

def accessor_chain
  @accessor_chain
end

#array ⇒ Object (readonly)

For testing only



8
9
10
 
# File 'lib/util/mslinn_binary_search.rb', line 8

def array
  @array
end

Instance Method Details

#enable_search ⇒ Object

Convert the SortedSet to an Array



16
17
18
 
# File 'lib/util/mslinn_binary_search.rb', line 16

def enable_search
  @array = @array.to_a
end

#find(stem) ⇒ Object

A match is found when the Array has an href which starts with the given stem

Parameters:

  • stem (String)

Returns:

  • first item from @array.url that matches, or nil if no match

Raises:



23
24
25
26
27
28
29
30
 
# File 'lib/util/mslinn_binary_search.rb', line 23

def find(stem)
  raise MSlinnBinarySearchError, 'Invalid find because stem to search for is nil.' if stem.nil?

  index = find_index(stem)
  return nil if index.nil?

  @array[index]
end

#find_index(stem) ⇒ Object

Returns index of first matching stem, or nil if @array is empty, or 0 if no stem specified.

Parameters:

  • stem (String)

Returns:

  • index of first matching stem, or nil if @array is empty, or 0 if no stem specified



34
35
36
37
38
39
40
41
42
43
 
# File 'lib/util/mslinn_binary_search.rb', line 34

def find_index(stem)
  return nil if @array.empty?
  return 0 if stem.nil? || stem.empty?

  mets = stem.reverse
  return nil if @array[0].url[0...mets.size] > mets # TODO: use chain eval for item
  return nil if @array[0].url[0] != mets[0]

  _find_index(mets, 0, @array.length - 1)
end

#find_indices(stem) ⇒ index

Returns of matching values, or [] if @array is empty, or entire array if no stem specified.

Parameters:

  • stem (String)

Returns:

  • (index) —

    of matching values, or [] if @array is empty, or entire array if no stem specified



47
48
49
50
51
52
53
54
55
 
# File 'lib/util/mslinn_binary_search.rb', line 47

def find_indices(stem)
  return [] if @array.empty?
  return @array if stem.nil? || stem.empty?

  first_index = _find_index(stem, 0, @array.length - 1)
  last_index = first_index
  last_index += 1 while @array[last_index].url.start_with? stem
  [first_index..last_index]
end

#index_of(lru_file) ⇒ int

Returns index of matching LruFile in @array, or nil if not found.

Parameters:

Returns:

  • (int) —

    index of matching LruFile in @array, or nil if not found

Raises:



59
60
61
62
63
 
# File 'lib/util/mslinn_binary_search.rb', line 59

def index_of(lru_file)
  raise MSlinnBinarySearchError, 'Invalid index_of lru_file (nil).' if lru_file.nil?

  find_index lru_file.url
end

#insert(lru_file) ⇒ Object

Parameters:

Raises:



77
78
79
80
81
82
 
# File 'lib/util/mslinn_binary_search.rb', line 77

def insert(lru_file)
  raise MSlinnBinarySearchError, 'Invalid insert because new item is nil.' if lru_file.nil?
  raise MSlinnBinarySearchError, "Invalid insert because new item has no chain (#{lru_file})" if lru_file.chain.nil?

  @array.add lru_file
end

#item_at(index) ⇒ LruFile

Returns item at given index in @array.

Returns:

  • (LruFile) —

    item at given index in @array

Raises:



66
67
68
69
70
71
72
73
74
 
# File 'lib/util/mslinn_binary_search.rb', line 66

def item_at(index)
  if index > @array.length - 1
    raise MSlinnBinarySearchError,
          "Invalid item_at index (#{index}) is greater than maximum stem (#{@array.length - 1})."
  end
  raise MSlinnBinarySearchError, "Invalid item_at index (#{index}) is less than zero." if index.negative?

  @array[index]
end

#prefix_search(suffix) ⇒ Object

TODO: Cache this method

Parameters:

  • suffix (String) —

    to use stem search on

Returns:

  • nil if @array is empty

  • the first item in @array if suffix is nil or an empty string



88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/util/mslinn_binary_search.rb', line 88

def prefix_search(suffix)
  return nil if @array.empty?
  return @array[0] if suffix.empty? || suffix.nil?

  low = search_index { |x| x.evaluate_with suffix }
  return [] if low.nil?

  high = low
  high += 1 while high < @array.length &&
                  @array[high].evaluate_with(suffix)
  @array[low..high]
end

#select_pages(stem) ⇒ APage

Returns matching APages, or [] if @array is empty, or entire array if no stem specified.

Parameters:

  • stem (String)

Returns:

  • (APage) —

    matching APages, or [] if @array is empty, or entire array if no stem specified



103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/util/mslinn_binary_search.rb', line 103

def select_pages(stem)
  first_index = find_index stem
  return [] if first_index.nil?

  last_index = first_index
  while last_index < @array.length - 1
    # LruFile.url is reversed, bug LruFile.page is not
    break unless @array[last_index + 1].url.start_with?(stem.reverse)

    last_index += 1
  end
  Range.new(first_index, last_index).map { |i| @array[i].page }
end