Data.DisjointSet

Documentation

data DisjointSet a

Instances

Ord a => Eq (DisjointSet a)

Methods

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

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

Ord a => Ord (DisjointSet a)

Methods

compare :: DisjointSet a -> DisjointSet a -> Ordering

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

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

(>) :: DisjointSet a -> DisjointSet a -> Bool

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

max :: DisjointSet a -> DisjointSet a -> DisjointSet a

min :: DisjointSet a -> DisjointSet a -> DisjointSet a

(Show a, Ord a) => Show (DisjointSet a)

Methods

showsPrec :: Int -> DisjointSet a -> ShowS

show :: DisjointSet a -> String

showList :: [DisjointSet a] -> ShowS

Ord a => Semigroup (DisjointSet a)

Methods

(<>) :: DisjointSet a -> DisjointSet a -> DisjointSet a

sconcat :: NonEmpty (DisjointSet a) -> DisjointSet a

stimes :: Integral b => b -> DisjointSet a -> DisjointSet a

Ord a => Monoid (DisjointSet a)

Methods

mempty :: DisjointSet a

mappend :: DisjointSet a -> DisjointSet a -> DisjointSet a

mconcat :: [DisjointSet a] -> DisjointSet a

empty :: DisjointSet a

singleton :: a -> DisjointSet a

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

singletons :: Eq a => Set a -> DisjointSet a

Create a disjoint set where all members are equal.

insert :: Ord a => a -> DisjointSet a -> DisjointSet a

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 a => a -> a -> DisjointSet a -> DisjointSet a

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.

representative :: Ord a => a -> DisjointSet a -> Maybe a

Find the set representative for this input.

representative' :: Ord a => a -> DisjointSet a -> (Maybe a, DisjointSet a)

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

toLists :: Ord a => DisjointSet a -> [[a]]