pprint/
utils.rs

1use std::usize;
2
3/// Text justification algorithm inspired by LaTeX's algorithm.
4///
5/// This function takes a list of document lengths and a maximum line width, and returns a vector
6/// of indices that represent the end of each line in the justified text. The algorithm minimizes
7/// the "badness" of each line, which is defined as the cube of the unused space at the end of the
8/// line.
9///
10/// # Arguments
11///
12/// * `sep_length` - The length of the separator between words.
13/// * `doc_lengths` - A vector of the lengths of each word in the document.
14/// * `max_width` - The maximum line width.
15///
16/// # Returns
17///
18/// A vector of indices that represent the end of each line in the justified text.
19pub fn text_justify(sep_length: usize, doc_lengths: &Vec<usize>, max_width: usize) -> Vec<usize> {
20    // Score struct to hold the badness and the index of the next word
21    #[derive(Clone, Debug)]
22    struct Score {
23        badness: usize,
24        j: usize,
25    }
26
27    // Initialize memoization vector with maximum badness and the index of the next word
28    let n = doc_lengths.len();
29    let mut memo = vec![
30        Score {
31            badness: usize::MAX,
32            j: n
33        };
34        n + 1
35    ];
36    // The last word has no badness and does not point to any next word
37    memo[n] = Score { badness: 0, j: 0 };
38
39    // Iterate over the words in reverse order
40    for i in (0..=n).rev() {
41        let mut line_length = 0;
42
43        // For each word, calculate the line length and badness
44        for j in i..n {
45            // Add the length of the current word to the line length
46            line_length += doc_lengths[j];
47            // Add the separator length if this is not the first word in the line
48            if j > i {
49                line_length += sep_length;
50            }
51            // Ensure that the line length does not exceed the maximum width
52            line_length = line_length.min(max_width);
53
54            // Calculate the badness as the cube of the unused space at the end of the line
55            let badness = (max_width - line_length).pow(3);
56            // Get the score of the next word
57            let next_score = memo[j + 1].clone();
58
59            // If the total badness of this line and the next is less than the current badness,
60            // update the score for this word
61            if badness + next_score.badness < memo[i].badness {
62                memo[i] = Score {
63                    badness: badness + next_score.badness,
64                    j: j + 1,
65                };
66            }
67            // If the line length has reached the maximum width, break the loop
68            if line_length >= max_width {
69                break;
70            }
71        }
72    }
73
74    // Generate the list of line breaks by scanning the memoization vector
75    (0..n)
76        .scan(0, |i, _| {
77            let j = memo[*i].j;
78            *i = j;
79            Some(j)
80        })
81        .collect::<Vec<_>>()
82}
pprint/utils.rs

pprint/
utils.rs
