X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit index 37ac23e..7bc4154 100644 --- a/lib/standard/ropes.nit +++ b/lib/standard/ropes.nit @@ -44,6 +44,11 @@ end private abstract class RopeNode # Length of the node var length = 0 + + # Transforms the current node to a Leaf. + # This might be costly to invoke since this produces a FlatString concatenation. + # Can be used internally to limit the growth of the Rope when working with small leaves. + fun to_leaf: Leaf is abstract end # Node that represents a concatenation between two nodes (of any RopeNode type) @@ -51,40 +56,47 @@ private class Concat super RopeNode # Left child of the node - var _left: nullable RopeNode = null + var left: nullable RopeNode # Right child of the node - var _right: nullable RopeNode = null - - fun left: nullable RopeNode do return _left - fun right: nullable RopeNode do return _right + var right: nullable RopeNode - fun left=(l: RopeNode) + init(l: nullable RopeNode, r: nullable RopeNode) do - _left = l - length = l.length - if _right != null then length += _right.length + left = l + right = r + if l != null then length += l.length + if r != null then length += r.length end - fun right=(r: RopeNode) + redef fun to_leaf do - _right = r - length = r.length - if _left != null then length += _left.length + if left == null then + if right == null then return new StringLeaf("".as(FlatString)) + return right.to_leaf + end + if right == null then return left.as(not null).to_leaf + return new StringLeaf((left.to_leaf.str.as(FlatString) + right.to_leaf.str.as(FlatString)).as(FlatString)) end end # Leaf of a Rope, contains a FlatString -private class Leaf +private abstract class Leaf super RopeNode # Encapsulated FlatString in the leaf node - var str: FlatString + var str: FlatText + +end + +private class StringLeaf + super Leaf init(val: FlatString) do self.str = val length = str.length end + redef fun to_leaf do return self end # Basic structure, binary tree with a root node. @@ -104,7 +116,7 @@ abstract class Rope # Creates a new Rope with `s` as root init from(s: String) do - if s isa RopeString then root = s.root else root = new Leaf(s.as(FlatString)) + if s isa RopeString then root = s.root else root = new StringLeaf(s.as(FlatString)) end private init from_root(r: RopeNode) @@ -121,7 +133,7 @@ abstract class Rope private fun leaves(from: Int): LeavesIterator do return new LeavesIterator(self, from) # Iterator on the substrings from 0, in forward order - fun substrings: IndexedIterator[Text] do return new SubstringsIterator(self, 0) + 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) @@ -265,7 +277,7 @@ class RopeString end # Inserts a String `str` at position `pos` - fun insert_at(str: String, pos: Int): RopeString + redef fun insert_at(str, pos) do if str.length == 0 then return self if self.length == 0 then return new RopeString.from(str) @@ -276,46 +288,50 @@ class RopeString var path = node_at(pos) - var last_concat = new Concat + var last_concat: Concat if path.offset == 0 then - last_concat.right = path.leaf - if str isa FlatString then last_concat.left = new Leaf(str) else last_concat.left = str.as(RopeString).root + if str isa FlatString then + last_concat = new Concat(new StringLeaf(str), path.leaf) + else + last_concat = new Concat(str.as(RopeString).root, path.leaf) + end else if path.offset == path.leaf.length then - if str isa FlatString then last_concat.right = new Leaf(str) else last_concat.right = str.as(RopeString).root - last_concat.left = path.leaf + if str isa FlatString then + last_concat = new Concat(path.leaf, new StringLeaf(str)) + else + last_concat = new Concat(path.leaf, str.as(RopeString).root) + 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 Leaf(r_half) - last_concat.left = new Leaf(l_half) - if str isa FlatString then last_concat.right = new Leaf(str) else last_concat.right = str.as(RopeString).root - cct.left = last_concat - last_concat = cct + var cct: Concat + var ll = new StringLeaf(l_half.as(FlatString)) + if str isa FlatString then + cct = new Concat(ll, new StringLeaf(str)) + else + cct = new Concat(ll, str.as(RopeString).root) + end + last_concat = new Concat(cct, new StringLeaf(r_half.as(FlatString))) 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 + last_concat = new Concat(last_concat, i.node.right) else - nod.left = i.node.left.as(not null) - nod.right = last_concat + last_concat = new Concat(i.node.left, last_concat) end - last_concat = nod end return new RopeString.from_root(last_concat) end # Adds `s` at the beginning of self - fun prepend(s: String): String do return insert_at(s, 0) + redef fun prepend(s) do return insert_at(s, 0) # Adds `s` at the end of self - fun append(s: String): String + redef fun append(s) do if self.is_empty then return s return new RopeString.from_root(append_to_path(root,s)) @@ -324,17 +340,25 @@ class RopeString # 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 + var cct: Concat if node isa Leaf then - cct.left = node - if s isa FlatString then cct.right = new Leaf(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 s isa FlatString then + cct = new Concat(node, new StringLeaf(s)) + else + cct = new Concat(node, s.as(RopeString).root) + end + else + var n = node.as(Concat) + var right = n.right + var lft = n.left.as(not null) if right == null then - if s isa FlatString then cct.right = new Leaf(s) else cct.right = s.as(RopeString).root + if s isa FlatString then + cct = new Concat(lft, new StringLeaf(s)) + else + cct = new Concat(lft, s.as(RopeString).root) + end else - cct.right = append_to_path(right, s) + cct = new Concat(lft, append_to_path(right, s)) end end return cct @@ -364,17 +388,13 @@ class RopeString var lf = path.leaf var offset = path.offset - if path.leaf.str.length - offset > len then lf = new Leaf(lf.str.substring(offset,len)) else lf = new Leaf(lf.str.substring_from(offset)) + 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)) var nod: RopeNode = lf 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 + nod = new Concat(nod, i.node.right) end var ret = new RopeString @@ -383,15 +403,11 @@ class RopeString path = ret.node_at(len-1) offset = path.offset - nod = new Leaf(path.leaf.str.substring(0, offset+1)) + 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 + nod = new Concat(i.node.left, nod) end ret.root = nod @@ -400,6 +416,26 @@ class RopeString 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) + var r = substring_from(pos) + var ret: String = new RopeString.from(l) + ret += s + return ret + r + end + +end + private class RopeStringChars super SequenceRead[Char]