Class: TaskJuggler::TernarySearchTree

Inherits:
Object
  • Object
show all
Defined in:
lib/taskjuggler/TernarySearchTree.rb

Overview

Classical ternary search tree implementation. It can store any list objects who’s elements are comparable. These are usually String or Array objects. Common elements (by value and index) are only stored once which makes it fairly efficient for large lists that have similar start sequences. It also provides a fast find method.

Instance Method Summary collapse

Constructor Details

#initialize(arg = nil) ⇒ TernarySearchTree

Create a new TernarySearchTree object. The optional arg can be an element to store in the new tree or a list of elements to store.



28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 28

def initialize(arg = nil)
  clear

  if arg.nil?
    return
  elsif arg.is_a?(Array)
    sortForBalancedTree(arg).each { |elem| insert(elem) }
  else
    insert(arg) if arg
  end
end

Instance Method Details

#balance! ⇒ Object

Balance the tree for more effective data retrieval.



147
148
149
150
151
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 147

def balance!
  list = sortForBalancedTree(to_a)
  clear
  list.each { |x| insert(x) }
end

#balanced ⇒ Object

Return a balanced version of the tree.



154
155
156
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 154

def balanced
  TernarySearchTree.new(to_a)
end

#collect(str = nil, &block) ⇒ Object

Invokes block for each element and returns the results as an Array.



128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 128

def collect(str = nil, &block)
  result = []

  result += @smaller.collect(str, &block) if @smaller
  # The strange looking (+'' << val) is for Ruby 1.8 compatibility.
  newStr = str.nil? ? (+'' << @value) : str + (+'' << @value)
  result << yield(newStr) if @last
  result += @equal.collect(newStr, &block) if @equal
  result += @larger.collect(str, &block) if @larger

  result
end

#find(str, partialMatch = false, index = 0) ⇒ Object Also known as: []

if str is stored in the tree it returns str. If partialMatch is true, it returns all items that start with str. index is for internal use only. If nothing is found it returns either nil or an empty list.



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 78

def find(str, partialMatch = false, index = 0)
  return nil if str.nil? || index > (maxIdx = str.length - 1)

  if str[index] < @value
    return @smaller.find(str, partialMatch, index) if @smaller
  elsif str[index] > @value
    return @larger.find(str, partialMatch, index) if @larger
  else
    if index == maxIdx
      # We've reached the end of the search pattern.
      if partialMatch
        # The strange looking (+'' << val) is for Ruby 1.8 compatibility.
        return collect { |v| str[0..-2] + (+'' << v) }
      else
        return str if @last
      end
    end

    return @equal.find(str, partialMatch, index + 1) if @equal
  end
  nil
end

#insert(str, index = 0) ⇒ Object Also known as: <<

Stores str in the tree. index is for internal use only.



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 41

def insert(str, index = 0)
  if str.nil? || str.empty?
    raise ArgumentError, "Cannot insert nil or empty lists"
  end
  if index > (maxIdx = str.length - 1) || index < 0
    raise ArgumentError, "index out of range [0..#{maxIdx}]"
  end

  @value = str[index] unless @value

  if str[index] < @value
    @smaller = TernarySearchTree.new unless @smaller
    @smaller.insert(str, index)
  elsif str[index] > @value
    @larger = TernarySearchTree.new unless @larger
    @larger.insert(str, index)
  else
    if index == maxIdx
      @last = true
    else
      @equal = TernarySearchTree.new unless @equal
      @equal.insert(str, index + 1)
    end
  end
end

#insertList(list) ⇒ Object

Insert the elements of list into the tree.



70
71
72
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 70

def insertList(list)
  list.each { |val| insert(val) }
end

#inspect(prefix = ' ', indent = 0) ⇒ Object 



158
159
160
161
162
163
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 158

def inspect(prefix = ' ', indent = 0)
  puts "#{' ' * indent}#{prefix} #{@value} #{@last ? '!' : ''}"
  @smaller.inspect('<', indent + 2) if @smaller
  @equal.inspect('=', indent + 2) if @equal
  @larger.inspect('>', indent + 2) if @larger
end

#length ⇒ Object

Returns the number of elements in the tree.



104
105
106
107
108
109
110
111
112
113
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 104

def length
  result = 0

  result += @smaller.length if @smaller
  result += 1 if @last
  result += @equal.length if @equal
  result += @larger.length if @larger

  result
end

#maxDepth(depth = 0) ⇒ Object

Return the maximum depth of the tree.



116
117
118
119
120
121
122
123
124
125
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 116

def maxDepth(depth = 0)
  depth += 1
  depths = []
  depths << @smaller.maxDepth(depth) if @smaller
  depths << @equal.maxDepth(depth) if @equal
  depths << @larger.maxDepth(depth) if @larger
  depths << depth if @last

  depths.max
end

#to_a ⇒ Object

Return an Array with all the elements stored in the tree.



142
143
144
 
# File 'lib/taskjuggler/TernarySearchTree.rb', line 142

def to_a
  collect{ |x| x}
end