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

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

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

- (Object) key (readonly)

Returns the value of attribute key



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

def key
  @key
end

- (Object) value (readonly)

Returns the value of attribute value



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

def value
  @value
end

Instance Method Details

- (Object) children 



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

def children
  @children.compact
end

- (Object) clear 



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

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

- (Object) each {|@value| ... }

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

- (Boolean) empty?

Returns:

  • (Boolean) 


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

def empty?
  self.size == 0
end

- (Object) find(key) 



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

- (Object) insert(key, value) 



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

- (Object) inspect 



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

- (Object) size 



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

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