DisjointSetForest (OpenIMAJ master project 1.3.1 API)

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

Methods
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

- 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

Class DisjointSetForest<T>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Set

Constructor Detail

DisjointSetForest

DisjointSetForest

Method Detail

find

makeSet

union

asList

size

isEmpty

contains

iterator

toArray

toArray

add

add

remove

containsAll

addAll

addAll

retainAll

removeAll

clear

size

numSets

getSubsets

partition

partitionSubsets