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
!).
core :: union_find
union–find algorithm using an efficient disjoint-set data structurebucketed_game :: bucketed_game
Game framework with an emphasis on efficient event coordinationaccept_scroll_and_zoom
gamnit :: camera_control_android
Two fingers camera manipulation, pinch to zoom and slide to scrollgamnit :: camera_control_linux
Mouse wheel and middle mouse button to control camerapthreads :: concurrent_array_and_barrier
A basic usage example of the modulespthreads
and pthreads::cocurrent_collections
pthreads :: concurrent_collections
Introduces thread-safe concurrent collectionsserialization :: custom_serialization
Example of an ad hoc serializer that is tailored to transform business specific objects into customized representation.egl
, sdl
and x11
FileServer
action, which is a standard and minimal file server
cocoa :: foundation
The Foundation Kit provides basic Objective-C classes and structuresfunctional_types.nit
functional :: functional_types
This module provides functional type to represents various function forms.gtk :: gtk_assistant
gtk :: gtk_dialogs
HttpRequest
class and services to create it
app::http_request
main service AsyncHttpRequest
Serializable::inspect
to show more useful information
Iterator
.
actors :: mandelbrot
Example implemented from "The computer Language Benchmarks Game" - Mandelbrotmarkdown2 :: markdown_html_rendering
HTML rendering of Markdown documentsmarkdown2 :: markdown_latex_rendering
LaTeX rendering of Markdown documentsmarkdown2 :: markdown_man_rendering
Manpages rendering of Markdown documentsmarkdown2 :: markdown_md_rendering
Markdown rendering of Markdown documentsmore_collections :: more_collections
Highly specific, but useful, collections-related classes.mpi :: mpi_simple
curl :: native_curl
Binding of C libCurl which allow us to interact with network.app.nit
on Android using a custom Java entry point
nitcc_runtime :: nitcc_runtime
Runtime library required by parsers and lexers generated by nitccnlp :: nlp_server
glesv2 :: opengles2_hello_triangle
Basic example of OpenGL ES 2.0 usage using SDL 2performance_analysis :: performance_analysis
Services to gather information on the performance of events by categoriesrestful
annotation documented at lib/nitcorn/restful.nit
sax :: sax_locator
Interface for associating a SAX event with a document location.Locator
.
msgpack :: serialization_common
Serialization services forserialization_write
and serialization_read
serialization :: serialization_core
Abstract services to serialize Nit objects to different formatsdeserialize_json
and JsonDeserializer
serialize_to_json
and JsonSerializer
msgpack :: serialization_write
Serialize full Nit objects to MessagePack formatroot
to execute
agent_simulation
by refining the Agent class to make
socket :: socket_simple_server
Simple server example using a non-blockingTCPServer
EulerCamera
and App::frame_core_draw
to get a stereoscopic view
gamnit :: texture_atlas_parser
Tool to parse XML texture atlas and generated Nit code to access subtextures
# 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 :
#
# ~~~raw
# 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 flat
# 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 512
# String using a tree-based representation with leaves as `FlatStrings`
private abstract class Rope
super Text
end
# Node that represents a concatenation between two `String`
private class Concat
super Rope
super String
redef fun chars do return new RopeChars(self)
redef fun bytes do return new RopeBytes(self)
redef var length is noinit
redef var byte_length is noinit
redef fun substrings do return new RopeSubstrings.from(self, 0)
redef fun empty do return ""
# Cache for the latest accessed FlatString in `self`
var flat_cache: FlatString is noinit
# Position of the beginning of `flat_cache` in `self`
var flat_last_pos_start: Int is noinit
redef fun to_cstring do
var len = _byte_length
var ns = new CString(len + 1)
ns[len] = 0
var off = 0
for i in substrings do
var ilen = i._byte_length
i.as(FlatString)._items.copy_to(ns, ilen, i.as(FlatString)._first_byte, off)
off += ilen
end
return ns
end
# Left child of the node
var left: String
# Right child of the node
var right: String
init do
var l = _left
var r = _right
_length = l.length + r.length
_byte_length = l.byte_length + r.byte_length
_flat_last_pos_start = _length
end
redef fun is_empty do return _byte_length == 0
redef fun output do
_left.output
_right.output
end
redef fun iterator do return new RopeCharIterator.from(self, 0)
redef fun *(i) do
var x: String = self
for j in [1 .. i[ do x += self
return x
end
redef fun [](i) do
assert i >= 0 and i < _length
var flps = _flat_last_pos_start
if i >= flps then
var fc = _flat_cache
if i < flps + fc._length then return fc.fetch_char_at(i - flps)
end
var lf = get_leaf_at(i)
return lf.fetch_char_at(i - _flat_last_pos_start)
end
fun get_leaf_at(pos: Int): FlatString do
var flps = _flat_last_pos_start
if pos >= flps then
var fc = _flat_cache
if pos < flps + fc._length then return fc
end
var s: String = self
var st = pos
loop
if s isa FlatString then break
s = s.as(Concat)
var lft = s._left
var llen = lft.length
if pos >= llen then
s = s._right
pos -= llen
else
s = lft
end
end
_flat_last_pos_start = st - pos
_flat_cache = s
return s
end
redef fun substring(from, count) do
if from < 0 then
count += from
if count < 0 then return ""
from = 0
end
var ln = _length
if (count + from) > ln then count = ln - from
if count <= 0 then return ""
var end_index = from + count - 1
var flps = _flat_last_pos_start
if from >= flps then
var fc = _flat_cache
if end_index < flps + fc._length then
return fc.substring_impl(from - flps, count, end_index - flps)
end
end
var lft = _left
var llen = lft.length
if from < llen then
if from + count < llen then return lft.substring(from, count)
var lsublen = llen - from
return lft.substring_from(from) + _right.substring(0, count - lsublen)
else
return _right.substring(from - llen, count)
end
end
redef fun reversed do return new Concat(_right.reversed, _left.reversed)
redef fun insert_at(s, pos) do
var lft = _left
if pos > lft.length then
return lft + _right.insert_at(s, pos - lft.length)
end
return lft.insert_at(s, pos) + _right
end
redef fun to_upper do return new Concat(_left.to_upper, _right.to_upper)
redef fun to_lower do return new Concat(_left.to_lower, _right.to_lower)
redef fun +(o) do
var s = o.to_s
var slen = s.byte_length
if s isa Concat then
return new Concat(self, s)
else
var r = _right
var rlen = r.byte_length
if rlen + slen > maxlen then return new Concat(self, s)
return new Concat(_left, r + s)
end
end
redef fun copy_to_native(dest, n, src_offset, dest_offset) do
var l = _left
if src_offset < l.byte_length then
var lcopy = l.byte_length - src_offset
lcopy = if lcopy > n then n else lcopy
l.copy_to_native(dest, lcopy, src_offset, dest_offset)
dest_offset += lcopy
n -= lcopy
src_offset = 0
end
_right.copy_to_native(dest, n, src_offset, dest_offset)
end
# Returns a balanced version of `self`
fun balance: String do
var children = new Array[String]
var rnod: String
var iter: nullable RopeCharIteratorPiece = new RopeCharIteratorPiece(self, false, false, null)
loop
if iter == null then break
rnod = iter.node
if not rnod isa Concat then
children.push rnod
iter = iter.prev
continue
end
if not iter.ldone then
iter.ldone = true
iter = new RopeCharIteratorPiece(rnod._left, false, false, iter)
else if not iter.rdone then
iter.rdone = true
iter = new RopeCharIteratorPiece(rnod._right, false, false, iter)
else
iter = iter.prev
end
end
return recurse_balance(children, children.length)
end
fun recurse_balance(nodes: Array[String], len: Int): String do
var finpos = 0
var stpos = 0
while stpos < len do
if len - stpos > 1 then
nodes[finpos] = new Concat(nodes[stpos], nodes[stpos + 1])
stpos += 2
else
nodes[finpos] = nodes[stpos]
stpos += 1
end
finpos += 1
end
if finpos == 1 then return nodes[0]
return recurse_balance(nodes, finpos)
end
end
redef class FlatString
redef fun insert_at(s, pos) do
var l = substring(0, pos)
var r = substring_from(pos)
return l + s + r
end
redef fun +(o) do
var s = o.to_s
var slen = s.byte_length
var mlen = _byte_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._first_byte
var mifrom = _first_byte
var sits = s._items
var ns = new CString(nlen + 1)
mits.copy_to(ns, mlen, mifrom, 0)
sits.copy_to(ns, slen, sifrom, mlen)
return new FlatString.full(ns, nlen, 0, length + s.length)
else if s isa Concat then
var sl = s._left
var sllen = sl.byte_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 RopeCharIteratorPiece
# 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 RopeCharIteratorPiece
end
# A reverse iterator capable of working with `Rope` objects
private class RopeByteReverseIterator
super IndexedIterator[Int]
# Current CString
var ns: CString is noautoinit
# Current position in CString
var pns: Int is noautoinit
# Position in the Rope (0-indexed)
var pos: Int is noautoinit
# Iterator on the substrings, does the Postfix part of
# the Rope traversal.
var subs: IndexedIterator[FlatString] is noautoinit
init from(root: Concat, pos: Int) do
self.pos = pos
subs = new ReverseRopeSubstrings.from(root, pos)
var s = subs.item
ns = s._items
pns = pos - subs.index
end
redef fun index do return pos
redef fun is_ok do return pos >= 0
redef fun item do return ns[pns]
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
var s = subs.item
ns = s._items
pns = s.last_byte
end
end
# Forward iterator on the bytes of a `Rope`
private class RopeByteIterator
super IndexedIterator[Int]
# Position in current `String`
var pns: Int is noautoinit
# Current `String` being iterated on
var ns: CString is noautoinit
# Substrings of the Rope
var subs: IndexedIterator[FlatString] is noautoinit
# Maximum position to iterate on (e.g. Rope.byte_length)
var max: Int is noautoinit
# Position (char) in the Rope (0-indexed)
var pos: Int is noautoinit
init from(root: Concat, pos: Int) do
subs = new RopeSubstrings.from(root, pos)
pns = pos - subs.index
self.pos = pos
ns = subs.item._items
max = root.byte_length - 1
end
redef fun item do return ns[pns]
redef fun is_ok do return pos <= max
redef fun index do return pos
redef fun next do
pns += 1
pos += 1
if pns < subs.item._byte_length then return
if not subs.is_ok then return
subs.next
if not subs.is_ok then return
ns = subs.item._items
pns = 0
end
end
# A reverse iterator capable of working with `Rope` objects
private class RopeCharReverseIterator
super IndexedIterator[Char]
# Current CString
var ns: String is noautoinit
# Current position in CString
var pns: Int is noautoinit
# Position in the Rope (0-indexed)
var pos: Int is noautoinit
# Iterator on the substrings, does the Postfix part of
# the Rope traversal.
var subs: IndexedIterator[String] is noautoinit
init from(root: Concat, pos: Int) do
self.pos = pos
subs = new ReverseRopeSubstrings.from(root, pos)
ns = subs.item
pns = pos - subs.index
end
redef fun index do return pos
redef fun is_ok do return pos >= 0
redef fun item do return ns[pns]
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
end
# Forward iterator on the chars of a `Rope`
private class RopeCharIterator
super IndexedIterator[Char]
# Position in current `String`
var pns: Int is noautoinit
# Current `String` being iterated on
var str: String is noautoinit
# Substrings of the Rope
var subs: IndexedIterator[String] is noautoinit
# Maximum position to iterate on (e.g. Rope.length)
var max: Int is noautoinit
# Position (char) in the Rope (0-indexed)
var pos: Int is noautoinit
init from(root: Concat, pos: Int) do
subs = new RopeSubstrings.from(root, pos)
pns = pos - subs.index
self.pos = pos
str = subs.item
max = root.length - 1
end
redef fun item do return str[pns]
redef fun is_ok do return pos <= max
redef fun index do return pos
redef fun next do
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
# Substrings of a Rope (i.e. Reverse postfix iterator on leaves)
private class ReverseRopeSubstrings
super IndexedIterator[FlatString]
# Visit Stack
var iter: RopeCharIteratorPiece is noinit
# Position in `Rope`
var pos: Int is noinit
# Current leaf
var str: FlatString is noinit
init from(root: Concat, pos: Int) do
var r = new RopeCharIteratorPiece(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 RopeCharIteratorPiece(rnod, false, true, r)
else
r.ldone = true
rnod = rnod._left
r = new RopeCharIteratorPiece(rnod, false, true, r)
end
else
str = rnod.as(FlatString)
r.ldone = true
iter = r
self.pos = pos - off
break
end
end
end
redef fun item do return str
redef fun index do return pos
redef fun is_ok do return pos >= 0
redef fun next do
if pos < 0 then return
var curr = iter.prev
var currit = curr.as(not null).node
while curr != null do
currit = curr.node
if not currit isa Concat then
str = currit.as(FlatString)
pos -= str.length
iter = curr
return
end
if not curr.rdone then
curr.rdone = true
curr = new RopeCharIteratorPiece(currit._right, false, false, curr)
continue
end
if not curr.ldone then
curr.ldone = true
curr = new RopeCharIteratorPiece(currit._left, false, false, curr)
continue
end
curr = curr.prev
end
pos = -1
end
end
# Substrings of a Rope (i.e. Postfix iterator on leaves)
private class RopeSubstrings
super IndexedIterator[FlatString]
# Visit Stack
var iter: RopeCharIteratorPiece 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: FlatString is noinit
init from(root: Concat, pos: Int) do
var r = new RopeCharIteratorPiece(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 RopeCharIteratorPiece(rnod, true, false, r)
else
rnod = rnod._left
r = new RopeCharIteratorPiece(rnod, true, false, r)
end
else
str = rnod.as(FlatString)
r.rdone = true
iter = r
self.pos = pos - off
break
end
end
end
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 += str.length
if pos > max then return
var it = iter.prev.as(not null)
var rnod = it.node
loop
if not rnod isa Concat then
it.ldone = true
it.rdone = true
str = rnod.as(FlatString)
iter = it
break
end
if not it.ldone then
rnod = rnod._left
it.ldone = true
it = new RopeCharIteratorPiece(rnod, false, false, it)
else if not it.rdone then
it.rdone = true
rnod = rnod._right
it = new RopeCharIteratorPiece(rnod, false, false, it)
else
it = it.prev.as(not null)
rnod = it.node
continue
end
end
end
end
# Implementation of a `StringCharView` for `Concat` objects
private class RopeChars
super StringCharView
redef type SELFTYPE: Concat
redef fun [](i) do
return target[i]
end
redef fun iterator_from(i) do return new RopeCharIterator.from(target, i)
redef fun reverse_iterator_from(i) do return new RopeCharReverseIterator.from(target, i)
end
# Implementation of a `StringCharView` for `Concat` objects
private class RopeBytes
super StringByteView
redef type SELFTYPE: Concat
var cache: FlatString is noinit
var cache_start: Int = -1
var cache_end: Int = -1
redef fun [](i) do
assert i >= 0 and i < target._byte_length
var flps = _cache_start
if i >= flps and i <= _cache_end then
return _cache.bytes[i - flps]
end
var lf = get_leaf_at(i)
return lf.bytes[i - _cache_start]
end
fun get_leaf_at(pos: Int): FlatString do
var flps = _cache_start
if pos >= flps and pos <= _cache_end then
return _cache
end
var s: String = target
var st = pos
loop
if s isa FlatString then break
s = s.as(Concat)
var lft = s._left
var llen = lft.byte_length
if pos >= llen then
s = s._right
pos -= llen
else
s = lft
end
end
_cache_start = st - pos
_cache_end = st - pos + s.byte_length - 1
_cache = s
return s
end
redef fun iterator_from(i) do return new RopeByteIterator.from(target, i)
redef fun reverse_iterator_from(i) do return new RopeByteReverseIterator.from(target, i)
end
lib/core/text/ropes.nit:15,1--709,3