/** An interface defining the operations on a complete partial order (CPO). Copyright (c) 1997-2013 The Regents of the University of California. All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. PT_COPYRIGHT_VERSION_2 COPYRIGHTENDKEY */ package ptolemy.graph; import java.util.Set; /////////////////////////////////////////////////////////////////// //// CPO /** An interface defining the operations on complete partial order (CPO). The definitions of these operations can be found in "Introduction to Lattices and Order," Cambridge University Press, 1990, by B. A. Davey and H. A. Priestley. Informal definitions are given in the code comments. Each element in the CPO is represented by an Object. For infinite CPOs, the result of some of the operations may be an infinite set, in which case, the class implementing those operations can throw an Exception. @author Yuhong Xiong @version $Id: CPO.java 65763 2013-03-07 01:54:37Z cxh $ @since Ptolemy II 0.2 @Pt.ProposedRating Green (yuhong) @Pt.AcceptedRating Green (kienhuis) */ public interface CPO { /////////////////////////////////////////////////////////////////// //// public methods //// /** Return the bottom element of this CPO. * The bottom element is the element in the CPO that is lower than * all the other elements. * @return An Object representing the bottom element, or * null if the bottom does not exist. */ public Object bottom(); /** Compare two elements in this CPO. * @param e1 An Object representing a CPO element. * @param e2 An Object representing a CPO element. * @return One of CPO.LOWER, CPO.SAME, * CPO.HIGHER, CPO.INCOMPARABLE. * @exception IllegalArgumentException If at least one of the * specified Objects is not an element of this CPO. */ public int compare(Object e1, Object e2); /** Compute the down-set of an element in this CPO. * The down-set of an element is the subset consisting of * all the elements lower than or the same as the specified element. * @param e An Object representing an element in this CPO. * @return An array of Objects representing the elements in the * down-set of the specified element. * @exception IllegalArgumentException If the specified Object is not * an element in this CPO, or the resulting set is infinite. */ public Object[] downSet(Object e); // FIXME: return Set instead of array /** Compute the greatest element of a subset. * The greatest element of a subset is an element in the * subset that is higher than all the other elements in the * subset. * @param subset A set of Objects representing the subset. * @return An Object representing the greatest element of the subset, * or null if the greatest element does not exist. * @exception IllegalArgumentException If at least one Object in the * specified array is not an element of this CPO. */ public Object greatestElement(Set subset); /** Compute the greatest lower bound (GLB) of two elements. * The GLB of two elements is the greatest element in the CPO * that is lower than or the same as both of the two elements. * @param e1 An Object representing an element in this CPO. * @param e2 An Object representing an element in this CPO. * @return An Object representing the GLB of the two specified * elements, or null if the GLB does not exist. * @exception IllegalArgumentException If at least one of the * specified Objects is not an element of this CPO. */ public Object greatestLowerBound(Object e1, Object e2); /** Compute the greatest lower bound (GLB) of a subset. * The GLB of a subset is the greatest element in the CPO that * is lower than or the same as all the elements in the * subset. * @param subset A set of Objects representing the subset. * @return An Object representing the GLB of the subset, or * null if the GLB does not exist. * @exception IllegalArgumentException If at least one Object * in the specified array is not an element of this CPO. */ public T greatestLowerBound(Set subset); /** Test if this CPO is a lattice. * A lattice is a CPO where the LUB and GLB of any pair of elements * exist. * @return True if this CPO is a lattice; * false otherwise. */ public boolean isLattice(); /** Compute the least element of a subset. * The least element of a subset is an element in the * subset that is lower than all the other element in the * subset. * @param subset A set of Objects representing the subset. * @return An Object representing the least element of the subset, * or null if the least element does not exist. * @exception IllegalArgumentException If at least one Object in the * specified array is not an element of this CPO. */ public Object leastElement(Set subset); /** Compute the least upper bound (LUB) of two elements. * The LUB of two elements is the least element in the CPO * that is greater than or the same as both of the two elements. * @param e1 An Object representing an element in this CPO. * @param e2 An Object representing an element in this CPO. * @return An Object representing the LUB of the two specified * elements, or null if the LUB does not exist. * @exception IllegalArgumentException If at least one of the * specified Objects is not an element of this CPO. */ public Object leastUpperBound(Object e1, Object e2); /** Compute the least upper bound (LUB) of a subset. * The LUB of a subset is the least element in the CPO that * is greater than or the same as all the elements in the * subset. * @param subset A set of Objects representing the subset. * @return An Object representing the LUB of the subset, or * null if the LUB does not exist. * @exception IllegalArgumentException If at least one Object * in the specified array is not an element of this CPO. */ public T leastUpperBound(Set subset); /** Return the top element of this CPO. * The top element is the element in the CPO that is higher than * all the other elements. * @return An Object representing the top element, or * null if the top does not exist. */ public Object top(); /** Compute the up-set of an element in this CPO. * The up-set of an element is the subset consisting of * all the elements higher than or the same as the specified element. * @param e An Object representing an element in this CPO. * @return An array of Objects representing the elements in the * up-set of the specified element. * @exception IllegalArgumentException If the specified Object is not * an element of this CPO, or the resulting set is infinite. */ public Object[] upSet(Object e); // FIXME: return Set instead of array /////////////////////////////////////////////////////////////////// //// public variables //// /** One of the return values of compare, indicating * that the first element is higher than the second. * @see #compare */ public static final int HIGHER = 1; /** One of the return values of compare, indicating * that the two elements are incomparable. * @see #compare */ public static final int INCOMPARABLE = 2; /** One of the return values of compare, indicating * that the first element is lower than the second. * @see #compare */ public static final int LOWER = -1; /** One of the return values of compare, indicating * that the two elements are the same. * @see #compare */ public static final int SAME = 0; /////////////////////////////////////////////////////////////////// //// public inner classes //// /** An enumeration type to represent the two different types of bounds * that can be calculated on a set of nodes in a CPO; either * a greatest lower bound or least upper bound. */ public static enum BoundType { /** Represents the greatest lower bound. */ GREATESTLOWER, /** Represents the least upper bound. */ LEASTUPPER } }