Next: Order1, Previous: LookRight, Up: Principles list
principle.order
D
On: iset(label(D))Order: list(label(D))Yields: bool
On: _.D.entry.onOrder: []Yields: false
{ selfSet: vec(label(D) ints)
self: label(D)
pos: ints
yield: ints
yieldS: ints
yieldL: vec(label(D) ints) }
OrderMakeNodes (priority 130),
OrderConditions (120), and OrderDist (90)
This principle assumes that the Graph principle (Graph) is used
on dimension D.
The argument variable On specifies the set of node labels
for each node to position it with respect to its daughters. The
default value is lexicalized by the lexical entry feature on on
D.
The argument variable Order specifies a total order on a subset
of the edge labels on D. Its default value is the empty list (i.e.
nothing is ordered).
The argument variable Yields specifies whether the yields
(true) or the daughters (false) of each node on D
shall be ordered. Its default value is false (i.e. the yields
are not ordered).
The order principle constrains the linear order of the nodes. In
particular, it orders the daughters of each node according to their
edge label, and positions the head with respect to the daughters using
their node label. The On argument specifies the set of
possible node labels for a node. The Order argument variable
specifies a total order on a subset of the set of labels.
Notice that there is also the more general Order1 principle
(Order1) where the Order argument variable specifies a
total order on sets of labels.
The order principle is most efficient if the following is satisfied:
Order is an exhaustive total order on all edge labels of dimension D
Yields is true
FS.int.seq of the Mozart FS library instead of Denys Duchier's
Select.seqUnion of his selection constraint package).
Here is the definition of the OrderMakeNodes constraint functor:
%% Copyright 2001-2008
%% by Ralph Debusmann <rade@ps.uni-sb.de> (Saarland University) and
%% Denys Duchier <duchier@ps.uni-sb.de> (LIFO, Orleans) and
%% Jorge Marques Pelizzoni <jpeliz@icmc.usp.br> (ICMC, Sao Paulo) and
%% Jochen Setz <info@jochensetz.de> (Saarland University)
%%
functor
import
Helpers(checkModel) at 'Helpers.ozf'
export
Constraint
prepare
RecordForAll = Record.forAll
define
proc {Constraint Nodes G Principle FD FS Select}
DVA2DIDA = Principle.dVA2DIDA
ArgRecProc = Principle.argRecProc
%%
DIDA = {DVA2DIDA 'D'}
in
%% check features
if {Helpers.checkModel 'OrderMakeNodes.oz' Nodes
[DIDA#eqdown]} then
%% get label lattice LabelLat
DIDA2LabelLat = G.dIDA2LabelLat
LabelLat = {DIDA2LabelLat DIDA}
%% get node set NodeSetM
NodeSetM = Nodes.1.nodeSet
in
for Node in Nodes do
Model = Node.DIDA.model
%%
{RecordForAll Model.selfSet proc {$ M} {FS.subset M NodeSetM} end}
{FS.subset Model.yield NodeSetM}
{FS.subset Model.yieldS NodeSetM}
{RecordForAll Model.yieldL proc {$ M} {FS.subset M NodeSetM} end}
%% get args
OnM = {ArgRecProc 'On' o('_': Node)}
in
%% self(v) in on(v)
{FS.include Model.'self' OnM}
%% pos(v) = uplus{ self_s(v) | s in selfs }
{FS.partition Model.selfSet Node.pos}
%% |self_l(v)| = 1 iff self(v) == l
for LA in LabelLat.constants do
LD = {LabelLat.aI2I LA}
in
{FD.equi
{FD.reified.equal {FS.card Model.selfSet.LA} 1}
{FD.reified.equal Model.'self' LD} 1}
end
end
end
end
end
Here is the definition of the OrderConditions constraint functor:
%% Copyright 2001-2008
%% by Ralph Debusmann <rade@ps.uni-sb.de> (Saarland University) and
%% Denys Duchier <duchier@ps.uni-sb.de> (LIFO, Orleans) and
%% Jorge Marques Pelizzoni <jpeliz@icmc.usp.br> (ICMC, Sao Paulo) and
%% Jochen Setz <info@jochensetz.de> (Saarland University)
%%
functor
import
Helpers(checkModel) at 'Helpers.ozf'
export
Constraint
define
proc {Constraint Nodes G Principle FD FS Select}
DVA2DIDA = Principle.dVA2DIDA
ArgRecProc = Principle.argRecProc
%%
DIDA = {DVA2DIDA 'D'}
in
%% check features
if {Helpers.checkModel 'OrderConditions.oz' Nodes
[DIDA#daughters
DIDA#daughtersL]} then
%% get label lattice LabelLat
DIDA2LabelLat = G.dIDA2LabelLat
LabelLat = {DIDA2LabelLat DIDA}
LCardI = LabelLat.card
%%
Models = {Map Nodes fun {$ Node} Node.DIDA.model end}
%%
YieldMs = {Map Models
fun {$ Model} Model.yield end}
%%
PosMs = {Map Nodes
fun {$ Node} Node.pos end}
in
for Node in Nodes do
Model = Node.DIDA.model
%% yield(v) = union{ pos(v') | v' in eqdown(v) }
Model.yield = {Select.union PosMs Model.eqdown}
%% yieldS(v) = union{ pos(v') | v' in down(v) }
Model.yieldS = {Select.union PosMs Model.down}
%% yieldS(v) = union{ yield(v') | v' in daughters(v) }
Model.yieldS = {Select.union YieldMs Model.daughters}
for LA in LabelLat.constants do
%% yield_l(v) = union{ yield(v') | v' in daughtersL_l(v) }
Model.yieldL.LA = {Select.union YieldMs Model.daughtersL.LA}
%% |daughtersL_l(v)| =< |yieldL_l(v)|
{FD.lesseq
{FS.card Model.daughtersL.LA}
{FS.card Model.yieldL.LA}}
end
%% yieldS(v) = union{ yield_l(v) | l in labels }
%% i.e. the union of the l-yields of v are its strict yield
Model.yieldS = {FS.unionN Model.yieldL}
%% yield(v) = pos(v) union yieldS(v)
Model.yield = {FS.unionN [Node.pos Model.yieldS]}
%% get ordered list of projections:
%% ProjLMs describes
%% proj: V -> (L -> 2^Pos) (Pos is the set of positions), where:
%% 1) if YieldsB==true then
%% proj(v)(l) = yieldL(v)(l) union selfSet(v)(l)
%% 2) if YieldsB==false then
%% proj(v)(l) = union{ pos(v') | v' in daughters(v)(l) } union
%% selfSet(v)(l)
OrderLIs = {ArgRecProc 'Order' o('_': Node)}
OrderLCardI = {Length OrderLIs}
OrderLAs = {Map OrderLIs LabelLat.i2AI}
YieldsB = {ArgRecProc 'Yields' o('_': Node)}==2
OrderProjLMs =
{Map OrderLAs
fun {$ LA}
M =
if YieldsB then
Model.yieldL.LA
else
DaughtersLM = Model.daughtersL.LA
PosDaughtersLM = {Select.union PosMs DaughtersLM}
in
%% opti
{FD.equal
{FS.card PosDaughtersLM}
{FS.card DaughtersLM}}
PosDaughtersLM
end
in
{FS.union M Model.selfSet.LA}
end}
in
%% order the projections list
if YieldsB andthen OrderLCardI==LCardI then
{Select.seqUnion OrderProjLMs Model.yield}
else
{FS.int.seq OrderProjLMs}
end
end
end
end
end
Here is the definition of the OrderDist constraint functor:
%% Copyright 2001-2008
%% by Ralph Debusmann <rade@ps.uni-sb.de> (Saarland University) and
%% Denys Duchier <duchier@ps.uni-sb.de> (LIFO, Orleans) and
%% Jorge Marques Pelizzoni <jpeliz@icmc.usp.br> (ICMC, Sao Paulo) and
%% Jochen Setz <info@jochensetz.de> (Saarland University)
%%
functor
import
% System(show)
Distributor(distributeDs distributeMs) at 'Distributor.ozf'
Helpers(checkModel) at 'Helpers.ozf'
export
Constraint
define
proc {Constraint Nodes G Principle FD FS Select}
DVA2DIDA = Principle.dVA2DIDA
%%
DIDA = {DVA2DIDA 'D'}
in
%% check features
if {Helpers.checkModel 'OrderDist.oz' Nodes
[DIDA#'self']} then
%% distribute self
SelfDs = {Map Nodes
fun {$ Node} Node.DIDA.model.'self' end}
in
{Distributor.distributeDs SelfDs FD}
end
end
end