order-statistic-tree: Order statistic trees based on weight-balanced trees

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

This repository contains an implementation of order statistic tree in Haskell programming language. I could not find an order statistic tree at Hackage, so I have to develop one.

This implementation uses weight-balanced trees which are desribed in

Also some code is based on containers package.

Implementation of order statistic tree is described in

Benchmarks

I tried to make this tree as fast as possible. The results on my i7-4790 with 16Gb RAM are following:


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.1, 0.1.1.0, 0.1.1.1, 0.1.1.1
Change log CHANGELOG.md
Dependencies base (>=4.8 && <5) [details]
License BSD-3-Clause
Copyright Lambda Kazan, 2016
Author Mansur Ziiatdinov
Maintainer mz@lambdasoft.ru
Category Data
Source repo head: git clone https://github.com/lambdakazan/ostree.git
Uploaded by MZiatdinov at 2018-11-02T07:16:44Z

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for order-statistic-tree-0.1.1.1

[back to package description]

Order Statistic Tree

This repository contains an implementation of order statistic tree in Haskell programming language.

I could not find an order statistic tree at Hackage, so I have to develop one.

This implementation uses weight-balanced trees as desribed in

Also some of its code is based on code from containers package.

Implementation of order statistic tree is described in

Installation

This package will be deployed to hackage, so you can install it using cabal:

cabal install order-statistic-tree

Building

cabal configure
cabal build

Testing

cabal configure --enable-tests --enable-benchmarks
cabal test

Benchmarks

I tried to make this tree as fast as possible. I'm not bos, but results on my i7-4790 with 16Gb RAM are following:

cabal configure --enable-tests --enable-benchmarks
cabal bench

If someone knows how to improve these results or benchmarking itself, please don't hesitate to contact me