1. Michele Bini
  2. Finger-deques


Finger-deques /

Filename Size Date modified Message
1.5 KB
1.3 KB
409 B
2.7 KB
167 B
5.9 KB
169 B
3.5 KB
Deques for Mythryl based on finger trees, with amortized O(1)
complexity, and O(log n) worst case operations.

This code implements deques using finger trees.

Previous implementations of deques (e.g. in Haskell) were based on 2-3
trees with size-annotating nodes.

This code was written in Mythryl: http://www.mythryl.org

* Description

This implementation is based on finger trees of plain, always balanced
binary trees; to this effect the finger structure has been modified to
allow easy assembling and disassembling of trees, by intermixing trees
with items.  This should reduce code size and improve performance, in
addition to remove the need for additional rebalancing steps.

* Copyright

Copyright (c) 2012 Michele Bini <michele.bini@gmail.com>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
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/>.