Class: Location

Inherits:
Object
  • Object
show all
Defined in:
lib/support/location.rb

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(node, onNode = true, incomingEdgeOffset = Node::UNSPECIFIED_OFFSET) ⇒ Location

optional parameters needed for testing



21
22
23
24
25
 
# File 'lib/support/location.rb', line 21

def initialize(node, onNode = true, incomingEdgeOffset = Node::UNSPECIFIED_OFFSET)
  @node = node
  @onNode = onNode
  @incomingEdgeOffset = incomingEdgeOffset
end

Instance Attribute Details

#incomingEdgeOffset ⇒ Object (readonly)

Returns the value of attribute incomingEdgeOffset.



16
17
18
 
# File 'lib/support/location.rb', line 16

def incomingEdgeOffset
  @incomingEdgeOffset
end

#node ⇒ Object (readonly)

Returns the value of attribute node.



16
17
18
 
# File 'lib/support/location.rb', line 16

def node
  @node
end

#onNode ⇒ Object (readonly)

Returns the value of attribute onNode.



16
17
18
 
# File 'lib/support/location.rb', line 16

def onNode
  @onNode
end

Instance Method Details

#depth ⇒ Object

get the depth of the location

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



151
152
153
154
155
156
157
 
# 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) ⇒ Object 



159
160
161
162
163
 
# File 'lib/support/location.rb', line 159

def jumpToNode(node)
  @node = node
  @onNode = true
  @incomingEdgeOffset = Node::UNSPECIFIED_OFFSET
end

#matchDataSource(dataSource, matchThis) ⇒ Object 



122
123
124
125
126
127
128
129
 
# 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) ⇒ Object 



131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# 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) ⇒ Object

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



50
51
52
53
54
55
56
57
58
59
 
# 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 ⇒ Object 



115
116
117
118
119
120
 
# 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) ⇒ Object

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.



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# 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

#traverseSuffixLink ⇒ Object 



43
44
45
 
# File 'lib/support/location.rb', line 43

def traverseSuffixLink
  self.jumpToNode(@node.suffixLink)
end

#traverseToNextSuffix(dataSource) ⇒ Object

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



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# 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 ⇒ Object

traverse to parent, return the range of characters covered



30
31
32
33
34
35
36
37
38
39
40
41
 
# 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