-- Initial order-statistic-tree.cabal generated by cabal init.  For further
--  documentation, see http://haskell.org/cabal/users-guide/

name:                order-statistic-tree
version:             0.1.1.1
synopsis:            Order statistic trees based on weight-balanced trees
description:         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
                     .
                     - Hirai, Yoichi, and Kazuhiko Yamamoto. "Balancing weight-balanced trees." Journal of Functional Programming 21.03 (2011): 287-307.
                     .
                     Also some code is based on containers package.
                     .
                     Implementation of order statistic tree is described in
                     .
                     - Cormen, T.H., Leiserson, Rivest, Stein. Introduction to algorithms. The MIT Press. 3rd ed.
                     .
                     = Benchmarks
                     .
                     I tried to make this tree as fast as possible. The results on my i7-4790 with 16Gb RAM are following:
                     .
                     - OSTree was created from 1.000.000 random numbers in 1.987 ± 0.015 s (e.g. for Data.Map.Strict - 2.081 ± 0.008 s);
                     - deletion from OSTree with 1.000.000 random numbers was made in 13.88 ± 0.14 ms;
                     - lookup from OSTree with 1.000.000 random numbers was made in 164.8 ± 1.06 ns;
                     - selection from OSTree with 1.000.000 random numbers was made in 56.54 ± 0.99 ns;
                     - full testing protocol can be found in result-bench.txt.
license:             BSD3
license-file:        LICENSE
author:              Mansur Ziiatdinov
maintainer:          mz@lambdasoft.ru
copyright:           Lambda Kazan, 2016
category:            Data
build-type:          Simple
extra-source-files:  README.md CHANGELOG.md
cabal-version:       >=1.10

library
  exposed-modules:     Data.OSTree
  other-modules:       Data.OSTree.Types, Data.OSTree.Internal
  -- other-extensions:    
  build-depends:       base >=4.8 && <5
  hs-source-dirs:      src
  default-language:    Haskell2010

test-suite test-ost
  type:                exitcode-stdio-1.0
  hs-source-dirs:      src, test
  main-is:             Spec.hs
  build-depends:       base >=4.8 && <5
                     , order-statistic-tree
                     , tasty >=0.11
                     , tasty-hunit >=0.9.2
                     , tasty-quickcheck >=0.8.4
  default-language:    Haskell2010

benchmark bench-ost
  type:                exitcode-stdio-1.0
  hs-source-dirs:      src, bench
  main-is:             Bench.hs
  build-depends:       base >=4.8 && <5
                     , order-statistic-tree
                     , criterion >=1.1.0.0
                     , containers >=0.5
                     , deepseq >=1.4 && <1.5
                     , random >=1.1 && <1.2
  default-language:    Haskell2010


source-repository head
  type:     git
  location: https://github.com/lambdakazan/ostree.git