Ropes (concatenation trees) for strings in D ?
Ali Çehreli via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Aug 14 03:59:06 PDT 2014
On 08/13/2014 10:57 PM, Carl Sturtivant wrote:
>
> This is the idea I mean.
>
http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf
>
> Here's a C++ implementation supported I think by gcc.
> http://www.sgi.com/tech/stl/Rope.html
>
> Is there a D implementation of a rope out there somewhere?
I am not aware of any but std.range.chain can be useful:
import std.range;
void main()
{
auto r = chain(chain("The qui", "ck brown"), " fox");
assert(r.equal("The quick brown fox"));
}
> How is unicode handled? Just by using dchar?
dchar is not necessary when using the rope as a sequence but it looks
like each section must be a valid UTF-8 sequence. The following example
where a Unicode character (ü) is split between two sections fails:
auto r = chain(chain("The q\xc3", "\xbcick brown"), " fox");
// std.utf.UTFException at ./phobos/std/utf.d(1109): Attempted
// to decode past the end of a string (at index 1)
assert(r.equal("The qüick brown fox"));
Of course, it works when the character is complete:
auto r = chain(chain("The qü", "ick brown"), " fox");
assert(r.equal("The qüick brown fox"));
But yes, for O(1) character access dchar is needed. (As you know, it
can't be exactly O(1) when there are a large amount of sections and one
needs to be memory-efficient for character index lookup.)
Ali
More information about the Digitalmars-d-learn
mailing list