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 = nil, 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 = nil, 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

#children ⇒ Object 



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

def children
  @children.compact
end

#clear ⇒ Object 



17
18
19
20
 
# File 'lib/gitrb/trie.rb', line 17

def clear
  @key = @value = nil
  @children = []
end

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

Yields:



26
27
28
29
 
# File 'lib/gitrb/trie.rb', line 26

def each(&block)
  yield(@value) if @value
  children.each {|child| child.each(&block) }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


22
23
24
 
# File 'lib/gitrb/trie.rb', line 22

def empty?
  self.size == 0
end

#find(key) ⇒ Object 



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

def find(key)
  if @key
    if @key.index(key) == 0
      self
    elsif key.index(@key) == 0
      child = @children[index(key)]
      child ? child.find(key) : Trie.new
    else
      Trie.new
    end
  else
    self
  end
end

#insert(key, value) ⇒ Object 



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/gitrb/trie.rb', line 50

def insert(key, value)
  if !@key
    @key = key
    @value = value
  elsif @key == key
    @value = value
  elsif @key.index(key) == 0
    child = Trie.new(@key, @value, @children)
    @children = []
    @children[@key[key.length].ord] = child
    @key = key
    @value = value
  elsif key.index(@key) == 0
    i = index(key)
    if @children[i]
      @children[i].insert(key, value)
    else
      @children[i] = Trie.new(key, value)
    end
  else
    n = 0
    n += 1 while key[n] == @key[n]

    child1 = Trie.new(@key, @value, @children)
    child2 = Trie.new(key, value)

    @value = nil
    @key = @key[0...n]
    @children = []
    @children[index(child1.key)] = child1
    @children[index(child2.key)] = child2
  end
end

#inspect ⇒ Object 



84
85
86
 
# File 'lib/gitrb/trie.rb', line 84

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

#size ⇒ Object 



31
32
33
 
# File 'lib/gitrb/trie.rb', line 31

def size
  children.inject(@value ? 1 : 0) {|sum, child| sum + child.size }
end