Safe Haskell	None
Language	Haskell2010

Treap.Rand

Contents

Data structure
Smart constructors
Query functions
Cuts and joins
Modification functions
General purpose functions
Pretty printing functions

Description

Fair implementation of the Treap data structure that uses random generator for priorities.

Synopsis

data RTreap m a = RTreap {
- rTreapGen :: !PureMT
- rTreapTree :: !(Treap m a)
}
emptyWithGen :: PureMT -> RTreap m a
oneWithGen :: Measured m a => PureMT -> a -> RTreap m a
empty :: RTreap m a
one :: Measured m a => a -> RTreap m a
size :: RTreap m a -> Int
at :: Int -> RTreap m a -> Maybe a
query :: forall m a. Measured m a => Int -> Int -> RTreap m a -> m
splitAt :: forall m a. Measured m a => Int -> RTreap m a -> (RTreap m a, RTreap m a)
merge :: Measured m a => RTreap m a -> RTreap m a -> RTreap m a
take :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a
drop :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a
rotate :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a
insert :: forall m a. Measured m a => Int -> a -> RTreap m a -> RTreap m a
delete :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a
withTreap :: (Treap m a -> r) -> RTreap m a -> r
overTreap :: (Treap m a -> Treap m a) -> RTreap m a -> RTreap m a
prettyPrint :: forall m a. (Coercible m a, Show a) => RTreap m a -> IO ()

Data structure

data RTreap m a Source #

Specialized version of Treap where priority is generated by the stored random generator.

Constructors

RTreap
Fields rTreapGen :: !PureMT rTreapTree :: !(Treap m a)

Instances

Monoid m => Measured m (RTreap m a) Source #	$ O(1) $. Takes cached value from the root.
Instance details Defined in Treap.Rand Methods measure :: RTreap m a -> m Source #
Foldable (RTreap m) Source #
Instance details Defined in Treap.Rand Methods fold :: Monoid m0 => RTreap m m0 -> m0 # foldMap :: Monoid m0 => (a -> m0) -> RTreap m a -> m0 # foldr :: (a -> b -> b) -> b -> RTreap m a -> b # foldr' :: (a -> b -> b) -> b -> RTreap m a -> b # foldl :: (b -> a -> b) -> b -> RTreap m a -> b # foldl' :: (b -> a -> b) -> b -> RTreap m a -> b # foldr1 :: (a -> a -> a) -> RTreap m a -> a # foldl1 :: (a -> a -> a) -> RTreap m a -> a # toList :: RTreap m a -> [a] # null :: RTreap m a -> Bool # length :: RTreap m a -> Int # elem :: Eq a => a -> RTreap m a -> Bool # maximum :: Ord a => RTreap m a -> a # minimum :: Ord a => RTreap m a -> a # sum :: Num a => RTreap m a -> a # product :: Num a => RTreap m a -> a #
Measured m a => IsList (RTreap m a) Source #	Pure implementation of `RTreap` construction functions. Uses `empty :: RTreap k a` as a starting point. Functions have the following time complexity: `fromList`: $ O(n\ \log \ n) $ `toList`: $ O(n) $ `>>>` `prettyPrint $ fromList @(RTreap (Sum Int) Int) [1..5]` 5,15:2 ╱╲ ╱ ╲ ╱ ╲ ╱ ╲ 1,1:1 3,12:4 ╱╲ ╱ ╲ ╱ ╲ 1,3:3 1,5:5
Instance details Defined in Treap.Rand Associated Types type Item (RTreap m a) :: Type # Methods fromList :: [Item (RTreap m a)] -> RTreap m a # fromListN :: Int -> [Item (RTreap m a)] -> RTreap m a # toList :: RTreap m a -> [Item (RTreap m a)] #
(Eq m, Eq a) => Eq (RTreap m a) Source #	$ O(n) $. This instance doesn't compare random generators inside trees.
Instance details Defined in Treap.Rand Methods (==) :: RTreap m a -> RTreap m a -> Bool # (/=) :: RTreap m a -> RTreap m a -> Bool #
(Show m, Show a) => Show (RTreap m a) Source #
Instance details Defined in Treap.Rand Methods showsPrec :: Int -> RTreap m a -> ShowS # show :: RTreap m a -> String # showList :: [RTreap m a] -> ShowS #
Generic (RTreap m a) Source #
Instance details Defined in Treap.Rand Associated Types type Rep (RTreap m a) :: Type -> Type # Methods from :: RTreap m a -> Rep (RTreap m a) x # to :: Rep (RTreap m a) x -> RTreap m a #
(NFData m, NFData a) => NFData (RTreap m a) Source #
Instance details Defined in Treap.Rand Methods rnf :: RTreap m a -> () #
type Rep (RTreap m a) Source #
Instance details Defined in Treap.Rand type Rep (RTreap m a) = D1 (MetaData "RTreap" "Treap.Rand" "treap-0.0.0.0-5jWw5ZFdWFjIs5c8K2QNdd" False) (C1 (MetaCons "RTreap" PrefixI True) (S1 (MetaSel (Just "rTreapGen") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 PureMT) :*: S1 (MetaSel (Just "rTreapTree") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Treap m a))))
type Item (RTreap m a) Source #
Instance details Defined in Treap.Rand type Item (RTreap m a) = a

Smart constructors

emptyWithGen :: PureMT -> RTreap m a Source #

$ O(1) $. Create empty RTreap with given random generator.

oneWithGen :: Measured m a => PureMT -> a -> RTreap m a Source #

$ O(1) $. Create singleton RTreap with given random generator.

empty :: RTreap m a Source #

$ O(1) $. Create empty RTreap using random generator with seed 0.

one :: Measured m a => a -> RTreap m a Source #

$ O(1) $. Create singleton RTreap using random generator with seed 0.

Query functions

size :: RTreap m a -> Int Source #

$ O(1) $. Returns the size of the RTreap.

Properties:

$ \forall (t\ ::\ \mathrm{Treap}\ m\ a)\ .\ \mathrm{size}\ t \geqslant 0 $

at :: Int -> RTreap m a -> Maybe a Source #

$ O(\log \ n) $. Lookup a value by a given key inside RTreap.

query :: forall m a. Measured m a => Int -> Int -> RTreap m a -> m Source #

$ O(\log \ n) $. Return value of monoidal accumulator on a segment [l, r).

Cuts and joins

splitAt :: forall m a. Measured m a => Int -> RTreap m a -> (RTreap m a, RTreap m a) Source #

$ O(\log \ n) $. Lifted to RTreap version of splitAt.

merge :: Measured m a => RTreap m a -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Lifted to RTreap version of merge.

take :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Lifted to RTreap version of take.

drop :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Lifted to RTreap version of drop.

rotate :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Lifted to RTreap version of rotate.

Modification functions

insert :: forall m a. Measured m a => Int -> a -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Insert a value into RTreap by given key.

delete :: forall m a. Measured m a => Int -> RTreap m a -> RTreap m a Source #

$ O(\log \ n) $. Delete RTreap node that contains given key. If there is no such key, RTreap remains unchanged.

General purpose functions

withTreap :: (Treap m a -> r) -> RTreap m a -> r Source #

Lift a function that works with Treap to RTreap.

overTreap :: (Treap m a -> Treap m a) -> RTreap m a -> RTreap m a Source #

Lift a function that works with Treap to RTreap.

Pretty printing functions

prettyPrint :: forall m a. (Coercible m a, Show a) => RTreap m a -> IO () Source #

Pretty prints RTreap without printing random generator.

Monoid m => Measured m (RTreap m a) Source #	\( O(1) \). Takes cached value from the root.
Instance details Defined in Treap.Rand Methods measure :: RTreap m a -> m Source #
Foldable (RTreap m) Source #
Instance details Defined in Treap.Rand Methods fold :: Monoid m0 => RTreap m m0 -> m0 # foldMap :: Monoid m0 => (a -> m0) -> RTreap m a -> m0 # foldr :: (a -> b -> b) -> b -> RTreap m a -> b # foldr' :: (a -> b -> b) -> b -> RTreap m a -> b # foldl :: (b -> a -> b) -> b -> RTreap m a -> b # foldl' :: (b -> a -> b) -> b -> RTreap m a -> b # foldr1 :: (a -> a -> a) -> RTreap m a -> a # foldl1 :: (a -> a -> a) -> RTreap m a -> a # toList :: RTreap m a -> [a] # null :: RTreap m a -> Bool # length :: RTreap m a -> Int # elem :: Eq a => a -> RTreap m a -> Bool # maximum :: Ord a => RTreap m a -> a # minimum :: Ord a => RTreap m a -> a # sum :: Num a => RTreap m a -> a # product :: Num a => RTreap m a -> a #
Measured m a => IsList (RTreap m a) Source #	Pure implementation of `RTreap` construction functions. Uses `empty :: RTreap k a` as a starting point. Functions have the following time complexity: `fromList`: \( O(n\ \log \ n) \) `toList`: \( O(n) \) `>>>` `prettyPrint $ fromList @(RTreap (Sum Int) Int) [1..5]` 5,15:2 ╱╲ ╱ ╲ ╱ ╲ ╱ ╲ 1,1:1 3,12:4 ╱╲ ╱ ╲ ╱ ╲ 1,3:3 1,5:5
Instance details Defined in Treap.Rand Associated Types type Item (RTreap m a) :: Type # Methods fromList :: [Item (RTreap m a)] -> RTreap m a # fromListN :: Int -> [Item (RTreap m a)] -> RTreap m a # toList :: RTreap m a -> [Item (RTreap m a)] #
(Eq m, Eq a) => Eq (RTreap m a) Source #	\( O(n) \). This instance doesn't compare random generators inside trees.
Instance details Defined in Treap.Rand Methods (==) :: RTreap m a -> RTreap m a -> Bool # (/=) :: RTreap m a -> RTreap m a -> Bool #
(Show m, Show a) => Show (RTreap m a) Source #
Instance details Defined in Treap.Rand Methods showsPrec :: Int -> RTreap m a -> ShowS # show :: RTreap m a -> String # showList :: [RTreap m a] -> ShowS #
Generic (RTreap m a) Source #
Instance details Defined in Treap.Rand Associated Types type Rep (RTreap m a) :: Type -> Type # Methods from :: RTreap m a -> Rep (RTreap m a) x # to :: Rep (RTreap m a) x -> RTreap m a #
(NFData m, NFData a) => NFData (RTreap m a) Source #
Instance details Defined in Treap.Rand Methods rnf :: RTreap m a -> () #
type Rep (RTreap m a) Source #
Instance details Defined in Treap.Rand type Rep (RTreap m a) = D1 (MetaData "RTreap" "Treap.Rand" "treap-0.0.0.0-5jWw5ZFdWFjIs5c8K2QNdd" False) (C1 (MetaCons "RTreap" PrefixI True) (S1 (MetaSel (Just "rTreapGen") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 PureMT) :*: S1 (MetaSel (Just "rTreapTree") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Treap m a))))
type Item (RTreap m a) Source #
Instance details Defined in Treap.Rand type Item (RTreap m a) = a