deltablue.java

来自「This is a resource based on j2me embedde」· Java 代码 · 共 1,011 行 · 第 1/3 页

/*
 * @(#)DeltaBlue.java	1.6 06/10/10
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program is free software; you can redistribute it and/or  
 * modify it under the terms of the GNU General Public License version  
 * 2 only, as published by the Free Software Foundation.   
 *   
 * This program is distributed in the hope that it will be useful, but  
 * WITHOUT ANY WARRANTY; without even the implied warranty of  
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU  
 * General Public License version 2 for more details (a copy is  
 * included at /legal/license.txt).   
 *   
 * You should have received a copy of the GNU General Public License  
 * version 2 along with this work; if not, write to the Free Software  
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
 * 02110-1301 USA   
 *   
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
 * Clara, CA 95054 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */
/*

  This is a Java implemention of the DeltaBlue algorithm described in:
    "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
    by Bjorn N. Freeman-Benson and John Maloney
    January 1990 Communications of the ACM,
    also available as University of Washington TR 89-08-06.

  This implementation by Mario Wolczko, Sun Microsystems, Sep 1996,
  based on the Smalltalk implementation by John Maloney.

*/

package COM.sun.labs.kanban.DeltaBlue;

import java.util.Vector;

import Benchmark;



/* 
Strengths are used to measure the relative importance of constraints.
New strengths may be inserted in the strength hierarchy without
disrupting current constraints.  Strengths cannot be created outside
this class, so pointer comparison can be used for value comparison.
*/

class Strength {

  private int strengthValue;
  private String name;

  private Strength(int strengthValue, String name)
  {
    this.strengthValue= strengthValue;
    this.name= name;
  }

  public static boolean stronger(Strength s1, Strength s2)
  {
    return s1.strengthValue < s2.strengthValue;
  }

  public static boolean weaker(Strength s1, Strength s2)
  {
    return s1.strengthValue > s2.strengthValue;
  }

  public static Strength weakestOf(Strength s1, Strength s2)
  {
    return weaker(s1, s2) ? s1 : s2;
  }

  public static Strength strongest(Strength s1, Strength s2)
  {
    return stronger(s1, s2) ? s1 : s2;
  }

  // for iteration
  public Strength nextWeaker()
  {
    switch (strengthValue) {
    case 0: return weakest;
    case 1: return weakDefault;
    case 2: return normal;
    case 3: return strongDefault;
    case 4: return preferred;
    case 5: return strongPreferred;

    case 6: 
    default:
      System.err.println("Invalid call to nextStrength()!");
      System.exit(1);
      return null;
    }
  }

  // Strength constants
  public final static Strength required       = new Strength(0, "required");
  public final static Strength strongPreferred= new Strength(1, "strongPreferred");
  public final static Strength preferred      = new Strength(2, "preferred");
  public final static Strength strongDefault  = new Strength(3, "strongDefault");
  public final static Strength normal	      = new Strength(4, "normal");
  public final static Strength weakDefault    = new Strength(5, "weakDefault");
  public final static Strength weakest	      = new Strength(6, "weakest");

  public void print()
  {
    System.out.print("strength[" + Integer.toString(strengthValue) + "]");
  }
}




//------------------------------ variables ------------------------------

// I represent a constrained variable. In addition to my value, I
// maintain the structure of the constraint graph, the current
// dataflow graph, and various parameters of interest to the DeltaBlue
// incremental constraint solver.

class Variable {

  public int value;               // my value; changed by constraints
  public Vector constraints;      // normal constraints that reference me
  public Constraint determinedBy; // the constraint that currently determines
                                  // my value (or null if there isn't one)
  public int mark;                // used by the planner to mark constraints
  public Strength walkStrength;   // my walkabout strength
  public boolean stay;            // true if I am a planning-time constant
  public String	name;             // a symbolic name for reporting purposes


  private Variable(String name, int initialValue, Strength walkStrength,
		   int nconstraints)
  {
    value= initialValue;
    constraints= new Vector(nconstraints);
    determinedBy= null;
    mark= 0;
    this.walkStrength= walkStrength;
    stay= true;
    this.name= name;
  }

  public Variable(String name, int value)
  {
    this(name, value, Strength.weakest, 2);
  }

  public Variable(String name)
  {
    this(name, 0, Strength.weakest, 2);
  }

  public void print()
  {
    System.out.print(name + "(");
    walkStrength.print();
    System.out.print("," + value + ")");
  }
  
  // Add the given constraint to the set of all constraints that refer to me.
  public void addConstraint(Constraint c)
  {
    constraints.addElement(c);
  }

  // Remove all traces of c from this variable.
  public void removeConstraint(Constraint c)
  {
    constraints.removeElement(c);
    if (determinedBy == c) determinedBy= null;
  }

  // Attempt to assign the given value to me using the given strength.
  public void setValue(int value, Strength strength)
  {
    EditConstraint e= new EditConstraint(this, strength);
    if (e.isSatisfied()) {
      this.value= value;
      DeltaBlue.planner.propagateFrom(this);
    }
    e.destroyConstraint();
  }

}




//------------------------ constraints ------------------------------------

// I am an abstract class representing a system-maintainable
// relationship (or "constraint") between a set of variables. I supply
// a strength instance variable; concrete subclasses provide a means
// of storing the constrained variables and other information required
// to represent a constraint.

abstract class Constraint {

  public Strength strength; // the strength of this constraint

  protected Constraint() {} // this has to be here because of
                            // Java's constructor idiocy.

  protected Constraint(Strength strength)
  {
    this.strength= strength;
  }

  // Answer true if this constraint is satisfied in the current solution.
  public abstract boolean isSatisfied();

  // Record the fact that I am unsatisfied.
  public abstract void markUnsatisfied();

  // Normal constraints are not input constraints. An input constraint
  // is one that depends on external state, such as the mouse, the
  // keyboard, a clock, or some arbitrary piece of imperative code.
  public boolean isInput() { return false; }

  // Activate this constraint and attempt to satisfy it.
  protected void addConstraint()
  {
    addToGraph();
    DeltaBlue.planner.incrementalAdd(this);
  }

  // Deactivate this constraint, remove it from the constraint graph,
  // possibly causing other constraints to be satisfied, and destroy
  // it.
  public void destroyConstraint()
  {
    if (isSatisfied()) DeltaBlue.planner.incrementalRemove(this);
    removeFromGraph();
  }

  // Add myself to the constraint graph.
  public abstract void addToGraph();

  // Remove myself from the constraint graph.
  public abstract void removeFromGraph();

  // Decide if I can be satisfied and record that decision. The output
  // of the choosen method must not have the given mark and must have
  // a walkabout strength less than that of this constraint.
  protected abstract void chooseMethod(int mark);

  // Set the mark of all input from the given mark.
  protected abstract void markInputs(int mark);

  // Assume that I am satisfied. Answer true if all my current inputs
  // are known. A variable is known if either a) it is 'stay' (i.e. it
  // is a constant at plan execution time), b) it has the given mark
  // (indicating that it has been computed by a constraint appearing
  // earlier in the plan), or c) it is not determined by any
  // constraint.
  public abstract boolean inputsKnown(int mark);

  // Answer my current output variable. Raise an error if I am not
  // currently satisfied.
  public abstract Variable output();

  // Attempt to find a way to enforce this constraint. If successful,
  // record the solution, perhaps modifying the current dataflow
  // graph. Answer the constraint that this constraint overrides, if
  // there is one, or nil, if there isn't.
  // Assume: I am not already satisfied.
  //
  public Constraint satisfy(int mark)
  {
    chooseMethod(mark);
    if (!isSatisfied()) {
      if (strength == Strength.required) {
	DeltaBlue.error("Could not satisfy a required constraint");
      }
      return null;
    }
    // constraint can be satisfied
    // mark inputs to allow cycle detection in addPropagate
    markInputs(mark);
    Variable out= output();
    Constraint overridden= out.determinedBy;
    if (overridden != null) overridden.markUnsatisfied();
    out.determinedBy= this;
    if (!DeltaBlue.planner.addPropagate(this, mark)) {
      System.out.println("Cycle encountered");
      return null;
    }
    out.mark= mark;
    return overridden;
  }

  // Enforce this constraint. Assume that it is satisfied.
  public abstract void execute();

  // Calculate the walkabout strength, the stay flag, and, if it is
  // 'stay', the value for the current output of this
  // constraint. Assume this constraint is satisfied.
  public abstract void recalculate();

  protected abstract void printInputs();

  protected void printOutput() { output().print(); }

  public void print()
  {
    int i, outIndex;

    if (!isSatisfied()) {
      System.out.print("Unsatisfied");
    } else {
      System.out.print("Satisfied(");
      printInputs();
      System.out.print(" -> ");
      printOutput();
      System.out.print(")");
    }
    System.out.print("\n");
  }

}



//-------------unary constraints-------------------------------------------

// I am an abstract superclass for constraints having a single