### Home Classes Methods

### In Files

- lib/taskjuggler/TernarySearchTree.rb

### Parent

Object

### Methods

- ::new
- #<<
- #[]
- #balance!
- #balanced
- #collect
- #find
- #insert
- #insertList
- #inspect
- #length
- #maxDepth
- #to_a

### Files

- CHANGELOG
- COPYING
- README.rdoc

### Class/Module Index

Quicksearch

- TaskJuggler
- TaskJuggler::Account
- TaskJuggler::AccountAttribute
- TaskJuggler::AccountCredit
- TaskJuggler::AccountCreditListAttribute
- TaskJuggler::AccountListRE
- TaskJuggler::AccountScenario
- TaskJuggler::AlertLevelDefinition
- TaskJuggler::AlertLevelDefinitions
- TaskJuggler::Allocation
- TaskJuggler::AllocationAttribute
- TaskJuggler::AttributeBase
- TaskJuggler::AttributeDefinition
- TaskJuggler::AttributeOverwrite
- TaskJuggler::BatchProcessor
- TaskJuggler::Booking
- TaskJuggler::BookingListAttribute
- TaskJuggler::BooleanAttribute
- TaskJuggler::CSVFile
- TaskJuggler::CellSettingPattern
- TaskJuggler::CellSettingPatternList
- TaskJuggler::Charge
- TaskJuggler::ChargeListAttribute
- TaskJuggler::ChargeSet
- TaskJuggler::ChargeSetListAttribute
- TaskJuggler::ChartPlotter
- TaskJuggler::ChartPlotterError
- TaskJuggler::CollisionDetector
- TaskJuggler::ColumnListAttribute
- TaskJuggler::ColumnTable
- TaskJuggler::Daemon
- TaskJuggler::DaemonConnector
- TaskJuggler::DaemonConnectorMixin
- TaskJuggler::DataCache
- TaskJuggler::DataCacheEntry
- TaskJuggler::DateAttribute
- TaskJuggler::DefinitionListAttribute
- TaskJuggler::DependencyListAttribute
- TaskJuggler::DurationAttribute
- TaskJuggler::ExportRE
- TaskJuggler::FileList
- TaskJuggler::FileRecord
- TaskJuggler::FixnumAttribute
- TaskJuggler::FlagListAttribute
- TaskJuggler::FloatAttribute
- TaskJuggler::FormatListAttribute
- TaskJuggler::GanttChart
- TaskJuggler::GanttContainer
- TaskJuggler::GanttHeader
- TaskJuggler::GanttHeaderScaleItem
- TaskJuggler::GanttLine
- TaskJuggler::GanttLoadStack
- TaskJuggler::GanttMilestone
- TaskJuggler::GanttRouter
- TaskJuggler::GanttTaskBar
- TaskJuggler::HTMLDocument
- TaskJuggler::HTMLElements
- TaskJuggler::HTMLGraphics
- TaskJuggler::ICalReport
- TaskJuggler::ICalendar
- TaskJuggler::ICalendar::Component
- TaskJuggler::ICalendar::Event
- TaskJuggler::ICalendar::Journal
- TaskJuggler::ICalendar::Person
- TaskJuggler::ICalendar::Todo
- TaskJuggler::Interval
- TaskJuggler::IntervalList
- TaskJuggler::JobInfo
- TaskJuggler::Journal
- TaskJuggler::JournalEntry
- TaskJuggler::JournalEntryList
- TaskJuggler::JournalSortListAttribute
- TaskJuggler::KateSyntax
- TaskJuggler::KeywordArray
- TaskJuggler::KeywordDocumentation
- TaskJuggler::Leave
- TaskJuggler::LeaveAllowance
- TaskJuggler::LeaveAllowanceList
- TaskJuggler::LeaveAllowanceListAttribute
- TaskJuggler::LeaveList
- TaskJuggler::LeaveListAttribute
- TaskJuggler::Limits
- TaskJuggler::Limits::Limit
- TaskJuggler::LimitsAttribute
- TaskJuggler::ListAttributeBase
- TaskJuggler::Log
- TaskJuggler::LogicalAttribute
- TaskJuggler::LogicalExpression
- TaskJuggler::LogicalExpressionAttribute
- TaskJuggler::LogicalExpressionListAttribute
- TaskJuggler::LogicalFlag
- TaskJuggler::LogicalFunction
- TaskJuggler::LogicalOperation
- TaskJuggler::ManagerResponsibilities
- TaskJuggler::ManagerStatusRecord
- TaskJuggler::Message
- TaskJuggler::MessageHandler
- TaskJuggler::MessageHandlerInstance
- TaskJuggler::MspXmlRE
- TaskJuggler::Navigator
- TaskJuggler::NavigatorElement
- TaskJuggler::NikuProject
- TaskJuggler::NikuReport
- TaskJuggler::NikuResource
- TaskJuggler::NodeListAttribute
- TaskJuggler::PTNProxy
- TaskJuggler::Painter
- TaskJuggler::Painter::Circle
- TaskJuggler::Painter::Color
- TaskJuggler::Painter::Element
- TaskJuggler::Painter::Ellipse
- TaskJuggler::Painter::FontMetrics
- TaskJuggler::Painter::FontMetricsData
- TaskJuggler::Painter::Group
- TaskJuggler::Painter::Line
- TaskJuggler::Painter::Points
- TaskJuggler::Painter::PolyLine
- TaskJuggler::Painter::Primitives
- TaskJuggler::Painter::Rect
- TaskJuggler::Painter::SVGSupport
- TaskJuggler::Painter::Text
- TaskJuggler::PlaceHolderCell
- TaskJuggler::ProcessIntercom
- TaskJuggler::ProcessIntercomIface
- TaskJuggler::Project
- TaskJuggler::ProjectBroker
- TaskJuggler::ProjectBrokerIface
- TaskJuggler::ProjectFileParser
- TaskJuggler::ProjectFileScanner
- TaskJuggler::ProjectRecord
- TaskJuggler::ProjectServer
- TaskJuggler::ProjectServerIface
- TaskJuggler::PropertyAttribute
- TaskJuggler::PropertyList
- TaskJuggler::PropertySet
- TaskJuggler::PropertyTreeNode
- TaskJuggler::Query
- TaskJuggler::RTFHandlers
- TaskJuggler::RTFNavigator
- TaskJuggler::RTFQuery
- TaskJuggler::RTFReport
- TaskJuggler::RTFReportLink
- TaskJuggler::RTFWithQuerySupport
- TaskJuggler::RealFormat
- TaskJuggler::RealFormatAttribute
- TaskJuggler::ReferenceAttribute
- TaskJuggler::Report
- TaskJuggler::ReportBase
- TaskJuggler::ReportContext
- TaskJuggler::ReportScenario
- TaskJuggler::ReportServer
- TaskJuggler::ReportServerIface
- TaskJuggler::ReportServerRecord
- TaskJuggler::ReportServlet
- TaskJuggler::ReportTable
- TaskJuggler::ReportTableCell
- TaskJuggler::ReportTableColumn
- TaskJuggler::ReportTableLegend
- TaskJuggler::ReportTableLine
- TaskJuggler::Resource
- TaskJuggler::ResourceListAttribute
- TaskJuggler::ResourceListRE
- TaskJuggler::ResourceScenario
- TaskJuggler::RichText
- TaskJuggler::RichTextAttribute
- TaskJuggler::RichTextDocument
- TaskJuggler::RichTextElement
- TaskJuggler::RichTextFunctionExample
- TaskJuggler::RichTextFunctionHandler
- TaskJuggler::RichTextImage
- TaskJuggler::RichTextIntermediate
- TaskJuggler::RichTextParser
- TaskJuggler::RichTextScanner
- TaskJuggler::RichTextSnip
- TaskJuggler::RichTextSyntaxRules
- TaskJuggler::Scenario
- TaskJuggler::ScenarioData
- TaskJuggler::ScenarioListAttribute
- TaskJuggler::Scoreboard
- TaskJuggler::ScoreboardInterval
- TaskJuggler::SheetHandlerBase
- TaskJuggler::SheetReceiver
- TaskJuggler::SheetSender
- TaskJuggler::Shift
- TaskJuggler::ShiftAssignment
- TaskJuggler::ShiftAssignments
- TaskJuggler::ShiftAssignmentsAttribute
- TaskJuggler::ShiftScenario
- TaskJuggler::SimpleQueryExpander
- TaskJuggler::SortListAttribute
- TaskJuggler::StatusSheetReceiver
- TaskJuggler::StatusSheetReport
- TaskJuggler::StatusSheetSender
- TaskJuggler::StdIoWrapper
- TaskJuggler::StringAttribute
- TaskJuggler::SymbolAttribute
- TaskJuggler::SymbolListAttribute
- TaskJuggler::SyntaxReference
- TaskJuggler::TOCEntry
- TaskJuggler::TSResourceRecord
- TaskJuggler::TSTaskRecord
- TaskJuggler::TableColumnDefinition
- TaskJuggler::TableColumnSorter
- TaskJuggler::TableOfContents
- TaskJuggler::TableReport
- TaskJuggler::TableReportColumn
- TaskJuggler::TagFile
- TaskJuggler::TagFile::TagFileEntry
- TaskJuggler::Task
- TaskJuggler::TaskDepListAttribute
- TaskJuggler::TaskDependency
- TaskJuggler::TaskListAttribute
- TaskJuggler::TaskListRE
- TaskJuggler::TaskScenario
- TaskJuggler::TernarySearchTree
- TaskJuggler::TextFormatter
- TaskJuggler::TextParser
- TaskJuggler::TextParser::Macro
- TaskJuggler::TextParser::MacroTable
- TaskJuggler::TextParser::Pattern
- TaskJuggler::TextParser::Rule
- TaskJuggler::TextParser::Scanner
- TaskJuggler::TextParser::Scanner::BufferStreamHandle
- TaskJuggler::TextParser::Scanner::FileStreamHandle
- TaskJuggler::TextParser::Scanner::MacroStackEntry
- TaskJuggler::TextParser::Scanner::StreamHandle
- TaskJuggler::TextParser::SourceFileInfo
- TaskJuggler::TextParser::StackElement
- TaskJuggler::TextParser::State
- TaskJuggler::TextParser::StateTransition
- TaskJuggler::TextParser::TextParserResultArray
- TaskJuggler::TextParser::TokenDoc
- TaskJuggler::TextReport
- TaskJuggler::TimeInterval
- TaskJuggler::TimeIntervalListAttribute
- TaskJuggler::TimeSheet
- TaskJuggler::TimeSheetReceiver
- TaskJuggler::TimeSheetRecord
- TaskJuggler::TimeSheetReport
- TaskJuggler::TimeSheetSender
- TaskJuggler::TimeSheetSummary
- TaskJuggler::TimeSheets
- TaskJuggler::Tj3
- TaskJuggler::Tj3AppBase
- TaskJuggler::Tj3Client
- TaskJuggler::Tj3Daemon
- TaskJuggler::Tj3Man
- TaskJuggler::Tj3SheetAppBase
- TaskJuggler::Tj3SsReceiver
- TaskJuggler::Tj3SsSender
- TaskJuggler::Tj3TsReceiver
- TaskJuggler::Tj3TsSender
- TaskJuggler::Tj3TsSummary
- TaskJuggler::Tj3WebD
- TaskJuggler::TjException
- TaskJuggler::TjRuntimeError
- TaskJuggler::TjTime
- TaskJuggler::TjpExample
- TaskJuggler::TjpExportRE
- TaskJuggler::TjpSyntaxRules
- TaskJuggler::TraceReport
- TaskJuggler::URLParameter
- TaskJuggler::UserManual
- TaskJuggler::VimSyntax
- TaskJuggler::WebServer
- TaskJuggler::WelcomePage
- TaskJuggler::WorkingHours
- TaskJuggler::WorkingHoursAttribute
- TaskJuggler::XMLBlob
- TaskJuggler::XMLComment
- TaskJuggler::XMLDocument
- TaskJuggler::XMLElement
- TaskJuggler::XMLNamedText
- TaskJuggler::XMLText
- Diff
- Diff::Hunk
- AppConfig
- Diffable
- DiffableString
- Object
- RuntimeConfig
- String

No matching classes.

# 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 25
    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) click to toggle source
Alias for: insert
[](str, partialMatch = false, index = 0) click to toggle source
Alias for: find
balance!() click to toggle source

Balance the tree for more effective data retrieval.

    # File lib/taskjuggler/TernarySearchTree.rb, line 144
    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 151
    def balanced
      TernarySearchTree.new(to_a)
    end

collect(str = nil, &block) click to toggle source

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

    # File lib/taskjuggler/TernarySearchTree.rb, line 125
    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 75
    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 38
    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 67
    def insertList(list)
      list.each { |val| insert(val) }
    end

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

    # File lib/taskjuggler/TernarySearchTree.rb, line 155
    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 101
    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 113
    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 139
    def to_a
      collect{ |x| x}
    end

[Validate]

Generated with the Darkfish Rdoc Generator 2.