/*  linebreaks3.c  */

/*  An optimal but inefficient algorithm.  */

/*
    This code uses an ADT called list_of_int that supports
    the following operations:
        emptylist()  returns the empty list
        empty(x)     returns true iff x is the empty list
        cons(x, y)   returns a list whose first element is x
                     and whose remaining elements are given
                     by the list y
        first        returns the first element of a nonempty list
        rest         returns the remaining elements of a nonempty list
        InitLists()
        DeleteLists()
*/
#include "linebreaks.h"
#include "lists.h"

list_of_int ChooseLB (int, int, int[], int, int*);

void ChooseLineBreaks (int n, int L[], int M, int B[]) {
    int cost;
    list_of_int breaks;
    int i;
    /*  Initialize list storage allocator.  */
    InitLists();
    breaks = ChooseLB (0, n, L, M, &cost);
    for (i = 0; i < n; i = i + 1) {
        B[i] = 0;
    }
    for ( ; ! empty (breaks); breaks = rest (breaks)) {
        B[first (breaks)] = 1;
    }
    /*  Deallocate all list storage.  */
    DeleteLists();
}

/*
    ChooseLB (i, n, L, M, costptr) returns a list of the optimal
    line breaks for L[i..n], and returns in costptr the value of
    the Ugliness function for those optimal line breaks.
*/

list_of_int ChooseLB (int i, int n, int L[], int M, int *costptr) {
    int n1 = n - 1;
    if (i == n1) {
        *costptr = 0;
        return emptylist();
    }
    else {
        list_of_int best = cons (i, ChooseLB (i + 1, n, L, M, costptr));
        int spaces = M - L[i];
        int cost = spaces * spaces * spaces + *costptr;
        int j = i + 1;
        int sum = L[i] + 1 + L[j];
        /*
            Loop invariant:
                i <= j < n,
                sum = j - i + the sum of L[i] through L[j]
                  (that is, sum is the length of words i..j when separated
                   by spaces),
                sum - L[j] <= M,
                best is a list of line breaks for L[i..n1],
                best is optimal among all lists of line breaks
                  for L[i..n1] that begin with a line break after
                  word i...word j-1, and
                cost is the Ugliness associated with best for words i..n1 only.
        */
        while ((sum <= M) && (j != n1)) {
            list_of_int breaks = ChooseLB (j + 1, n, L, M, costptr);
            int spaces = M - sum;
            int newcost = spaces * spaces * spaces + *costptr;
            if (newcost < cost) {
                best = cons (j, breaks);
                cost = newcost;
            }
            j = j + 1;
            sum = sum + 1 + L[j];
        }
        if (sum > M) {
            *costptr = cost;
            return best;
        }
        else {
            /*  j == n1, and the last line costs nothing  */
            *costptr = 0;
            return emptylist();
        }
    }
}