working on finite set constraints...
Thu Dec 21 07:40:43 PST 2006 kilian.sprotte@gmail.com
* working on finite set constraints...
diff -rN -u old-gecol-1/ffi.lisp new-gecol/ffi.lisp
--- old-gecol-1/ffi.lisp 2014-07-13 18:33:22.000000000 -0700
+++ new-gecol/ffi.lisp 2014-07-13 18:33:22.000000000 -0700
@@ -45,11 +45,28 @@
:icl-def ;The default consistency for a constraint.
)
+(defcenum set-rel-type
+ :srt-eq ; equality
+ :srt-nq ; disequality
+ :srt-sub ; subset
+ :srt-sup ; superset
+ :srt-disj ; disjoint
+ :srt-cmpl ; complement
+ )
+
+(defcenum set-op-type
+ :sot-union ; union
+ :sot-dunion ; disjoint union
+ :sot-inter ; intersection
+ :sot-minus ; difference
+ )
+
(defcfun ("create_space" create-space) :pointer
(varnum :int)
(varmin :int)
(varmax :int)
- (boolnum :int))
+ (boolnum :int)
+ (setnum :int))
(defcfun ("dispose_space" dispose-space) :void
(space :pointer))
@@ -295,3 +312,139 @@
(x :int)
(m :int))
+;;; Sets
+
+(defcfun gec-fs-space-put :void
+ "Place the SetVar SET into SPACE.
+After SPACE has been constructed with only the number of
+SetVars given, this needs to be done for each one.
+
+This allows for different initializations of each
+SetVar by using GEC-FS-MAKE-*."
+ (space :pointer)
+ (ind :int)
+ (set :pointer))
+
+(defcfun gec-fs-space-get :pointer
+ "Access SetVar at IND in SPACE."
+ (space :pointer)
+ (ind :int))
+
+(defcfun gec-fs-make-const :pointer
+ "Make constant SetVar of CARD with DOM (int array)."
+ (space :pointer)
+ (card :int)
+ (dom :pointer))
+
+(defcfun gec-fs-make-bounds :pointer
+ "Make SetVar with lower-bound and upper-bound.
+The dom pointers are int arrays."
+ (space :pointer)
+ (lower-card :int)
+ (lower-dom :pointer)
+ (upper-card :int)
+ (upper-dom :pointer))
+
+(defcfun gec-fs-make-lower-bound :pointer
+ "Make SetVar with lower-bound and empty upper-bound."
+ (space :pointer)
+ (lower-card :int)
+ (lower-dom :pointer))
+
+(defcfun gec-fs-make-upper-bound :pointer
+ "Make SetVar with empty lower-bound and given upper-bound."
+ (space :pointer)
+ (upper-card :int)
+ (upper-dom :pointer))
+
+(defcfun gec-fs-glb-size :unsigned-int
+ "Return number of elements in the greatest lower bound."
+ (set :pointer))
+
+(defcfun gec-fs-lub-size :unsigned-int
+ "Return number of elements in the least upper bound."
+ (set :pointer))
+
+(defcfun gec-fs-unknown-size :unsigned-int
+ "Return number of unknown elements (elements in lub but not in glb)."
+ (set :pointer))
+
+(defcfun gec-fs-card-min :unsigned-int
+ "Return cardinality minimum."
+ (set :pointer))
+
+(defcfun gec-fs-card-max :unsigned-int
+ "Return cardinality maximum."
+ (set :pointer))
+
+(defcfun gec-fs-lub-min :int
+ "Return minimum element of least upper bound."
+ (set :pointer))
+
+(defcfun gec-fs-lub-max :int
+ "Return maximum element of least upper bound."
+ (set :pointer))
+
+(defcfun gec-fs-glb-min :int
+ "Return minimum element of greatest lower bound."
+ (set :pointer))
+
+(defcfun gec-fs-glb-max :int
+ "Return maximum of greatest lower bound."
+ (set :pointer))
+
+(defcfun gec-fs-contains :boolean
+ "Test whether i is in greatest lower bound."
+ (set :pointer)
+ (x :int))
+
+(defcfun gec-fs-not-contains :boolean
+ "Test whether i is not in the least upper bound."
+ (set :pointer)
+ (x :int))
+
+(defcfun gec-fs-assigned :boolean
+ "Test whether this variable is assigned."
+ (set :pointer))
+
+(defcfun gec-fs-cardinality-const :void
+ (space :pointer)
+ (set :pointer)
+ (min :unsigned-int)
+ (max :unsigned-int))
+
+(defcfun gec-fs-cardinality :void
+ (space :pointer)
+ (set :pointer)
+ (x :int))
+
+(defcfun gec-fs-rel-setvar-setreltype-setvar :void
+ (space :pointer)
+ (x :pointer)
+ (r set-rel-type)
+ (y :pointer))
+
+(defcfun gec-fs-rel-intvar-setreltype-setvar :void
+ (space :pointer)
+ (x :int)
+ (r set-rel-type)
+ (y :pointer))
+
+(defcfun gec-fs-rel-setvar-setoptype-setvar-setreltype-setvar :void
+ (space :pointer)
+ (x :pointer)
+ (op set-op-type)
+ (y :pointer)
+ (r set-rel-type)
+ (z :pointer))
+
+(defcfun gec-fs-min :void
+ (space :pointer)
+ (set :pointer)
+ (x :int))
+
+(defcfun gec-fs-max :void
+ (space :pointer)
+ (set :pointer)
+ (x :int))
+
diff -rN -u old-gecol-1/gec.lisp new-gecol/gec.lisp
--- old-gecol-1/gec.lisp 2014-07-13 18:33:22.000000000 -0700
+++ new-gecol/gec.lisp 2014-07-13 18:33:22.000000000 -0700
@@ -69,4 +69,41 @@
(with-foreign-object (xs :int n)
(dotimes (i n)
(setf (mem-aref xs :int i) (nth i list)))
- (%gec-element-const space xs n ind var level))))
\ No newline at end of file
+ (%gec-element-const space xs n ind var level))))
+
+;;; Sets
+
+(defun gec-fs-enumerate-lower-bound (set)
+ (unless (zerop (gec-fs-glb-size set))
+ (iter
+ (for potential-elt from (gec-fs-glb-max set)
+ downto (gec-fs-glb-min set))
+ (when (gec-fs-contains set potential-elt)
+ (collect potential-elt at beginning)))))
+
+(defun gec-fs-enumerate-upper-bound (set)
+ (unless (zerop (gec-fs-lub-size set))
+ (iter
+ (for potential-elt from (gec-fs-lub-max set)
+ downto (gec-fs-lub-min set))
+ (unless (gec-fs-not-contains set potential-elt)
+ (collect potential-elt at beginning)))))
+
+(defun gec-fs-value (set)
+ "Assumes that SET is assigned."
+ (gec-fs-enumerate-lower-bound set))
+
+;;; TODO this needs to be optimized (dont iterate over list twice, if possible)
+(defmacro with-list-as-int-array ((list array size) &body body)
+ (check-type array symbol)
+ (check-type size symbol)
+ (let ((=list= (gensym "LIST")))
+ `(let* ((,=list= ,list)
+ (,size (length ,=list=)))
+ (cffi:with-foreign-object (,array :int ,size)
+ (iter
+ (for elt in ,=list=)
+ (for i upfrom 0)
+ (setf (cffi:mem-aref ,array :int i) elt))
+ ,@body))))
+
diff -rN -u old-gecol-1/gecol.asd new-gecol/gecol.asd
--- old-gecol-1/gecol.asd 2014-07-13 18:33:22.000000000 -0700
+++ new-gecol/gecol.asd 2014-07-13 18:33:22.000000000 -0700
@@ -39,6 +39,7 @@
"-lgecodesearch"
"-lgecodekernel"
"-lgecodeint"
+ "-lgecodeset"
"-lgecodeminimodel"
"-lstdc++"))
diff -rN -u old-gecol-1/glue.cpp new-gecol/glue.cpp
--- old-gecol-1/glue.cpp 2014-07-13 18:33:22.000000000 -0700
+++ new-gecol/glue.cpp 2014-07-13 18:33:22.000000000 -0700
@@ -27,13 +27,55 @@
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "gecode/int.hh"
+#include "gecode/set.hh"
#include "gecode/search.hh"
#include "gecode/minimodel.hh"
using namespace Gecode;
+// TODO avoid using void pointer for Space ?
+
+class Simple : public Space {
+protected:
+ IntVarArray vars;
+ BoolVarArray bools;
+ SetVarArray sets;
+public:
+ Simple(int varnum, int varmin, int varmax,
+ int boolnum,
+ int setnum) : vars(this, varnum, varmin, varmax),
+ bools(this, boolnum, 0, 1),
+ sets(this,setnum)
+ {
+ }
+ /// Constructor for cloning \a s
+ Simple(bool share, Simple& s) : Space(share,s) {
+ vars.update(this, share, s.vars);
+ bools.update(this, share, s.bools);
+ sets.update(this, share, s.sets);
+ }
+ /// Copy during cloning
+ virtual Space*
+ copy(bool share) {
+ return new Simple(share,*this);
+ }
+ // TODO clean this up
+ IntVarArray* get_vars () {
+ return &vars;
+ }
+ IntVarArray get_vars2 () {
+ return vars;
+ }
+ BoolVarArray get_bools2 () {
+ return bools;
+ }
+ SetVarArray get_sets () {
+ return sets;
+ }
+};
+
extern "C" {
- void* create_space(int varnum, int varmin, int varmax, int boolnum);
+ void* create_space(int varnum, int varmin, int varmax, int boolnum, int setnum);
void dispose_space(void* space);
void* create_search_engine(void* space);
void dispose_search_engine(void* engine);
@@ -79,42 +121,39 @@
void gec_element_vars(void* space, int* xs, int n, int x0, int x1, int level);
void gec_mod_12(void* space, int x, int m);
+ // Sets
+ void gec_fs_space_put(Simple* space, int ind, SetVar* set);
+ SetVar* gec_fs_space_get(Simple* space, int ind);
+ SetVar* gec_fs_make_const(Simple* space, int card, int *dom);
+ SetVar* gec_fs_make_bounds(Simple* space,
+ int lower_card, int *lower_dom,
+ int upper_card, int *upper_dom);
+ SetVar* gec_fs_make_lower_bound(Simple* space, int lower_card, int *lower_dom);
+ SetVar* gec_fs_make_upper_bound(Simple* space, int upper_card, int *upper_dom);
+ unsigned int gec_fs_glb_size(SetVar* set);
+ unsigned int gec_fs_lub_size(SetVar* set);
+ unsigned int gec_fs_unknown_size(SetVar* set);
+ unsigned int gec_fs_card_min(SetVar* set);
+ unsigned int gec_fs_card_max(SetVar* set);
+ int gec_fs_lub_min(SetVar* set);
+ int gec_fs_lub_max(SetVar* set);
+ int gec_fs_glb_min(SetVar* set);
+ int gec_fs_glb_max(SetVar* set);
+ bool gec_fs_contains(SetVar* set, int x);
+ bool gec_fs_not_contains(SetVar* set, int x);
+ bool gec_fs_assigned(SetVar* set);
+ void gec_fs_cardinality_const(Simple* space, SetVar* set, unsigned int min, unsigned int max);
+ void gec_fs_cardinality(Simple* space, SetVar* set, int x);
+ void gec_fs_rel_setvar_setreltype_setvar(Simple* space, SetVar* x, SetRelType r, SetVar* y);
+ void gec_fs_rel_intvar_setreltype_setvar(Simple* space, int x, SetRelType r, SetVar* y);
+ void gec_fs_rel_setvar_setoptype_setvar_setreltype_setvar(Simple* space, SetVar* x, SetOpType op, SetVar* y, SetRelType r, SetVar* z);
+ void gec_fs_min(Simple* space, SetVar* s, int x);
+ void gec_fs_max(Simple* space, SetVar* s, int x);
}
-class Simple : public Space {
-protected:
- IntVarArray vars;
- BoolVarArray bools;
-public:
- Simple(int varnum, int varmin, int varmax,
- int boolnum) : vars(this, varnum, varmin, varmax),
- bools(this, boolnum, 0, 1)
- {
- }
- /// Constructor for cloning \a s
- Simple(bool share, Simple& s) : Space(share,s) {
- vars.update(this, share, s.vars);
- bools.update(this, share, s.bools);
- }
- /// Copy during cloning
- virtual Space*
- copy(bool share) {
- return new Simple(share,*this);
- }
- IntVarArray* get_vars () {
- return &vars;
- }
- IntVarArray get_vars2 () {
- return vars;
- }
- BoolVarArray get_bools2 () {
- return bools;
- }
-};
-
-void* create_space(int varnum, int varmin, int varmax, int boolnum)
+void* create_space(int varnum, int varmin, int varmax, int boolnum, int setnum)
{
- Simple* s = new Simple(varnum, varmin, varmax, boolnum);
+ Simple* s = new Simple(varnum, varmin, varmax, boolnum, setnum);
return (void*)s;
}
@@ -448,3 +487,149 @@
IntVar start = minus(s, vars[x], vars[m], ICL_DOM);
mult(s, oct, twelve, start, ICL_DOM);
}
+
+// Sets
+void gec_fs_space_put(Simple* space, int ind, SetVar* set)
+{
+ SetVarArray sets = space->get_sets();
+ sets[ind] = *set;
+}
+
+SetVar* gec_fs_space_get(Simple* space, int ind)
+{
+ SetVarArray sets = space->get_sets();
+ return &(sets[ind]);
+}
+
+SetVar* gec_fs_make_const(Simple* space, int card, int *dom)
+{
+ IntSet d(dom, card);
+ return new SetVar(space, d, d);
+}
+
+SetVar* gec_fs_make_bounds(Simple* space,
+ int lower_card, int *lower_dom,
+ int upper_card, int *upper_dom)
+{
+ IntSet ld(lower_dom, lower_card);
+ IntSet ud(upper_dom, upper_card);
+ return new SetVar(space, ld, ud);
+}
+
+SetVar* gec_fs_make_lower_bound(Simple* space,
+ int lower_card, int *lower_dom)
+{
+ IntSet ld(lower_dom, lower_card);
+ return new SetVar(space, ld, IntSet::empty);
+}
+
+SetVar* gec_fs_make_upper_bound(Simple* space,
+ int upper_card, int *upper_dom)
+{
+ IntSet ud(upper_dom, upper_card);
+ return new SetVar(space, IntSet::empty, ud);
+}
+
+unsigned int gec_fs_glb_size(SetVar* set)
+{
+ return set->glbSize();
+}
+
+unsigned int gec_fs_lub_size(SetVar* set)
+{
+ return set->lubSize();
+}
+
+unsigned int gec_fs_unknown_size(SetVar* set)
+{
+ return set->unknownSize();
+}
+
+unsigned int gec_fs_card_min(SetVar* set)
+{
+ return set->cardMin();
+}
+
+unsigned int gec_fs_card_max(SetVar* set)
+{
+ return set->cardMax();
+}
+
+int gec_fs_lub_min(SetVar* set)
+{
+ return set->lubMin();
+}
+
+int gec_fs_lub_max(SetVar* set)
+{
+ return set->lubMax();
+}
+
+int gec_fs_glb_min(SetVar* set)
+{
+ return set->glbMin();
+}
+
+int gec_fs_glb_max(SetVar* set)
+{
+ return set->glbMax();
+}
+
+bool gec_fs_contains(SetVar* set, int x)
+{
+ return set->contains(x);
+}
+
+bool gec_fs_not_contains(SetVar* set, int x)
+{
+ return set->notContains(x);
+}
+
+bool gec_fs_assigned(SetVar* set)
+{
+ return set->assigned();
+}
+
+void gec_fs_cardinality_const(Simple* space, SetVar* set, unsigned int min, unsigned int max)
+{
+ cardinality(space, *set, min, max);
+}
+
+void gec_fs_cardinality(Simple* space, SetVar* set, int x)
+{
+ IntVarArray vars = space->get_vars2();
+ cardinality(space, *set, vars[x]);
+}
+
+void gec_fs_rel_setvar_setreltype_setvar(Simple* space, SetVar* x, SetRelType r, SetVar* y)
+{
+ rel(space, *x, r, *y);
+}
+
+void gec_fs_rel_intvar_setreltype_setvar(Simple* space, int x, SetRelType r, SetVar* y)
+{
+ IntVarArray vars = space->get_vars2();
+ rel(space, vars[x], r, *y);
+}
+
+// TODO ...
+
+// operation/relation
+void gec_fs_rel_setvar_setoptype_setvar_setreltype_setvar(Simple* space, SetVar* x, SetOpType op, SetVar* y, SetRelType r, SetVar* z)
+{
+ rel(space, *x, op, *y, r, *z);
+}
+
+// TODO ...
+
+void gec_fs_min(Simple* space, SetVar* s, int x)
+{
+ IntVarArray vars = space->get_vars2();
+ min(space, *s, vars[x]);
+}
+
+void gec_fs_max(Simple* space, SetVar* s, int x)
+{
+ IntVarArray vars = space->get_vars2();
+ max(space, *s, vars[x]);
+}
diff -rN -u old-gecol-1/package.lisp new-gecol/package.lisp
--- old-gecol-1/package.lisp 2014-07-13 18:33:22.000000000 -0700
+++ new-gecol/package.lisp 2014-07-13 18:33:22.000000000 -0700
@@ -76,4 +76,40 @@
#:gec-rel-const
#:gec-rel-reif
#:gec-rel-var
+ ;; Sets
+ #:gec-fs-space-put
+ #:gec-fs-space-get
+ #:gec-fs-make-const
+ #:gec-fs-make-bounds
+ #:gec-fs-make-lower-bound
+ #:gec-fs-make-upper-bound
+ #:gec-fs-glb-size
+ #:gec-fs-lub-size
+ #:gec-fs-unknown-size
+ #:gec-fs-card-min
+ #:gec-fs-card-max
+ #:gec-fs-lub-min
+ #:gec-fs-lub-max
+ #:gec-fs-glb-min
+ #:gec-fs-glb-max
+ #:gec-fs-contains
+ #:gec-fs-not-contains
+ #:gec-fs-assigned
+ ;;; Sets - lisp extensions
+ #:gec-fs-enumerate-lower-bound
+ #:gec-fs-enumerate-upper-bound
+ #:gec-fs-value
+ #:gec-fs-cardinality-const
+ #:gec-fs-cardinality
+ #:gec-fs-rel-setvar-setreltype-setvar
+ #:gec-fs-rel-setvar-setreltype-setvar-boolvar
+ #:gec-fs-rel-intvar-setreltype-setvar
+ #:gec-fs-rel-intvar-setreltype-setvar-boolvar
+ #:gec-fs-rel-setvar-setoptype-setvar-setreltype-setvar
+ #:gec-fs-min
+ #:gec-fs-max
+
+ ;;; utils
+ #:with-list-as-int-array
))
+