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

  }

}