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



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

#keyObject (readonly)

Returns the value of attribute key



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

def key
  @key
end

#valueObject (readonly)

Returns the value of attribute value



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

def value
  @value
end

Instance Method Details

#childrenObject



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

def children
  @children.compact
end

#clearObject



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

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

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

Yields:

  • (@value)


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



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

#inspectObject



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

#sizeObject



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

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