Class: Gitrb::Trie

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

Overview

Trie data structure to store sha1s

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of Trie.



9
10
11
12
13
 
# File 'lib/gitrb/trie.rb', line 9

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.



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

def key
  @key
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



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

def value
  @value
end

Instance Method Details

#children ⇒ Object 



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

def children
  @children.compact
end

#clear ⇒ Object 



19
20
21
22
 
# File 'lib/gitrb/trie.rb', line 19

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

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

Yields:



28
29
30
31
 
# File 'lib/gitrb/trie.rb', line 28

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/gitrb/trie.rb', line 24

def empty?
  self.size == 0
end

#find(key) ⇒ Object 



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

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 



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
83
84
 
# File 'lib/gitrb/trie.rb', line 52

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 



86
87
88
 
# File 'lib/gitrb/trie.rb', line 86

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

#size ⇒ Object 



33
34
35
 
# File 'lib/gitrb/trie.rb', line 33

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