Overeasy.Assoc

See Assoc.

Documentation

data Assoc x a

Associates keys and values in such a way that inserting duplicate values induces equivalences on their keys. Invariant: fwd and bwd maps contain only root keys.

Instances

Generic (Assoc x a)

Defined in Overeasy.Assoc

Associated Types

type Rep (Assoc x a) :: Type -> Type

Methods

from :: Assoc x a -> Rep (Assoc x a) x0

to :: Rep (Assoc x a) x0 -> Assoc x a

(Show a, Show x) => Show (Assoc x a)

Defined in Overeasy.Assoc

Methods

showsPrec :: Int -> Assoc x a -> ShowS

show :: Assoc x a -> String

showList :: [Assoc x a] -> ShowS

(NFData a, NFData x) => NFData (Assoc x a)

Defined in Overeasy.Assoc

Methods

rnf :: Assoc x a -> ()

(Eq a, Eq x) => Eq (Assoc x a)

Defined in Overeasy.Assoc

Methods

(==) :: Assoc x a -> Assoc x a -> Bool

(/=) :: Assoc x a -> Assoc x a -> Bool

type Rep (Assoc x a)

Defined in Overeasy.Assoc

type Rep (Assoc x a) = D1 ('MetaData "Assoc" "Overeasy.Assoc" "overeasy-0.2.0-7Shit7pE5Ru2Ny0HoLxUG4" 'False) (C1 ('MetaCons "Assoc" 'PrefixI 'True) (S1 ('MetaSel ('Just "assocFwd") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (IntLikeMap x a)) :*: (S1 ('MetaSel ('Just "assocBwd") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (HashMap a x)) :*: S1 ('MetaSel ('Just "assocEquiv") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (EquivFind x)))))

assocFwd :: Assoc x a -> IntLikeMap x a

Map from id to element

assocBwd :: Assoc x a -> HashMap a x

Map from element to id

assocEquiv :: Assoc x a -> EquivFind x

Equivalence classes of ids

assocSize :: Assoc x a -> Int

How many values are in the map?

assocNew :: Assoc x a

Creates an empty assoc

assocSingleton :: (Coercible x Int, Hashable a) => x -> a -> Assoc x a

Creates a singleton assoc

data AssocInsertRes x

The result of inserting into the assoc, if you're interested.

Constructors

AssocInsertResUnchanged

AssocInsertResCreated

AssocInsertResUpdated

AssocInsertResMerged !(IntLikeSet x)

Instances

Show (AssocInsertRes x)

Defined in Overeasy.Assoc

Methods

showsPrec :: Int -> AssocInsertRes x -> ShowS

show :: AssocInsertRes x -> String

showList :: [AssocInsertRes x] -> ShowS

Eq (AssocInsertRes x)

Defined in Overeasy.Assoc

Methods

(==) :: AssocInsertRes x -> AssocInsertRes x -> Bool

(/=) :: AssocInsertRes x -> AssocInsertRes x -> Bool

assocInsertInc :: (Coercible x Int, Ord x, Eq a, Hashable a) => x -> a -> Assoc x a -> ((x, AssocInsertRes x), Assoc x a)

Insert into the assoc (raw version)

assocInsert :: (Coercible x Int, Ord x, Eq a, Hashable a) => x -> a -> State (Assoc x a) (x, AssocInsertRes x)

Insert into the assoc (the state version)

assocFromList :: (Coercible x Int, Ord x, Eq a, Hashable a) => [(x, a)] -> Assoc x a

Build an assoc from a list of pairs

assocToList :: Coercible x Int => Assoc x a -> [(x, a)]

Turn an assoc into a list of pairs (NOTE - emits only root keys!)

assocMember :: Coercible x Int => x -> Assoc x a -> Bool

Is the given key in the assoc?

assocLookupByKey :: Coercible x Int => x -> Assoc x a -> Maybe a

Forward lookup

assocPartialLookupByKey :: Coercible x Int => x -> Assoc x a -> a

PARTIAL forward lookup

assocLookupByValue :: (Eq a, Hashable a) => a -> Assoc x a -> Maybe x

Backward lookup

assocPartialLookupByValue :: (Eq a, Hashable a) => a -> Assoc x a -> x

PARTIAL backward lookup

assocLookupRoot :: Coercible x Int => x -> Assoc x a -> x

Finds the root for the given key (id if not found)

assocRoots :: Coercible x Int => Assoc x a -> [x]

List all root (live, non-compactible) keys

assocLeaves :: Coercible x Int => Assoc x a -> [x]

List all leaf (dead, compactible) keys

assocMembers :: Coercible x Int => Assoc x a -> [x]

List all entries (root and leaf)

assocCanCompact :: Assoc x a -> Bool

Are there dead keys in the equiv from assocInsert?

assocCompactInc :: Coercible x Int => Assoc x a -> (IntLikeMap x x, Assoc x a)

Removes all dead keys in the equiv (raw version).

assocCompact :: Coercible x Int => State (Assoc x a) (IntLikeMap x x)

Removes all dead keys in the equiv (state version). Returns map of dead leaf node -> live root node

assocRemoveAllInc :: (Coercible x Int, Eq a, Hashable a) => [x] -> Assoc x a -> Assoc x a

Removes the given keys from the assoc (raw version)

assocRemoveAll :: (Coercible x Int, Eq a, Hashable a) => [x] -> State (Assoc x a) ()

Removes the given keys from the assoc (state version). Values will only be removed from the assoc if the key is a singleton root. If a key is not found, it is simply ignored.

assocUnion :: (Coercible x Int, Ord x, Eq a, Hashable a) => Assoc x a -> Assoc x a -> Assoc x a

Join two assocs (uses the first as the base)

assocFootprint :: (Coercible x Int, Eq a, Hashable a) => a -> Assoc x a -> IntLikeSet x

Returns the footprint of the given value - all keys that map to it (root and leaf)