-# This file is part of NIT ( http://www.nitlanguage.org ).
+# This file is part of NIT (http://www.nitlanguage.org).
#
-# This file is free software, which comes along with NIT. This software is
-# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
-# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
-# PARTICULAR PURPOSE. You can modify it if you want, provided this header
-# is kept unaltered, and a notification of the changes is added.
-# You are allowed to redistribute it and sell it, alone or as a part of
-# another product.
-
-# Nit implementation of the Ropes (see Ropes : An Alternative to Strings,
-# SOFTWARE - PRACTICE AND EXPERIENCE, VOL. 25(12), 1315 - 1330 (DECEMBER 1995)
-# Hans. J Boehm, Russ Atkinson and Michael Plass)
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
#
-# A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Tree-based representation of a String.
+#
+# Ropes are a data structure introduced in a 1995 paper from
+# Hans J. Boehm, Russ Atkinson and Michael Plass.
+# See : `Ropes : an Alternative to Strings`, `Software - Practice and Experience,
+# Vol. 25(12), 1315-1330 (December 1995)`.
+#
+# The implementation developed here provides an automatic change
+# of data structure depending on the length of the leaves.
+#
+# The length from which a `Rope` is built from a `flat` string
+# if defined at top-level (see `maxlen`) and can be redefined by clients
+# depending on their needs (e.g. if you need to bench the speed of
+# the creation of concat nodes, lower the size of maxlen).
+#
+# A Rope as defined in the original paper is a Tree made of concatenation
+# nodes and containing `Flat` (that is Array-based) strings as Leaves.
+#
+# Example :
+#
+# ` Concat `
+# ` / \ `
+# ` Concat Concat `
+# ` / \ / \ `
+# `"My" " Name" " is" " Simon." `
+#
+# Note that the above example is not representative of the actual implementation
+# of `Ropes`, since short leaves are merged to keep the rope at an acceptable
+# height (hence, this rope here might actually be a `FlatString` !).
module ropes
intrude import string
-# Used when searching for a particular node
-# Returns the path to the node from the root of the rope
-# Also, the node and the offset for seeked position in the rope
-private class Path
- # Leaf found
- var leaf: Leaf
- # Offset in leaf
- var offset: Int
- # Stack of the nodes traversed, and the path used
- var stack: List[PathElement]
-end
+# Maxlen is the maximum length of a Leaf node
+#
+# When concatenating two leaves, if `new_length` > `maxlen`,
+# A `Concat` node is created instead
+#
+# Its purpose is to limit the depth of the `Rope` (this
+# improves performance when accessing/iterating).
+fun maxlen: Int do return 64
-# An element for a Path, has the concat node and whether or not
-# left or right child was visited.
-private class PathElement
- # Visited node
- var node: Concat
- # Was the left child visited ?
- var left = false
- # Was the right child visited ?
- var right = false
+# String using a tree-based representation with leaves as `FlatStrings`
+private abstract class Rope
+ super Text
end
-# A node for a Rope
-private abstract class RopeNode
- # Length of the node
- var length = 0
+private abstract class RopeString
+ super Rope
+ super String
+
+ redef fun chars is cached do return new RopeChars(self)
end
-# Node that represents a concatenation between two nodes (of any RopeNode type)
+# Node that represents a concatenation between two `String`
private class Concat
- super RopeNode
+ super RopeString
- # Left child of the node
- var _left: nullable RopeNode = null
- # Right child of the node
- var _right: nullable RopeNode = null
+ redef var length: Int
- fun left: nullable RopeNode do return _left
- fun right: nullable RopeNode do return _right
+ redef fun substrings do return new RopeSubstrings(self)
- fun left=(l: RopeNode)
- do
- _left = l
- length = l.length
- if _right != null then length += _right.length
- end
+ redef fun empty do return ""
- fun right=(r: RopeNode)
- do
- _right = r
- length = r.length
- if _left != null then length += _left.length
+ redef fun to_cstring is cached do
+ var len = length
+ var ns = new NativeString(len + 1)
+ ns[len] = '\0'
+ var off = 0
+ for i in substrings do
+ var ilen = i.length
+ i.as(FlatString).items.copy_to(ns, ilen, i.as(FlatString).index_from, off)
+ off += ilen
+ end
+ return ns
end
-end
-
-# Leaf of a Rope, contains a FlatString
-private abstract class Leaf
- super RopeNode
-
- # Encapsulated FlatString in the leaf node
- var str: FlatText
-
-end
-private class StringLeaf
- super Leaf
+ # Left child of the node
+ var left: String
+ # Right child of the node
+ var right: String
- init(val: FlatString) do
- self.str = val
- length = str.length
+ init(l: String, r: String) is old_style_init do
+ left = l
+ right = r
+ length = l.length + r.length
end
-end
-
-# Basic structure, binary tree with a root node.
-#
-# Also shared services by subsequent implementations.
-abstract class Rope
- super Text
-
- # Root node, entry point of a Rope.
- private var root: RopeNode
-
- # Cached version of self as a flat String
- private var str_representation: nullable NativeString = null
+ redef fun output do
+ left.output
+ right.output
+ end
- # Empty Rope
- init do from("")
+ redef fun iterator do return new RopeIter(self)
- # Creates a new Rope with `s` as root
- init from(s: String) do
- if s isa RopeString then root = s.root else root = new StringLeaf(s.as(FlatString))
+ redef fun *(i) do
+ var x: String = self
+ for j in [1 .. i[ do x += self
+ return x
end
- private init from_root(r: RopeNode)
- do
- root = r
+ redef fun [](i) do
+ var llen = left.length
+ if i >= llen then return right[i - llen]
+ return left[i]
end
- redef fun length do return root.length
-
- # Iterator on the nodes of the rope, in forward postfix order
- private fun postfix(from: Int): Postfix do return new Postfix.from(self, from)
-
- # Iterator on the leaves of the rope, forward order
- private fun leaves(from: Int): LeavesIterator do return new LeavesIterator(self, from)
-
- # Iterator on the substrings from 0, in forward order
- redef fun substrings do return new SubstringsIterator(self, 0)
-
- # 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
- i.output
+ redef fun substring(from, len) do
+ var llen = left.length
+ if from < llen then
+ if from + len < llen then return left.substring(from,len)
+ var lsublen = llen - from
+ return left.substring_from(from) + right.substring(0, len - lsublen)
+ else
+ return right.substring(from - llen, len)
end
end
- redef fun to_cstring
- do
- if str_representation != null then return str_representation.as(not null)
-
- var native_final_str = calloc_string(length + 1)
-
- native_final_str[length] = '\0'
+ redef fun reversed do return new Concat(right.reversed, left.reversed)
- if self.length == 0 then
- str_representation = native_final_str
- return native_final_str
+ redef fun insert_at(s, pos) do
+ if pos > left.length then
+ return left + right.insert_at(s, pos - left.length)
end
-
- var offset = 0
-
- for i in substrings do
- var str = i.flatten
- if str isa FlatString then str.items.copy_to(native_final_str, str.length, str.index_from, offset)
- offset += i.length
- end
-
- str_representation = native_final_str
-
- return native_final_str
+ return left.insert_at(s, pos) + right
end
- # Path to the Leaf for `position`
- private fun node_at(position: Int): Path
- do
- assert position >= 0 and position < length
- return get_node_from(root.as(not null), 0, position, new List[PathElement])
- end
+ redef fun to_upper do return new Concat(left.to_upper, right.to_upper)
- # 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)
+ redef fun to_lower do return new Concat(left.to_lower, right.to_lower)
- 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)
+ redef fun +(o) do
+ var s = o.to_s
+ var slen = s.length
+ if s isa Concat then
+ return new Concat(self, s)
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)
+ var r = right
+ var rlen = r.length
+ if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
+ return new Concat(left, r + s)
end
end
-
- redef fun ==(o)
- do
- if not o isa Text then return false
- if o.length != self.length then return false
- var oit = o.chars.iterator
- for i in self.chars.iterator do
- if i != oit.item then return false
- oit.next
- end
- return true
- end
end
-# Rope that cannot be modified
-class RopeString
+# Mutable `Rope`, optimized for concatenation operations
+#
+# A `RopeBuffer` is an efficient way of building a `String` when
+# concatenating small strings.
+#
+# It does concatenations in an optimized way by having a
+# mutable part and an immutable part built by efficiently
+# concatenating strings in chain.
+#
+# Every concatenation operation is done by copying a string to
+# the mutable part and flushing it when full.
+#
+# However, when a long string is appended to the `Buffer`,
+# the concatenation is done at it would be in a `Rope`.
+class RopeBuffer
super Rope
- super String
+ super Buffer
- redef fun to_s do return self
+ redef fun chars: Sequence[Char] is cached do return new RopeBufferChars(self)
- redef fun empty do return once new RopeString.from("")
+ # The final string being built on the fly
+ private var str: String is noinit
- redef var chars: SequenceRead[Char] = new RopeStringChars(self)
+ # Current concatenation buffer
+ private var ns: NativeString is noinit
- redef fun reversed
- do
- var ret = empty.as(RopeString)
- for i in substrings do
- ret = ret.prepend(i.reversed.to_s).as(RopeString)
- end
- return ret
+ # Next available (e.g. unset) character in the `Buffer`
+ private var rpos = 0
+
+ # Keeps track of the buffer's currently dumped part
+ #
+ # This might happen if for instance, a String was being
+ # built by concatenating small parts of string and suddenly
+ # a long string (length > maxlen) is appended.
+ private var dumped: Int is noinit
+
+ # Length of the complete rope
+ redef var length = 0
+
+ # Length of the mutable part
+ #
+ # Is also used as base to compute the size of the next
+ # mutable native string (`ns`)
+ private var buf_size: Int is noinit
+
+ redef fun substrings: Iterator[String] do return new RopeBufSubstringIterator(self)
+
+ # Builds an empty `RopeBuffer`
+ init do
+ str = ""
+ ns = new NativeString(maxlen)
+ buf_size = maxlen
+ dumped = 0
end
- redef fun to_upper
- do
- var ret = empty
- for i in substrings do
- ret += i.to_upper
- end
- return ret
+ # Builds a new `RopeBuffer` with `str` in it.
+ init from(str: String) do
+ self.str = str
+ ns = new NativeString(maxlen)
+ buf_size = maxlen
+ length = str.length
+ dumped = 0
end
- redef fun to_lower
- do
- var ret = empty
- for i in substrings do
- ret += i.to_lower
- end
- return ret
+ # Resets the informations of the `Buffer`
+ #
+ # This is called when doing in-place modifications
+ # on a previously to_s'd `RopeBuffer`
+ private fun reset do
+ var nns = new NativeString(buf_size)
+ var blen = rpos - dumped
+ ns.copy_to(nns, blen, dumped, 0)
+ dumped = 0
+ rpos = blen
+ written = false
end
- redef fun +(o) do return insert_at(o.to_s, length)
+ redef fun empty do return new RopeBuffer
- redef fun *(n)
- do
- var ret = new RopeString.from("")
- for i in [0..n[ do
- ret = (ret + self).as(RopeString)
+ redef fun clear do
+ str = ""
+ length = 0
+ rpos = 0
+ dumped = 0
+ if written then
+ ns = new NativeString(buf_size)
+ written = false
end
- return ret
end
- # Inserts a String `str` at position `pos`
- redef fun insert_at(str, pos)
- do
- if str.length == 0 then return self
- if self.length == 0 then return new RopeString.from(str)
-
- assert pos >= 0 and pos <= length
+ redef fun substring(from, count) do
+ var strlen = str.length
- if pos == length then return append(str).as(RopeString)
+ if from < 0 then
+ count += from
+ if count < 0 then count = 0
+ from = 0
+ end
- var path = node_at(pos)
+ if count > length then count = length - from
- var last_concat = new Concat
+ if count == 0 then return empty
- if path.offset == 0 then
- last_concat.right = path.leaf
- if str isa FlatString then last_concat.left = new StringLeaf(str) else last_concat.left = str.as(RopeString).root
- else if path.offset == path.leaf.length then
- if str isa FlatString then last_concat.right = new StringLeaf(str) else last_concat.right = str.as(RopeString).root
- last_concat.left = path.leaf
+ if from < strlen then
+ var subpos = strlen - from
+ if count <= subpos then
+ return new RopeBuffer.from(str.substring(from, count))
+ else
+ var l = str.substring_from(from)
+ var rem = count - subpos
+ var nns = new NativeString(rem)
+ ns.copy_to(nns, rem, dumped, 0)
+ return new RopeBuffer.from(l + nns.to_s_with_length(rem))
+ end
else
- var s = path.leaf.str
- var l_half = s.substring(0, s.length - path.offset)
- var r_half = s.substring_from(s.length - path.offset)
- var cct = new Concat
- cct.right = new StringLeaf(r_half.as(FlatString))
- last_concat.left = new StringLeaf(l_half.as(FlatString))
- if str isa FlatString then last_concat.right = new StringLeaf(str) else last_concat.right = str.as(RopeString).root
- cct.left = last_concat
- last_concat = cct
+ var nns = new NativeString(count)
+ ns.copy_to(nns, count, dumped, 0)
+ return new RopeBuffer.from(nns.to_s_with_length(count))
end
+ end
- for i in path.stack.reverse_iterator do
- var nod = new Concat
- if i.left then
- nod.right = i.node.right.as(not null)
- nod.left = last_concat
+ redef fun append(s) do
+ var slen = s.length
+ length += slen
+ var rp = rpos
+ if s isa Rope or slen > maxlen then
+ if rp > 0 and dumped != rp then
+ str += new FlatString.with_infos(ns, rp - dumped, dumped, rp - 1)
+ dumped = rp
+ end
+ str = str + s
+ return
+ end
+ var remsp = buf_size - rp
+ var sits: NativeString
+ var begin: Int
+ if s isa FlatString then
+ begin = s.index_from
+ sits = s.items
+ else if s isa FlatBuffer then
+ begin = 0
+ sits = s.items
+ else
+ if slen <= remsp then
+ for i in s.chars do
+ ns[rpos] = i
+ rpos += 1
+ end
else
- nod.left = i.node.left.as(not null)
- nod.right = last_concat
+ var spos = 0
+ for i in [0..remsp[ do
+ ns[rpos] = s[spos]
+ rpos += 1
+ spos += 1
+ end
+ dump_buffer
+ while spos < slen do
+ ns[rpos] = s[spos]
+ spos += 1
+ rpos += 1
+ end
end
- last_concat = nod
+ return
end
-
- return new RopeString.from_root(last_concat)
- end
-
- # Adds `s` at the beginning of self
- redef fun prepend(s) do return insert_at(s, 0)
-
- # Adds `s` at the end of self
- redef fun append(s)
- do
- if self.is_empty then return s
- return new RopeString.from_root(append_to_path(root,s))
- end
-
- # Builds a new path from root to the rightmost node with s appended
- private fun append_to_path(node: RopeNode, s: String): RopeNode
- do
- var cct = new Concat
- if node isa Leaf then
- cct.left = node
- if s isa FlatString then cct.right = new StringLeaf(s) else cct.right = s.as(RopeString).root
- else if node isa Concat then
- var right = node.right
- if node.left != null then cct.left = node.left.as(not null)
- if right == null then
- if s isa FlatString then cct.right = new StringLeaf(s) else cct.right = s.as(RopeString).root
+ if slen <= remsp then
+ if remsp <= 0 then
+ dump_buffer
+ rpos = 0
else
- cct.right = append_to_path(right, s)
+ sits.copy_to(ns, slen, begin, rp)
+ rpos += slen
end
+ else
+ sits.copy_to(ns, remsp, begin, rp)
+ rpos = buf_size
+ dump_buffer
+ var nlen = slen - remsp
+ sits.copy_to(ns, nlen, begin + remsp, 0)
+ rpos = nlen
end
- return cct
end
- # O(log(n))
- #
- # var rope = new RopeString.from("abcd")
- # assert rope.substring(1, 2) == "bc"
- # assert rope.substring(-1, 2) == "a"
- # assert rope.substring(1, 0) == ""
- # assert rope.substring(2, 5) == "cd"
- #
- redef fun substring(pos, len)
- do
- if pos < 0 then
- len += pos
- pos = 0
+ redef fun add(c) do
+ var rp = rpos
+ if rp >= buf_size then
+ dump_buffer
+ rp = 0
end
+ ns[rp] = c
+ rp += 1
+ length += 1
+ rpos = rp
+ end
- if pos + len > length then len = length - pos
-
- if len <= 0 then return new RopeString.from("")
-
- var path = node_at(pos)
+ # Converts the Buffer to a FlatString, appends it to
+ # the final String and re-allocates a new larger Buffer.
+ private fun dump_buffer do
+ written = false
+ var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+ str += nstr
+ var bs = buf_size
+ bs = bs * 2
+ ns = new NativeString(bs)
+ buf_size = bs
+ dumped = 0
+ end
- var lf = path.leaf
- var offset = path.offset
+ redef fun output do
+ str.output
+ new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1).output
+ end
- if path.leaf.str.length - offset > len then lf = new StringLeaf(lf.str.substring(offset,len).as(FlatString)) else lf = new StringLeaf(lf.str.substring_from(offset).as(FlatString))
+ # Enlarge is useless here since the `Buffer`
+ # part is automatically dumped when necessary.
+ #
+ # Also, since the buffer can not be overused by a
+ # single string, there is no need for manual
+ # resizing.
+ #
+ # "You have no power here !"
+ redef fun enlarge(i) do end
- var nod: RopeNode = lf
+ redef fun to_s do
+ written = true
+ var nnslen = rpos - dumped
+ if nnslen == 0 then return str
+ return str + new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+ end
- for i in path.stack.reverse_iterator do
- if i.right then continue
- var tmp = new Concat
- tmp.left = nod
- var r = i.node.right
- if r != null then tmp.right = r
- nod = tmp
+ redef fun reverse do
+ # Flush the buffer in order to only have to reverse `str`.
+ if rpos > 0 and dumped != rpos then
+ str += new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+ dumped = rpos
end
+ str = str.reversed
+ end
- var ret = new RopeString
- ret.root = nod
-
- path = ret.node_at(len-1)
-
- offset = path.offset
- nod = new StringLeaf(path.leaf.str.substring(0, offset+1).as(FlatString))
-
- for i in path.stack.reverse_iterator do
- if i.left then continue
- var tmp = new Concat
- tmp.right = nod
- var l = i.node.left
- if l != null then tmp.left = l
- nod = tmp
+ redef fun upper do
+ if written then reset
+ str = str.to_upper
+ var mits = ns
+ for i in [0 .. rpos[ do
+ mits[i] = mits[i].to_upper
end
+ end
- ret.root = nod
-
- return ret
+ redef fun lower do
+ if written then reset
+ str = str.to_lower
+ var mits = ns
+ for i in [0 .. rpos[ do
+ mits[i] = mits[i].to_lower
+ end
end
end
redef class FlatString
- redef fun append(s) do return (new RopeString.from(self)) + s
-
- redef fun prepend(s) do return (new RopeString.from(self)).prepend(s)
-
- redef fun insert_at(s, pos)
- do
- if pos == 0 then return prepend(s)
- if pos == length then return append(s)
-
- var l = substring(0,pos)
+ redef fun insert_at(s, pos) do
+ var l = substring(0, pos)
var r = substring_from(pos)
- var ret: String = new RopeString.from(l)
- ret += s
- return ret + r
+ return l + s + r
+ end
+
+ redef fun +(o) do
+ var s = o.to_s
+ var slen = s.length
+ var mlen = length
+ if slen == 0 then return self
+ if mlen == 0 then return s
+ var nlen = slen + mlen
+ if s isa FlatString then
+ if nlen > maxlen then return new Concat(self, s)
+ var mits = items
+ var sifrom = s.index_from
+ var mifrom = index_from
+ var sits = s.items
+ var ns = new NativeString(nlen + 1)
+ mits.copy_to(ns, mlen, mifrom, 0)
+ sits.copy_to(ns, slen, sifrom, mlen)
+ return ns.to_s_with_length(nlen)
+ else if s isa Concat then
+ var sl = s.left
+ var sllen = sl.length
+ if sllen + mlen > maxlen then return new Concat(self, s)
+ return new Concat(self + sl, s.right)
+ else
+ abort
+ end
end
+end
+# A simple linked list for use with iterators
+private class RopeIterPiece
+ # The encapsulated node of the `Rope`
+ var node: String
+ # Was its left child (if any) visited ?
+ var ldone: Bool
+ # Was its right child (if any) visited ?
+ var rdone: Bool
+ # The previous node in the list.
+ var prev: nullable RopeIterPiece
end
-private class RopeStringChars
- super SequenceRead[Char]
+# A reverse iterator capable of working with `Rope` objects
+private class RopeReviter
+ super IndexedIterator[Char]
- var tgt: Rope
+ # Current NativeString
+ var ns: String
+ # Current position in NativeString
+ var pns: Int
+ # Position in the Rope (0-indexed)
+ var pos: Int
+ # Iterator on the substrings, does the Postfix part of
+ # the Rope traversal.
+ var subs: IndexedIterator[String]
- redef fun [](pos)
- do
- assert pos < tgt.length
- var path = tgt.node_at(pos)
- return path.leaf.str.chars[path.offset]
+ init(root: RopeString) is old_style_init do
+ pos = root.length - 1
+ subs = new ReverseRopeSubstrings(root)
+ ns = subs.item
+ pns = ns.length - 1
end
- redef fun iterator do return iterator_from(0)
-
- redef fun iterator_from(pos) do return new RopeCharIterator(tgt, pos)
+ init from(root: RopeString, pos: Int) do
+ self.pos = pos
+ subs = new ReverseRopeSubstrings.from(root, pos)
+ ns = subs.item
+ pns = pos - subs.index
+ end
- redef fun reverse_iterator do return reverse_iterator_from(tgt.length-1)
+ redef fun index do return pos
- redef fun reverse_iterator_from(pos) do return new ReverseRopeCharIterator(tgt, pos)
-end
+ redef fun is_ok do return pos >= 0
-# Used to iterate on a Rope
-private class IteratorElement
+ redef fun item do return ns[pns]
- init(e: RopeNode)
- do
- if e isa Leaf then
- left = true
- right = true
- end
- node = e
+ redef fun next do
+ pns -= 1
+ pos -= 1
+ if pns >= 0 then return
+ if not subs.is_ok then return
+ subs.next
+ if not subs.is_ok then return
+ ns = subs.item
+ pns = ns.length - 1
end
-
- # The node being visited
- var node: RopeNode
- # If the node has a left child, was it visited ?
- var left = false
- # If the node has a right child, was it visited ?
- var right = false
- # Was the current node visited ?
- var done = false
end
-# Simple Postfix iterator on the nodes of a Rope
-private class Postfix
- super IndexedIterator[RopeNode]
-
- # Target Rope to iterate on
- var target: Rope
+# Forward iterator on the chars of a `Rope`
+private class RopeIter
+ super IndexedIterator[Char]
- # Current position in Rope
+ # Position in current `String`
+ var pns: Int
+ # Current `String` being iterated on
+ var str: String
+ # Substrings of the Rope
+ var subs: IndexedIterator[String]
+ # Maximum position to iterate on (e.g. Rope.length)
+ var max: Int
+ # Position (char) in the Rope (0-indexed)
var pos: Int
- # Visited nodes
- var stack = new List[IteratorElement]
+ init(root: RopeString) is old_style_init do
+ subs = new RopeSubstrings(root)
+ pns = 0
+ str = subs.item
+ max = root.length - 1
+ pos = 0
+ end
- init from(tgt: Rope, pos: Int)
- do
- self.target = tgt
+ init from(root: RopeString, pos: Int) do
+ subs = new RopeSubstrings.from(root, pos)
+ pns = pos - subs.index
self.pos = pos
- 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 item = new IteratorElement(i.node)
- item.left = true
- if i.right then item.right = true
- stack.push item
- end
- var item = new IteratorElement(path.leaf)
- item.done = true
- stack.push item
+ str = subs.item
+ max = root.length - 1
end
- redef fun item
- do
- assert is_ok
- return stack.last.node
- end
+ redef fun item do return str[pns]
- redef fun is_ok do return not stack.is_empty
+ redef fun is_ok do return pos <= max
redef fun index do return pos
redef fun next do
- if stack.is_empty then return
- if pos > target.length-1 then
- stack.clear
- return
- end
- var lst = stack.last
- if lst.done then
- if lst.node isa Leaf then
- pos += lst.node.length
- end
- stack.pop
- next
- return
- end
- if not lst.left then
- lst.left = true
- var nod = lst.node
- if nod isa Concat and nod.left != null then
- stack.push(new IteratorElement(nod.left.as(not null)))
- next
- return
- end
- end
- if not lst.right then
- lst.right = true
- var nod = lst.node
- if nod isa Concat and nod.right != null then
- stack.push(new IteratorElement(nod.right.as(not null)))
- next
- return
- end
- end
- lst.done = true
+ pns += 1
+ pos += 1
+ if pns < subs.item.length then return
+ if not subs.is_ok then return
+ subs.next
+ if not subs.is_ok then return
+ str = subs.item
+ pns = 0
end
end
-# Iterates on the leaves (substrings) of the Rope
-class LeavesIterator
- super IndexedIterator[Leaf]
-
- private var nodes: Postfix
+# Substrings of a Rope (i.e. Reverse postfix iterator on leaves)
+private class ReverseRopeSubstrings
+ super IndexedIterator[String]
+
+ # Visit Stack
+ var iter: RopeIterPiece is noinit
+ # Position in `Rope`
+ var pos: Int is noinit
+
+ # Current leaf
+ var str: String is noinit
+
+ init(root: RopeString) is old_style_init do
+ var r = new RopeIterPiece(root, false, true, null)
+ pos = root.length - 1
+ var lnod: String = root
+ loop
+ if lnod isa Concat then
+ lnod = lnod.right
+ r = new RopeIterPiece(lnod, false, true, r)
+ else
+ str = lnod
+ iter = r
+ break
+ end
+ end
+ end
- init(tgt: Rope, pos: Int)
- do
- nodes = tgt.postfix(pos)
+ init from(root: RopeString, pos: Int) do
+ var r = new RopeIterPiece(root, false, true, null)
+ var rnod: String = root
+ var off = pos
+ loop
+ if rnod isa Concat then
+ if off >= rnod.left.length then
+ off -= rnod.left.length
+ rnod = rnod.right
+ r = new RopeIterPiece(rnod, false, true, r)
+ else
+ r.ldone = true
+ rnod = rnod.left
+ r = new RopeIterPiece(rnod, false, true, r)
+ end
+ else
+ str = rnod
+ r.ldone = true
+ iter = r
+ self.pos = pos - off
+ break
+ end
+ end
end
- redef fun is_ok do return nodes.is_ok
+ redef fun item do return str
- redef fun item
- do
- assert is_ok
- return nodes.item.as(Leaf)
- end
+ redef fun index do return pos
- redef fun index do return nodes.index
+ redef fun is_ok do return pos >= 0
- redef fun next
- do
- while nodes.is_ok do
- nodes.next
- if nodes.is_ok and nodes.item isa Leaf then break
+ redef fun next do
+ if pos < 0 then return
+ var curr = iter.prev
+ var currit = curr.node
+ while curr != null do
+ currit = curr.node
+ if not currit isa Concat then
+ str = currit
+ pos -= str.length
+ iter = curr
+ return
+ end
+ if not curr.rdone then
+ curr.rdone = true
+ curr = new RopeIterPiece(currit.right, false, false, curr)
+ continue
+ end
+ if not curr.ldone then
+ curr.ldone = true
+ curr = new RopeIterPiece(currit.left, false, false, curr)
+ continue
+ end
+ curr = curr.prev
end
+ pos = -1
end
end
-# Uses the leaves and calculates a new substring on each iteration
-class SubstringsIterator
- super IndexedIterator[Text]
+private class RopeBufSubstringIterator
+ super Iterator[String]
- private var nodes: IndexedIterator[Leaf]
+ # Iterator on the substrings of the building string
+ var iter: Iterator[String]
+ # Makes a String out of the buffered part of the Ropebuffer
+ var nsstr: String
+ # Did we attain the buffered part ?
+ var nsstr_done = false
- # Current position in Rope
- var pos: Int
-
- # Current substring, computed from the current Leaf and indexes
- var substring: Text
-
- init(tgt: Rope, pos: Int)
- do
- nodes = tgt.leaves(pos)
- self.pos = pos
- if pos < 0 or pos >= tgt.length then return
- make_substring
- end
-
- # Compute the bounds of the current substring and makes the substring
- private fun make_substring
- do
- substring = nodes.item.str
- var min = 0
- var length = substring.length
- if nodes.index < pos then
- min = pos - nodes.index
- end
- substring = substring.substring(min, length)
+ init(str: RopeBuffer) is old_style_init do
+ iter = str.str.substrings
+ nsstr = new FlatString.with_infos(str.ns, str.rpos - str.dumped, str.dumped, str.rpos - 1)
+ if str.length == 0 then nsstr_done = true
end
- redef fun is_ok do return nodes.is_ok
+ redef fun is_ok do return iter.is_ok or not nsstr_done
- redef fun item
- do
+ redef fun item do
assert is_ok
- return substring
+ if iter.is_ok then return iter.item
+ return nsstr
end
- redef fun index do return pos
-
- redef fun next
- do
- pos += substring.length
- nodes.next
- if nodes.is_ok then make_substring
+ redef fun next do
+ if iter.is_ok then
+ iter.next
+ return
+ end
+ nsstr_done = true
end
-
end
-class RopeCharIterator
- super IndexedIterator[Char]
-
- var substrings: IndexedIterator[Text]
-
- var pos: Int
-
- var max: Int
-
- var substr_iter: IndexedIterator[Char]
+# Substrings of a Rope (i.e. Postfix iterator on leaves)
+private class RopeSubstrings
+ super IndexedIterator[String]
+
+ # Visit Stack
+ var iter: RopeIterPiece is noinit
+ # Position in `Rope`
+ var pos: Int is noinit
+ # Maximum position in `Rope` (i.e. length - 1)
+ var max: Int is noinit
+
+ # Current leaf
+ var str: String is noinit
+
+ init(root: RopeString) is old_style_init do
+ var r = new RopeIterPiece(root, true, false, null)
+ pos = 0
+ max = root.length - 1
+ var rnod: String = root
+ loop
+ if rnod isa Concat then
+ rnod = rnod.left
+ r = new RopeIterPiece(rnod, true, false, r)
+ else
+ str = rnod
+ r.rdone = true
+ iter = r
+ break
+ end
+ end
+ end
- init(tgt: Rope, from: Int)
- do
- substrings = tgt.substrings_from(from)
- max = tgt.length - 1
- if not substrings.is_ok then
- pos = tgt.length
- return
+ init from(root: RopeString, pos: Int) do
+ var r = new RopeIterPiece(root, true, false, null)
+ max = root.length - 1
+ var rnod: String = root
+ var off = pos
+ loop
+ if rnod isa Concat then
+ if off >= rnod.left.length then
+ r.rdone = true
+ off -= rnod.left.length
+ rnod = rnod.right
+ r = new RopeIterPiece(rnod, true, false, r)
+ else
+ rnod = rnod.left
+ r = new RopeIterPiece(rnod, true, false, r)
+ end
+ else
+ str = rnod
+ r.rdone = true
+ iter = r
+ self.pos = pos - off
+ break
+ end
end
- pos = from
- substr_iter = substrings.item.chars.iterator
end
- redef fun item do return substr_iter.item
+ redef fun item do return str
redef fun is_ok do return pos <= max
redef fun index do return pos
- redef fun next
- do
- pos += 1
- if substr_iter.is_ok then
- substr_iter.next
- end
- if not substr_iter.is_ok then
- substrings.next
- if substrings.is_ok then
- substr_iter = substrings.item.chars.iterator
+ redef fun next do
+ pos += str.length
+ if pos > max then return
+ var it = iter.prev
+ var rnod = it.node
+ loop
+ if not rnod isa Concat then
+ it.ldone = true
+ it.rdone = true
+ str = rnod
+ iter = it.as(not null)
+ break
+ end
+ if not it.ldone then
+ rnod = rnod.left
+ it.ldone = true
+ it = new RopeIterPiece(rnod, false, false, it)
+ else if not it.rdone then
+ it.rdone = true
+ rnod = rnod.right
+ it = new RopeIterPiece(rnod, false, false, it)
+ else
+ it = it.prev
+ rnod = it.node
+ continue
end
end
end
end
-private class ReversePostfix
- super IndexedIterator[RopeNode]
+# Implementation of a `StringCharView` for `RopeString` objects
+private class RopeChars
+ super StringCharView
- var target: Rope
+ var tgt: RopeString
- var pos: Int
+ init(s: RopeString) is old_style_init do tgt = s
- var min = 0
+ redef fun [](i) do
+ return tgt[i]
+ end
- var stack = new List[IteratorElement]
+ redef fun iterator_from(i) do return new RopeIter.from(tgt, i)
- 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 reverse_iterator_from(i) do return new RopeReviter.from(tgt, i)
- redef fun item do
- assert is_ok
- return stack.last.node
- end
+end
- redef fun is_ok do return not stack.is_empty
+# An Iterator over a RopeBuffer.
+class RopeBufferIter
+ super IndexedIterator[Char]
- redef fun index do return pos
+ # Subiterator.
+ var sit: IndexedIterator[Char]
- 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
+ # Native string iterated over.
+ var ns: NativeString
+
+ # Current position in `ns`.
+ var pns: Int
-private class ReverseLeavesIterator
- super IndexedIterator[Leaf]
+ # Maximum position iterable.
+ var maxpos: Int
- var nodes: ReversePostfix
+ redef var index: Int
- init(tgt: Rope, from: Int)
- do
- nodes = tgt.reverse_postfix(from)
+ # Init the iterator from a RopeBuffer.
+ init(t: RopeBuffer) is old_style_init do
+ ns = t.ns
+ maxpos = t.rpos
+ sit = t.str.chars.iterator
+ pns = t.dumped
+ index = 0
end
- redef fun is_ok do return nodes.is_ok
+ # Init the iterator from a RopeBuffer starting from `pos`.
+ init from(t: RopeBuffer, pos: Int) do
+ ns = t.ns
+ maxpos = t.length
+ sit = t.str.chars.iterator_from(pos)
+ pns = pos - t.str.length
+ index = pos
+ end
+
+ redef fun is_ok do return index < maxpos
redef fun item do
- assert is_ok
- return nodes.item.as(Leaf)
+ if sit.is_ok then return sit.item
+ return ns[pns]
end
redef fun next do
- while nodes.is_ok do
- nodes.next
- if nodes.is_ok then if nodes.item isa Leaf then break
+ index += 1
+ if sit.is_ok then
+ sit.next
+ else
+ pns += 1
end
end
-
- redef fun index do return nodes.index
-
end
-private class ReverseSubstringsIterator
- super IndexedIterator[Text]
+# Reverse iterator over a RopeBuffer.
+class RopeBufferReviter
+ super IndexedIterator[Char]
- var leaves: ReverseLeavesIterator
+ # Subiterator.
+ var sit: IndexedIterator[Char]
- var pos: Int
+ # Native string iterated over.
+ var ns: NativeString
- var str: Text
+ # Current position in `ns`.
+ var pns: Int
- 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
+ redef var index: Int
+
+ # Init the iterator from a RopeBuffer.
+ init(tgt: RopeBuffer) is old_style_init do
+ sit = tgt.str.chars.reverse_iterator
+ pns = tgt.rpos - 1
+ index = tgt.length - 1
+ ns = tgt.ns
end
- fun make_substring
- do
- if pos >= (leaves.index + str.length - 1) then return
- str = str.substring(0, (pos - leaves.index + 1))
+ # Init the iterator from a RopeBuffer starting from `pos`.
+ init from(tgt: RopeBuffer, pos: Int) do
+ sit = tgt.str.chars.reverse_iterator_from(pos - tgt.rpos - tgt.dumped)
+ pns = pos - tgt.str.length
+ index = pos
+ ns = tgt.ns
end
- redef fun is_ok do return leaves.is_ok
+ redef fun is_ok do return index > 0
redef fun item do
- assert is_ok
- return str
+ if pns >= 0 then return ns[pns]
+ return sit.item
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
+ index -= 1
+ if pns >= 0 then
+ pns -= 1
+ else
+ sit.next
+ end
end
end
-private class ReverseRopeCharIterator
- super IndexedIterator[Char]
-
- var substrs: IndexedIterator[Text]
+# View on the chars of a `RopeBuffer`
+class RopeBufferChars
+ super BufferCharView
- var pos: Int
+ redef type SELFTYPE: RopeBuffer
- var subiter: IndexedIterator[Char]
+ redef fun [](i) do
+ if i < target.str.length then
+ return target.str[i]
+ else
+ return target.ns[i - target.str.length]
+ end
+ end
- init(tgt: Rope, from: Int)
- do
- substrs = tgt.reverse_substrings_from(from)
- if not substrs.is_ok then
- pos = -1
- return
+ redef fun []=(i,c) do
+ if i == target.length then target.add c
+ if i < target.str.length then
+ var s = target.str
+ var l = s.substring(0, i)
+ var r = s.substring_from(i + 1)
+ target.str = l + c.to_s + r
+ else
+ target.ns[i - target.str.length] = c
end
- subiter = substrs.item.chars.reverse_iterator
- pos = from
end
- redef fun is_ok do return pos >= 0
+ redef fun add(c) do target.add c
- redef fun item do
- assert is_ok
- return subiter.item
- end
+ redef fun push(c) do target.add c
- redef fun index do return pos
+ redef fun iterator_from(i) do return new RopeBufferIter.from(target, i)
- 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
+ redef fun reverse_iterator_from(i) do return new RopeBufferReviter.from(target, i)
end
-
nitlanguage / nit.git / blobdiff