Copyright	(c) Galois Inc 2014-2019
Maintainer	Joe Hendrix <jhendrix@galois.com>
Safe Haskell	Safe
Language	Haskell98

Data.Parameterized.Utils.BinTree

Description

Synopsis

data MaybeS v
- = JustS !v
- | NothingS
fromMaybeS :: a -> MaybeS a -> a
data Updated a
- = Updated !a
- | Unchanged !a
updatedValue :: Updated a -> a
data TreeApp e t
- = BinTree !e !t !t
- | TipTree
class IsBinTree t e | t -> e where
- asBin :: t -> TreeApp e t
- tip :: t
- bin :: e -> t -> t -> t
- size :: t -> Int
balanceL :: IsBinTree c e => e -> c -> c -> c
balanceR :: IsBinTree c e => e -> c -> c -> c
glue :: IsBinTree c e => c -> c -> c
merge :: IsBinTree c e => c -> c -> c
filterGt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
filterLt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
insert :: IsBinTree c e => (e -> e -> Ordering) -> e -> c -> Updated c
delete :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
union :: IsBinTree c e => (e -> e -> Ordering) -> c -> c -> c
link :: IsBinTree c e => e -> c -> c -> c
data PairS f s = PairS !f !s

Documentation

data MaybeS v Source #

A strict version of Maybe

Constructors

JustS !v
NothingS

Instances

Functor MaybeS Source #
Instance details Defined in Data.Parameterized.Utils.BinTree Methods fmap :: (a -> b) -> MaybeS a -> MaybeS b # (<$) :: a -> MaybeS b -> MaybeS a #
Applicative MaybeS Source #
Instance details Defined in Data.Parameterized.Utils.BinTree Methods pure :: a -> MaybeS a # (<>) :: MaybeS (a -> b) -> MaybeS a -> MaybeS b # liftA2 :: (a -> b -> c) -> MaybeS a -> MaybeS b -> MaybeS c # (>) :: MaybeS a -> MaybeS b -> MaybeS b # (<*) :: MaybeS a -> MaybeS b -> MaybeS a #
Alternative MaybeS Source #
Instance details Defined in Data.Parameterized.Utils.BinTree Methods empty :: MaybeS a # (<\|>) :: MaybeS a -> MaybeS a -> MaybeS a # some :: MaybeS a -> MaybeS [a] # many :: MaybeS a -> MaybeS [a] #

fromMaybeS :: a -> MaybeS a -> a Source #

data Updated a Source #

Updated a contains a value that has been flagged on whether it was modified by an operation.

Constructors

Updated !a
Unchanged !a

updatedValue :: Updated a -> a Source #

data TreeApp e t Source #

Constructors

BinTree !e !t !t
TipTree

class IsBinTree t e | t -> e where Source #

Methods

asBin :: t -> TreeApp e t Source #

tip :: t Source #

bin :: e -> t -> t -> t Source #

size :: t -> Int Source #

Instances

IsBinTree (MapF k2 a) (Pair k2 a) Source #
Instance details Defined in Data.Parameterized.Map Methods asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a) Source # tip :: MapF k2 a Source # bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a Source # size :: MapF k2 a -> Int Source #

balanceL :: IsBinTree c e => e -> c -> c -> c Source #

balanceL p l r returns a balanced tree for the sequence l ++ [p] ++ r.

It assumes that l and r are close to being balanced, and that only l may contain too many elements.

balanceR :: IsBinTree c e => e -> c -> c -> c Source #

balanceR p l r returns a balanced tree for the sequence l ++ [p] ++ r.

It assumes that l and r are close to being balanced, and that only r may contain too many elements.

glue :: IsBinTree c e => c -> c -> c Source #

glue l r concatenates l and r.

It assumes that l and r are already balanced with respect to each other.

merge :: IsBinTree c e => c -> c -> c Source #

Concatenate two trees that are ordered with respect to each other.

filterGt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c Source #

Returns only entries that are less than predicate with respect to the ordering and Nothing if no elements are discarded.

filterLt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c Source #

filterLt k m returns submap of m that only contains entries that are smaller than k. If no entries are deleted then return Nothing.

insert :: IsBinTree c e => (e -> e -> Ordering) -> e -> c -> Updated c Source #

insert p m inserts the binding into m. It returns an Unchanged value if the map stays the same size and an updated value if a new entry was inserted.

delete Source #

Arguments

:: IsBinTree c e
=> (e -> Ordering)	Predicate that returns whether the entry is less than, greater than, or equal to the key we are entry that we are looking for.
-> c
-> MaybeS c

union :: IsBinTree c e => (e -> e -> Ordering) -> c -> c -> c Source #

Union two sets

link :: IsBinTree c e => e -> c -> c -> c Source #

link is called to insert a key and value between two disjoint subtrees.

data PairS f s Source #

A Strict pair

Constructors

PairS !f !s