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.



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

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.



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

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

#balanced ⇒ Object

Return a balanced version of the tree.



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

def balanced
  TernarySearchTree.new(to_a)
end

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

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



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

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.



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

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.



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

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.



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

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

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



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

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.



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

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.



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

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.



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

def to_a
  collect{ |x| x}
end