int next = 1;
trial = trial(num2choose, next);
} else {
+ if(this.rootNodes.size() == 1) {
+ return false;
+ }
int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
int num2choose = 0;
- if(next == this.sNodeVecs.size()) {
+ while(next == this.sNodeVecs.size()) {
// backtrack
num2choose = this.rootNodes.lastElement().size();
this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
return false;
}
next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
-
- }
+ }
num2choose++;
// reduce one from the last one
this.rootNodes.lastElement().removeElementAt(this.rootNodes.lastElement().size() - 1);
for(int i = 1; i < this.rootNodes.size(); i++) {
int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid();
while(next < tmp) {
- this.node2Combine.add(new Vector<ScheduleNode>());
Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
- for(index = 0; index < toadd.size(); index++) {
- this.node2Combine.lastElement().add(toadd.elementAt(index));
+ if(toadd != null) {
+ this.node2Combine.add(new Vector<ScheduleNode>());
+ for(index = 0; index < toadd.size(); index++) {
+ this.node2Combine.lastElement().add(toadd.elementAt(index));
+ }
+ } else {
+ this.node2Combine.add(null);
}
next++;
}
next++;
}
while(next < this.sNodeVecs.size()) {
- this.node2Combine.add(new Vector<ScheduleNode>());
Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
- for(index = 0; index < toadd.size(); index++) {
- this.node2Combine.lastElement().add(toadd.elementAt(index));
+ if(toadd != null) {
+ this.node2Combine.add(new Vector<ScheduleNode>());
+ for(index = 0; index < toadd.size(); index++) {
+ this.node2Combine.lastElement().add(toadd.elementAt(index));
+ }
+ } else {
+ this.node2Combine.add(null);
}
next++;
}
// no more nodes available to add
return false;
}
- this.rootNodes.add(new Vector<ScheduleNode>());
- first = false;
}
- this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
- num2choose--;
- index++;
- if(index == this.sNodeVecs.elementAt(next).size()) {
- index = 0;
+ if(this.sNodeVecs.elementAt(next) != null) {
+ if(first) {
+ this.rootNodes.add(new Vector<ScheduleNode>());
+ first = false;
+ }
+ this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
+ num2choose--;
+ index++;
+ if(index == this.sNodeVecs.elementAt(next).size()) {
+ index = 0;
+ next++;
+ first = true;
+ }
+ } else {
next++;
first = true;
}
}
this.combine = new Vector<Vector<Combine>>();
for(int i = 0; i < this.node2Combine.size(); i++) {
- this.combine.add(new Vector<Combine>());
- for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
- this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j)));
+ if(this.node2Combine.elementAt(i) == null) {
+ this.combine.add(null);
+ } else {
+ this.combine.add(new Vector<Combine>());
+ for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
+ this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j)));
+ }
}
}
this.lastchoices = null;
// no more available combination under this choice
// choose another choice
int next = this.node2Combine.size() - 1;
- boolean iter = false;;
+ boolean iter = false;
do{
- this.lastchoices[next]++;
- if(this.lastchoices[next] > this.node2Combine.elementAt(next).elementAt(0).getCid()) {
- // break the rule that a node can only be combined to nodes with smaller colorid.
- // backtrack
+ if(this.node2Combine.elementAt(next) != null) {
+ this.lastchoices[next]++;
+ if((this.lastchoices[next] == this.rootNodes.size() ||
+ (this.rootNodes.elementAt(this.lastchoices[next]).elementAt(0).getCid() >
+ this.node2Combine.elementAt(next).elementAt(0).getCid()))){
+ // break the rule that a node can only be combined to nodes with smaller colorid.
+ // or no more buckets
+ // backtrack
+ next--;
+ iter = true;
+ } else {
+ iter = false;
+ }
+ } else {
next--;
iter = true;
- } else {
- iter = false;
}
}while(iter && !(next < 0));
if(next < 0) {
private boolean firstexpand(int next, boolean first) {
for(int i = next; i < this.node2Combine.size(); i++) {
- int choice = this.lastchoices[i];
- for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
- Combine tmp = this.combine.elementAt(i).elementAt(j);
- if(!first) {
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- }
- tmp.root = choice;
- tmp.index = 0;
- if(!first) {
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ if(this.node2Combine.elementAt(i) != null) {
+ int choice = this.lastchoices[i];
+ for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
+ Combine tmp = this.combine.elementAt(i).elementAt(j);
+ if(!first) {
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
+ }
+ tmp.root = choice;
+ tmp.index = 0;
+ if(!first) {
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ }
}
- }
- if(first) {
- this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size();
- for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) {
- this.rootNStates.elementAt(choice).elementAt(j)[i] = 0;
+ if(first) {
+ this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size();
+ for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) {
+ this.rootNStates.elementAt(choice).elementAt(j)[i] = 0;
+ }
}
}
}
}
private boolean innertrial(int next, int layer) {
+ if((this.combine.elementAt(next) == null) ||
+ (this.combine.elementAt(next).size() < 2)) {
+ // skip over empty buckets and bucket with only one obj ( make sure
+ // at least one obj is existing in the chosen bucket)
+ if(next - 1 < 0) {
+ return false;
+ } else {
+ return innertrial(next - 1, ++layer);
+ }
+ }
Combine tmp = this.combine.elementAt(next).lastElement();
// try to move it backward
int root = tmp.root;
return innertrial(next - 1, ++layer);
}
} else if(tmp.root != root) {
+ if((tmp.root == this.lastchoices[next]) &&
+ (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] == 1)) {
+ // only 1 obj left in the chosen bucket
+ // can not move this one
+ // try the bucket in node2combine before
+ if(next - 1 < 0) {
+ return false;
+ } else {
+ return innertrial(next - 1, ++layer);
+ }
+ }
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- tmp.root = root;
+ //tmp.root = root;
+ int newroot = tmp.root + 1;
+ tmp.root = newroot;
tmp.index = 0;
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
// make all left things in this color bucket reset
- for(t += 1; t < this.combine.elementAt(next).size(); t++) {
+ for(t++; t < this.combine.elementAt(next).size(); t++) {
tmp = this.combine.elementAt(next).elementAt(t);
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- tmp.root = root;
+ tmp.root = newroot;
tmp.index = 0;
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
}
}
} else {
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
+ int tmproot = tmp.root;
+ int tmpindex = tmp.index;
tmp.root = root;
tmp.index = index;
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ int desroot = tmp.root;
+ int desindex = tmp.index;
+ // make all left things in this color bucket reset
+ t++;
+ boolean first = true;
+ while(t < this.combine.elementAt(next).size()) {
+ int k = 0;
+ if(first) {
+ k = 1;
+ first = false;
+ }
+ for(; (k < this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) && (t < this.combine.elementAt(next).size()); t++) {
+ tmp = this.combine.elementAt(next).elementAt(t);
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
+ tmp.root = desroot;
+ tmp.index = desindex;
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ }
+ if(k == this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) {
+ desindex++;
+ }
+ }
if(layer != 0) {
return firstexpand(next+1, this.first4choice);
}
}
}
} else {
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- tmp.root = root;
- tmp.index = index;
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
- if(layer != 0) {
- return firstexpand(next+1, this.first4choice);
+ if((tmp.root != this.lastchoices[next]) ||
+ (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] > 1)) {
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
+ tmp.root = root;
+ tmp.index = index;
+ this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ if(layer != 0) {
+ return firstexpand(next+1, this.first4choice);
+ }
+ return true;
+ } else {
+ // only 1 obj with the color next exist on the chosen bucket this time,
+ // can not move it, try objs in forward color bucket
+ if(next - 1 < 0) {
+ return false;
+ } else {
+ return innertrial(next - 1, ++layer);
+ }
}
- return true;
}
}
tmp.index = index;
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
t += 2;
+ Combine tmpt = null;
if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
this.rootNStates.elementAt(root).elementAt(index)[next]) {
// need to continue propagate
while(t < this.combine.elementAt(next).size()) {
- tmp = this.combine.elementAt(next).elementAt(t);
- if ((tmp.root != root) || (tmp.index != index)) {
+ tmpt = this.combine.elementAt(next).elementAt(t);
+ if ((tmpt.root != root) || (tmpt.index != index)) {
break;
}
t++;
}
if(t == this.combine.elementAt(next).size()) {
+ // last element of this color bucket
if(index + 1 < this.rootNodes.elementAt(root).size()) {
// there is available place inside the same color bucket
Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
boolean suc = propagateOne(next, root, index + 1, t - 1, tmpbk);
- if(!suc) {
+ /*if(!suc) {
// fail, roll back
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
tmp.root = rootbk;
tmp.index = indexbk;
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
- }
+ }*/
return suc;
} else if(root+1 < this.rootNodes.size()) { // check if there are another bucket
// yes
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- tmp.root = root + 1;
- tmp.index = 0;
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
+ tmpt.root = root + 1;
+ tmpt.index = 0;
+ this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
return firstexpand(next+1, this.first4choice);
} else {
// no, roll back
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
return false;
}
- } else if(tmp.root != root) {
+ } else if(tmpt.root != root) {
Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]--;
- tmpbk.root = tmp.root;
+ tmpbk.root = tmpt.root;
tmpbk.index = 0;
- root = tmp.root;
this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++;
- index = tmp.index;
+ root = tmpt.root;
+ index = tmpt.index;
// make all left things in this color bucket reset
for(t += 1; t < this.combine.elementAt(next).size(); t++) {
- tmp = this.combine.elementAt(next).elementAt(t);
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
- tmp.root = root;
- tmp.index = 0;
- this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
+ tmpt = this.combine.elementAt(next).elementAt(t);
+ this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
+ tmpt.root = root;
+ tmpt.index = 0;
+ this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
}
return firstexpand(next+1, this.first4choice);
- } else if(tmp.index != index) {
+ } else if(tmpt.index != index) {
Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
- boolean suc = propagateOne(next, root, tmp.index, t - 1, tmpbk);
+ boolean suc = propagateOne(next, root, tmpt.index, t - 1, tmpbk);
if(!suc) {
// fail, roll back
this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
projects / IRC.git / blobdiff