<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Aug 14, 2014 at 3:59 AM, Ali Çehreli <span dir="ltr"><<a href="mailto:digitalmars-d-learn@puremagic.com" target="_blank">digitalmars-d-learn@puremagic.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="">On 08/13/2014 10:57 PM, Carl Sturtivant wrote:<br>
><br>
> This is the idea I mean.<br>
> <a href="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf" target="_blank">http://citeseer.ist.psu.edu/<u></u>viewdoc/download?doi=10.1.1.<u></u>14.9450&rep=rep1&type=pdf</a> <br>

><br>
> Here's a C++ implementation supported I think by gcc.<br>
> <a href="http://www.sgi.com/tech/stl/Rope.html" target="_blank">http://www.sgi.com/tech/stl/<u></u>Rope.html</a><br>
><br>
> Is there a D implementation of a rope out there somewhere?<br>
<br></div>
I am not aware of any but std.range.chain can be useful:<br></blockquote><div><br></div><div><br></div><div>chain is very limited compared to what ropes provide. Eg: efficient inserting of a string inside a rope, space efficient maintaining of entire edit history, rebalancing, etc.</div>
<div><br></div><div>Ropes are very well suited for various applications (text editors, file system indexing, large scale text processing etc).</div><div><br></div><div>std.rope would be a very welcome addition for real world applications.</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
import std.range;<br>
<br>
void main()<br>
{<br>
    auto r = chain(chain("The qui", "ck brown"), " fox");<br>
    assert(r.equal("The quick brown fox"));<div class=""><br>
}<br>
<br>
> How is unicode handled? Just by using dchar?<br>
<br></div>
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:<br>
<br>
    auto r = chain(chain("The q\xc3", "\xbcick brown"), " fox");<br>
    // std.utf.UTFException@./phobos/<u></u>std/utf.d(1109): Attempted<br>
    // to decode past the end of a string (at index 1)<br>
    assert(r.equal("The qüick brown fox"));<br>
<br>
Of course, it works when the character is complete:<br>
<br>
    auto r = chain(chain("The qü", "ick brown"), " fox");<br>
    assert(r.equal("The qüick brown fox"));<br>
<br>
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.)<br>
<br>
Ali<br>
<br>
</blockquote></div><br></div></div>