class Location

This class keeps track of the next value to check in a suffix tree

If we are located at a node, there are several options for the next value which are in the map of value-to-node.

If we are not on a node, there is an incoming edge with at least one value so we store the offset of that value in the data source

The location can never be onNode at a leaf, but can be at a leaf with an incomingEdgeOffset at or past the leaf's incomingEdgeStartOffset

Attributes

incomingEdgeOffset[R]
node[R]
onNode[R]

Public Class Methods

new(node, onNode = true, incomingEdgeOffset = Node::UNSPECIFIED_OFFSET) click to toggle source

optional parameters needed for testing

# File lib/support/location.rb, line 21
def initialize(node, onNode = true, incomingEdgeOffset = Node::UNSPECIFIED_OFFSET)
  @node = node
  @onNode = onNode
  @incomingEdgeOffset = incomingEdgeOffset
end

Public Instance Methods

depth() click to toggle source

get the depth of the location

Requires nodes with “valueDepth” property (nodeFactory with :valueDepth=>true, followed by traversal with ValueDepthVisitor)

# File lib/support/location.rb, line 151
def depth
  if (@onNode) then
    return @node.valueDepth
  else
    return @node.parent.valueDepth + @incomingEdgeOffset - @node.incomingEdgeStartOffset
  end
end
jumpToNode(node) click to toggle source
# File lib/support/location.rb, line 159
def jumpToNode(node)
  @node = node
  @onNode = true
  @incomingEdgeOffset = Node::UNSPECIFIED_OFFSET
end
matchDataSource(dataSource, matchThis) click to toggle source
# File lib/support/location.rb, line 122
def matchDataSource(dataSource, matchThis)
  matchThis.each_with_index do |value, index|
    if (!self.matchValue(dataSource, value)) then
      break
    end
  end
  self
end
matchValue(dataSource, value) click to toggle source
# File lib/support/location.rb, line 131
def matchValue(dataSource, value)
  if (@onNode) then
    if (@node.children.has_key?(value)) then
      self.traverseDownChildValue(value)
      return true
    end
  else
    if (dataSource.valueAt(@incomingEdgeOffset) == value) then
      self.traverseDownEdgeValue()
      return true
    end
  end
  return false
end
traverseDownChildValue(value) click to toggle source

From the current Node with a given child value, traverse past that value

# File lib/support/location.rb, line 50
def traverseDownChildValue(value)
  @node = @node.children[value]
  if (@node.incomingEdgeLength == 1) then
    @onNode = true
    @incomingEdgeOffset = Node::UNSPECIFIED_OFFSET
  else
    @onNode = false
    @incomingEdgeOffset = @node.incomingEdgeStartOffset + 1
  end
end
traverseDownEdgeValue() click to toggle source
# File lib/support/location.rb, line 115
def traverseDownEdgeValue()
  @incomingEdgeOffset += 1
  if (!@node.isLeaf && (@incomingEdgeOffset > @node.incomingEdgeEndOffset)) then
    @onNode = true
  end
end
traverseSkipCountDown(dataSource, startOffset, endOffset) click to toggle source

From the current location on a Node, traverse down assuming the characters on the path exist, which allows skip/count method to be used to move down.

# File lib/support/location.rb, line 90
def traverseSkipCountDown(dataSource, startOffset, endOffset)
  done = false
  while (!done) do
    @node = @node.children[dataSource.valueAt(startOffset)]
    if (@node.isLeaf) then
      @onNode = false
      @incomingEdgeOffset = @node.incomingEdgeStartOffset + (endOffset - startOffset + 1)
    else
      incomingEdgeLength = @node.incomingEdgeLength
      startOffset += incomingEdgeLength
      remainingLength = endOffset - startOffset + 1
      @onNode = (remainingLength == 0)
      # if remaining length is negative, it means we have past where we need to be
      # by that amount, incoming edge offset is set to end reduced by that amount
      if (remainingLength < 0) then
        @incomingEdgeOffset = @node.incomingEdgeEndOffset + remainingLength + 1
      else
        @incomingEdgeOffset = @node.incomingEdgeStartOffset
      end
    end

    done = (@node.isLeaf || (remainingLength <= 0))
  end
end
traverseToNextSuffix(dataSource) click to toggle source

From the current location that does NOT have a suffix link, either because it is on an edge or because it is on a newly created internal node, traverse to the next suffix

Returns true if it actually traversed, otherwise false

# File lib/support/location.rb, line 68
def traverseToNextSuffix(dataSource)
  if (@node.isRoot) then
    return false
  end
  upStart, upEnd = self.traverseUp
  if (@node.isRoot) then
    if (upStart < upEnd) then
      self.traverseSkipCountDown(dataSource, upStart + 1, upEnd)
    else
      @onNode = true
    end
  else
    @node = @node.suffixLink
    self.traverseSkipCountDown(dataSource, upStart, upEnd)
  end
  return true
end
traverseUp() click to toggle source

traverse to parent, return the range of characters covered

# File lib/support/location.rb, line 30
def traverseUp
  incomingEdgeStart = @node.incomingEdgeStartOffset
  if (@onNode) then
    incomingEdgeEnd = @node.incomingEdgeEndOffset
  else
    incomingEdgeEnd = @incomingEdgeOffset - 1
  end
  @node = @node.parent
  @incomingEdgeOffset = Node::UNSPECIFIED_OFFSET
  @onNode = true
  return incomingEdgeStart, incomingEdgeEnd
end