- # Path to the Leaf for `position`
- private fun node_at(position: Int): Path
- do
- assert position >= 0 and position <= length
- if position == length then
- var st = new List[PathElement]
- stack_to_end(root,st)
- if not st.is_empty then
- var lst = st.last
- var lf = lst.node.right
- if lf != null then
- return new Path(lf.as(Leaf), lf.length, st)
- else
- lf = lst.node.left
- return new Path(lf.as(Leaf), lf.length, st)
- end
- else
- return new Path(root.as(Leaf), length, st)
- end
- end
- return get_node_from(root, 0, position, new List[PathElement])
- end
-
- # Special case for when the required pos is length
- private fun stack_to_end(nod: RopeNode, st: List[PathElement])
- do
- if nod isa Leaf then return
- var n = nod.as(Concat)
- var r = n.right
- var ele = new PathElement(n)
- ele.right = true
- st.push(ele)
- if r != null then
- stack_to_end(r, st)
- end
- return
- end
-
- # Builds the path to Leaf at position `seek_pos`
- private fun get_node_from(node: RopeNode, curr_pos: Int, seek_pos: Int, stack: List[PathElement]): Path
- do
- assert curr_pos >= 0
- if node isa Leaf then return new Path(node, seek_pos - curr_pos, stack)
- node = node.as(Concat)
-
- if node.left != null then
- var next_pos = curr_pos + node.left.length
- stack.add(new PathElement(node))
- if next_pos > seek_pos then
- stack.last.left = true
- return get_node_from(node.left.as(not null), curr_pos, seek_pos, stack)
- end
- stack.last.right = true
- return get_node_from(node.right.as(not null), next_pos, seek_pos, stack)
- else
- var vis = new PathElement(node)
- vis.right = true
- stack.add(vis)
- return get_node_from(node.right.as(not null), curr_pos, seek_pos, stack)
- end
- end