Treap.Pure

Pure efficient implementation of the implicit treap data structure with the segment tree interface.

NOTE: Letter \( d \) in the documentation below means depth of the tree. Real depth depends on the strategy for creating Priority. If the strategy is poor, the depth can be linear. However, if priorities are generated randomly, expected depth is \( O(\log \ n) \).

Data structure

newtype Size

Size of the Treap data structure. Guaranteed to be always non-negative.

Constructors

Size

Fields

• unSize :: Int

Instances

Eq Size

Defined in Treap.Pure

Methods

(==) :: Size -> Size -> Bool

(/=) :: Size -> Size -> Bool

Num Size

Defined in Treap.Pure

Methods

(+) :: Size -> Size -> Size

(-) :: Size -> Size -> Size

(*) :: Size -> Size -> Size

negate :: Size -> Size

abs :: Size -> Size

signum :: Size -> Size

fromInteger :: Integer -> Size

Ord Size

Defined in Treap.Pure

Methods

compare :: Size -> Size -> Ordering

(<) :: Size -> Size -> Bool

(<=) :: Size -> Size -> Bool

(>) :: Size -> Size -> Bool

(>=) :: Size -> Size -> Bool

max :: Size -> Size -> Size

min :: Size -> Size -> Size

Read Size

Defined in Treap.Pure

Methods

readsPrec :: Int -> ReadS Size

readList :: ReadS [Size]

readPrec :: ReadPrec Size

readListPrec :: ReadPrec [Size]

Show Size

Defined in Treap.Pure

Methods

showsPrec :: Int -> Size -> ShowS

show :: Size -> String

showList :: [Size] -> ShowS

Generic Size

Defined in Treap.Pure

Associated Types

type Rep Size :: Type -> Type

Methods

from :: Size -> Rep Size x

to :: Rep Size x -> Size

NFData Size

Defined in Treap.Pure

Methods

rnf :: Size -> ()

type Rep Size

Defined in Treap.Pure

type Rep Size = D1 (MetaData "Size" "Treap.Pure" "treap-0.0.0.0-5jWw5ZFdWFjIs5c8K2QNdd" True) (C1 (MetaCons "Size" PrefixI True) (S1 (MetaSel (Just "unSize") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int)))

newtype Priority

Priority in the Treap data structure.

Constructors

Priority

Fields

• unPriority :: Word64

Instances

Eq Priority

Defined in Treap.Pure

Methods

(==) :: Priority -> Priority -> Bool

(/=) :: Priority -> Priority -> Bool

Ord Priority

Defined in Treap.Pure

Methods

compare :: Priority -> Priority -> Ordering

(<) :: Priority -> Priority -> Bool

(<=) :: Priority -> Priority -> Bool

(>) :: Priority -> Priority -> Bool

(>=) :: Priority -> Priority -> Bool

max :: Priority -> Priority -> Priority

min :: Priority -> Priority -> Priority

Read Priority

Defined in Treap.Pure

Methods

readsPrec :: Int -> ReadS Priority

readList :: ReadS [Priority]

readPrec :: ReadPrec Priority

readListPrec :: ReadPrec [Priority]

Show Priority

Defined in Treap.Pure

Methods

showsPrec :: Int -> Priority -> ShowS

show :: Priority -> String

showList :: [Priority] -> ShowS

Generic Priority

Defined in Treap.Pure

Associated Types

type Rep Priority :: Type -> Type

Methods

from :: Priority -> Rep Priority x

to :: Rep Priority x -> Priority

NFData Priority

Defined in Treap.Pure

Methods

rnf :: Priority -> ()

type Rep Priority

Defined in Treap.Pure

type Rep Priority = D1 (MetaData "Priority" "Treap.Pure" "treap-0.0.0.0-5jWw5ZFdWFjIs5c8K2QNdd" True) (C1 (MetaCons "Priority" PrefixI True) (S1 (MetaSel (Just "unPriority") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word64)))

data Treap m a

Treap data structure.

Constructors

Node !Size !Priority !m a !(Treap m a) !(Treap m a)

Empty

Instances

Monoid m => Measured m (Treap m a)

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

Defined in Treap.Pure

Methods

measure :: Treap m a -> m

Foldable (Treap m)

Defined in Treap.Pure

Methods

fold :: Monoid m0 => Treap m m0 -> m0

foldMap :: Monoid m0 => (a -> m0) -> Treap m a -> m0

foldr :: (a -> b -> b) -> b -> Treap m a -> b

foldr' :: (a -> b -> b) -> b -> Treap m a -> b

foldl :: (b -> a -> b) -> b -> Treap m a -> b

foldl' :: (b -> a -> b) -> b -> Treap m a -> b

foldr1 :: (a -> a -> a) -> Treap m a -> a

foldl1 :: (a -> a -> a) -> Treap m a -> a

toList :: Treap m a -> [a]

null :: Treap m a -> Bool

length :: Treap m a -> Int

elem :: Eq a => a -> Treap m a -> Bool

maximum :: Ord a => Treap m a -> a

minimum :: Ord a => Treap m a -> a

sum :: Num a => Treap m a -> a

product :: Num a => Treap m a -> a

Measured m a => IsList (Treap m a)

This instance allows to create Treap from the list of triples. If all priorities are random then the expected performance of the fromList function is \( O(n\ \log \ n)\).

TODO: It's possible to implement \( O(n) \) algorithm however. See issue #15: https://github.com/chshersh/treap/issues/15

Defined in Treap.Pure

Associated Types

type Item (Treap m a) :: Type

Methods

fromList :: [Item (Treap m a)] -> Treap m a

fromListN :: Int -> [Item (Treap m a)] -> Treap m a

toList :: Treap m a -> [Item (Treap m a)]

(Eq m, Eq a) => Eq (Treap m a)

Defined in Treap.Pure

Methods

(==) :: Treap m a -> Treap m a -> Bool

(/=) :: Treap m a -> Treap m a -> Bool

(Read m, Read a) => Read (Treap m a)

Defined in Treap.Pure

Methods

readsPrec :: Int -> ReadS (Treap m a)

readList :: ReadS [Treap m a]

readPrec :: ReadPrec (Treap m a)

readListPrec :: ReadPrec [Treap m a]

(Show m, Show a) => Show (Treap m a)

Defined in Treap.Pure

Methods

showsPrec :: Int -> Treap m a -> ShowS

show :: Treap m a -> String

showList :: [Treap m a] -> ShowS

Generic (Treap m a)

Defined in Treap.Pure

Associated Types

type Rep (Treap m a) :: Type -> Type

Methods

from :: Treap m a -> Rep (Treap m a) x

to :: Rep (Treap m a) x -> Treap m a

(NFData m, NFData a) => NFData (Treap m a)

Defined in Treap.Pure

Methods

rnf :: Treap m a -> ()

type Rep (Treap m a)

Defined in Treap.Pure

type Rep (Treap m a) = D1 (MetaData "Treap" "Treap.Pure" "treap-0.0.0.0-5jWw5ZFdWFjIs5c8K2QNdd" False) (C1 (MetaCons "Node" PrefixI False) ((S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Size) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Priority) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 m))) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Treap m a)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Treap m a))))) :+: C1 (MetaCons "Empty" PrefixI False) (U1 :: Type -> Type))

type Item (Treap m a)

Defined in Treap.Pure

type Item (Treap m a) = (Priority, a)

Smart constructors

empty :: Treap m a

\( O(1) \). Creates empty Treap.

one :: Measured m a => Priority -> a -> Treap m a

\( O(1) \). Creates singleton Treap.

Query functions

size :: Treap m a -> Size

\( O(1) \). Returns the number of the elements in the Treap. Always non-negative.

Properties:

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

sizeInt :: Treap m a -> Int

Take size of the Treap as Int.

monoid :: Monoid m => Treap m a -> m

\( O(1) \). Returns accumulated value in the root of the tree.

at :: forall m a. Int -> Treap m a -> Maybe a

\( O(d) \). Lookup a value inside Treap by a given index.

query :: forall m a. Measured m a => Int -> Int -> Treap m a -> m

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

Cuts and joins

splitAt :: forall m a. Measured m a => Int -> Treap m a -> (Treap m a, Treap m a)

\( O(d) \). splitAt i t splits Treap by the given index into two treaps (t1, t2) such that the following properties hold:

1. \( \mathrm{size}\ t_1 = i \)
2. \( \mathrm{size}\ t_2 = n - i \)
3. \( \mathrm{merge}\ t_1\ t_2 \equiv t \)

Special cases:

1. If \( i \leqslant 0 \) then the result is (empty, t).
2. If \( i \geqslant n \) then the result is (t, empty).

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

\( O(\max\ d_1\ d_2) \). Merge two Treaps into single one.

>>> pone p a = one (Priority p) a :: Treap (Sum Int) Int
>>> prettyPrint $ merge (merge (pone 1 3) (pone 4 5)) (merge (pone 3 0) (pone 5 9))
   4,17:9
     ╱
   3,8:5
     ╱╲
    ╱  ╲
   ╱    ╲
1,3:3 1,0:0

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

\( O(d) \). take n t returns Treap that contains first n elements of the given Treap t.

Special cases:

1. If \( i \leqslant 0 \) then the result is empty.
2. If \( i \geqslant n \) then the result is t.

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

\( O(d) \). drop n t returns Treap without first n elements of the given Treap t.

Special cases:

1. If \( i \leqslant 0 \) then the result is t.
2. If \( i \geqslant n \) then the result is empty.

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

\( O(d) \). Rotate a Treap to the right by a given number of elements modulo treap size. In simple words, rotate n t takes first n elements of t and puts them at the end of t in the same order. If the given index is negative, then this function rotates left.

Modification functions

insert :: forall m a. Measured m a => Int -> Priority -> a -> Treap m a -> Treap m a

\( O(d) \). Insert a value into Treap with given key and priority. Updates monoidal accumulator accordingly.

delete :: forall m a. Measured m a => Int -> Treap m a -> Treap m a

\( O(d) \). Delete element from Treap by the given index. If index is out of bounds, Treap remains unchanged.

Core internal functions

recalculate :: Measured m a => Treap m a -> Treap m a

\( O(1) \). Calculate size and the value of the monoidal accumulator in the given root node. This function doesn't perform any recursive calls and it assumes that the values in the children are already correct. So use this function only in bottom-up manner.