Class: MiniFTS::SearchableMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/minifts/searchable_map.rb

Overview

A radix tree (compressed prefix tree) implementing a Map-like interface with string keys, plus efficient prefix and fuzzy (Levenshtein) lookup. Used internally by MiniFTS as the inverted index, but useful on its own.

This is a faithful port of MiniSearch's SearchableMap. The tree is a nested Hash: every non-empty string key is an edge label pointing at a child Hash, and the empty-string key (LEAF) holds the value stored at that node.

Constant Summary collapse

LEAF =

Sentinel key marking a node that carries a stored value. It is the empty string, which can never be an edge label (edge labels are non-empty).

""

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree = {}, prefix = "") ⇒ SearchableMap

Normally called without arguments to create an empty map. The arguments are for internal use, when building a derived view at a prefix (see #at_prefix).



26
27
28
29
30
 
# File 'lib/minifts/searchable_map.rb', line 26

def initialize(tree = {}, prefix = "")
  @tree = tree
  @prefix = prefix
  @size = nil
end

Instance Attribute Details

#prefix ⇒ Object (readonly)

Returns the value of attribute prefix.



22
23
24
 
# File 'lib/minifts/searchable_map.rb', line 22

def prefix
  @prefix
end

#tree ⇒ Object (readonly)

Returns the value of attribute tree.



19
20
21
 
# File 'lib/minifts/searchable_map.rb', line 19

def tree
  @tree
end

Class Method Details

.from(entries) ⇒ Object

Builds a SearchableMap from an iterable of [key, value] entries.



154
155
156
157
158
 
# File 'lib/minifts/searchable_map.rb', line 154

def self.from(entries)
  map = new
  entries.each { |key, value| map.set(key, value) }
  map
end

.from_object(object) ⇒ Object

Builds a SearchableMap from a Hash of entries.



161
162
163
 
# File 'lib/minifts/searchable_map.rb', line 161

def self.from_object(object)
  from(object)
end

Instance Method Details

#at_prefix(prefix) ⇒ Object

Returns a mutable view of this map containing only entries whose keys start with prefix.

Raises:



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/minifts/searchable_map.rb', line 34

def at_prefix(prefix)
  raise Error, "Mismatched prefix" unless prefix.start_with?(@prefix)

  node, path = track_down(@tree, tail(prefix, @prefix.length))

  if node.nil?
    parent_node, key = path.last
    parent_node.each_key do |k|
      next unless k != LEAF && k.start_with?(key)

      child = {}
      child[tail(k, key.length)] = parent_node[k]
      return SearchableMap.new(child, prefix)
    end
  end

  # When no subtree matches, MiniSearch relies on the constructor's default
  # (`tree = new Map()`) to yield an empty, still-iterable view.
  SearchableMap.new(node.nil? ? {} : node, prefix)
end

#clear ⇒ Object

Removes all entries.



56
57
58
59
60
 
# File 'lib/minifts/searchable_map.rb', line 56

def clear
  @size = nil
  @tree.clear
  nil
end

#delete(key) ⇒ Object

Deletes the entry at key, if present.



63
64
65
66
67
 
# File 'lib/minifts/searchable_map.rb', line 63

def delete(key)
  @size = nil
  remove(@tree, key)
  nil
end

#each(&block) ⇒ Object

Yields (or returns an Enumerator over) [key, value] pairs, in the same order as MiniSearch's tree iterator (depth-first, siblings in reverse insertion order).



72
73
74
75
76
77
 
# File 'lib/minifts/searchable_map.rb', line 72

def each(&block)
  return enum_for(:each) unless block_given?

  dfs(@tree, @prefix, &block)
  self
end

#entries ⇒ Array<Array>

Returns all [key, value] entries.

Returns:

  • (Array<Array>) —

    all [key, value] entries



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

def entries
  map { |entry| entry }
end

#fetch(key) ⇒ Object

Fetches the value at key, calling the block to create and store it if absent. Returns the existing or newly created value.

Raises:



144
145
146
147
148
149
150
151
 
# File 'lib/minifts/searchable_map.rb', line 144

def fetch(key)
  raise Error, "key must be a string" unless key.is_a?(String)

  @size = nil
  node = create_path(@tree, key)
  node[LEAF] = yield unless node.key?(LEAF)
  node[LEAF]
end

#fuzzy_get(key, max_edit_distance) ⇒ Object

Returns a Hash mapping each matching key to a [value, edit_distance] pair, for every key within max_edit_distance (Levenshtein) of key.



96
97
98
 
# File 'lib/minifts/searchable_map.rb', line 96

def fuzzy_get(key, max_edit_distance)
  fuzzy_search(@tree, key, max_edit_distance)
end

#get(key) ⇒ Object?

Returns the value at key, or nil if absent.

Returns:

  • (Object, nil) —

    the value at key, or nil if absent



101
102
103
104
 
# File 'lib/minifts/searchable_map.rb', line 101

def get(key)
  node = lookup(@tree, key)
  node.nil? ? nil : node[LEAF]
end

#has?(key) ⇒ Boolean

Returns whether key is present.

Returns:

  • (Boolean) —

    whether key is present



107
108
109
110
 
# File 'lib/minifts/searchable_map.rb', line 107

def has?(key)
  node = lookup(@tree, key)
  !node.nil? && node.key?(LEAF)
end

#keys ⇒ Array<String>

Returns all keys.

Returns:

  • (Array<String>) —

    all keys



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

def keys
  map { |entry| entry[0] }
end

#set(key, value) ⇒ Object

Sets key to value. Returns self, to allow chaining.

Raises:



113
114
115
116
117
118
119
120
 
# File 'lib/minifts/searchable_map.rb', line 113

def set(key, value)
  raise Error, "key must be a string" unless key.is_a?(String)

  @size = nil
  node = create_path(@tree, key)
  node[LEAF] = value
  self
end

#size ⇒ Integer

Returns the number of entries.

Returns:

  • (Integer) —

    the number of entries



123
124
125
126
127
128
129
 
# File 'lib/minifts/searchable_map.rb', line 123

def size
  return @size unless @size.nil?

  @size = 0
  each { @size += 1 }
  @size
end

#update(key) ⇒ Object

Updates the value at key using the given block, which receives the current value (or nil). Returns self.

Raises:



133
134
135
136
137
138
139
140
 
# File 'lib/minifts/searchable_map.rb', line 133

def update(key)
  raise Error, "key must be a string" unless key.is_a?(String)

  @size = nil
  node = create_path(@tree, key)
  node[LEAF] = yield(node[LEAF])
  self
end

#values ⇒ Array

Returns all values.

Returns:

  • (Array) —

    all values



90
91
92
 
# File 'lib/minifts/searchable_map.rb', line 90

def values
  map { |entry| entry[1] }
end