Newer
Older
import java.util.List;
import java.util.ArrayList;

Peter Wagenhuber
committed
import java.util.Iterator;

Peter Wagenhuber
committed
import java.lang.Math;

Peter Wagenhuber
committed
import java.util.ConcurrentModificationException;
import java.util.concurrent.ThreadLocalRandom;
private List<Channel> chanlist;
private List<Droplet> dropletList;
public Nloc (List<Channel> chanlist) {
this.chanlist = chanlist;
this.dropletList = new ArrayList<Droplet>();
}
public List<Droplet>
getShortestSequenceOnlyDefaultPathHeader(String [] modulesToVisit) {
// start at last bifrucation of payload droplet and move up all bifurcatons
// while adding header droplets that only have paths with default channels
// at bifurcations
// the list representing the sequence //
List<Droplet> dropletSequence = null;
Pump pump = this.getPump();
// get the payload path
List<List<Channel>> pathlist = this.getAllPaths();
List<Channel> moduleChanList = null;
List<Channel> payloadPath = null;
try {
moduleChanList = this.getModulesByName(Arrays.asList(modulesToVisit));
payloadPath = this.getDesiredPath(moduleChanList, pathlist);
} catch (Exception e) {
System.out.println(e.getMessage());
System.exit(1);
}
// set up initial list of sequence tuples
Droplet payloadDroplet = new Droplet(DropletType.PAYLOAD,"p");
SequenceTuple payldTuple = new SequenceTuple(payloadDroplet,payloadPath,0,0);
Channel previousBifurcation = payldTuple.getPreviousBifurcation();
payldTuple.setCurrentBifurcation(previousBifurcation);
List<SequenceTuple> s1 = new ArrayList<SequenceTuple>();
s1.add(payldTuple);
/* while still bifurcatins to cover (bifurcation not pump) ascend along
* the path of bifurcations of payload droplet and add header droplets
* that only take default paths at bifurcations
* if no header droplet found that only takes default paths stop and
* return empty list droplets indicating no suitable sequence found
*/
boolean suitableHeaderFound = true;
do {
Channel currentBifurcation = payldTuple.getCurrentBifurcation();
// check if header droplet needed
Channel bifurcSuccessor =
payloadPath.get(payloadPath.indexOf(currentBifurcation) + 1);
Channel bifurcationDefaultPath =
currentBifurcation.getChildrenList().get(0);
// bifurcation priority: prio = 0 if default channel; prio >= 1 if not
// default and threrfore header droplet needed
int prio = currentBifurcation.getChildrenList().indexOf(bifurcSuccessor);
if (prio > 0) {
// we need a header droplet
// get list of all possible header paths
List<List<Channel>> possibleHeaderPathlist = this.getAllPathsFromTo(
pump,bifurcationDefaultPath);
// find header droplets with only default pahts
List<SequenceTuple> headersWithDefaultPaths =
new ArrayList<SequenceTuple>();
for (List<Channel> path: possibleHeaderPathlist) {
if (this.pathOnlyContainsDefaults(path)) {
String randHeaderName =
"h-" + ThreadLocalRandom.current().nextInt(1000, 10000);
SequenceTuple tmpTuple =
new SequenceTuple(new Droplet(DropletType.HEADER,randHeaderName),
path, currentBifurcation);
headersWithDefaultPaths.add(tmpTuple);
// calculate and set pump offsets
List<Channel> payloadPathToCurrentBifurcation =
payloadPath.subList(0,payloadPath.indexOf(currentBifurcation) + 1);
int pathLenPayloadDroplet = this.getPayloadPathlength(
payloadPathToCurrentBifurcation);
int maxPathLenNewDroplet = getHeaderPathlength(path);
int minPathLenNewDroplet =
maxPathLenNewDroplet - bifurcationDefaultPath.getHSteps() + 1;
int newTupleMinPos = minPathLenNewDroplet - pathLenPayloadDroplet;
int newTupleMaxPos = maxPathLenNewDroplet - pathLenPayloadDroplet;
tmpTuple.setMinPos(newTupleMinPos);
tmpTuple.setMaxPos(newTupleMaxPos);
}
}
if (headersWithDefaultPaths.isEmpty()) {
// if no header with default path is found empty sequencetuple list
// and stop the search
s1.clear();
suitableHeaderFound = false;
} else {
int oldSeqTupListLen = s1.size();
for (SequenceTuple hstup: headersWithDefaultPaths) {
if (!SequenceTuple.conflictingOffsets(hstup, s1)) {
s1.add(hstup);
if ( !(payldTuple.getCurrentBifurcation() instanceof Pump) &&
oldSeqTupListLen >= s1.size()) {
s1.clear();
suitableHeaderFound = false;
}
payldTuple.setCurrentBifurcation(payldTuple.getPreviousBifurcation());
} else {
// no header needed just ascend to next bifurcation
payldTuple.setCurrentBifurcation(payldTuple.getPreviousBifurcation());
}
} while (suitableHeaderFound &&
!(payldTuple.getCurrentBifurcation() instanceof Pump));
if (!s1.isEmpty()) {
int min = 0, max = 0;
for (SequenceTuple stl: s1) {
int tmp = stl.getMinPos();
if (tmp > max) max = tmp;
if (tmp < min) min = tmp;
}
int span = max - min;
pump.setSteps(span);
s1 = setTuplePumpoffsetToPumpPosition(s1, min);
dropletSequence = generateDropletListRecursive(new ArrayList<Droplet>(),
s1, s1.get(0).getMinPos());
}
return dropletSequence;
public List<Droplet> getShortestSequence(String[] modulesToVisit,
SequenceGenerationMode mode) {
List<Droplet> dropletSequence = null;
if (mode == SequenceGenerationMode.ONLYDEFAULT) {
dropletSequence = getShortestSequenceOnlyDefaultPathHeader(modulesToVisit);
} else {
Pump pump = this.getPump();
List<List<SequenceTuple>> possibleSequences;
List<SequenceTuple> currentSeq;

Peter Wagenhuber
committed
List<List<Channel>> pathlist = this.getAllPaths();
List<Channel> moduleChanList;
List<Channel> payloadPath;
try {
moduleChanList = this.getModulesByName(Arrays.asList(modulesToVisit));
payloadPath = this.getDesiredPath(moduleChanList, pathlist);

Peter Wagenhuber
committed
possibleSequences = getPossibleSequences(modulesToVisit, mode);
// sort the list of possible sequences according to the sequences length
possibleSequences.sort((a,b) -> a.size() - b.size());

Peter Wagenhuber
committed

Peter Wagenhuber
committed
pump.removeAllDroplets();
currentSeq = possibleSequences.remove(0);

Peter Wagenhuber
committed
int min = 0, max = 0;
for (SequenceTuple stl: currentSeq) {
int tmp = stl.getMinPos();
if (tmp > max) max = tmp;
if (tmp < min) min = tmp;
}
int span = max - min;
pump.setSteps(span);

Peter Wagenhuber
committed
currentSeq = setTuplePumpoffsetToPumpPosition(currentSeq, min);

Peter Wagenhuber
committed
dropletSequence = generateDropletListRecursive(new ArrayList<Droplet>(), currentSeq, currentSeq.get(0).getMinPos());

Peter Wagenhuber
committed
currentSeq = resetPayloadDropletPosition(currentSeq);
} while (!possibleSequences.isEmpty() &&
!(dropletSequence.size() == currentSeq.size() &&
this.sequenceFunctional(payloadPath)));
if (dropletSequence.size() != currentSeq.size()) {
dropletSequence.clear();
}

Peter Wagenhuber
committed
} catch(NoSuchModuleException nsme) {
System.out.println(nsme.getMessage());
System.exit(1);
} catch(NlocStructureException nse) {
System.out.println(nse.getMessage());
System.exit(1);
}
}
return dropletSequence;

Peter Wagenhuber
committed
public boolean pathOnlyContainsDefaults(List<Channel> path) {
boolean onlyDefaults = true;
for (Channel ch: path) {
if (ch.isBifurcation()) {
onlyDefaults &= path.contains(ch.getChildrenList().get(0));
}
}
return onlyDefaults;
}

Peter Wagenhuber
committed
public void setDropletList(List<Droplet> dropletList) {
this.dropletList = dropletList;
}

Peter Wagenhuber
committed
public List<SequenceTuple> resetPayloadDropletPosition(
List<SequenceTuple> currentSequence) {
for (SequenceTuple stup: currentSequence) {
if (stup.getDroplet().getType() == DropletType.PAYLOAD) {
stup.setMinPos(0);
stup.setMaxPos(0);
}
}
return currentSequence;
}
public List<SequenceTuple> setTuplePumpoffsetToPumpPosition(
List<SequenceTuple> currentSequence, int minOffset) {

Peter Wagenhuber
committed
for (SequenceTuple stup: currentSequence) {
int pumpOffsetMin = stup.getMinPos();
stup.setMinPos(pumpOffsetMin + Math.abs(minOffset));
int pumpOffsetMax = stup.getMaxPos();
stup.setMaxPos(pumpOffsetMax + Math.abs(minOffset));
}
return currentSequence;
}

Peter Wagenhuber
committed
public List<Droplet> generateDropletListRecursive(

Peter Wagenhuber
committed
List<Droplet> dropletList, List<SequenceTuple> currentSequence,
int currentPos) {
if (dropletList.size() == currentSequence.size()) {
return dropletList;
} else {
if (dropletList.isEmpty() ||
!Position.isOccupied(dropletList, currentPos)) {
SequenceTuple tmpTup = currentSequence.get(dropletList.size());
Droplet tmpDr = tmpTup.getDroplet();
tmpDr.setPosition(new Position(this.getPump(), currentPos));
Channel pumpOutlet = tmpTup.getPumpOutlet();
tmpDr.setPumpOutlet(pumpOutlet);

Peter Wagenhuber
committed
dropletList.add(tmpDr);
// set current pos to minimum of the following sequence tuple
if (dropletList.size() < currentSequence.size()) {
currentPos =
currentSequence.get(dropletList.size()).getMinPos();
}
return generateDropletListRecursive(dropletList, currentSequence,
currentPos);
} else {
SequenceTuple tmpTup = currentSequence.get(dropletList.size());
if (currentPos < tmpTup.getMaxPos()) {
currentPos++;
return generateDropletListRecursive(dropletList, currentSequence,
currentPos);
} else {
ListIterator<Droplet> revIter = dropletList.listIterator(
dropletList.size());
boolean found = false;
while (!found && revIter.hasPrevious()) {
Droplet tmpDr = revIter.previous();
SequenceTuple tmpTup1 = currentSequence.get(dropletList.size() - 1);
if (tmpDr.getPosition().getSteps() == currentPos &&
currentPos < tmpTup1.getMaxPos()) {
found = true;
}

Peter Wagenhuber
committed
revIter.remove();
}
if (found) {
currentPos++;
return generateDropletListRecursive(dropletList, currentSequence,
currentPos);
} else {
return dropletList;
}

Peter Wagenhuber
committed
}
}
}
}
public List<List<SequenceTuple>> getPossibleSequences(
String[] modulesToVisit, SequenceGenerationMode mode) throws NoSuchModuleException {
Droplet payloadDroplet = new Droplet(DropletType.PAYLOAD,"p");
List<List<SequenceTuple>> sequences = new ArrayList<List<SequenceTuple>>();
List<List<Channel>> pathlist = this.getAllPaths();
try {
// Create initial list of possilbe sequences
List<Channel> moduleChanList =
this.getModulesByName(Arrays.asList(modulesToVisit));
List<Channel> payloadPath = this.getDesiredPath(moduleChanList, pathlist);
SequenceTuple plt = new SequenceTuple(payloadDroplet,payloadPath,0,0);
Channel previousBifurcation = plt.getPreviousBifurcation();
plt.setCurrentBifurcation(previousBifurcation);
List<SequenceTuple> s1 = new ArrayList<SequenceTuple>();
s1.add(plt);
sequences.add(s1);
List<List<SequenceTuple>> oldsequences;
do {
oldsequences = new ArrayList<List<SequenceTuple>>(sequences);
List<List<SequenceTuple>> tmpSeqs = new ArrayList<List<SequenceTuple>>();
for (List<SequenceTuple> stl: sequences) {
tmpSeqs.addAll(
}
sequences = tmpSeqs;
} while (sequences.size() != oldsequences.size());
} catch (Exception e) {
System.out.println( e.getMessage());
}
return sequences;
}
public void addChannel(Channel chan) {
chanlist.add(chan);
}
public Sink getSink() {
Sink sink = null;
for (Channel chan : chanlist) {
if (chan instanceof Sink) sink = (Sink)chan;
}
return sink;
}
public Pump getPump() {
Pump pump = null;
for (Channel chan : chanlist) {
if (chan instanceof Pump) pump = (Pump)chan;
}
return pump;
}
public boolean sequenceFunctional(List<Channel> payloadPath) {
boolean works = true;

Peter Wagenhuber
committed
while (!allDropletsInSink()) {
} catch (CoalescedDropletException e) {
works = false;
//System.out.println("Coalesce! Droplet: " + e.getDroplet().getName() + " Position: " + e.getDroplet().getPosition().getChannel().getName());
} catch (PayloadPathIncorrectException exc) {
works = false;
System.out.println("Payload path not correct");
break;
}
}
return works;
}
public List<Droplet> getDropletList() {
return dropletList;
}
public void moveDroplets(List<Channel> payloadPath)
throws CoalescedDropletException, PayloadPathIncorrectException {

Peter Wagenhuber
committed
Droplet[] drArr = this.dropletList.toArray(new Droplet[dropletList.size()]);
for (Droplet dr : drArr) {
if (dr.getType() == DropletType.PAYLOAD) {
if (payloadPath.contains(dr.getPosition().getChannel())) {
throw new PayloadPathIncorrectException();
}
}

Peter Wagenhuber
committed
for (Droplet dr: drArr) {
if (dr.coalesce()) {
throw new CoalescedDropletException(dr);
}

Peter Wagenhuber
committed
public List<Channel> getBifurcationList(List<Channel> desiredPath) {

Peter Wagenhuber
committed
List<Channel> bfList = new ArrayList<Channel>();
for (Channel ch: desiredPath) {

Peter Wagenhuber
committed
bfList.add(ch);

Peter Wagenhuber
committed
}

Peter Wagenhuber
committed
}
return bfList;

Peter Wagenhuber
committed
}
public static int getPayloadPathlength(List<Channel> path) {
int len = 0;
for (Channel ch: path) {
len += ch.getPSteps();
}
return len;
}
public static int getHeaderPathlength(List<Channel> path) {
int len = 0;
for (Channel ch: path) {
len += ch.getHSteps();
}
return len;
}

Peter Wagenhuber
committed
public boolean allDropletsInSink() {
boolean allInSink = true;
for (Droplet dr : dropletList) {
allInSink &= dr.isInSink();
}
return allInSink;
public List<Channel> getDesiredPath(List<Channel> modules,
List<List<Channel>> pathlist) throws NlocStructureException {
List<Channel> found = new ArrayList<Channel>();
for (List<Channel> path : pathlist) {
List<Channel> modlist = new ArrayList<Channel>();
for (Channel ch: path) {
if (ch instanceof Module) {
modlist.add(ch);
}
}
if (modules.equals(modlist) && found.isEmpty()) {
found = path;
} else if (modules.equals(modlist) && !found.isEmpty()) {
throw new NlocStructureException("Paths are not unique!");
}
if (found.isEmpty()) {
throw new NlocStructureException("No path found that covers all given Modules");
return found;
}
public Channel getModuleByName(String name) throws NoSuchModuleException {
Channel found = null;
for (Channel ch: chanlist) {
if (ch.getName().equals(name)) {
found = ch;
}
}
if (found == null) throw new NoSuchModuleException(name);
return found;
}
public List<Channel> getModulesByName(List<String> names)
throws NoSuchModuleException {
List<Channel> ret = new ArrayList<Channel>();
for (String name : names) {
Channel ch = getModuleByName(name);
if (name != null) {
ret.add(ch);
public List<List<Channel>> getAllPathsFromTo(Channel from, Channel to) {
List<List<Channel>> pl = new ArrayList<List<Channel>>();
List<Channel> path = new ArrayList<Channel>();
getAllPathsRecursive(from, to, path, pl);
return pl;
}
public List<List<Channel>> getAllPaths() {
List<List<Channel>> pl = new ArrayList<List<Channel>>();
List<Channel> path = new ArrayList<Channel>();
getAllPathsRecursive(this.getPump(), this.getSink(), path, pl);
private void getAllPathsRecursive(Channel chan, Channel end, List<Channel> path, List<List<Channel>> pathlist) {
if (chan.equals(end)) {
pathlist.add(path);
} else {
for (Channel ch : chan.getChildrenList()) {
getAllPathsRecursive(ch, end, new ArrayList<Channel>(path), pathlist);
public List<List<SequenceTuple>> computeSequences(List<SequenceTuple> seqTup,
SequenceGenerationMode mode){

Peter Wagenhuber
committed
List<List<SequenceTuple>> seqTupList = new ArrayList<List<SequenceTuple>>();
getSequencesAtBifurcationRecursive(seqTup, 0, seqTupList, mode);

Peter Wagenhuber
committed
return seqTupList;
}
private void getSequencesAtBifurcationRecursive(
List<SequenceTuple> seqTupList, int currentSeqTupIndex,
List<List<SequenceTuple>> possibleSequences,
SequenceGenerationMode mode) {
SequenceTuple currentSeqTup = seqTupList.get(currentSeqTupIndex);
Channel currentBifurcation = currentSeqTup.getCurrentBifurcation();

Peter Wagenhuber
committed
List<Channel> dropletPath = currentSeqTup.getPath();
Channel bifurcSuccessor =
dropletPath.get(dropletPath.indexOf(currentBifurcation) + 1);
// bifurcation priority: prio = 0 if default channel; prio >= 1 if not
// default and threrfore header droplet needed
int prio = currentBifurcation.getChildrenList().indexOf(bifurcSuccessor);

Peter Wagenhuber
committed
if (currentSeqTup.equals(seqTupList.get(seqTupList.size() - 1))) {
// if at last sequence tuple add another header droplet tuple if needed
// and add the list of sequence tuples to the possible sequences list
if (dropletPath.contains(currentBifurcation) && prio > 0 &&
!(currentBifurcation instanceof Pump)) {

Peter Wagenhuber
committed
// we need header droplet

Peter Wagenhuber
committed
// cirst check all possible paths of header droplets

Peter Wagenhuber
committed
Channel defaultChan = currentBifurcation.getChildrenList().get(0);

Peter Wagenhuber
committed
List<List<Channel>> pathList =

Peter Wagenhuber
committed
this.getAllPathsFromTo(dropletPath.get(0), defaultChan);
currentSeqTup.
setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());

Peter Wagenhuber
committed
if (mode == SequenceGenerationMode.EXHAUSTIVE) {
for (List<Channel> path: pathList) {
List<SequenceTuple> tmp =
generateNewListOfSequenceTuples(seqTupList,
path, currentBifurcation, currentSeqTup, dropletPath,
defaultChan);

Peter Wagenhuber
committed

Peter Wagenhuber
committed
}
} else if (mode == SequenceGenerationMode.RANDOMHEADER) {
List<Channel> path =
pathList.get(ThreadLocalRandom.current().nextInt(0,pathList.size()));
List<SequenceTuple> tmp =
generateNewListOfSequenceTuples(seqTupList,
path, currentBifurcation, currentSeqTup, dropletPath,
defaultChan);

Peter Wagenhuber
committed
possibleSequences.add(tmp);
}
} else if ( !(currentBifurcation instanceof Pump)) {
// we still have some bifurcations to check
currentSeqTup.
setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());
getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex,

Peter Wagenhuber
committed
} else {
possibleSequences.add(seqTupList);

Peter Wagenhuber
committed
}
//possibleSequences.add(seqTupList);
if (dropletPath.contains(currentBifurcation) && prio > 0 &&
!(currentBifurcation instanceof Pump)) {
// we need header droplet
// cirst check all possible paths of header droplets
Channel defaultChan = currentBifurcation.getChildrenList().get(0);
List<List<Channel>> pathList =
this.getAllPathsFromTo(dropletPath.get(0), defaultChan);
currentSeqTup.
setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());
if (mode == SequenceGenerationMode.EXHAUSTIVE) {
for (List<Channel> path: pathList) {
List<SequenceTuple> tmp = generateNewListOfSequenceTuples(seqTupList,
path, currentBifurcation, currentSeqTup, dropletPath,
defaultChan);
getSequencesAtBifurcationRecursive(tmp, currentSeqTupIndex + 1,
possibleSequences, mode);
} else if (mode == SequenceGenerationMode.RANDOMHEADER) {
List<Channel> path = pathList.get(
ThreadLocalRandom.current().nextInt(0,pathList.size()));
List<SequenceTuple> tmp = generateNewListOfSequenceTuples(seqTupList,
path, currentBifurcation, currentSeqTup, dropletPath,
defaultChan);
getSequencesAtBifurcationRecursive(tmp, currentSeqTupIndex + 1,
} else if (!(currentBifurcation instanceof Pump)) {
// we still have some bifurcations to check
currentSeqTup.
setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());
getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex,
} else {
getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex + 1,
}
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
private List<SequenceTuple> generateNewListOfSequenceTuples(
List<SequenceTuple> seqTupList, List<Channel> path,
Channel currentBifurcation, SequenceTuple currentSeqTup,
List<Channel> dropletPath, Channel defaultChan) {
List<SequenceTuple> tmp = new ArrayList<SequenceTuple>();
for (SequenceTuple stup: seqTupList) {
tmp.add(new SequenceTuple(stup));
}
String randHeaderName =
"h-" + ThreadLocalRandom.current().nextInt(1000, 10000);
SequenceTuple tmpTuple =
new SequenceTuple(new Droplet(DropletType.HEADER,randHeaderName),
path, currentBifurcation);
tmpTuple.setCurrentBifurcation(tmpTuple.getPreviousBifurcation());
tmp.add(tmpTuple);
// calculate and set pump offsets
int minPos = currentSeqTup.getMinPos();
int maxPos = currentSeqTup.getMaxPos();
List<Channel> pathToCurrentBifurcation =
dropletPath.subList(0,dropletPath.indexOf(currentBifurcation) + 1);
int pathLenCurrDroplet = 0;
if (currentSeqTup.getDroplet().getType() == DropletType.HEADER) {
pathLenCurrDroplet = getHeaderPathlength(pathToCurrentBifurcation);
} else {
pathLenCurrDroplet = getPayloadPathlength(pathToCurrentBifurcation);
}
int maxPathLenNewDroplet = getHeaderPathlength(path);
int minPathLenNewDroplet =
maxPathLenNewDroplet - defaultChan.getHSteps() + 1;
int newTupleMinPos =
minPos - (pathLenCurrDroplet - minPathLenNewDroplet);
int newTupleMaxPos =
maxPos - (pathLenCurrDroplet - maxPathLenNewDroplet);
tmpTuple.setMinPos(newTupleMinPos);
tmpTuple.setMaxPos(newTupleMaxPos);
return tmp;
}