-- 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.0.0
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 2.087 ± 0.021 s (e.g. for Data.Map.Strict - 1.977 ± 0.016 s);
                     - deletion from OSTree with 1.000.000 random numbers was made in 13.94 ± 0.93 ms;
                     - lookup from OSTree with 1.000.000 random numbers was made in 208.2 ± 3.48 ns;
                     - selection from OSTree with 1.000.000 random numbers was made in 92.72 ± 1.91 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:  
cabal-version:       >=1.10

library
  exposed-modules:     Data.OSTree
  -- other-modules:       
  -- other-extensions:    
  build-depends:       base >=4.8 && <4.9
  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 && <4.9
                     , order-statistic-tree
                     , tasty >=0.11 && <0.12
                     , tasty-hunit >=0.9.2 && <0.10
                     , tasty-quickcheck >=0.8.4 && <0.9
  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 && <4.9
                     , order-statistic-tree
                     , criterion >=1.1.0.0 && <1.2
                     , containers >=0.5 && <0.6
                     , 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