Quickrope: purefunctional 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 subbranch is not more than twice the size of the secondtolargest branch. This ensures the selfbalancing 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 geometricallyexpading dynamic arrays. Currently, the only local operations implemented is insertion at the beginning or end of the sequence.
Source
Quickrope /
Filename  Size  Date modified  Message 

1.4 KB

…  
13.9 KB

… 