| Class | TaskJuggler::TernarySearchTree |
| In: |
lib/taskjuggler/TernarySearchTree.rb
|
| Parent: | Object |
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.
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.
# 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
Balance the tree for more effective data retrieval.
# File lib/taskjuggler/TernarySearchTree.rb, line 146 def balance! list = sortForBalancedTree(to_a) clear list.each { |x| insert(x) } end
Invokes block for each element and returns the results as an Array.
# 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
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.
# 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
Stores str in the tree. index is for internal use only.
# 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
Insert the elements of list into the tree.
# File lib/taskjuggler/TernarySearchTree.rb, line 69 def insertList(list) list.each { |val| insert(val) } end
# 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
Returns the number of elements in the tree.
# 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
Return the maximum depth of the tree.
# 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