Data.Urn.Internal

Types

Parameters of the trees

type Weight = Word

newtype Index

Constructors

Index

Fields

• getIndex :: Word

Instances

Eq Index

Methods

(==) :: Index -> Index -> Bool

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

Ord Index

Methods

compare :: Index -> Index -> Ordering

(<) :: Index -> Index -> Bool

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

(>) :: Index -> Index -> Bool

(>=) :: Index -> Index -> Bool

max :: Index -> Index -> Index

min :: Index -> Index -> Index

NFData Index

Methods

rnf :: Index -> ()

newtype Size

Constructors

Size

Fields

• getSize :: Word

Instances

Bounded Size

Methods

minBound :: Size

maxBound :: Size

Enum Size

Methods

succ :: Size -> Size

pred :: Size -> Size

toEnum :: Int -> Size

fromEnum :: Size -> Int

enumFrom :: Size -> [Size]

enumFromThen :: Size -> Size -> [Size]

enumFromTo :: Size -> Size -> [Size]

enumFromThenTo :: Size -> Size -> Size -> [Size]

Eq Size

Methods

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

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

Integral Size

Methods

quot :: Size -> Size -> Size

rem :: Size -> Size -> Size

div :: Size -> Size -> Size

mod :: Size -> Size -> Size

quotRem :: Size -> Size -> (Size, Size)

divMod :: Size -> Size -> (Size, Size)

toInteger :: Size -> Integer

Num Size

Methods

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

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

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

negate :: Size -> Size

abs :: Size -> Size

signum :: Size -> Size

fromInteger :: Integer -> Size

Ord Size

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

Real Size

Methods

toRational :: Size -> Rational

Show Size

Methods

showsPrec :: Int -> Size -> ShowS

show :: Size -> String

showList :: [Size] -> ShowS

Bits Size

Methods

(.&.) :: Size -> Size -> Size

(.|.) :: Size -> Size -> Size

xor :: Size -> Size -> Size

complement :: Size -> Size

shift :: Size -> Int -> Size

rotate :: Size -> Int -> Size

zeroBits :: Size

bit :: Int -> Size

setBit :: Size -> Int -> Size

clearBit :: Size -> Int -> Size

complementBit :: Size -> Int -> Size

testBit :: Size -> Int -> Bool

bitSizeMaybe :: Size -> Maybe Int

bitSize :: Size -> Int

isSigned :: Size -> Bool

shiftL :: Size -> Int -> Size

unsafeShiftL :: Size -> Int -> Size

shiftR :: Size -> Int -> Size

unsafeShiftR :: Size -> Int -> Size

rotateL :: Size -> Int -> Size

rotateR :: Size -> Int -> Size

popCount :: Size -> Int

FiniteBits Size

Methods

finiteBitSize :: Size -> Int

countLeadingZeros :: Size -> Int

countTrailingZeros :: Size -> Int

NFData Size

Methods

rnf :: Size -> ()

Tree types (and constructors)

data BTree a

Constructors

BLeaf a

BNode !(WTree a) !(WTree a)

Instances

Eq a => Eq (BTree a)

Methods

(==) :: BTree a -> BTree a -> Bool

(/=) :: BTree a -> BTree a -> Bool

Ord a => Ord (BTree a)

Methods

compare :: BTree a -> BTree a -> Ordering

(<) :: BTree a -> BTree a -> Bool

(<=) :: BTree a -> BTree a -> Bool

(>) :: BTree a -> BTree a -> Bool

(>=) :: BTree a -> BTree a -> Bool

max :: BTree a -> BTree a -> BTree a

min :: BTree a -> BTree a -> BTree a

Show a => Show (BTree a)

Methods

showsPrec :: Int -> BTree a -> ShowS

show :: BTree a -> String

showList :: [BTree a] -> ShowS

NFData a => NFData (BTree a)

Methods

rnf :: BTree a -> ()

data WTree a

Constructors

WTree

Fields

• weight :: !Weight
• btree :: !(BTree a)

Instances

Eq a => Eq (WTree a)

Methods

(==) :: WTree a -> WTree a -> Bool

(/=) :: WTree a -> WTree a -> Bool

Ord a => Ord (WTree a)

Methods

compare :: WTree a -> WTree a -> Ordering

(<) :: WTree a -> WTree a -> Bool

(<=) :: WTree a -> WTree a -> Bool

(>) :: WTree a -> WTree a -> Bool

(>=) :: WTree a -> WTree a -> Bool

max :: WTree a -> WTree a -> WTree a

min :: WTree a -> WTree a -> WTree a

Show a => Show (WTree a)

Methods

showsPrec :: Int -> WTree a -> ShowS

show :: WTree a -> String

showList :: [WTree a] -> ShowS

NFData a => NFData (WTree a)

Methods

rnf :: WTree a -> ()

pattern WLeaf :: forall a. Weight -> a -> WTree a

pattern WNode :: forall a. Weight -> WTree a -> WTree a -> WTree a

data Urn a

Constructors

Urn

Fields

• size :: !Size
• wtree :: !(WTree a)

Instances

Show a => Show (Urn a)

This Show instance prints out the elements from most-weighted to least-weighted; however, do not rely on the order of equally-weighted elements, as this may depend on details of the implementation.

Methods

showsPrec :: Int -> Urn a -> ShowS

show :: Urn a -> String

showList :: [Urn a] -> ShowS

NFData a => NFData (Urn a)

Methods

rnf :: Urn a -> ()

Sampling/lookup (WTrees and BTrees)

sample :: WTree a -> Index -> a

bsample :: BTree a -> Index -> a

Insertion (Urns)

insert :: Weight -> a -> Urn a -> Urn a

uninsert :: Urn a -> (Weight, a, Weight, Maybe (Urn a))

Update and construct (WTrees)

update :: (Weight -> a -> (Weight, a)) -> WTree a -> Index -> (Weight, a, Weight, a, WTree a)

replace :: Weight -> a -> WTree a -> Index -> (Weight, a, WTree a)

construct :: NonEmpty (Weight, a) -> Urn a

General weight-based WTree traversal

foldWTree :: (Weight -> a -> b) -> (Weight -> b -> WTree a -> b) -> (Weight -> WTree a -> b -> b) -> Size -> WTree a -> b

Raw random index generation

randomIndexWith :: Functor f => ((Word, Word) -> f Word) -> Urn a -> f Index

Debugging

showUrnTreeStructureWith :: (a -> String) -> Urn a -> String

showUrnTreeStructure :: Show a => Urn a -> String