Next: Order1, Previous: LookRight, Up: Principles list
principle.order
D
On: iset(label(D))
Order: list(label(D))
Yields: bool
On: _.D.entry.on
Order: []
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 endHere 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 endHere 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