Class: Gitrb::Trie

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/gitrb/trie.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key = '', value = nil, children = []) ⇒ Trie

Returns a new instance of Trie.



7
8
9
10
11
 
# File 'lib/gitrb/trie.rb', line 7

def initialize(key = '', value = nil, children = [])
  @key = key
  @value = value
  @children = children
end

Instance Attribute Details

#key ⇒ Object (readonly)

Returns the value of attribute key.



5
6
7
 
# File 'lib/gitrb/trie.rb', line 5

def key
  @key
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



5
6
7
 
# File 'lib/gitrb/trie.rb', line 5

def value
  @value
end

Instance Method Details

#clear ⇒ Object 



13
14
15
16
17
 
# File 'lib/gitrb/trie.rb', line 13

def clear
  @key = ''
  @value = nil
  @children.clear
end

#dup ⇒ Object 



57
58
59
 
# File 'lib/gitrb/trie.rb', line 57

def dup
  Trie.new(@key.dup, @value ? @value.dup : nil, @children.map {|c| c ? c.dup : nil })
end

#each {|@value| ... } ⇒ Object

Yields:



48
49
50
51
 
# File 'lib/gitrb/trie.rb', line 48

def each(&block)
  yield(@value) if !@key.empty?
  @children.compact.each {|c| c.each(&block) }
end

#find(key) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/gitrb/trie.rb', line 19

def find(key)
  if key.empty?
    self
  else
    child = @children[key[0].ord]
    if child && key[0...child.key.length] == child.key
      child.find(key[child.key.length..-1])
    else
      nil
    end
  end
end

#insert(key, value) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/gitrb/trie.rb', line 32

def insert(key, value)
  if key.empty?
    @value = value
    self
  else
    idx = key[0].ord
    child = @children[idx]
    if child
      child.split(key) if key[0...child.key.length] != child.key
      child.insert(key[child.key.length..-1], value)
    else
      @children[idx] = Trie.new(key, value)
    end
  end
end

#inspect ⇒ Object 



61
62
63
 
# File 'lib/gitrb/trie.rb', line 61

def inspect
  "#<Gitrb::Trie @key=#{@key.inspect}, @value=#{@value.inspect}, @children=#{@children.compact.inspect}>"
end

#split(key) ⇒ Object 



65
66
67
68
69
70
71
72
73
 
# File 'lib/gitrb/trie.rb', line 65

def split(key)
  prefix = 0
  prefix += 1 while key[prefix] == @key[prefix]
  child = Trie.new(@key[prefix..-1], @value, @children)
  @children = []
  @children[@key[prefix].ord] = child
  @key = @key[0...prefix]
  @value = nil
end

#values ⇒ Object 



53
54
55
 
# File 'lib/gitrb/trie.rb', line 53

def values
  to_a
end