Treap.Rand

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

Data structure

data RTreap m a

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)

\( O(1) \). Takes cached value from the root.

Defined in Treap.Rand

Methods

measure :: RTreap m a -> m

Foldable (RTreap m)

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)

Pure implementation of RTreap construction functions. Uses empty :: RTreap k a as a starting point. Functions have the following time complexity:

1. fromList: \( O(n\ \log \ n) \)
2. 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

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)

\( O(n) \). This instance doesn't compare random generators inside trees.

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)

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)

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)

Defined in Treap.Rand

Methods

rnf :: RTreap m a -> ()

type Rep (RTreap m a)

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)

Defined in Treap.Rand

type Item (RTreap m a) = a

Smart constructors

emptyWithGen :: PureMT -> RTreap m a

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

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

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

empty :: RTreap m a

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

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

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

Query functions

size :: RTreap m a -> Int

\( 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

\( 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

\( 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)

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

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

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

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

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

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

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

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

\( 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

\( 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

\( 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

Lift a function that works with Treap to RTreap.

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

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 ()

Pretty prints RTreap without printing random generator.