Class: AutoCompletion

Inherits:
Object
  • Object
show all
Defined in:
lib/autocompletion.rb,
lib/autocompletion/version.rb

Overview

AutoCompletion A binary search for prefix-matching is used to determine left- and right- boundary. This means even with 1_000_000 items, a maximum of 40 comparisons is required.

Examples:

Autocomplete words

auto = AutoCompletion.words(%w[foo bar baz])
auto.complete('f') # => ["foo"]
auto.complete('b') # => ["bar", "baz"]
auto.complete('z') # => []

Autocomplete objects by attributes

Person  = Struct.new(:first_name, :last_name)
people  = [
  Person.new("Peter", "Parker"),
  Person.new("Luke", "Skywalker"),
  Person.new("Anakin", "Skywalker"),
]
auto    = AutoCompletion.map_keys(people) { |person|
  [person.first_name, person.last_name]
}

auto.complete("P")
# => [#<struct Person first_name="Peter", last_name="Parker">]

auto.complete("S")
# => [#<struct Person first_name="Luke", last_name="Skywalker">,
#     #<struct Person first_name="Anakin", last_name="Skywalker">]

auto.complete("S", "L")
# => [#<struct Person first_name="Luke", last_name="Skywalker">]

Defined Under Namespace

Classes: InvalidOrder

Constant Summary collapse

Version =

The version of the gem

Gem::Version.new("0.0.3")

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(entities, force = false) ⇒ AutoCompletion

Returns a new instance of AutoCompletion.

Parameters:

  • entities (Array<Array>) —

    A flat array of the form [prefix1, value1, prefix2, value2, …] containing all prefixes and their corresponding value.

  • force (Boolean) (defaults to: false) —

    If force is set to true, the order of entities is not verified. Use this only if you know what you’re doing.

Raises:

See Also:

  • AutoCompletion::map


95
96
97
98
 
# File 'lib/autocompletion.rb', line 95

def initialize(entities, force=false)
  @entities = entities
  raise InvalidOrder unless force || valid?
end

Instance Attribute Details

#entities ⇒ Object (readonly)

All stored entities. A flat array of the form [prefix1, value1, prefix2, value2, …]



85
86
87
 
# File 'lib/autocompletion.rb', line 85

def entities
  @entities
end

Class Method Details

.map_key(entities) ⇒ AutoCompletion

Returns Map a list of entities to one of its attributes. The block should return string which can be prefix-searched.

Returns:

  • (AutoCompletion) —

    Map a list of entities to one of its attributes. The block should return string which can be prefix-searched.



70
71
72
73
74
75
76
 
# File 'lib/autocompletion.rb', line 70

def self.map_key(entities)
  mapped = entities.map { |entity|
    [yield(entity), entity]
  }

  unordered_tuples(mapped)
end

.map_keys(entities) ⇒ AutoCompletion

Returns Map a list of entities to many of their attributes. The block should return an array of strings which can be prefix-searched.

Returns:

  • (AutoCompletion) —

    Map a list of entities to many of their attributes. The block should return an array of strings which can be prefix-searched.



58
59
60
61
62
63
64
65
 
# File 'lib/autocompletion.rb', line 58

def self.map_keys(entities)
  mapped = entities.flat_map { |entity|
    keys = yield(entity)
    keys.flat_map { |key| [key, entity] }
  }

  unordered_tuples(mapped.each_slice(2))
end

.unordered_tuples(entities) ⇒ AutoCompletion

Returns Creates an AutoCompletion for an unordered array of the form [[“prefix”, value], …].

Returns:

  • (AutoCompletion) —

    Creates an AutoCompletion for an unordered array of the form [[“prefix”, value], …].



80
81
82
 
# File 'lib/autocompletion.rb', line 80

def self.unordered_tuples(entities)
  new(entities.sort_by(&:first).flatten(1), true)
end

.words(words) ⇒ AutoCompletion

Returns An autocompletion for a list of words.

Returns:



51
52
53
 
# File 'lib/autocompletion.rb', line 51

def self.words(words)
  unordered_tuples(words.map { |word| [word, word] })
end

Instance Method Details

#complete(*prefixes) ⇒ Array

Returns an array of distinct entities matching the given prefixes.

Parameters:

  • prefixes (String) —

    A list of prefixes to match. All given prefixes must be matched.

Returns:

  • (Array) —

    Returns an array of distinct entities matching the given prefixes.



145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/autocompletion.rb', line 145

def complete(*prefixes)
  # short-cut
  return [] if empty? || prefixes.empty? || prefixes.any? { |word|
    word < @entities.first[0,word.size] || word > @entities[-2][0,word.size]
  }

  slices = prefixes.map { |word|
    slice = range_search(word)
    return [] unless slice # short-cut

    slice
  }

  result = @entities[slices.pop].each_slice(2).map(&:last).uniq
  slices.each do |slice|
    result &= @entities[slice].each_slice(2).map(&:last)
  end

  result
end

#count_distinct_entitites ⇒ Integer

Returns The number of distinct entities.

Returns:

  • (Integer) —

    The number of distinct entities



121
122
123
124
125
126
127
128
 
# File 'lib/autocompletion.rb', line 121

def count_distinct_entitites
  result = {}
  @entities.each_slice(2) do |key, value|
    result[value] = true
  end

  result.size
end

#count_distinct_prefixes ⇒ Integer

Returns The number of distinct prefixes.

Returns:

  • (Integer) —

    The number of distinct prefixes



131
132
133
134
135
136
137
138
 
# File 'lib/autocompletion.rb', line 131

def count_distinct_prefixes
  result = {}
  @entities.each_slice(2) do |key, value|
    result[key] = true
  end

  result.size
end

#empty? ⇒ Boolean

Returns true if there are no prefixes stored in this AutoCompletion instance.

Returns:

  • (Boolean) —

    Returns true if there are no prefixes stored in this AutoCompletion instance.



110
111
112
 
# File 'lib/autocompletion.rb', line 110

def empty?
  @entities.empty?
end

#inspect ⇒ Object

See Also:

  • Object#inspect


221
222
223
224
225
226
227
228
229
 
# File 'lib/autocompletion.rb', line 221

def inspect
  sprintf "\#<%s:%x size: %d, unique: %d, %p..%p>",
          self.class,
          object_id>>1,
          size,
          count_distinct_prefixes,
          @entities[0],
          @entities[-2]
end

#range_search(prefix) ⇒ nil, Range<Integer>

Returns nil if AutoCompletion#empty? Returns -1..-1 if the prefix is smaller than the smallest key Returns AutoCompletion#size..AutoCompletion#size if the prefix is bigger than the biggest key Returns the range for all matched keys and values otherwise

Returns:

  • (nil, Range<Integer>) —

    Returns nil if AutoCompletion#empty? Returns -1..-1 if the prefix is smaller than the smallest key Returns AutoCompletion#size..AutoCompletion#size if the prefix is bigger than the biggest key Returns the range for all matched keys and values otherwise



171
172
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/autocompletion.rb', line 171

def range_search(prefix)
  prefix_size   = prefix.size
  length        = size()
  found         = nil
  left          = 0
  right         = length-1
  found         = false
  max_exc_right = length

  return nil if empty?
  return -1..-1 if @entities[0][0,prefix_size] > prefix # prefix is smaller than smallest value
  return length..length if @entities[-2][0,prefix_size] < prefix # prefix is bigger than biggest value

  # binary search for smallest index
  # mark biggest right which includes prefix, and biggest mark that doesn't include prefix
  while(left<right)
    index     = (left+right)>>1
    cmp_value = @entities.at(index<<1)[0,prefix_size]
    case cmp_value <=> prefix
      when -1 then
        left          = index+1
      when 1 then
        right         = index
        max_exc_right = right
      else # 0
        right         = index
    end
  end
  return nil unless @entities.at(left<<1)[0,prefix_size] == prefix
  final_left = left

  # binary search for biggest index
  right = max_exc_right-1
  while(left<right)
    index     = (left+right)>>1
    cmp_value = @entities.at(index<<1)[0,prefix_size]
    if cmp_value > prefix then
      right = index
    else
      left = index+1
    end
  end
  final_right = right
  final_right -= 1 unless @entities.at(right<<1)[0,prefix_size] == prefix

  return (final_left<<1)..((final_right<<1)+1)
end

#size ⇒ Integer

Returns The number of prefixes stored. Note that the same prefix can occur multiple times.

Returns:

  • (Integer) —

    The number of prefixes stored. Note that the same prefix can occur multiple times.



116
117
118
 
# File 'lib/autocompletion.rb', line 116

def size
  @entities.size>>1
end

#valid? ⇒ Boolean

Returns true if the prefixes are in a valid order.

Returns:

  • (Boolean) —

    Returns true if the prefixes are in a valid order.



102
103
104
105
106
 
# File 'lib/autocompletion.rb', line 102

def valid?
  @entities.each_slice(2).each_cons(2).all? { |(a,_),(b,_)|
    a <= b
  }
end