Class: ArrayTrie

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

Overview

ArrayTrie is a trie-like, prefix-tree data structure that maps from arrays to values. This differs from a traditional trie, which maps strings to values.

ArrayTrie is implemented in terms of Ruby hashes, so members of your array keys must behave by Ruby’s hash contracts: ruby-doc.org/core-2.3.1/Hash.html#class-Hash-label-Hash+Keys

If you wish to construct a prefix tree with non-Array keys, please see PrefixTrie, which can map arbitrary keys to values, so long as your keys can be converted to and from arrays.

Defined Under Namespace

Classes: PrefixTrie

Constant Summary collapse

STOP =

This constant is part of a private API. You should avoid using this constant if possible, as it may be removed or be changed in the future.

Just a unique marker value. Using Class.new is better than using Object.new, because it makes sense when inspected.

Class.new
VERSION = 
"0.1.2"

Instance Method Summary collapse

Constructor Details

#initialize(root = {}) ⇒ ArrayTrie

Returns a new instance of ArrayTrie.



21
22
23
 
# File 'lib/array_trie.rb', line 21

def initialize(root = {})
  @root = root
end

Instance Method Details

#[](parts) ⇒ Any?

Retrieve a value for the given key

Parameters:

  • parts (Array)

Returns:

  • (Any) —

    the previously stored value

  • (nil) —

    if the given key was not found



30
31
32
33
34
 
# File 'lib/array_trie.rb', line 30

def [](parts)
  last_node, remaining = traverse(@root, parts)
  return nil unless remaining.empty?
  last_node[STOP]
end

#[]=(parts, value) ⇒ Object

Set a key to a value

Parameters:

  • parts (Array) —

    the key

  • value (Any) —

    the value



40
41
42
43
 
# File 'lib/array_trie.rb', line 40

def []=(parts, value)
  last_node, * = traverse(@root, parts, true)
  last_node[STOP] = value
end

#breadth_first ⇒ Enumerator

Returns a breadth-first enumerator.

Returns:

  • (Enumerator) —

    a breadth-first enumerator



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

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

#count ⇒ Integer

Count the number of key-value pairs in this trie.

Returns:

  • (Integer) 


111
112
113
 
# File 'lib/array_trie.rb', line 111

def count
  breadth_first.count
end

#count_prefix(parts) ⇒ Integer

Returns Number of keys under the given prefix.

Returns:

  • (Integer) —

    Number of keys under the given prefix



89
90
91
92
 
# File 'lib/array_trie.rb', line 89

def count_prefix(parts)
  trie = subtrie(parts)
  trie ? trie.count : 0
end

#depth_first ⇒ Enumerator

Returns a depth-first enumerator.

Returns:

  • (Enumerator) —

    a depth-first enumerator



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

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

#include?(parts) ⇒ Boolean

Returns true if this array is a key in this trie.

Parameters:

  • parts (Array)

Returns:

  • (Boolean) 


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

def include?(parts)
  last_node, remaining = traverse(@root, parts)
  return false unless remaining.empty?
  last_node.key?(STOP)
end

#include_prefix?(parts) ⇒ Boolean

Returns true if this array is a prefix of an array in this trie

Parameters:

  • parts (Array)

Returns:

  • (Boolean) 


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

def include_prefix?(parts)
  _, remaining = traverse(@root, parts)
  remaining.empty?
end

#insert_subtrie(parts, trie) ⇒ Object

insert a subtrie into this trie.

Parameters:

Returns:

  • self

Raises:

  • (ArgumentError) 


50
51
52
53
54
55
56
 
# File 'lib/array_trie.rb', line 50

def insert_subtrie(parts, trie)
  raise ArgumentError.new("trie must be a trie") unless trie.is_a? self.class
  raise ArgumentError.new("cannot insert a subtrie at the root") if parts.empty?
  parent, * = traverse(@root, parts[0...-1], true)
  parent[parts.last] = trie.root
  self
end

#subtrie(parts) ⇒ ArrayTrie

Retrieve a view into this trie at the given key. Underlying data storage is shared with the subtrie.

Parameters:

  • parts (Array)

Returns:



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

def subtrie(parts)
  last_node, remaining = traverse(@root, parts)
  return nil unless remaining.empty?
  self.class.new(last_node)
end