One
of the most striking features of QOCA is its simple interface. To understand the
interface design, consider a simple application, that of a constraintbased graphics
editor. The editor essentially provides three operations: the user may add objects or
constraints, the user may delete an object or constraint, and finally the user may edit or
directly manipulate an object. At any point in time, the configuration of the editor
consists of a set of graphic objects, a set of constraints over variables in the objects
and a current solution which is an assignment to the variables that satisfies the
constraints. The variables correspond to graphical attributes of the objects in the
diagram and the diagram on the graphics display is, therefore, simply a visual
representation of the current solution. Reflecting this
discussion, the QOCA toolkit is based on the metric space model, a new metaphor
for constraint interaction. In this model, there is a metric which gives the
distance between two assignments to the variables, and at any time there is a current set
of constraints and a current solution. Mirroring the operations in the graphic editor,
interaction in the metric space model can occur in three ways. First, a constraint
may be added to the current set of constraints in which case the new solution is the
assignment which is closest to the old assignment and which satisfies the new constraint
set. Second, a constraint may be deleted from the current set of constraints, in
which case the current solution remains unchanged. Finally, the current solution may
be manipulated by "suggesting" values for some of the variables. The new
solution is the assignment which is closest to the old assignment and to the requested
variable values and which satisfies the constraint set. The constraint set remains
unchanged.
The metric space model is closely related to the now classic hierarchical constraints approach.
The reason that we have based the toolkit on the metric space model rather than directly
on the constraint hierarchy model is that in the metric space model editing a variable
value is viewed as a different operation to constraint deletion and addition while the
natural way to model variable editing in the constraint hierarchy approach is as a
sequence of constraint deletion and additions. The advantage of having an explicit
operation for editing is that the speed requirements for editing are much more stringent
than for constraint deletion and addition because of the need to provide continuous
feedback during direct manipulation. Thus for efficiency it is important to provide
a specialized algorithm for editing which can take advantage of the fact that the current
solution is "close" to the next solution rather than using algorithms for
arbitrary constraint deletion and addition. A related advantage of the metric space model
is that we believe it more directly matches the application program needs, so it provides
a simpler and more natural interface for the application programmer.
QOCA implements the metric space model by means of three main
components: constrained variables, called CFloats, linear arithmetic constraints,
called LinConstraints, and constraint solvers, called Solvers.
Internally a CFloat, v, has a value, a
desired value, both of which are floating point numbers as well as a stay
weight, and an edit weight, which, respectively, indicate the importance of
leaving the variable unchanged if it is not being edited and the importance of changing it
to the desired value when the variable is being edited. Both weights are
nonnegative floats. The weights are set by the application programmer when the CFloat
is created and cannot be subsequently changed. Applications set the desired value
when the variable is created and also when the variable is selected for editing. The
solver is responsible for setting the actual value and will also update the desired value
to be the actual value when appropriate. To the application programmer the CFloat
appears to have a single value, since they set the desired value using the method SuggestValue,
call the solver, and then read the actual value using GetValue. However, for book
keeping reasons, the solver requires CFloats to keep the two values separate.
There are a number of different types of CFloats.
The standard CFloat used by the application programmer is the unrestricted
CFloat whose value can range over all reals. Internally the solvers also make use
of restricted CFloats whose value must be nonnegative and which are
used to represent slack variables and artificial variables.
Linear arithmetic constraints, that is LinConstraints,
can be constructed from CFloats. They have the standard form:
(a_{1} * x_{1}) + ...
+ (a_{n} * x_{n}) op c
where op is one of <, >,
>=, <= or ==, c is a float and the a_{i}s
are floats and the x_{i}s are CFloats. Note that QOCA
takes advantage of the C++ facilities for overloading operators so as to allow the natural
specification of constraints.
Actually, neither CFloats nor LinConstraints
are directly manipulated by the programmer. Instead, for efficiency and safeness
they are manipulated by means of the referencecounted "handles," CFloatHandle
and ConstraintHandle respectively. These can be assigned and constructed in
the obvious ways.
Constraint solvers form the heart of QOCA. Interaction
with a solver has two modes: constraint manipulation and editing.
Each solver provides the following Boolean methods for constraint
manipulation. Linear constraints can be added to the solver one at a time using AddConstraint.
Each time the solver checks that the new constraint is compatible with the current
constraints. If it is not, the constraint is not added and false is
returned. The solver methods RemoveConstraint allows the application
programmer to remove a constraint which is currently in the solver or indicate that it has
been changed. After the application programmer has finished adding or removing
constraints from the solver they must call the solver method Solve to find a new
assignment for the variables which is as close as possible to the current solution. The
desired values are then updated to the new solution. The reason for requiring the
programmer to perform an explicit call to Solve rather than implicitly calling Solve
after each addition or deletion is that it may be quite expensive, so should only be
called when needed.
The editing mode is used to modify the values of the
"edit" variables. Typically this occurs during direct manipulation.
First the application programmer tells the solver which variables are to be edited
using multiple calls to SetEditVar. Next BeginEdit is
called. This initializes internal data structures for fast "resolving" of
the constraints. Now during manipulation the application programmer repeatedly sets
the desired values of the edit variables and then calls the solver function Resolve
which efficiently computes the new solution to the constraints which is as close as
possible to the old solution and to the new desired values of the edit variables.
Finally the application programmer calls EndEdit to signal the end of the edit
phase.
Consider a diagram consisting of a point (xm, ym)
and a line from (xl, yl) to (xu, yu) in which the
point is constrained to lie at the midpoint of the line. The following program
fragment creates the variables and constraints, adds them to the solver and calls Solve
to compute the initial position. The constructor for CFloatHandles takes three
arguments: the stay and edit weights together with an initial desired value. Note
that both xm and ym have a stay weight of zero indicating that they are
"dependent variables," although they have a nonzero edit weight (otherwise,
editing could never change their value!). Next the program chooses xm and ym
to be the edit variables, and then repeatedly samples the mouse to find the desired
values and calls Resolve to compute the new value until the user releases the
mouse button, which finishes the edit cycle.

CFloatHandle
xl(1,1000,45.5);
CFloatHandle xl(1,1000,45.5);
CFloatHandle xm(0,1000,0);
CFloatHandle xu(1,1000,60);
CFloatHandle yl(1,1000,45.5);
CFloatHandle ym(0,1000,0);
CFloatHandle yu(1,1000,60);ConstraintHandle
xcon = (1*xl + 1*xu  2*xm == 0;
ConstraintHandle ycon = (1*yl + 1*yu  2*ym == 0);
CassSolver solver;
solver.AddConstraint(xcon);
solver.AddConstraint(ycon);
solver.Solve();
DrawLine(xl.GetValue(),yl.GetValue(),xu.GetValue(),yu.GetValue());
solver.SetEditVar(xm);
solver.SetEditVar(ym);
solv.BeginEdit();
while (mouse.button.down) {
xm.SuggestValue(mouse.x);
ym.SuggestValue(mouse.y);
solver.Resolve();
DrawLine(xl.GetValue(),yl.GetValue(),xu.GetValue(),yu.GetValue());
}
solver.EndEdit(); 
The above example is for the C++ version of QOCA.
Apart from the lack of overloaded operators and slight differences in the naming
conventions, the interface to the Java version is similar. CFloats and LinConstraints
are used directly since pointer variables in Java are reference counted. The
following is the corresponding Java code for the above example.

QcCFloat xl = new QcCFloat(1,
1000, 45.5f);
QcCFloat xm = new QcCFloat(0, 1000, 0);
QcCFloat xu = new QcCFloat(1, 1000, 60);
QcCFloat yl = new QcCFloat(1, 1000, 45.5f);
QcCFloat ym = new QcCFloat(0, 1000, 0);
QcCFloat yu = new QcCFloat(1, 1000, 60);QcLinConstraint
xcon = new QcLinConstraint();
QcLinPoly xpoly = new QcLinPoly();
xpoly.addTerm(new QcLinPolyTerm(1, xl));
xpoly.addTerm(new QcLinPolyTerm(1, xu));
xpoly.addTerm(new QcLinPolyTerm(2, xm));
xcon.makeEq(xpoly, 0);
QcLinConstraint ycon = new QcLinConstraint();
QcLinPoly ypoly = new QcLinPoly();
ypoly.addTerm(new QcLinPolyTerm(1, yl));
ypoly.addTerm(new QcLinPolyTerm(1, yu));
ypoly.addTerm(new QcLinPolyTerm(2, ym));
ycon.makeEq(ypoly, 0);
QcCassSolver solv;
solver.addConstraint(xcon);
solver.adConstraint(ycon);
solver.solve();
drawLine(xl.getValue(),yl.getValue(),xu.getValue(),yu.getValue());
solver.setEditVar(xm);
solver.setEditVar(ym);
solver.beginEdit();
while (mouse.button.down) {
xm.suggestValue(mouse.x);
ym.suggestValue(mouse.y);
solver.resolve();
drawLine(xl.getValue(),yl.getValue(),xu.getValue(),yu.getValue());
}
solver.endEdit(); 
