org.latdraw.partition
Class BasicPartition

java.lang.Object
  org.latdraw.partition.IntArray
      org.latdraw.partition.BasicPartition

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Comparable, Partition

public class BasicPartition
extends IntArray
implements Partition, java.lang.Comparable

This class implement the basic operations for partition on the set {0, 1, ..., n-1}. A class that wants to implement partitions on an arbibtrary set can use this class internally. It can also be used as a wrapper for an array of int's in order to use the equals and hashCode methods.

It is based on my unpublished note: Partition Algorithms which can be obtained at http://www.math.hawaii.edu/~ralph/Notes/.

Version:

$Id: BasicPartition.java,v 1.1 2008/08/01 19:30:57 ralph Exp $

Author:

Ralph Freese

Field Summary

Fields inherited from class org.latdraw.partition.IntArray

array, size

Fields inherited from interface org.latdraw.partition.Partition

BLOCK, EWK, HUMAN, INTERNAL, ONE_INDEXED

Constructor Summary

BasicPartition(int[] part)

BasicPartition(int[] part, boolean oneIndexed)

Method Summary

int	compareTo(java.lang.Object o) The order of a linear extension respecting rank.
int[][]	getBlocks() Get the block form of this partition as an array of arrays.
boolean	isRelated(int i, int j)
boolean	isRepresentative(int i)
boolean	isZero()
Partition	join(Partition part2) * Note r and s must be roots and distinct.
void	joinBlocks(int r, int s) Note r and s must be roots and distinct.
static boolean	leq(int[] u, int[] v)
boolean	leq(Partition part2)
static void	main(java.lang.String[] args)
Partition	meet(Partition part2)
void	normalize() This modifies this.array.
static void	normalize(int[] part) Modify part so that it is in normal form.
int	numberOfBlocks() Does not need normalized form.
static BasicPartition	one(int asize)
static BasicPartition	one(int asize, boolean oneIndexed)
static java.lang.String	partToKissString(int[] part) Make String representation of the partition for the .con and related files.
static int	permutabilityLevel(int a, int b, Partition par0, Partition par1) This returns the least k such that (a,b) is in the k-fold relational product of par0 and par1, with par0 coming first and k counting the total occurances of par0 or par1.
static int	permutabilityLevel(Partition par0, Partition par1) This is the max of permutabilityLevel(a, b, par0, par1) over all (a, b) in the join.
int	rank()
int	representative(int i) This is the public way of finding the root.
int[]	representatives()
java.lang.String	toString()
java.lang.String	toString(int kind)
static BasicPartition	zero(int asize)
static BasicPartition	zero(int asize, boolean oneIndexed)

Methods inherited from class org.latdraw.partition.IntArray

clone, equalIntArrays, equals, get, getArray, hashCode, intArrayToString, set, setIntArray, size, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.latdraw.partition.Partition

size, toArray

Constructor Detail

BasicPartition

public BasicPartition(int[] part)

BasicPartition

public BasicPartition(int[] part,
                      boolean oneIndexed)

Method Detail

compareTo

public int compareTo(java.lang.Object o)

The order of a linear extension respecting rank.

Specified by:

compareTo in interface java.lang.Comparable

zero

public static BasicPartition zero(int asize)

zero

public static BasicPartition zero(int asize,
                                  boolean oneIndexed)

one

public static BasicPartition one(int asize)

one

public static BasicPartition one(int asize,
                                 boolean oneIndexed)

isRelated

public boolean isRelated(int i,
                         int j)

Specified by:

isRelated in interface Partition

numberOfBlocks

public int numberOfBlocks()

Does not need normalized form. Simply counts the negative entries.

Specified by:

numberOfBlocks in interface Partition

rank

public int rank()

joinBlocks

public void joinBlocks(int r,
                       int s)

Note r and s must be roots and distinct.

join

public Partition join(Partition part2)

Description copied from interface: Partition

* Note r and s must be roots and distinct.

Specified by:

join in interface Partition

permutabilityLevel

public static int permutabilityLevel(int a,
                                     int b,
                                     Partition par0,
                                     Partition par1)

This returns the least k such that (a,b) is in the k-fold relational product of par0 and par1, with par0 coming first and k counting the total occurances of par0 or par1. It returns -1 if (a,b) is not in the join.

permutabilityLevel

public static int permutabilityLevel(Partition par0,
                                     Partition par1)

This is the max of permutabilityLevel(a, b, par0, par1) over all (a, b) in the join.

meet

public Partition meet(Partition part2)

Specified by:

meet in interface Partition

leq

public boolean leq(Partition part2)

Specified by:

leq in interface Partition

leq

public static boolean leq(int[] u,
                          int[] v)

normalize

public void normalize()

This modifies this.array.

Specified by:

normalize in interface Partition

normalize

public static void normalize(int[] part)

Modify part so that it is in normal form.

isZero

public boolean isZero()

Specified by:

isZero in interface Partition

toString

public java.lang.String toString()

Overrides:

toString in class IntArray

toString

public java.lang.String toString(int kind)

Specified by:

toString in interface Partition

partToKissString

public static java.lang.String partToKissString(int[] part)

Make String representation of the partition for the .con and related files.

getBlocks

public int[][] getBlocks()

Get the block form of this partition as an array of arrays.

Specified by:

getBlocks in interface Partition

representative

public int representative(int i)

This is the public way of finding the root. Unlike root it does not modify array.

Specified by:

representative in interface Partition

isRepresentative

public boolean isRepresentative(int i)

Specified by:

isRepresentative in interface Partition

representatives

public int[] representatives()

Specified by:

representatives in interface Partition

main

public static void main(java.lang.String[] args)