Data.DisjointMap

Documentation

data DisjointMap k v

Instances

(Ord k, Ord v) => Eq (DisjointMap k v)

Methods

(==) :: DisjointMap k v -> DisjointMap k v -> Bool

(/=) :: DisjointMap k v -> DisjointMap k v -> Bool

(Ord k, Ord v) => Ord (DisjointMap k v)

Methods

compare :: DisjointMap k v -> DisjointMap k v -> Ordering

(<) :: DisjointMap k v -> DisjointMap k v -> Bool

(<=) :: DisjointMap k v -> DisjointMap k v -> Bool

(>) :: DisjointMap k v -> DisjointMap k v -> Bool

(>=) :: DisjointMap k v -> DisjointMap k v -> Bool

max :: DisjointMap k v -> DisjointMap k v -> DisjointMap k v

min :: DisjointMap k v -> DisjointMap k v -> DisjointMap k v

(Show k, Ord k, Show v) => Show (DisjointMap k v)

Methods

showsPrec :: Int -> DisjointMap k v -> ShowS

show :: DisjointMap k v -> String

showList :: [DisjointMap k v] -> ShowS

(Ord k, Monoid v) => Monoid (DisjointMap k v)

Methods

mempty :: DisjointMap k v

mappend :: DisjointMap k v -> DisjointMap k v -> DisjointMap k v

mconcat :: [DisjointMap k v] -> DisjointMap k v

empty :: DisjointMap k v

singleton :: k -> v -> DisjointMap k v

Create a disjoint set with one member. O(1).

singletons :: Eq k => Set k -> v -> DisjointMap k v

Create a disjoint set where all members are equal.

insert :: (Ord k, Monoid v) => k -> v -> DisjointMap k v -> DisjointMap k v

Insert x into the disjoint set. If it is already a member, then do nothing, otherwise x has no equivalence relations. O(logn).

union :: (Ord k, Monoid v) => k -> k -> DisjointMap k v -> DisjointMap k v

Create an equivalence relation between x and y. If either x or y are not already is the disjoint set, they are first created as singletons.

lookup :: Ord k => k -> DisjointMap k v -> Maybe v

representative :: Ord k => k -> DisjointMap k v -> Maybe k

Find the set representative for this input.

representative' :: Ord k => k -> DisjointMap k v -> (Maybe k, DisjointMap k v)

Find the set representative for this input. Returns a new disjoint set in which the path has been compressed.

toLists :: Ord k => DisjointMap k v -> [([k], v)]