// Cut a list off at a certain point in order to stay within a
// defined "budget" (according to a user-defined function giving
// a price for each element)

sclass CutListToBudget<A> {
  settable double maxPrice;
  settable Iterable<A> inputList;
  gettable L<A> outputList;
  gettable double finalPrice;
  
  // cut up last element to fill remaining budget?
  settable bool allowPartial;
  
  // last element of outputList before reduction
  // (if there was a reduction)
  gettable A fullLastElement;
  
  swappable double getPrice(A element) { throw unimplemented(); }
  
  // reduce an element to fit a budget
  // can return null if no reduced element is possible
  swappable A reduceElement(A element, double budget) { null; }
  
  *(IF1<A, Double> *getPrice) {}
  *(IF1<A, Double> *getPrice, double *maxPrice, Iterable<A> *inputList) {}
  
  run {
    outputList = new L;
    finalPrice = 0;
    fOr (element : inputList) {
      double price = getPrice(element);
      if (finalPrice + price > maxPrice) {
        if (allowPartial) {
          A partial = reduceElement(element, maxPrice-finalPrice);
          if (partial != null) {
            fullLastElement = element;
            finalPrice += getPrice(partial);
            outputList.add(partial);
            if (finalPrice > maxPrice)
              fail("reduceElement failure (over budget)");
          }
        }
        break;
      }
      finalPrice += price;
      outputList.add(element);
    }
  }
  
  L<A> get() {
    if (outputList == null) run();
    ret outputList;
  }
  
  selfType allowPartial(IF2<A, Double, A> reduceElement) {
    this.reduceElement = reduceElement;
    ret allowPartial(true);
  }
  
  A lastElement() {
    ret last(get());
  }
  
  Percent lastElementKeptPercentage() {
    ret fullLastElement == null ?: Percent(getPrice(lastElement())/getPrice(fullLastElement)*100);
  }
}

Began life as a copy of #1035616