net.sf.bddbddb.order
Class Order

java.lang.Object
  net.sf.bddbddb.order.Order

All Implemented Interfaces:

java.lang.Comparable, java.lang.Iterable, java.util.Collection, java.util.List

public class Order
extends java.lang.Object
implements java.util.List, java.lang.Comparable

Represents an order. This is just a List with a few extra utility functions.

Version:

$Id: Order.java 435 2005-02-13 03:24:59Z cs343 $

Author:

jwhaley

Field Summary

static double[]	COMPLEXITY_MULTI
static double[]	COMPLEXITY_SINGLE
static double	INTERLEAVE_WEIGHT
static double	PRECEDENCE_WEIGHT

Constructor Summary

Order(java.util.List l)
Construct a new Order from the given list.

Order(Order o)
Construct a new Order that is a copy of the given Order.

Method Summary

void	add(int index, java.lang.Object element)
boolean	add(java.lang.Object o)
boolean	addAll(java.util.Collection c)
boolean	addAll(int index, java.util.Collection c)
static java.util.Map	calcLongSimilarities(java.util.Collection c) Given a collection of orders, find its similarities and the number of occurrences of each similarity.
void	clear()
int	compareTo(java.lang.Object arg0)
int	compareTo(Order that) Compares orders lexigraphically.
double	complexity() Returns a measure of the complexity of this order.
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection c)
boolean	equals(java.lang.Object obj)
boolean	equals(Order that)
java.util.Collection	findLongSimilarities(Order that) Return the collection of suborders that are similar between this order and the given order.
java.lang.Object	get(int index)
java.util.Collection	getAllInterleaveConstraints() Get all interleave constraints of this order.
java.util.Collection	getAllPrecedenceConstraints() Get all precedence constraints of this order.
java.util.Collection	getConstraints() Return the collection of constraints in this order.
java.util.List	getFlattened() Return the flattened version of this list.
int	hashCode()
int	indexOf(java.lang.Object o)
boolean	isEmpty()
java.util.Iterator	iterator()
int	lastIndexOf(java.lang.Object o)
java.util.ListIterator	listIterator()
java.util.ListIterator	listIterator(int index)
int	numberOfElements() Returns the number of elements in this order.
int	numInterleaveConstraints() Get the number of interleave constraints in this order.
int	numPrecedenceConstraints() Get the number of precedence constraints in this order.
boolean	obeysConstraint(OrderConstraint c) Returns true if this order obeys the given constraint.
static Order	parse(java.lang.String s, java.util.Map nameToObj) Parse an order from a string.
java.lang.Object	remove(int index)
boolean	remove(java.lang.Object o)
boolean	removeAll(java.util.Collection c)
boolean	retainAll(java.util.Collection c)
java.lang.Object	set(int index, java.lang.Object element)
double	similarity(Order that) Returns the similarity between two orders as a number between 0.0 and 1.0.
int	size()
java.util.List	subList(int fromIndex, int toIndex)
java.lang.Object[]	toArray()
java.lang.Object[]	toArray(java.lang.Object[] a)
java.lang.String	toString()
java.lang.String	toVarOrderString(java.util.Map variableToBDDDomain) Generate a BDD order string from this variable order.

Methods inherited from class java.lang.Object

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

Field Detail

PRECEDENCE_WEIGHT

public static double PRECEDENCE_WEIGHT

INTERLEAVE_WEIGHT

public static double INTERLEAVE_WEIGHT

COMPLEXITY_SINGLE

public static double[] COMPLEXITY_SINGLE

COMPLEXITY_MULTI

public static double[] COMPLEXITY_MULTI

Constructor Detail

Order

public Order(Order o)

Construct a new Order that is a copy of the given Order.

Parameters:

o - order to copy

Order

public Order(java.util.List l)

Construct a new Order from the given list.

Parameters:

l - list

Method Detail

obeysConstraint

public boolean obeysConstraint(OrderConstraint c)

Returns true if this order obeys the given constraint.

Parameters:

c - constraint

Returns:

true if this order obeys the constraint, false otherwise

getConstraints

public java.util.Collection getConstraints()

Return the collection of constraints in this order.

Returns:

collection of constraints

numberOfElements

public int numberOfElements()

Returns the number of elements in this order. This includes elements within interleaves.

Returns:

number of elements in this order

getFlattened

public java.util.List getFlattened()

Return the flattened version of this list.

Returns:

flattened version of this list

getAllInterleaveConstraints

public java.util.Collection getAllInterleaveConstraints()

Get all interleave constraints of this order.

Returns:

collection of interleave constraints

numInterleaveConstraints

public int numInterleaveConstraints()

Get the number of interleave constraints in this order.

Returns:

number of interleave constraints

getAllPrecedenceConstraints

public java.util.Collection getAllPrecedenceConstraints()

Get all precedence constraints of this order.

Returns:

collection of precedence constraints

numPrecedenceConstraints

public int numPrecedenceConstraints()

Get the number of precedence constraints in this order.

Returns:

number of precedence constraints

similarity

public double similarity(Order that)

Returns the similarity between two orders as a number between 0.0 and 1.0. 1.0 means that the orders are exactly the same, and 0.0 means they have no similarities. Precedence constraints are weighted by the factor "PRECEDENCE_WEIGHT", and interleave constraints are weighted by the factor "INTERLEAVE_WEIGHT".

Parameters:

that -

Returns:

similarity measure between 0.0 and 1.0

complexity

public double complexity()

Returns a measure of the complexity of this order. Higher numbers are more complex (i.e. have more constraints)

Returns:

a measure of the complexity of this order

compareTo

public int compareTo(java.lang.Object arg0)

Specified by:

compareTo in interface java.lang.Comparable

compareTo

public int compareTo(Order that)

Compares orders lexigraphically.

Parameters:

that - order to compare to

Returns:

-1, 0, or 1 if this order is less than, equal to, or greater than

equals

public boolean equals(Order that)

equals

public boolean equals(java.lang.Object obj)

Specified by:

equals in interface java.util.Collection

Specified by:

equals in interface java.util.List

Overrides:

equals in class java.lang.Object

add

public boolean add(java.lang.Object o)

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

add

public void add(int index,
                java.lang.Object element)

Specified by:

add in interface java.util.List

addAll

public boolean addAll(int index,
                      java.util.Collection c)

Specified by:

addAll in interface java.util.List

addAll

public boolean addAll(java.util.Collection c)

Specified by:

addAll in interface java.util.Collection

Specified by:

addAll in interface java.util.List

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.List

containsAll

public boolean containsAll(java.util.Collection c)

Specified by:

containsAll in interface java.util.Collection

Specified by:

containsAll in interface java.util.List

get

public java.lang.Object get(int index)

Specified by:

get in interface java.util.List

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Collection

Specified by:

hashCode in interface java.util.List

Overrides:

hashCode in class java.lang.Object

indexOf

public int indexOf(java.lang.Object o)

Specified by:

indexOf in interface java.util.List

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.List

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

lastIndexOf

public int lastIndexOf(java.lang.Object o)

Specified by:

lastIndexOf in interface java.util.List

listIterator

public java.util.ListIterator listIterator()

Specified by:

listIterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator(int index)

Specified by:

listIterator in interface java.util.List

remove

public java.lang.Object remove(int index)

Specified by:

remove in interface java.util.List

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.List

removeAll

public boolean removeAll(java.util.Collection c)

Specified by:

removeAll in interface java.util.Collection

Specified by:

removeAll in interface java.util.List

retainAll

public boolean retainAll(java.util.Collection c)

Specified by:

retainAll in interface java.util.Collection

Specified by:

retainAll in interface java.util.List

set

public java.lang.Object set(int index,
                            java.lang.Object element)

Specified by:

set in interface java.util.List

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

subList

public java.util.List subList(int fromIndex,
                              int toIndex)

Specified by:

subList in interface java.util.List

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

toArray

public java.lang.Object[] toArray(java.lang.Object[] a)

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

toVarOrderString

public java.lang.String toVarOrderString(java.util.Map variableToBDDDomain)

Generate a BDD order string from this variable order.

Parameters:

variableToBDDDomain - map from variable to BDD

Returns:

BDD order string

parse

public static Order parse(java.lang.String s,
                          java.util.Map nameToObj)

Parse an order from a string.

Parameters:

s - string to parse

nameToObj - map from name to object (variable, etc.)

Returns:

order

calcLongSimilarities

public static java.util.Map calcLongSimilarities(java.util.Collection c)

Given a collection of orders, find its similarities and the number of occurrences of each similarity.

Parameters:

c - collection of orders

Returns:

map from order similarities to frequencies

findLongSimilarities

public java.util.Collection findLongSimilarities(Order that)

Return the collection of suborders that are similar between this order and the given order. Duplicates are eliminated.

Parameters:

that - other order

Returns:

collection of suborders that are similar