mondrian.util
Class PartiallyOrderedSet<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          mondrian.util.PartiallyOrderedSet<E>

Type Parameters:

E - Element type

All Implemented Interfaces:

Iterable<E>, Collection<E>, Set<E>

public class PartiallyOrderedSet<E>
extends AbstractSet<E>

Partially-ordered set.

When you create a partially-ordered set ('poset' for short) you must provide an PartiallyOrderedSet.Ordering that determines the order relation. The ordering must be:

• reflexive: e.lte(e) returns true;
• anti-symmetric: if e.lte(f) returns true, then f.lte(e) returns false only if e = f;
• transitive: if e.lte(f) returns true and f.lte(g) returns true, then e.lte(g) must return true.

Note that not all pairs of elements are related. If is OK if e.lte(f) returns false and f.lte(e) returns false also.

In addition to the usual set methods, there are methods to determine the immediate parents and children of an element in the set, and method to find all elements which have no parents or no children (i.e. "root" and "leaf" elements).

A lattice is a special kind of poset where there is a unique top and bottom element. You can use a PartiallyOrderedSet for a lattice also. It may be helpful to add the top and bottom elements to the poset on construction.

Author:

Julian Hyde

Nested Class Summary

static interface

PartiallyOrderedSet.Ordering<E> Ordering relation.

Constructor Summary

PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering)
Creates a partially-ordered set.

PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering, Collection<E> collection)
Creates a partially-ordered set, and populates it with a given collection.

Method Summary

boolean	add(E e) Adds an element to this lattice.
void	clear()
boolean	contains(Object o)
List<E>	getAncestors(E e) Returns a list of values in the set that are less-than a given value.
List<E>	getChildren(E e) Returns the values in this partially-ordered set that are less-than a given value and there are no intervening values.
List<E>	getDescendants(E e) Returns a list of values in the set that are less-than a given value.
List<E>	getNonChildren()
List<E>	getNonParents()
List<E>	getParents(E e) Returns the values in this partially-ordered set that are greater-than a given value and there are no intervening values.
boolean	isValid(boolean fail) Checks internal consistency of this lattice.
Iterator<E>	iterator()
void	out(StringBuilder buf)
boolean	remove(Object o)
int	size()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, isEmpty, retainAll, toArray, toArray

Constructor Detail

PartiallyOrderedSet

public PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering)

Creates a partially-ordered set.

Parameters:

ordering - Ordering relation

PartiallyOrderedSet

public PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering,
                           Collection<E> collection)

Creates a partially-ordered set, and populates it with a given collection.

Parameters:

ordering - Ordering relation

collection - Initial contents of partially-ordered set

Method Detail

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Set<E>

Specified by:

iterator in class AbstractCollection<E>

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Specified by:

size in class AbstractCollection<E>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Overrides:

contains in class AbstractCollection<E>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

Overrides:

remove in class AbstractCollection<E>

add

public boolean add(E e)

Adds an element to this lattice.

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Overrides:

add in class AbstractCollection<E>

isValid

public boolean isValid(boolean fail)

Checks internal consistency of this lattice.

Parameters:

fail - Whether to throw an assertion error

Returns:

Whether valid

out

public void out(StringBuilder buf)

getChildren

public List<E> getChildren(E e)

Returns the values in this partially-ordered set that are less-than a given value and there are no intervening values.

If the value is not in this set, returns the empty list.

Parameters:

e - Value

Returns:

List of values in this set that are directly less than the given value

See Also:

getDescendants(E)

getParents

public List<E> getParents(E e)

Returns the values in this partially-ordered set that are greater-than a given value and there are no intervening values.

If the value is not in this set, returns the empty list.

Parameters:

e - Value

Returns:

List of values in this set that are directly greater than the given value

See Also:

getAncestors(E)

getNonChildren

public List<E> getNonChildren()

getNonParents

public List<E> getNonParents()

clear

public void clear()

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

getDescendants

public List<E> getDescendants(E e)

Returns a list of values in the set that are less-than a given value. The list is in topological order but order is otherwise non-deterministic.

Parameters:

e - Value

Returns:

Values less than given value

getAncestors

public List<E> getAncestors(E e)

Returns a list of values in the set that are less-than a given value. The list is in topological order but order is otherwise non-deterministic.

Parameters:

e - Value

Returns:

Values less than given value