1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 1998 - 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Joachim Schimpf, IC-Parc 20% 21% END LICENSE BLOCK 22% ---------------------------------------------------------------------- 23% System: ECLiPSe Constraint Logic Programming System 24% Version: $Id: changeset.pl,v 1.2 2009/07/16 09:11:25 jschimpf Exp $ 25% 26% Description: Predicates to efficiently compute the set of 27% variables modified during a propagation sequence. 28% 29% Authors: J.Schimpf, IC-Parc 30% 31% ---------------------------------------------------------------------- 32 33:- module(changeset). 34 35:- comment(categories, ["Algorithms","Constraints"]). 36:- comment(summary, "Compute sets of modified variables"). 37:- comment(author, "Joachim Schimpf, IC-Parc"). 38:- comment(copyright, "Cisco Systems, Inc."). 39:- comment(date, "$Date: 2009/07/16 09:11:25 $"). 40 41:- comment(monitor_changes_arr/5, [ 42 summary:"Monitor variables for modifications", 43 amode:monitor_changes_arr(+,+,+,+,-), 44 args:["VarArr":"A structure containing variables", 45 "Prio":"Priority for the monitoring demons", 46 "CondList":"Suspension list spec", 47 "AttrMod":"Suspension list attribute module", 48 "ChangeStream":"A lazy list of lists of changes"], 49 desc:html(" 50 This predicate monitors an array of variables for certain 51 modifications, and creates a continuous stream of lists of indices of 52 modified variables, e.g. 53 <PRE> 54 monitor_changes_arr(VarArr, 8, [min of fd, max of fd], fd, Stream) 55 </PRE> 56 will monitor the variables in VarArr for modifications of their min/max 57 fd-attributes. The monitor will run with a priority of 8 to 9. 58 All variable modifications that occur between two wakings of the 59 monitor will be detected by the monitor. It will then create a list 60 of indices of the modified variables, and append this list to 61 ChangeStream. 62 <PRE> 63 [eclipse 4]: X1::1..9, X2::1..8, 64 monitor_changes_arr(v(X1,X2), 8, 65 [min of fd, max of fd], fd, Changes), 66 X1 #> X2, X2 #>= 5. 67 68 Changes = [[1], [2, 1]|More] 69 X1 = X1{[6..9]} 70 X2 = X2{[5..8]} 71 </PRE> 72 What happened here is that the first constraint X1 #> X2 caused X1 to 73 change its lower bound, therefore [1] was appended to the Changes list. 74 Then X2 #>= 5 raised the lower bound of X2 and (because X1 #> X2) 75 the lower bound of X1, therefore both variable indices [1,2] were 76 appended to the Changes list. 77 <P> 78 The priority of the monitor should be set up such that is is lower than 79 the priority of the propagation constraints. In that case, the lists 80 that get appended to ChangeStream represent exactly the set of variables 81 (without duplicates) that were modified by one propagation sequence. 82 <P> 83 Note that the ChangeStream can be used to trigger actions whenever 84 new changes get appended, for example: 85 <PRE> 86 delay report_changes(X) if var(X). 87 report_changes([]). 88 report_changes([X|T]) :- 89 printf(\"The following variables changed: %Mw%n%b\", [X]), 90 report_changes(T). 91 92 93 [eclipse 11]: X1::1..9, X2::1..8, 94 monitor_changes_arr(v(X1,X2), 8, 95 [min of fd, max of fd], fd, Changes), 96 report_changes(Changes), 97 X1 #> X2, X2 #>= 5. 98 The following variables changed: [1] 99 The following variables changed: [2, 1] 100 ... 101 <PRE> 102 ")]). 103 104:- comment(monitor_changes/6, [ 105 summary:"Monitor variables for modifications", 106 amode:monitor_changes(+,+,+,+,+,-), 107 args:["Vars":"A list containing variables", 108 "Templates":"A list of terms corresponding to the variables", 109 "Prio":"Priority for the monitoring demons", 110 "CondList":"Suspension list spec", 111 "AttrMod":"Suspension list attribute module", 112 "ChangeStream":"A lazy list of lists of changes"], 113 desc:html(" 114 Like monitor_changes_arr/5, but (instead of array indices) the 115 ChangeStream contains the elements of the Templates-list that 116 correspond to the modified variables, thus allowing arbitrary 117 information to be conveyed to the code that processes the changes. 118 <PRE> 119 [eclipse 10]: X1::1..9, X2::1..8, 120 monitor_changes([X1,X2],[info(1,X1),info(2,X2)], 8, 121 [min of fd, max of fd], fd, Stream), 122 X1 #> X2, X2 #>= 5. 123 124 Stream = [[info(1, X1{[6..9]})], [info(2, X2{[5..8]}), info(1, X1)]|More] 125 X1 = X1{[6..9]} 126 X2 = X2{[5..8]} 127 </PRE> 128 ")]). 129 130:- export 131 monitor_changes_arr/5, 132 monitor_changes/6. 133 134:- import setarg/3 from sepia_kernel. 135:- import get_attribute/3 from sepia_kernel. 136 137monitor_changes_arr(VarArr, Prio, Cond, AttrMod, ChangeStream) :- 138 Store = set(Empty), 139 functor(VarArr, _, N), 140 setup_demons_arr(VarArr, Prio, Cond, AttrMod, Store, N), 141 Prio1 is Prio+1, 142 suspend(flush_change_list(Store, ChangeStream), Prio1, Empty->inst). 143 144 setup_demons_arr(_VarArr, _Prio, _Cond, _AttrMod, _Store, 0) :- !. 145 setup_demons_arr(VarArr, Prio, Cond, AttrMod, Store, N) :- 146 arg(N, VarArr, X), 147 N1 is N-1, 148 make_suspension(change_monitor(X, N, Store, Susp), Prio, Susp), 149 insert_all(X, Susp, Cond, AttrMod), 150 setup_demons_arr(VarArr, Prio, Cond, AttrMod, Store, N1). 151 152 153monitor_changes(Vars, Templates, Prio, Cond, AttrMod, ChangeStream) :- 154 Store = set(Empty), 155 setup_demons(Vars, Templates, Prio, Cond, AttrMod, Store), 156 Prio1 is Prio+1, 157 suspend(flush_change_list(Store, ChangeStream), Prio1, Empty->inst). 158 159 setup_demons([], _Templates, _Prio, _Cond, _AttrMod, _Store). 160 setup_demons([X|Xs], [T|Ts], Prio, Cond, AttrMod, Store) :- 161 make_suspension(change_monitor(X, T, Store, Susp), Prio, Susp), 162 insert_all(X, Susp, Cond, AttrMod), 163 setup_demons(Xs, Ts, Prio, Cond, AttrMod, Store). 164 165 insert_all(_, _, [], _). 166 insert_all(X, Susp, [Cond|Conds], AttrMod) :- 167 insert_suspension(X, Susp, Cond, AttrMod), 168 insert_all(X, Susp, Conds, AttrMod). 169 170 171:- demon change_monitor/4. 172change_monitor(X, Template, Store, _Susp) :- 173 var(X), 174 Store = set(Old), 175 ( Old = [] -> true ; true ), 176 setarg(1, Store, [Template|Old]). 177change_monitor(X, Template, Store, Susp) :- 178 nonvar(X), 179 Store = set(Old), 180 ( Old = [] -> true ; true ), 181 setarg(1, Store, [Template|Old]), 182 kill_suspension(Susp). 183 184 185flush_change_list(Store, ChangeStream) :- 186 Store = set(Changes), 187 get_priority(Prio1), 188 suspend(flush_change_list(Store, More), Prio1, Empty->inst), 189 setarg(1, Store, Empty), 190 ChangeStream = [Changes|More]. % last! 191 192 193/* 194 195lib(fd). 196 197List = [X1,X2,X3,X4,X5,X6,X7,X8,X9], 198List::0..9, 199Terms = [1-X1,2-X2,3-X3,4-X4,5-X5,6-X6,7-X7,8-X8,9-X9], 200monitor_changes(List, Terms, 8, [min of fd, max of fd], fd, Stream), 201report_changes(Stream), 202call_priority((X4#>6, X7#<3, X2=5),5). 203 204List = [X1,X2,X3,X4,X5,X6,X7,X8,X9], List::0..9, VarArr =.. [vars|List], 205monitor_changes_arr(VarArr, 8, [min of fd, max of fd], fd, Stream), 206report_changes(Stream), 207call_priority((X4#>6, X7#<3, X2=5),5). 208 209List = [X1,X2,X3,X4,X5,X6,X7,X8,X9], List::0..9, VarArr =.. [vars|List], 210monitor_changes_arr(VarArr, 8, [min of fd, max of fd], fd, Stream), 211report_changes(Stream), 212X4#>6, X7#<3, X2=5. 213 214 215delay report_changes(X) if var(X). 216report_changes([]). 217report_changes([X|T]) :- 218 printf("changes: %Mw%n%b", [X]), 219 report_changes(T). 220 221 222re_solve(_Handle, _VarArr, []). 223re_solve(Handle, VarArr, [ChangedVarIndices|More]) :- 224 transfer_some_bounds(ChangedVars), 225 lp_re_solve(Handle, ChangedVarIndices, ObjVal), 226 suspend(lp_re_solve(Handle, More), 9, More->inst). 227*/ 228