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

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 146
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 153
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 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) 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 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

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

Also aliased as: <<

insertList(list) click to toggle source

Insert the elements of list into the tree.

# File lib/taskjuggler/TernarySearchTree.rb, line 69
def insertList(list)
  list.each { |val| insert(val) }
end

inspect(prefix = ' ', indent = 0) click to toggle source

# 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() click to toggle source

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

maxDepth(depth = 0) click to toggle source

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

to_a() click to toggle source

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

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