Data.OSTree

Order Statistic Tree

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 of its 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. I'm not bos, but 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.

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

Documentation

data OSTree a

Order statistic tree with elements of type a

Instances

Eq a => Eq (OSTree a)

Defined in Data.OSTree.Types

Methods

(==) :: OSTree a -> OSTree a -> Bool

(/=) :: OSTree a -> OSTree a -> Bool

Show a => Show (OSTree a)

Defined in Data.OSTree.Types

Methods

showsPrec :: Int -> OSTree a -> ShowS

show :: OSTree a -> String

showList :: [OSTree a] -> ShowS

Generic (OSTree a)

Defined in Data.OSTree.Types

Associated Types

type Rep (OSTree a) :: * -> *

Methods

from :: OSTree a -> Rep (OSTree a) x

to :: Rep (OSTree a) x -> OSTree a

type Rep (OSTree a)

Defined in Data.OSTree.Types

type Rep (OSTree a)

Creating OSTree

empty :: OSTree a

O(1). Returns an empty tree

singleton :: a -> OSTree a

O(1). Returns a tree with single element

Search Tree operations

size :: OSTree a -> Size

Returns size of the tree

insert :: Ord a => a -> OSTree a -> OSTree a

O(log n). Insert the element into the tree

lookup :: Ord a => a -> OSTree a -> Maybe a

O(log n). Lookup the element in the tree

delete :: Ord a => a -> OSTree a -> OSTree a

O(log n). Delete first occurence of the element from the tree

deleteFindMin :: OSTree a -> (a, OSTree a)

O(log n). Delete and find the minimal element.

deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
deleteFindMin                                            Error: can not return the minimal element of an empty map

deleteFindMax :: OSTree a -> (a, OSTree a)

O(log n). Delete and find the maximal element.

deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
deleteFindMax empty                                      Error: can not return the maximal element of an empty map

Conversions

toList :: OSTree a -> [a]

O(n). Return list of elements of the tree

fromList :: Ord a => [a] -> OSTree a

O(n log n). Convert list of elements to the tree

Statistics

select

Arguments

:: OSTree a

tree

-> Int

index i, starting from 1

-> Maybe a

if there are at least i elements, returns i-th least element

O(log n). Returns i-th least element of the tree