Merge: example: add 24 game task of Rosetta code

[nit.git] / lib / standard / ropes.nit

diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit
index ad09beb..902649a 100644 (file)
--- a/lib/standard/ropes.nit
+++ b/lib/standard/ropes.nit
@@ -16,8 +16,12 @@
 #
 # Ropes are a data structure introduced in a 1995 paper from
 # Hans J. Boehm, Russ Atkinson and Michael Plass.
 #
 # 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)`.
+#
+# 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 implementation developed here provides an automatic change
 # of data structure depending on the length of the leaves.

@@ -32,11 +36,11 @@
 #
 # Example :
 #
 #
 # Example :
 #

-# `            Concat                   `
-# `          /        \                 `
-# `    Concat          Concat           `
-# `   /      \        /      \          `
-# `"My"     " Name"  " is"   " Simon."  `
+#                  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
 #
 # 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

@@ -63,20 +67,20 @@ private abstract class RopeString
        super Rope
        super String
 
        super Rope
        super String
 

-       redef fun chars is cached do return new RopeChars(self)
+       redef var chars is lazy do return new RopeChars(self)

 end
 
 # Node that represents a concatenation between two `String`
 private class Concat
        super RopeString
 
 end
 
 # Node that represents a concatenation between two `String`
 private class Concat
        super RopeString
 

-       redef var length: Int
+       redef var length is noinit

 
        redef fun substrings do return new RopeSubstrings(self)
 
        redef fun empty do return ""
 
 
        redef fun substrings do return new RopeSubstrings(self)
 
        redef fun empty do return ""
 

-       redef fun to_cstring is cached do
+       redef var to_cstring is lazy do

                var len = length
                var ns = new NativeString(len + 1)
                ns[len] = '\0'
                var len = length
                var ns = new NativeString(len + 1)
                ns[len] = '\0'

@@ -94,10 +98,8 @@ private class Concat
        # Right child of the node
        var right: String
 
        # Right child of the node
        var right: String
 

-       init(l: String, r: String) is old_style_init do
-               left = l
-               right = r
-               length = l.length + r.length
+       init do
+               length = left.length + right.length

        end
 
        redef fun output do
        end
 
        redef fun output do

@@ -151,10 +153,30 @@ private class Concat
                else
                        var r = right
                        var rlen = r.length
                else
                        var r = right
                        var rlen = r.length

-                       if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
+                       if rlen + slen > maxlen then return new Concat(self, s)

                        return new Concat(left, r + s)
                end
        end
                        return new Concat(left, r + s)
                end
        end

+
+       redef fun copy_to_native(dest, n, src_offset, dest_offset) do
+               var subs = new RopeSubstrings.from(self, src_offset)
+               var st = src_offset - subs.pos
+               var off = dest_offset
+               while n > 0 do
+                       var it = subs.item
+                       if n > it.length then
+                               var cplen = it.length - st
+                               it.items.copy_to(dest, cplen, st, off)
+                               off += cplen
+                               n -= cplen
+                       else
+                               it.items.copy_to(dest, n, st, off)
+                               n = 0
+                       end
+                       subs.next
+                       st = 0
+               end
+       end

 end
 
 # Mutable `Rope`, optimized for concatenation operations
 end
 
 # Mutable `Rope`, optimized for concatenation operations

@@ -175,7 +197,7 @@ class RopeBuffer
        super Rope
        super Buffer
 
        super Rope
        super Buffer
 

-       redef fun chars: Sequence[Char] is cached do return new RopeBufferChars(self)
+       redef var chars: Sequence[Char] is lazy do return new RopeBufferChars(self)

 
        # The final string being built on the fly
        private var str: String is noinit
 
        # The final string being built on the fly
        private var str: String is noinit

@@ -202,7 +224,7 @@ class RopeBuffer
        # mutable native string (`ns`)
        private var buf_size: Int is noinit
 
        # mutable native string (`ns`)
        private var buf_size: Int is noinit
 

-       redef fun substrings: Iterator[String] do return new RopeBufSubstringIterator(self)
+       redef fun substrings do return new RopeBufSubstringIterator(self)

 
        # Builds an empty `RopeBuffer`
        init do
 
        # Builds an empty `RopeBuffer`
        init do

@@ -229,6 +251,7 @@ class RopeBuffer
                var nns = new NativeString(buf_size)
                var blen = rpos - dumped
                ns.copy_to(nns, blen, dumped, 0)
                var nns = new NativeString(buf_size)
                var blen = rpos - dumped
                ns.copy_to(nns, blen, dumped, 0)

+               ns = nns

                dumped = 0
                rpos = blen
                written = false
                dumped = 0
                rpos = blen
                written = false

@@ -240,6 +263,11 @@ class RopeBuffer
                str = ""
                length = 0
                rpos = 0
                str = ""
                length = 0
                rpos = 0

+               dumped = 0
+               if written then
+                       ns = new NativeString(buf_size)
+                       written = false
+               end

        end
 
        redef fun substring(from, count) do
        end
 
        redef fun substring(from, count) do

@@ -277,15 +305,7 @@ class RopeBuffer
                var slen = s.length
                length += slen
                var rp = rpos
                var slen = s.length
                length += slen
                var rp = rpos

-               if s isa Rope 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
-               if slen > maxlen then
+               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
                        if rp > 0 and dumped != rp then
                                str += new FlatString.with_infos(ns, rp - dumped, dumped, rp - 1)
                                dumped = rp

@@ -325,12 +345,11 @@ class RopeBuffer
                        return
                end
                if slen <= remsp then
                        return
                end
                if slen <= remsp then

-                       sits.copy_to(ns, slen, begin, rp)
-                       if rp == buf_size then
-                               rpos = buf_size
+                       if remsp <= 0 then

                                dump_buffer
                                rpos = 0
                        else
                                dump_buffer
                                rpos = 0
                        else

+                               sits.copy_to(ns, slen, begin, rp)

                                rpos += slen
                        end
                else
                                rpos += slen
                        end
                else

@@ -345,14 +364,13 @@ class RopeBuffer
 
        redef fun add(c) do
                var rp = rpos
 
        redef fun add(c) do
                var rp = rpos

-               length += 1
-               ns[rp] = c
-               rp += 1
-               if rp == buf_size then
-                       rpos = rp
+               if rp >= buf_size then

                        dump_buffer
                        rp = 0
                end
                        dump_buffer
                        rp = 0
                end

+               ns[rp] = c
+               rp += 1
+               length += 1

                rpos = rp
        end
 
                rpos = rp
        end
 

@@ -392,15 +410,12 @@ class RopeBuffer
        end
 
        redef fun reverse do
        end
 
        redef fun reverse do

-               str = str.reversed
-               var nns = new NativeString(buf_size)
-               var j = rpos
-               var mits = ns
-               for i in [0 .. rpos[ do
-                       nns[i] = mits[j]
-                       j -= 1
+               # 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
                end

-               ns = nns
+               str = str.reversed

        end
 
        redef fun upper do
        end
 
        redef fun upper do

@@ -626,7 +641,7 @@ private class ReverseRopeSubstrings
 
        redef fun next do
                if pos < 0 then return
 
        redef fun next do
                if pos < 0 then return

-               var curr: nullable RopeIterPiece = iter.prev
+               var curr = iter.prev

                var currit = curr.node
                while curr != null do
                        currit = curr.node
                var currit = curr.node
                while curr != null do
                        currit = curr.node

@@ -653,12 +668,12 @@ private class ReverseRopeSubstrings
 end
 
 private class RopeBufSubstringIterator
 end
 
 private class RopeBufSubstringIterator

-       super Iterator[String]
+       super Iterator[FlatText]

 
        # Iterator on the substrings of the building string
 
        # Iterator on the substrings of the building string

-       var iter: Iterator[String]
+       var iter: Iterator[FlatText]

        # Makes a String out of the buffered part of the Ropebuffer
        # Makes a String out of the buffered part of the Ropebuffer

-       var nsstr: String
+       var nsstr: FlatString

        # Did we attain the buffered part ?
        var nsstr_done = false
 
        # Did we attain the buffered part ?
        var nsstr_done = false
 

@@ -687,7 +702,7 @@ end
 
 # Substrings of a Rope (i.e. Postfix iterator on leaves)
 private class RopeSubstrings
 
 # Substrings of a Rope (i.e. Postfix iterator on leaves)
 private class RopeSubstrings

-       super IndexedIterator[String]
+       super IndexedIterator[FlatString]

 
        # Visit Stack
        var iter: RopeIterPiece is noinit
 
        # Visit Stack
        var iter: RopeIterPiece is noinit

@@ -697,7 +712,7 @@ private class RopeSubstrings
        var max: Int is noinit
 
        # Current leaf
        var max: Int is noinit
 
        # Current leaf

-       var str: String is noinit
+       var str: FlatString is noinit

 
        init(root: RopeString) is old_style_init do
                var r = new RopeIterPiece(root, true, false, null)
 
        init(root: RopeString) is old_style_init do
                var r = new RopeIterPiece(root, true, false, null)

@@ -709,7 +724,7 @@ private class RopeSubstrings
                                rnod = rnod.left
                                r = new RopeIterPiece(rnod, true, false, r)
                        else
                                rnod = rnod.left
                                r = new RopeIterPiece(rnod, true, false, r)
                        else

-                               str = rnod
+                               str = rnod.as(FlatString)

                                r.rdone = true
                                iter = r
                                break
                                r.rdone = true
                                iter = r
                                break

@@ -734,7 +749,7 @@ private class RopeSubstrings
                                        r = new RopeIterPiece(rnod, true, false, r)
                                end
                        else
                                        r = new RopeIterPiece(rnod, true, false, r)
                                end
                        else

-                               str = rnod
+                               str = rnod.as(FlatString)

                                r.rdone = true
                                iter = r
                                self.pos = pos - off
                                r.rdone = true
                                iter = r
                                self.pos = pos - off

@@ -753,12 +768,12 @@ private class RopeSubstrings
                pos += str.length
                if pos > max then return
                var it = iter.prev
                pos += str.length
                if pos > max then return
                var it = iter.prev

-               var rnod: String = it.node
+               var rnod = it.node

                loop
                        if not rnod isa Concat then
                                it.ldone = true
                                it.rdone = true
                loop
                        if not rnod isa Concat then
                                it.ldone = true
                                it.rdone = true

-                               str = rnod
+                               str = rnod.as(FlatString)

                                iter = it.as(not null)
                                break
                        end
                                iter = it.as(not null)
                                break
                        end

@@ -783,17 +798,15 @@ end
 private class RopeChars
        super StringCharView
 
 private class RopeChars
        super StringCharView
 

-       var tgt: RopeString
-
-       init(s: RopeString) is old_style_init do tgt = s
+       redef type SELFTYPE: RopeString

 
        redef fun [](i) do
 
        redef fun [](i) do

-               return tgt[i]
+               return target[i]

        end
 
        end
 

-       redef fun iterator_from(i) do return new RopeIter.from(tgt, i)
+       redef fun iterator_from(i) do return new RopeIter.from(target, i)

 
 

-       redef fun reverse_iterator_from(i) do return new RopeReviter.from(tgt, i)
+       redef fun reverse_iterator_from(i) do return new RopeReviter.from(target, i)

 
 end
 
 
 end
 

@@ -813,7 +826,7 @@ class RopeBufferIter
        # Maximum position iterable.
        var maxpos: Int
 
        # Maximum position iterable.
        var maxpos: Int
 

-       redef var index: Int
+       redef var index

 
        # Init the iterator from a RopeBuffer.
        init(t: RopeBuffer) is old_style_init do
 
        # Init the iterator from a RopeBuffer.
        init(t: RopeBuffer) is old_style_init do

@@ -863,7 +876,7 @@ class RopeBufferReviter
        # Current position in `ns`.
        var pns: Int
 
        # Current position in `ns`.
        var pns: Int
 

-       redef var index: Int
+       redef var index

 
        # Init the iterator from a RopeBuffer.
        init(tgt: RopeBuffer) is old_style_init do
 
        # Init the iterator from a RopeBuffer.
        init(tgt: RopeBuffer) is old_style_init do