1 // defines the sets and the relations used
15 DomainSet::DomainSet(char *name) {
24 void DomainSet::reset() {
29 char * DomainSet::getelementtype() {
33 int DomainSet::gettype() {
34 return flag%DOMAINSET_TYPED;
37 void DomainSet::settype(char *type) {
39 flag|=DOMAINSET_TYPED;
42 void DomainSet::setsubsets(char **subsets, int numsubsets) {
43 this->subsets=subsets;
44 this->numsubsets=numsubsets;
45 flag=DOMAINSET_SUBSET;
48 void DomainSet::setpartition(char **subsets, int numsubsets) {
49 this->subsets=subsets;
50 this->numsubsets=numsubsets;
51 flag=DOMAINSET_PARTITION;
54 void DomainSet::print() {
56 if (DOMAINSET_TYPED&flag)
59 if (DOMAINSET_PARTITION&flag)
61 for(int i=0;i<numsubsets;i++)
63 printf("%s ",subsets[i]);
65 printf("| %s",subsets[i]);
66 printf("Size: %d",set->size());
69 char * DomainSet::getname() {
73 WorkSet * DomainSet::getset() {
77 int DomainSet::getnumsubsets() {
81 char * DomainSet::getsubset(int i) {
90 DRelation::DRelation(char *n, char *d, char *r, int t, bool b) {
91 domain=d;range=r;type=t;name=n;
92 relation=new WorkRelation();
97 void DRelation::reset() {
99 relation=new WorkRelation();
102 bool DRelation::isstatic() {
106 char * DRelation::getdomain() {
110 char * DRelation::getrange() {
114 WorkSet* DRelation::gettokenrange() {
118 void DRelation::settokenrange(WorkSet *ws) {
124 void DRelation::print() {
125 printf("%s: %s -> %s (",name,domain,range);
126 if (type&DRELATION_MANYDOMAIN)
131 if (type&DRELATION_MANYRANGE)
139 char * DRelation::getname() {
143 WorkRelation * DRelation::getrelation() {
151 // class DomainRelation
153 DomainRelation::DomainRelation(DomainSet **s, int ns, DRelation **r,int nr) {
155 relations=r;numrelations=nr;
156 settable=new Hashtable((unsigned int (*)(void *)) & hashstring,(int (*)(void *,void *)) &equivalentstrings);
157 relationtable=new Hashtable((unsigned int (*)(void *)) & hashstring,(int (*)(void *,void *)) &equivalentstrings);
158 for(int i=0;i<numsets;i++)
159 settable->put(sets[i]->getname(),sets[i]);
160 for(int i=0;i<numrelations;i++)
161 relationtable->put(relations[i]->getname(),relations[i]);
164 void DomainRelation::reset() {
165 for(int i=0;i<numsets;i++) {
168 for(int i=0;i<numrelations;i++) {
169 relations[i]->reset();
173 bool DomainRelation::issupersetof(DomainSet *sub,DomainSet *super) {
177 sub=getsuperset(sub);
182 void DomainRelation::print() {
183 for(int i=0;i<numsets;i++) {
188 for(int i=0;i<numrelations;i++) {
189 relations[i]->print();
194 DomainSet * DomainRelation::getset(char * setname) {
196 return (DomainSet *)settable->get(setname);
200 DRelation * DomainRelation::getrelation(char * relationname) {
201 if (relationname!=NULL)
202 return (DRelation *)relationtable->get(relationname);
207 DomainRelation::~DomainRelation() {
209 delete(relationtable);
210 for(int i=0;i<numsets;i++)
212 for(int i=0;i<numrelations;i++)
213 delete(relations[i]);
218 void DomainRelation::addallsubsets(DomainSet *ds, WorkSet *ws) {
219 WorkSet *tmp=new WorkSet(true);
221 while(!tmp->isEmpty()) {
222 DomainSet *s=(DomainSet *)tmp->firstelement();
223 tmp->removeobject(s);
225 for(int j=0;j<s->getnumsubsets();j++) {
226 tmp->addobject(getset(s->getsubset(j)));
232 WorkSet * DomainRelation::conflictdelsets(char * setname, char * boundset) {
233 /* Want to know what set removals insertion into "setname" could cause */
234 if (equivalentstrings(setname,"int"))
235 return new WorkSet(true);
236 if (equivalentstrings(setname,"token"))
237 return new WorkSet(true);
238 DomainSet *bs=getset(boundset);
239 WorkSet *wsret=new WorkSet(true);
240 WorkSet *ws=new WorkSet(true);
246 DomainSet *oldcs=getset(setname);
247 DomainSet *cs=getsuperset(oldcs);
251 if (ws->contains(cs)) {
252 if (cs->gettype()==DOMAINSET_PARTITION &&
253 !equivalentstrings(cs->getname(),boundset)) {
256 ws=new WorkSet(true);
258 DomainSet *bs=getset(boundset);
259 addallsubsets(bs,ws);
261 bs=getsuperset(oldbs);
264 if (bs->gettype()!=DOMAINSET_PARTITION) {
265 for(int i=0;i<bs->getnumsubsets();i++) {
266 DomainSet *tss=getset(bs->getsubset(i));
268 addallsubsets(tss,ws);
273 bs=getsuperset(oldbs);
279 if (cs->gettype()==DOMAINSET_PARTITION) {
280 /* We have a partition...got to look at all other subsets */
281 for(int i=0;i<cs->getnumsubsets();i++) {
282 if (!equivalentstrings(cs->getsubset(i),oldcs->getname())) {
283 addallsubsets(getset(cs->getsubset(i)),wsret);
294 DomainSet * DomainRelation::getsuperset(DomainSet *s) {
295 char *name=s->getname();
296 for(int i=0;i<numsets;i++)
297 for (int j=0;j<sets[i]->getnumsubsets();j++) {
298 if(equivalentstrings(name,sets[i]->getsubset(j)))
304 WorkSet * DomainRelation::conflictaddsets(char * setname, char *boundset, model *m) {
305 /* Want to know what set additions insertion into "setname" could cause */
306 if (equivalentstrings(setname,"int"))
307 return new WorkSet(true);
308 if (equivalentstrings(setname,"token"))
309 return new WorkSet(true);
310 DomainSet *bs=getset(boundset);
311 WorkSet *wsret=new WorkSet(true);
312 WorkSet *ws=new WorkSet(true);
318 Guidance *g=m->getguidance();
319 DomainSet *ds=getset(g->insertiontoset(setname));
321 if (ws->contains(ds))
323 wsret->addobject(ds);
331 WorkSet * DomainRelation::removeconflictdelsets(char *setname) {
332 /* Obviously remove from all subsets*/
333 WorkSet *tmp=new WorkSet(true);
334 WorkSet *wsret=new WorkSet(true);
335 tmp->addobject(getset(setname));
336 while(!tmp->isEmpty()) {
337 DomainSet *s=(DomainSet *)tmp->firstelement();
338 tmp->removeobject(s);
340 for(int j=0;j<s->getnumsubsets();j++)
341 tmp->addobject(getset(s->getsubset(j)));
347 WorkSet * DomainRelation::removeconflictaddsets(char *setname, model *m) {
348 /* Remove could cause addition to a new set...*/
349 DomainSet *ds=getset(setname);
350 Guidance *g=m->getguidance();
351 char *settoputin=g->removefromset(setname);
352 if (settoputin==NULL)
353 return new WorkSet(true);
354 return conflictaddsets(settoputin, setname, m);
357 DomainSet * DomainRelation::getsource(DomainSet *s) {
358 return getsuperset(s);
361 void DomainRelation::addtoset(Element *ele, DomainSet *settoadd, model *m) {
362 /* Assumption is that object is not in set*/
363 if(settoadd->getset()->contains(ele)) /* Already in set-no worries */
365 if(settoadd->gettype()==DOMAINSET_PARTITION) {
366 /* Have to find subset to add to */
367 char *subsettoadd=m->getguidance()->insertiontoset(settoadd->getname());
368 DomainSet *setptr=getset(subsettoadd);
369 while(setptr!=settoadd) {
370 setptr->getset()->addobject(ele);
371 m->triggerrule(ele,setptr->getname());
372 setptr=getsuperset(setptr);
375 settoadd->getset()->addobject(ele);
376 m->triggerrule(ele,settoadd->getname());
377 DomainSet *oldptr=settoadd;
378 DomainSet *ptr=getsuperset(oldptr);
379 while((ptr!=NULL)&&(!ptr->getset()->contains(ele))) {
380 ptr->getset()->addobject(ele);
381 m->triggerrule(ele,ptr->getname());
383 ptr=getsuperset(ptr);
386 ptr->gettype()==DOMAINSET_PARTITION) {
387 /* may have to do removes....*/
388 for(int i=0;i<ptr->getnumsubsets();i++) {
389 char *subset=ptr->getsubset(i);
390 DomainSet *ptrsubset=getset(subset);
391 if (oldptr!=ptrsubset&&
392 ptrsubset->getset()->contains(ele)) {
394 WorkSet *ws=new WorkSet(true);
395 ws->addobject(ptrsubset);
396 while(!ws->isEmpty()) {
397 DomainSet *ds=(DomainSet *)ws->firstelement();
398 ws->removeobject(ds);
399 if (ds->getset()->contains(ele)) {
400 for(int j=0;j<ds->getnumsubsets();j++) {
401 ws->addobject(getset(ds->getsubset(j)));
403 removefromthisset(ele, ds,m);
413 void DomainRelation::abstaddtoset(Element *ele, DomainSet *settoadd, model *m) {
414 /* Assumption is that object is not in set*/
415 if(settoadd->getset()->contains(ele)) /* Already in set-no worries */
417 if(settoadd->gettype()==DOMAINSET_PARTITION) {
418 /* Have to find subset to add to */
419 char *subsettoadd=m->getguidance()->insertiontoset(settoadd->getname());
420 DomainSet *setptr=getset(subsettoadd);
421 while(setptr!=settoadd) {
422 setptr->getset()->addobject(ele);
423 m->triggerrule(ele,setptr->getname());
424 setptr=getsuperset(setptr);
427 settoadd->getset()->addobject(ele);
428 m->triggerrule(ele,settoadd->getname());
429 DomainSet *oldptr=settoadd;
430 DomainSet *ptr=getsuperset(oldptr);
431 while((ptr!=NULL)&&(!ptr->getset()->contains(ele))) {
432 ptr->getset()->addobject(ele);
433 m->triggerrule(ele,ptr->getname());
435 ptr=getsuperset(ptr);
439 void DomainRelation::removefromthisset(Element *ele, DomainSet *ds, model *m) {
440 ds->getset()->removeobject(ele); /*removed from set*/
441 /* Next need to search relations */
442 for(int i=0;i<numrelations;i++) {
443 DRelation * relation=relations[i];
444 if (equivalentstrings(relation->getdomain(),ds->getname()))
445 for(Element *target=(Element *) relation->getrelation()->getobj(ele);target!=NULL;target=(Element *) relation->getrelation()->getobj(ele)) {
446 relation->getrelation()->remove(ele,target);
447 if (relation->isstatic()) {
448 /* Have to actually remove target*/
449 DomainSet *targetset=getset(relation->getrange());
450 delfromsetmovetoset(target,targetset,m);
453 if (equivalentstrings(relation->getrange(),ds->getname()))
454 for(Element *target=(Element *) relation->getrelation()->invgetobj(ele);target!=NULL;target=(Element *) relation->getrelation()->invgetobj(ele)) {
455 relation->getrelation()->remove(target,ele);
456 if (relation->isstatic()) {
457 DomainSet *targetset=getset(relation->getdomain());
458 delfromsetmovetoset(target,targetset,m);
464 void DomainRelation::delfromsetmovetoset(Element *ele,DomainSet *deletefromset,model *m) {
465 WorkSet *ws=new WorkSet(true);
466 ws->addobject(deletefromset);
467 while(!ws->isEmpty()) {
468 DomainSet *ds=(DomainSet *)ws->firstelement();
469 ws->removeobject(ds);
470 if (ds->getset()->contains(ele)) {
471 for(int j=0;j<ds->getnumsubsets();j++) {
472 ws->addobject(getset(ds->getsubset(j)));
474 removefromthisset(ele, ds,m);
478 char *mts=m->getguidance()->removefromset(deletefromset->getname());
479 DomainSet *movetoset=getset(mts);
480 addtoset(ele, movetoset, m); //Add to the movetoset now...
483 int DomainRelation::getnumrelation() {
487 DRelation * DomainRelation::getrelation(int i) {
492 bool DomainRelation::fixstuff() {
493 bool anychange=false;
494 /* Guaranteed fixpoint because we keep removing items...finite # of items */
497 for(int i=0;i<numsets;i++) {
498 if(checksubset(sets[i])) {
503 for(int i=0;i<numrelations;i++) {
504 if(checkrelations(relations[i])) {
510 /* Fix point only necessary if repairing */
521 /* propagate the changes so that all the subset inclusion and partition
522 constraints are satisfied. */
523 bool DomainRelation::checksubset(DomainSet *ds) {
524 // remove all elements in ds that are not contained by its superset
526 DomainSet *superset=getsuperset(ds);
527 WorkSet *ws=ds->getset();
528 WorkSet *wssuper=ds->getset();
530 void *ele=ws->firstelement();
532 if (!wssuper->contains(ele)) {
534 ele=ws->getnextelement(ele);
537 ws->removeobject(old);
540 ele=ws->getnextelement(ele);
542 /* Superset inclusion property guaranteed */
545 /* If an element is contained by more than one subset, remove it from
546 all subsets but the first one. If an element is not contained by
547 any subset, remove it from the superset */
548 if (ds->gettype()==DOMAINSET_PARTITION) {
549 ele=ws->firstelement();
552 for(int i=0;i<ds->getnumsubsets();i++) {
553 char *subsetname=ds->getsubset(i);
554 DomainSet *subset=getset(subsetname);
555 if (subset->getset()->contains(ele)) {
559 /* Partition exclusion property */
562 subset->getset()->removeobject(ele);
568 /* Partition inclusion property */
571 ws->removeobject(ele);
574 ele=ws->getnextelement(ele);
582 bool DomainRelation::checkrelations(DRelation *dr) {
583 DomainSet *range=getset(dr->getrange());
584 DomainSet *domain=getset(dr->getdomain());
585 WorkSet *rangeset=NULL,*domainset=NULL;
588 rangeset=range->getset();
590 domainset=domain->getset();
591 WorkRelation *rel=dr->getrelation();
592 Tuple ele=rel->firstelement();
593 while(!ele.isnull()) {
594 if((domainset!=NULL&&!domainset->contains(ele.left))||
595 (rangeset!=NULL&&!rangeset->contains(ele.right))) {
598 ele=rel->getnextelement(l,r);
604 ele=rel->getnextelement(ele.left,ele.right);
607 /* Relation is clean now also */