From 4dc13a4da6f68edc5cbca25ac34b05751e095eb4 Mon Sep 17 00:00:00 2001
From: Lucas Bajolet <r4pass@hotmail.com>
Date: Thu, 5 Jun 2014 10:43:00 -0400
Subject: [PATCH 1/1] lib/standard/ropes: Added backwards equivalents of
 previously defined iterators.

Signed-off-by: Lucas Bajolet <r4pass@hotmail.com>
---
 lib/standard/ropes.nit |  198 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 198 insertions(+)

diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit
index a2b010d..b1aad2e 100644
--- a/lib/standard/ropes.nit
+++ b/lib/standard/ropes.nit
@@ -126,6 +126,18 @@ abstract class Rope
 	# Iterator on the substrings, starting at position `from`, in forward order
 	fun substrings_from(from: Int): IndexedIterator[Text] do return new SubstringsIterator(self, from)
 
+	# Iterator on the nodes of the rope, in backwards postfix order
+	private fun reverse_postfix(from: Int): ReversePostfix do return new ReversePostfix.from(self, from)
+
+	# Iterator on the leaves of the rope, backwards order
+	private fun reverse_leaves(from: Int): ReverseLeavesIterator do return new ReverseLeavesIterator(self,from)
+
+	# Iterator on the substrings, in reverse order
+	fun reverse_substrings: IndexedIterator[Text] do return new ReverseSubstringsIterator(self, length-1)
+
+	# Iterator on the substrings, in reverse order, starting iteration at position `from`
+	fun reverse_substrings_from(from: Int): IndexedIterator[Text] do return new ReverseSubstringsIterator(self, from)
+
 	redef fun output
 	do
 		for i in substrings do
@@ -611,3 +623,189 @@ class RopeCharIterator
 	end
 end
 
+private class ReversePostfix
+	super IndexedIterator[RopeNode]
+
+	var target: Rope
+
+	var pos: Int
+
+	var min = 0
+
+	var stack = new List[IteratorElement]
+
+	init from(tgt: Rope, pos: Int)
+	do
+		self.pos = pos
+		target = tgt
+		if pos < 0 or pos >= tgt.length then return
+		var path = tgt.node_at(pos)
+		self.pos -= path.offset
+		for i in path.stack do
+			var elemt = new IteratorElement(i.node)
+			elemt.right = true
+			if i.left then
+				elemt.left = true
+			end
+			stack.push elemt
+		end
+		stack.push(new IteratorElement(path.leaf))
+		stack.last.done = true
+	end
+
+	redef fun item do
+		assert is_ok
+		return stack.last.node
+	end
+
+	redef fun is_ok do return not stack.is_empty
+
+	redef fun index do return pos
+
+	redef fun next
+	do
+		if stack.is_empty then return
+		if pos < min then
+			stack.clear
+			return
+		end
+		var lst = stack.last
+		if lst.done then
+			stack.pop
+			next
+			return
+		end
+		if not lst.right then
+			var nod = lst.node.as(Concat)
+			var rgt = nod.right
+			lst.right = true
+			if rgt != null then
+				stack.push(new IteratorElement(rgt))
+				next
+				return
+			end
+		end
+		if not lst.left then
+			var nod = lst.node.as(Concat)
+			var lft = nod.left
+			lst.left = true
+			if lft != null then
+				stack.push(new IteratorElement(lft))
+				next
+				return
+			end
+		end
+		if lst.node isa Leaf then pos -= lst.node.length
+		lst.done = true
+	end
+end
+
+private class ReverseLeavesIterator
+	super IndexedIterator[Leaf]
+
+	var nodes: ReversePostfix
+
+	init(tgt: Rope, from: Int)
+	do
+		nodes = tgt.reverse_postfix(from)
+	end
+
+	redef fun is_ok do return nodes.is_ok
+
+	redef fun item do
+		assert is_ok
+		return nodes.item.as(Leaf)
+	end
+
+	redef fun next do
+		while nodes.is_ok do
+			nodes.next
+			if nodes.is_ok then if nodes.item isa Leaf then break
+		end
+	end
+
+	redef fun index do return nodes.index
+
+end
+
+private class ReverseSubstringsIterator
+	super IndexedIterator[Text]
+
+	var leaves: ReverseLeavesIterator
+
+	var pos: Int
+
+	var str: Text
+
+	init(tgt: Rope, from: Int)
+	do
+		leaves = tgt.reverse_leaves(from)
+		pos = from
+		if not leaves.is_ok then return
+		str = leaves.item.str
+		make_substring
+	end
+
+	fun make_substring
+	do
+		if pos >= (leaves.index + str.length - 1) then return
+		str = str.substring(0, (pos - leaves.index + 1))
+	end
+
+	redef fun is_ok do return leaves.is_ok
+
+	redef fun item do
+		assert is_ok
+		return str
+	end
+
+	redef fun index do return pos
+
+	redef fun next do
+		pos -= str.length
+		leaves.next
+		if not leaves.is_ok then return
+		str = leaves.item.str
+		make_substring
+	end
+end
+
+private class ReverseRopeCharIterator
+	super IndexedIterator[Char]
+
+	var substrs: IndexedIterator[Text]
+
+	var pos: Int
+
+	var subiter: IndexedIterator[Char]
+
+	init(tgt: Rope, from: Int)
+	do
+		substrs = tgt.reverse_substrings_from(from)
+		if not substrs.is_ok then
+			pos = -1
+			return
+		end
+		subiter = substrs.item.chars.reverse_iterator
+		pos = from
+	end
+
+	redef fun is_ok do return pos >= 0
+
+	redef fun item do
+		assert is_ok
+		return subiter.item
+	end
+
+	redef fun index do return pos
+
+	redef fun next do
+		pos -= 1
+		if subiter.is_ok then subiter.next
+		if not subiter.is_ok then
+			if substrs.is_ok then substrs.next
+			if substrs.is_ok then subiter = substrs.item.chars.reverse_iterator
+		end
+	end
+end
+
-- 
1.7.9.5