endrov.util.collection
Class Partitioning<E>

java.lang.Object
  endrov.util.collection.Partitioning<E>

public class Partitioning<E>
extends java.lang.Object

Partitioning, or equivalence relation between elements. The class will help computing the total equivalence (compute transitivity) given a few equivalences. Worst-case complexity: Upper bound, O(n) group joins, O(n) for one group join. Lookup is O(1). For structured partitioning on images, likely O(n) group joins, but most joins cost only O(1), so linear cost. There is an alternative implementation with O(1) join and O(log n) lookup. It can be optimized (constant time) with path compression.

Constructor Summary

Partitioning()

Method Summary

void	createElement(E e) Create an element with no initial relations except reflexivity.
void	createSpecifyEquivalent(E a, E b) Specify two elements as equivalent.
void	existingSpecifyEquivalent(E a, E b) Specify two existing elements as equivalent.
java.util.List<java.util.Set<E>>	filterSize(java.util.List<java.util.Set<E>> list, int minSize) Remove all entries smaller than a certain volume
java.util.Set<E>	getPartition(E e) Get equivalent elements for one element
java.util.List<java.util.Set<E>>	getPartitions() Get all partitions
boolean	isEquivalent(E a, E b) Check if two elements are equivalent
void	specifyEquivalent(E a, E b) Specify two elements as equivalent.

Methods inherited from class java.lang.Object

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

Constructor Detail

Partitioning

public Partitioning()

Method Detail

createElement

public void createElement(E e)

Create an element with no initial relations except reflexivity. Checks if it exists first, will not disrupt relations

specifyEquivalent

public void specifyEquivalent(E a,
                              E b)

Specify two elements as equivalent. Must have been created before.

createSpecifyEquivalent

public void createSpecifyEquivalent(E a,
                                    E b)

Specify two elements as equivalent. Create these elements if they did not exist before. This function is heavily optimized.

existingSpecifyEquivalent

public void existingSpecifyEquivalent(E a,
                                      E b)

Specify two existing elements as equivalent. Might be slower than automatically creating new partitions

isEquivalent

public boolean isEquivalent(E a,
                            E b)

Check if two elements are equivalent

getPartition

public java.util.Set<E> getPartition(E e)

Get equivalent elements for one element

getPartitions

public java.util.List<java.util.Set<E>> getPartitions()

Get all partitions

filterSize

public java.util.List<java.util.Set<E>> filterSize(java.util.List<java.util.Set<E>> list,
                                                   int minSize)

Remove all entries smaller than a certain volume