Nloc.java

package nloc;

import java.util.List;
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.Arrays;
import java.lang.Math;

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<List<SequenceTuple>> sanitizeSequences(
//      List<List<SequenceTuple>> possibleSequences) {
//
//    List<List<SequenceTuple>> tmpSeqs = 
//      new ArrayList<List<SequenceTuple>>();
//
//    for(List<SequenceTuple> seqTupList: possibleSequences) {
//
//      List<SequenceTuple> tmpStl = new ArrayList<SequenceTuple>(seqTupList);
//
//      for (SequenceTuple seqTup: seqTupList) {
//
//        if (seqTup.getDroplet().getType() != DropletType.PAYLOAD) {
//
//          List<Channel> hPath = seqTup.getPath();
//
//          // generate sublist for comaparison containing the rest of the 
//          // sequence tuples 
//          List<SequenceTuple> compList = 
//            seqTupList.sublist(seqTupList.indexOf(seqTup),
//                seqTupList.size() - 1);
//          
//          for (SequenceTuple compTuple: compList) {
//            List<Channel> cPath = compTuple.getPath();
//
//            if (seqTup.overlaps(compTuple)) {
//              // check if path is the same
//              // if so then merge the droplets to one 
//              // if not adjust the min and max position
//              // if the adjustment is not possible remove the sequence
//              if (hPath.equals(cPath)) {
//                SequenceTuple newTup = SequenceTuple.merge(seqTup,compTuple);
//                tmpStl.remove(seqTup);
//                tmpStl.remove(compTuple);
//                tmpStl.add(newTup);
//              } // end paths are equal
//              else {
//                int hMin = seqTup.getMinPos();
//                int hMax = seqTup.getMaxPos();
//                int cMin = compTuple.getMaxPos();
//                int cMax = compTuple.getMaxPos();
//                if (hMin == hMax && cMin == cMax) {
//                  tmpStl.clear();
//                } else if ((hMax - hMin) < (cMax - cMin)) {
//                  if (hMax < cMax) {
//                    compTuple.setMinPos(hMax + 1);
//                  } else {
//                    compTuple.setMaxPos(hMin - 1);
//                  }
//                } else if ((hMax - hMin) > (cMax - cMin)) {
//                  if (cMax < hMax) {
//                    seqTup.setMinPos(cMax + 1);
//                  } else {
//                    seqTup.setMaxPos(cMin - 1);
//                  }
//                } else if ((hMax - hMin) > (cMax - cMin)) {
//                  if (hMin == cMin) {
//                    
//                  } else if (hMin < cMin) {
//                    seqTup.setMaxPos(cMin - 1);  
//                  } else {
//                    compTuple.setMaxPos(hMin - 1);
//                  }
//                }
//
//              } // end paths are not equal
//
//            } // typles overlap
//          } // end iter restlist
//        } // payload droplet
//      } // end iter sequence 
//      if (!tmpStl.isEmpty()) {
//        tmpSeqs.add(tmpStl);
//      }
//    } // end iter possibleSequences 
//    return tmpSeqs;
//  }

      //ListIterator<SequenceTuple> seqIter = currentSeq.ListIterator();

      //while (seqIter.hasNext()) {
      //  SequenceTuple currentSeqTuple = seqIter.next();
      //  int minPos = currentSeqTuple.getMinPos();
      //  int maxPos = currentSeqTuple.getMaxPos();

      //  Position initialDropletPosition = new Position(pump, minPos);
      //  Droplet currentDroplet = currentSeqTuple.getDroplet();
      //  
      //  if (position.alreadyOccupied(dropletSequence)) {
      //    // if occupied first try to increase position until max is reached
      //    // if max is also occupied then step back one droplet in list 
      //    // and increase its position
      //    // if all fails return null pump indicating that no sequence could 
      //    // be found
      //    for (int i = minPos; i <= maxPos; i++) {

      //    }

      //  } else {
      //    currentDroplet.setPosition(initialDropletPosition);
      //    dropletSequence.add(currentDroplet);
      //  }
      //}
       
  public Pump getShortestSequence(String[] modulesToVisit) {

    Pump pump = this.getPump();
    try {
      List<List<SequenceTuple>> possibleSequences =
        getPossibleSequences(modulesToVisit);

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

      List<SequenceTuple> currentSeq = possibleSequences.get(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);
    
      possibleSequences = setTuplePumpoffsetToPumpPosition(possibleSequences, 
          min);

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

      
    } catch(NoSuchModuleException nsme) {
      System.out.println(nsme.getMessage());
    }

    return pump;
  }

  public List<List<SequenceTuple>> setTuplePumpoffsetToPumpPosition(
      List<List<SequenceTuple>> possibleSequences, int minOffset) {
      
    for (List<SequenceTuple> stl: possibleSequences) {
      for (SequenceTuple stup: stl) {
        int pumpOffsetMin = stup.getMinPos();
        stup.setMinPos(pumpOffsetMin + Math.abs(minOffset));

        int pumpOffsetMax = stup.getMaxPos();
        stup.setMaxPos(pumpOffsetMax + Math.abs(minOffset));
      }
    }
    return possibleSequences;
  }

  private 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();
            revIter.remove();
            SequenceTuple tmpTup1 = currentSequence.get(dropletList.size() - 1);

            if (tmpDr.getPosition().getSteps() == currentPos &&
                currentPos < tmpTup1.getMaxPos()) {
              found = true;
            }
          }
          if (found) {
            currentPos++;
            return generateDropletListRecursive(dropletList, currentSequence,
                currentPos);
          } else {
            return dropletList;
          }
        }
      }
    }
  }

  public List<List<SequenceTuple>> getPossibleSequences(
    String[] modulesToVisit) 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);
      List<SequenceTuple> s1 = new ArrayList<SequenceTuple>();
      s1.add(plt);

      sequences.add(s1);

      List<Channel> bifurcationList = this.getBifurcationList(payloadPath);

      // actually compile list of sequences going through the bifurcations from
      // "end" to "start"
      for (int i = bifurcationList.size() - 1; i >= 0; --i) {
        Channel currentBifurcation = bifurcationList.get(i);
        List<List<SequenceTuple>> tmpSeqs = new ArrayList<List<SequenceTuple>>();
        for (List<SequenceTuple> stl: sequences) {
          tmpSeqs.addAll(
              this.getSequencesAtBifurcation(stl, currentBifurcation));
        }
        sequences = tmpSeqs;
      }
    } 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 simulate() {
    boolean works = true;
    while (!allDropletsInSink()) {
      try {
        this.moveDroplets();
      } catch (CoalescedDropletException e) {
        works = false;
        System.out.println(e.getDroplet());
        break;
      }
    }
    return works;
  }

  public List<Droplet> getDropletList() {
    return dropletList;
  }

  public void moveDroplets() throws CoalescedDropletException {
    for (Droplet dr : dropletList) {
      dr.move();
    }
    for (Droplet dr: dropletList) {
      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>> getSequencesAtBifurcation(
      List<SequenceTuple> seqTup, Channel currentBifurcation) {


    List<List<SequenceTuple>> seqTupList = new ArrayList<List<SequenceTuple>>();
    SequenceTuple currentSeqTup = seqTup.get(0);

    getSequencesAtBifurcationRecursive(seqTup, currentSeqTup, seqTupList,
        currentBifurcation);

    return seqTupList;
  }

  private void getSequencesAtBifurcationRecursive(
      List<SequenceTuple> seqTupList, SequenceTuple currentSeqTup, 
      List<List<SequenceTuple>> possibleSequences, Channel currentBifurcation) {

    // check if header droplet is needed
    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) {
        System.out.println("At last sequence tuple and adding header droplet(s) to: " + currentSeqTup.getDroplet().getName() + ": " + currentSeqTup.getMinPos());
        System.out.println("");
        // 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);

        for (List<Channel> path: pathList) {
          List<SequenceTuple> tmp = new ArrayList<SequenceTuple>(seqTupList);
          SequenceTuple tmpTuple = 
            new SequenceTuple(new Droplet(DropletType.HEADER,"h"),path);
          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;

          //System.out.println("minPos: " + minPos + " pathLenCurrDroplet: " +
          //    pathLenCurrDroplet + " minPathLenNewDroplet: " + minPathLenNewDroplet);
          int newTupleMinPos = 
            minPos - (pathLenCurrDroplet - minPathLenNewDroplet);
          int newTupleMaxPos = 
            maxPos - (pathLenCurrDroplet - maxPathLenNewDroplet);

          tmpTuple.setMinPos(newTupleMinPos);
          tmpTuple.setMaxPos(newTupleMaxPos);

          possibleSequences.add(tmp);
        }
      } else {
        System.out.println("At last sequence tuple and NOT adding header droplet(s) to: " + currentSeqTup.getDroplet().getName() + ": " + currentSeqTup.getMinPos());
        System.out.println("");
        possibleSequences.add(seqTupList);
      }
    } else {
      if (dropletPath.contains(currentBifurcation) && prio > 0) {
        System.out.println("NOT at last sequence tuple and ");
        System.out.println("Adding header droplet(s) to: " + currentSeqTup.getDroplet().getName() + ": " + currentSeqTup.getMinPos());
        System.out.println("");
        // 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);

        for (List<Channel> path: pathList) {
          List<SequenceTuple> tmp = new ArrayList<SequenceTuple>(seqTupList);
          SequenceTuple tmpTuple = 
            new SequenceTuple(new Droplet(DropletType.HEADER,"h"),path);
          tmp.add(seqTupList.indexOf(currentSeqTup) + 1, 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;

          //System.out.println("minPos: " + minPos + " pathLenCurrDroplet: " +
          //    pathLenCurrDroplet + " minPathLenNewDroplet: " + minPathLenNewDroplet);
          int newTupleMinPos = 
            minPos - (pathLenCurrDroplet - minPathLenNewDroplet);
          int newTupleMaxPos = 
            maxPos - (pathLenCurrDroplet - maxPathLenNewDroplet);

          tmpTuple.setMinPos(newTupleMinPos);
          tmpTuple.setMaxPos(newTupleMaxPos);

          getSequencesAtBifurcationRecursive(tmp, 
              seqTupList.get(seqTupList.indexOf(currentSeqTup) + 1), 
              possibleSequences, currentBifurcation); 
        }
      } else {
        System.out.println("NOT at last sequence tuple and NOT adding header droplets to: " + currentSeqTup.getDroplet().getName() + ": " + currentSeqTup.getMinPos());
        System.out.println("");
        getSequencesAtBifurcationRecursive(seqTupList, 
            seqTupList.get(seqTupList.indexOf(currentSeqTup) + 1), 
            possibleSequences, currentBifurcation); 

      }
    }
  }
}