package com.conveyal.r5.profile;

import com.conveyal.r5.analyst.fare.InRoutingFareCalculator;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * An implementation of DominatingList, retaining pareto-optimal paths on time and fare.
 */
public class FareDominatingList implements DominatingList {
    private InRoutingFareCalculator fareCalculator;

    private LinkedList<McRaptorSuboptimalPathProfileRouter.McRaptorState> states = new LinkedList<>();

    public FareDominatingList(InRoutingFareCalculator fareCalculator) {
        this.fareCalculator = fareCalculator;
    }

    @Override
    public boolean add(McRaptorSuboptimalPathProfileRouter.McRaptorState state) {
        int thisFare = fareCalculator.calculateFare(state).getFarePaid();

        for (Iterator<McRaptorSuboptimalPathProfileRouter.McRaptorState> it = states.iterator(); it.hasNext();) {
            McRaptorSuboptimalPathProfileRouter.McRaptorState other = it.next();

            int otherFare = fareCalculator.calculateFare(other).getFarePaid();

            // using geq/leq below to avoid codominant states in the same place on the pareto curve
            if (other.time <= state.time && otherFare <= thisFare) {
                return false;
            }

            if (other.time >= state.time && otherFare >= thisFare) {
                it.remove();
            }
        }

        // if we haven't returned false by now, state is nondominated.
        states.add(state);
        return true;
    }

    @Override
    public Collection<McRaptorSuboptimalPathProfileRouter.McRaptorState> getNonDominatedStates() {
        return states;
    }
}

@@ -27,16 +27,64 @@
 ofile;%0A%0A
+import com.conveyal.r5.analyst.fare.FareBounds;%0A
 import c
@@ -670,170 +670,523 @@
     
-@Override%0A    public boolean add(McRaptorSuboptimalPathProfileRouter.McRaptorState state) %7B%0A        int thisFare = fareCalculator.calculateFare(state).get
+/** Is dominator strictly better than dominatee? */%0A    private boolean dominates (McRaptorSuboptimalPathProfileRouter.McRaptorState dominator, McRaptorSuboptimalPathProfileRouter.McRaptorState dominatee) %7B%0A        // apply strict dominance if fares and transfer privileges are same%0A        FareBounds dominatorFare = fareCalculator.calculateFare(dominator);%0A        FareBounds dominateeFare = fareCalculator.calculateFare(dominatee);%0A        if (dominatorFare.cumulativeFarePaid == dominateeFare.cumulative
 FarePaid
 ();%0A
@@ -1173,36 +1173,35 @@
 mulativeFarePaid
-();%0A
+ &&
 %0A        for (It
@@ -1197,126 +1197,860 @@
     
-for (Iterator%3CMcRaptorSuboptimalPathProfileRouter.McRaptorState%3E it = states.iterator(); it.hasNext();) %7B
+        dominatorFare.transferPrivilege.maxValue == dominateeFare.transferPrivilege.maxValue &&%0A                dominatorFare.expirationTime %3E= dominateeFare.expirationTime &&%0A                dominatorFare.numberLimit %3E= dominateeFare.numberLimit) %7B%0A            return dominator.time %3C dominatee.time;%0A        %7D else %7B%0A            // non-strict dominance%0A            int dominateeConsumedValue = dominateeFare.cumulativeFarePaid - dominateeFare.transferPrivilege.maxValue;%0A            // if you can get to this location using the dominator for less than the %22consumed cost%22 -- i.e. the fare%0A            // minus any potential discounts -- of the dominatee, the dominatee is dominated.%0A            return dominator.time %3C dominatee.time && dominatorFare.cumulativeFarePaid %3C dominateeConsumedValue;%0A        %7D
 %0A    
+%7D%0A%0A
     
-    
+@Override%0A    public boolean add(
 McRa
@@ -2099,27 +2099,133 @@
 ate 
-other = it.n
+newState) %7B%0A        for (Iterator%3CMcRaptorSuboptimalPathProfileRouter.McRaptorState%3E it = states.iterator(); it.hasN
 ext();
-%0A
+) %7B
 %0A   
@@ -2237,71 +2237,76 @@
     
-int otherFare = fareCalculator.calculateFare(other).getFarePaid
+McRaptorSuboptimalPathProfileRouter.McRaptorState existing = it.next
 ();%0A
@@ -2426,57 +2426,37 @@
 if (
-other.time %3C= state.time && otherFare %3C= thisFare
+dominates(existing, newState)
 ) %7B%0A
@@ -2520,57 +2520,37 @@
 if (
-other.time %3E= state.time && otherFare %3E= thisFare
+dominates(newState, existing)
 ) %7B%0A
@@ -2693,17 +2693,20 @@
 tes.add(
-s
+newS
 tate);%0A 

implement proper algorithm for non-greedy fare calculation.