Class: DS::Trie

Inherits:
Tree
  • Object
show all
Defined in:
lib/ds/trees/trie.rb,
lib/ds/trees/trie/node.rb

Overview

Trie dictionary data structure

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Attributes inherited from Tree

#children, #data, #parent

Instance Method Summary collapse

Methods inherited from Tree

#<<, #get_leaves, h, #height, #izometric?, #leaf?, #leaf_count, #levels, #lowest_height, #mirror!, #sibblings, #to_a, #width

Constructor Details

#initialize(value = nil, alphabet = nil) ⇒ Trie

Returns a new instance of Trie.



6
7
8
9
 
# File 'lib/ds/trees/trie.rb', line 6

def initialize(value = nil, alphabet = nil)
  @root = Node.new(value)
  self.alphabet = (alphabet || %w(- a b c d e f g h i j k l m n o p q r s t u v w x y z))
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



4
5
6
 
# File 'lib/ds/trees/trie.rb', line 4

def root
  @root
end

Instance Method Details

#[](k) ⇒ Object 



39
40
41
 
# File 'lib/ds/trees/trie.rb', line 39

def [](k)
  find(k)
end

#[]=(k, v) ⇒ Object 



29
30
31
 
# File 'lib/ds/trees/trie.rb', line 29

def []=(k, v)
  insert(k, v)
end

#alphabet ⇒ Object 



16
17
18
 
# File 'lib/ds/trees/trie.rb', line 16

def alphabet
  @alphabet.keys
end

#alphabet=(arr) ⇒ Object 



11
12
13
14
 
# File 'lib/ds/trees/trie.rb', line 11

def alphabet=(arr)
  @alphabet = {}
  arr.each_with_index { |c, i| @alphabet[c] = i }
end

#delete(s) ⇒ Object 



43
44
45
46
 
# File 'lib/ds/trees/trie.rb', line 43

def delete(s)
  letters = s.scan(/./)
  root.delete(letters, self)
end

#each(&block) ⇒ Object 



48
49
50
 
# File 'lib/ds/trees/trie.rb', line 48

def each(&block)
  visit(root, '', &block)
end

#find(s) ⇒ Object 



33
34
35
36
37
 
# File 'lib/ds/trees/trie.rb', line 33

def find(s)
  letters = get_letters(s)
  node = root.get(letters, self)
  node.data if node
end

#insert(s, value = true) ⇒ Object 



24
25
26
27
 
# File 'lib/ds/trees/trie.rb', line 24

def insert(s, value = true)
  letters = get_letters(s)
  root.put(letters, value, self)
end

#key(chr) ⇒ Object 



20
21
22
 
# File 'lib/ds/trees/trie.rb', line 20

def key(chr)
  @alphabet[chr]
end

#to_h ⇒ Object 



73
74
75
76
77
 
# File 'lib/ds/trees/trie.rb', line 73

def to_h
  h = {}
  each { |k, v| h[k] = v }
  h
end

#visit(node, prefix) {|prefix, node.data| ... } ⇒ Object

Yields:

  • (prefix, node.data) 


52
53
54
55
56
57
 
# File 'lib/ds/trees/trie.rb', line 52

def visit(node, prefix, &block)
  yield prefix, node.data if node.data
  node.children.each_with_index do |n, i|
    visit(n, prefix + alphabet[i], &block) if n
  end
end

#with_prefix(prefix, &block) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/ds/trees/trie.rb', line 59

def with_prefix(prefix, &block)
  letters = get_letters(prefix)
  node = root.get(letters, self)
  if block_given?
    return nil unless node
    visit(node, prefix, &block)
  else
    arr = []
    return arr unless node
    visit(node, prefix) { |n| arr << n }
    arr
  end
end