class TaskJuggler::TernarySearchTree

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.

Public Class Methods

new(arg = nil) click to toggle source

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 26
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

Public Instance Methods

<<(str, index = 0)
Alias for: insert
[](str, partialMatch = false, index = 0)
Alias for: find
balance!() click to toggle source

Balance the tree for more effective data retrieval.

# File lib/taskjuggler/TernarySearchTree.rb, line 145
def balance!
  list = sortForBalancedTree(to_a)
  clear
  list.each { |x| insert(x) }
end
balanced() click to toggle source

Return a balanced version of the tree.

# File lib/taskjuggler/TernarySearchTree.rb, line 152
def balanced
  TernarySearchTree.new(to_a)
end
collect(str = nil) { |newStr| ... } click to toggle source

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

# File lib/taskjuggler/TernarySearchTree.rb, line 126
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) click to toggle source

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 76
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
Also aliased as: []
insert(str, index = 0) click to toggle source

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

# File lib/taskjuggler/TernarySearchTree.rb, line 39
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
Also aliased as: <<
insertList(list) click to toggle source

Insert the elements of list into the tree.

# File lib/taskjuggler/TernarySearchTree.rb, line 68
def insertList(list)
  list.each { |val| insert(val) }
end
inspect(prefix = ' ', indent = 0) click to toggle source
# File lib/taskjuggler/TernarySearchTree.rb, line 156
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() click to toggle source

Returns the number of elements in the tree.

# File lib/taskjuggler/TernarySearchTree.rb, line 102
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) click to toggle source

Return the maximum depth of the tree.

# File lib/taskjuggler/TernarySearchTree.rb, line 114
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() click to toggle source

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

# File lib/taskjuggler/TernarySearchTree.rb, line 140
def to_a
  collect{ |x| x}
end