Class: ArrayTrie::PrefixTrie

Inherits:
Object
  • Object
show all
Defined in:
lib/array_trie/prefix_trie.rb

Overview

A trie-like, prefix-tree data structure that maps arbitrary keys to values, provided that the keys may be transformed to and from arrays, as each instance uses an underlying ArrayTrie instance for storage.

If you only care about trie membership, just map your values to ‘true`. If your trie keys are already arrays, you can use ArrayTrie directly for improved performance.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(to_a, from_a, trie = ArrayTrie.new) ⇒ PrefixTrie

Create a new Trie

Parameters:

  • to_a (#call) —

    A callable that given a key, returns that key as an array.

  • from_a (#call) —

    Inverse of to_a. A callable that given an array, returns the key form of that array.

  • trie (ArrayTrie) (defaults to: ArrayTrie.new) —

    (ArrayTrie.new) Underlying trie to use for storage.



56
57
58
59
60
 
# File 'lib/array_trie/prefix_trie.rb', line 56

def initialize(to_a, from_a, trie = ArrayTrie.new)
  @to_a = to_a
  @from_a = from_a
  @trie = trie
end

Class Method Details

.of_arrays ⇒ PrefixTrie

Create a new trie for mapping arrays to values.

Returns:



42
43
44
45
46
47
 
# File 'lib/array_trie/prefix_trie.rb', line 42

def self.of_arrays
  new(
    proc { |x| x },
    proc { |x| x }
  )
end

.of_paths ⇒ PrefixTrie

Create a new Trie for mapping paths to values. This could be useful for storing a large amount of paths-to-data mappings, and querying the trie based on path prefix.

Returns:



17
18
19
 
# File 'lib/array_trie/prefix_trie.rb', line 17

def self.of_paths
  of_strings_split_by('/')
end

.of_strings ⇒ PrefixTrie

Create a new trie for mapping strings to values. This could be useful

Returns:



24
25
26
 
# File 'lib/array_trie/prefix_trie.rb', line 24

def self.of_strings
  of_strings_split_by('')
end

.of_strings_split_by(delim) ⇒ PrefixTrie

Create a trie for mapping delimited strings to values. String keys will be split by the delimiter for storage.

Returns:



32
33
34
35
36
37
 
# File 'lib/array_trie/prefix_trie.rb', line 32

def self.of_strings_split_by(delim)
  new(
    proc { |str| str.split(delim) },
    proc { |parts| parts.join(delim) }
  )
end

Instance Method Details

#[](key) ⇒ Object 



62
63
64
 
# File 'lib/array_trie/prefix_trie.rb', line 62

def [](key)
  @trie[to_a(key)]
end

#[]=(key, value) ⇒ Object 



66
67
68
 
# File 'lib/array_trie/prefix_trie.rb', line 66

def []=(key, value)
  @trie[to_a(key)] = value
end

#breadth_first ⇒ Object 



98
99
100
101
102
 
# File 'lib/array_trie/prefix_trie.rb', line 98

def breadth_first
  enum = transform_enumerator(@trie.breadth_first)
  return enum unless block_given?
  enum.each { |path, value| yield(path, value) }
end

#count ⇒ Object 



104
105
106
 
# File 'lib/array_trie/prefix_trie.rb', line 104

def count
  @trie.count
end

#count_prefix(key) ⇒ Object 



88
89
90
 
# File 'lib/array_trie/prefix_trie.rb', line 88

def count_prefix(key)
  @trie.count_prefix(to_a key)
end

#depth_first ⇒ Object 



92
93
94
95
96
 
# File 'lib/array_trie/prefix_trie.rb', line 92

def depth_first
  enum = transform_enumerator(@trie.depth_first)
  return enum unless block_given?
  enum.each { |path, value| yield(path, value) }
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


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

def include?(key)
  @trie.include?(to_a key)
end

#include_prefix?(key) ⇒ Boolean

Returns:

  • (Boolean) 


84
85
86
 
# File 'lib/array_trie/prefix_trie.rb', line 84

def include_prefix?(key)
  @trie.include_prefix?(to_a key)
end

#insert_subtrie(key, subtrie) ⇒ Object 



70
71
72
 
# File 'lib/array_trie/prefix_trie.rb', line 70

def insert_subtrie(key, subtrie)
  @trie.insert_subtrie(to_a(key), subtrie.trie)
end

#subtrie(key) ⇒ Object 



74
75
76
77
78
 
# File 'lib/array_trie/prefix_trie.rb', line 74

def subtrie(key)
  lower_subtrie = @trie.subtrie(to_a(key))
  return nil unless lower_subtrie
  self.class.new(@to_a, @from_a, lower_subtrie)
end