Nloc.java

package nloc;

import java.util.List;
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.Iterator;
import java.util.Arrays;
import java.lang.Math;
import java.util.ConcurrentModificationException;
import java.util.concurrent.ThreadLocalRandom;


public class Nloc {

  public static final int MIN_TIMEDIFF = 0;
  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);
              break;
            }
          }
          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;

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

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

        do {

          pump.removeAllDroplets();
          currentSeq = possibleSequences.remove(0);

          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);

          currentSeq = setTuplePumpoffsetToPumpPosition(currentSeq, min);

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

          currentSeq = resetPayloadDropletPosition(currentSeq);
        } while (!possibleSequences.isEmpty() && 
            !(dropletSequence.size() == currentSeq.size() &&
              this.sequenceFunctional(payloadPath)));

        if (dropletSequence.size() != currentSeq.size()) {
          dropletSequence.clear();
        }


      } catch(NoSuchModuleException nsme) {
        System.out.println(nsme.getMessage());
        System.exit(1);
      } catch(NlocStructureException nse) {
        System.out.println(nse.getMessage());
        System.exit(1);
      }

    }
    return dropletSequence;
  }

  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;
  }

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

  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) {

    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;
  }

  public List<Droplet> generateDropletListRecursive(
      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);

        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;
            }
            revIter.remove();
          }
          if (found) {
            currentPos++;
            return generateDropletListRecursive(dropletList, currentSequence,
                currentPos);
          } else {
            return dropletList;
          }
        }
      }
    }
  }

  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(
              this.computeSequences(stl, mode));
        }
        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;
    while (!allDropletsInSink()) {
      try {
        this.moveDroplets(payloadPath);
      } catch (CoalescedDropletException e) {
        works = false;
        //System.out.println("Coalesce! Droplet: " + e.getDroplet().getName() + " Position: " + e.getDroplet().getPosition().getChannel().getName());
        break;
      } 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 {

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

  public List<Channel> getBifurcationList(List<Channel> desiredPath) {

    List<Channel> bfList = new ArrayList<Channel>();

    for (Channel ch: desiredPath) {
      if (ch.isBifurcation()) {
        bfList.add(ch);
      }
    }
    return bfList;
  }
    
  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;
  }

  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);
      }
    }
    return ret;
  }

  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);
    return pl;
  }

  private void getAllPathsRecursive(Channel chan, Channel end, List<Channel> path, List<List<Channel>> pathlist) {
    path.add(chan);
    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){

    List<List<SequenceTuple>> seqTupList = new ArrayList<List<SequenceTuple>>();

    getSequencesAtBifurcationRecursive(seqTup, 0, seqTupList, mode);

    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();

    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);

    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)) {
        // 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);

            possibleSequences.add(tmp);
          }
        } 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);
          possibleSequences.add(tmp);
        }
      } else if ( !(currentBifurcation instanceof Pump)) {
        // we still have some bifurcations to check
        currentSeqTup.
          setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());
        getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex,
            possibleSequences, mode);
      } else {
        possibleSequences.add(seqTupList);
      }
    } else {
        //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, 
              possibleSequences, mode); 
        }
      } else if (!(currentBifurcation instanceof Pump)) {
        // we still have some bifurcations to check
        currentSeqTup.
          setCurrentBifurcation(currentSeqTup.getPreviousBifurcation());
        getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex,
            possibleSequences, mode);
      } else {
        getSequencesAtBifurcationRecursive(seqTupList, currentSeqTupIndex + 1, 
            possibleSequences, mode); 

      }
    }
  }

  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;
  }
}