Source

Quickrope /

Filename Size Date modified Message
1.3 KB
13.6 KB
Quickrope: pure-functional indexable sequences with O(log log n) local
operations.


Copyright (c) 2011,2012 Michele Bini

This program is free software: you can redistribute it and/or modify
it under the terms of the version 3 of the GNU General Public License
as published by the Free Software Foundation.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.


Implementation details:

Every node maintains the property that the size of the
largest sub-branch is not more than twice the size of the
second-to-largest branch.

This ensures the self-balancing property of the tree.

Each node has 3 subtrees.  The above property permits one of the
subtrees to be arbitrarily smaller than the other two, allowing
to design local operations on the tree with O(log(log(N)) to O(1)
average complexity instead the usual O(log N) for balanced binary
trees.  This makes ropes competitive to (non functional)
gap buffers and geometrically-expading dynamic arrays.

Currently, the only local operations implemented is insertion at the
beginning or end of the sequence.