Data.Queue.Indexed.Braun

Type-indexed Braun heaps.

Documentation

data Braun n a where

A Braun heap. Somewhat based on this implementation, but with a different strategy for maintaining invariants.

A braun tree is one where every left branch has at most one more element than the right branch.

Constructors

Leaf :: Braun 0 a

Node :: !(Offset n m) -> a -> Braun n a -> Braun m a -> Braun ((n + m) + 1) a

Instances

Ord a => IndexedQueue Braun a

Methods

empty :: Braun 0 a

minView :: Braun (1 + n) a -> (a, Braun n a)

singleton :: a -> Braun 1 a

insert :: a -> Braun n a -> Braun (1 + n) a

minViewMay :: Braun n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Braun m a -> b) -> b

NFData a => NFData (Braun n a)

Methods

rnf :: Braun n a -> ()

data Offset n m where

The "singleton" for whether or not the left branch is larger than the right.

Constructors

Even :: Offset n n

Lean :: Offset (1 + n) n

Instances

NFData (Offset n m)

Methods

rnf :: Offset n m -> ()