structures-0.2: "Advanced" Data Structures

Safe HaskellNone

Data.Vector.Set

Description

A non-standard zeroless-binary deamortized cache-oblivious Set

Synopsis

Documentation

data Set a Source

Constructors

S0 
S1 !(Array a) 
S2 !(Array a) !(Array a) !(Partial (Array a)) !(Set a) 
S3 !(Array a) !(Array a) !(Array a) !(Partial (Array a)) !(Set a) 

Instances

Show (Array a) => Show (Set a) 

size :: Set a -> IntSource

O(log n) gives a conservative upper bound on size, assuming no collisions

insert :: (Arrayed a, Ord a) => a -> Set a -> Set aSource

O(log n) worst case

member :: (Arrayed a, Ord a) => a -> Set a -> BoolSource

O(log^n) worst and amortized

member1 :: (Arrayed a, Ord a) => a -> Array a -> BoolSource

merge :: (Arrayed a, Ord a) => Array a -> Array a -> Partial (Array a)Source

search :: (Int -> Bool) -> Int -> Int -> IntSource

Offset binary search

Assuming l <= h. Returns h if the predicate is never True over [l..h)