org.openimaj.util.set

Class DisjointSetForest<T>

java.lang.Object

org.openimaj.util.set.DisjointSetForest<T>

Type Parameters:

T - the type of elements maintained by this set

All Implemented Interfaces:

Iterable<T>, Collection<T>, Set<T>

public class DisjointSetForest<T>
extends Object
implements Set<T>

Implementation of a Disjoint Set Forest data structure.

A disjoint set holds a set of elements partitioned into a number of non-overlapping subsets. The disjoint set forest holds each subset as a tree structure, with the representative of each subset being the root of the respective tree.

See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more information.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Constructor Summary

Constructors

Constructor and Description
DisjointSetForest() Construct a new Disjoint Set Forest.
DisjointSetForest(int initialCapacity) Constructs a new Disjoint Set Forest, with the specified initial capacity.

Method Summary

Modifier and Type	Method and Description
boolean	add(T e)
T	add(T elem, T repr) Add an element to the given set.
boolean	addAll(Collection<? extends T> collection) Add all the elements in the collection to this disjoint set forest.
boolean	addAll(Collection<? extends T> collection, boolean sameSet) Add all the elements in the collection to this disjoint set forest.
List<T>	asList()
void	clear()
boolean	contains(Object o)
boolean	containsAll(Collection<?> collection)
T	find(T x) Search for the representative of the subset containing the element x.
Set<Set<T>>	getSubsets() Get all the subsets stored in this forest.
boolean	isEmpty()
Iterator<T>	iterator()
T	makeSet(T o) Make a new subset from the given item
int	numSets() Get the number of subsets
static <T> DisjointSetForest<T>	partition(List<T> values, Comparator<T> comparator) Construct a DisjointSetForest by partitioning the given values using the given Comparator to determine equality of pairs of values.
static <T> Set<Set<T>>	partitionSubsets(List<T> values, Comparator<T> comparator) Extract the subsets formed by constructing a DisjointSetForest which partitions the given values using the given Comparator to determine equality of pairs of values.
boolean	remove(Object o)
boolean	removeAll(Collection<?> c)
boolean	retainAll(Collection<?> c)
int	size()
int	size(T o) Get the size of a subset
Object[]	toArray()
<E> E[]	toArray(E[] a)
T	union(T x, T y) Joint the subsets belonging to the objects x and y.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Set

equals, hashCode, spliterator

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

DisjointSetForest

public DisjointSetForest()

Construct a new Disjoint Set Forest.

DisjointSetForest

public DisjointSetForest(int initialCapacity)

Constructs a new Disjoint Set Forest, with the specified initial capacity.

Parameters:

initialCapacity - The initial capacity

Method Detail

find

public T find(T x)

Search for the representative of the subset containing the element x. This implementation uses path compression to flatten the trees during the find operation. This will lead to performance improvements on subsequent find operations.

Parameters:

x - the element

Returns:

the representative element or null if x isn't in the forest.

makeSet

public T makeSet(T o)

Make a new subset from the given item

Parameters:

o - the item

Returns:

the item if the subset was created successfully; null otherwise.

union

public T union(T x,
               T y)

Joint the subsets belonging to the objects x and y.

Parameters:

x - the x object.

y - the y object.

Returns:

the new root, or null if x or y are not in the disjoint set forest, or x and y are already in the same set.

asList

public List<T> asList()

Returns:

the contents of the forest as a list

size

public int size()

Specified by:

size in interface Collection<T>

Specified by:

size in interface Set<T>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<T>

Specified by:

isEmpty in interface Set<T>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<T>

Specified by:

contains in interface Set<T>

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface Collection<T>

Specified by:

iterator in interface Set<T>

toArray

public Object[] toArray()

Specified by:

toArray in interface Collection<T>

Specified by:

toArray in interface Set<T>

toArray

public <E> E[] toArray(E[] a)

Specified by:

toArray in interface Collection<T>

Specified by:

toArray in interface Set<T>

add

public boolean add(T e)

Specified by:

add in interface Collection<T>

Specified by:

add in interface Set<T>

add

public T add(T elem,
             T repr)

Add an element to the given set.

Parameters:

elem - Element to add

repr - A representative of the set to add to

Returns:

The representative of the set containing the added element, or null if elem is already contained in this set.

Throws:

IllegalArgumentException - If repr is not an element of this forest.

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<T>

Specified by:

remove in interface Set<T>

containsAll

public boolean containsAll(Collection<?> collection)

Specified by:

containsAll in interface Collection<T>

Specified by:

containsAll in interface Set<T>

addAll

public boolean addAll(Collection<? extends T> collection)

Add all the elements in the collection to this disjoint set forest. Each element will be added to its own set.

Specified by:

addAll in interface Collection<T>

Specified by:

addAll in interface Set<T>

Parameters:

collection - The collection to add

Returns:

true is any elements were added; false otherwise.

addAll

public boolean addAll(Collection<? extends T> collection,
                      boolean sameSet)

Add all the elements in the collection to this disjoint set forest.

Parameters:

collection - The collection to add

sameSet - Are the elements in the collection to be added to the same set?

Returns:

true is any elements were added; false otherwise.

retainAll

public boolean retainAll(Collection<?> c)

Specified by:

retainAll in interface Collection<T>

Specified by:

retainAll in interface Set<T>

removeAll

public boolean removeAll(Collection<?> c)

Specified by:

removeAll in interface Collection<T>

Specified by:

removeAll in interface Set<T>

clear

public void clear()

Specified by:

clear in interface Collection<T>

Specified by:

clear in interface Set<T>

size

public int size(T o)

Get the size of a subset

Parameters:

o - an object in the subset

Returns:

the number of objects in the subset

numSets

public int numSets()

Get the number of subsets

Returns:

the number of subset

getSubsets

public Set<Set<T>> getSubsets()

Get all the subsets stored in this forest.

Returns:

subsets

partition

public static <T> DisjointSetForest<T> partition(List<T> values,
                                                 Comparator<T> comparator)

Construct a DisjointSetForest by partitioning the given values using the given Comparator to determine equality of pairs of values.

Type Parameters:

T - the type of elements maintained by this set

Parameters:

values - the values to partition

comparator - the comparator to determine equality of values

Returns:

the new DisjointSetForest representing the partitioning

partitionSubsets

public static <T> Set<Set<T>> partitionSubsets(List<T> values,
                                               Comparator<T> comparator)

Extract the subsets formed by constructing a DisjointSetForest which partitions the given values using the given Comparator to determine equality of pairs of values.

Type Parameters:

T - the type of elements maintained by this set

Parameters:

values - the values to partition

comparator - the comparator to determine equality of values

Returns:

the subsets representing the partitioning