hi all
i need some help with this program.
basically i have to create a text formatter like word or TeX.
given a block of text i have to insert line breaks so that each line of the text will fit within a certain width.
so for each line i have to associate a penalty
so..
penalty = (text_width - linesize)^3
what i need to do is given an unformatted text and a desired width find a way to compute the formatting that minimizes the penalty
heres what i have so far. a lot of it is just ideas when i run it it does nothing.....
Code:#include <iostream>
#include <vector>
#include <string>
//////////////////////////////////////////////////////
///
/// Usage:
///
/// format_text text_width
///
/// reads lines of text on standard input, then
/// prints the text, formatted, on standard output.
///
/// line breaking is done to minimize a penalty
function.
///
//////////////////////////////////////////////////////
#include "sprint.h"
using std::vector;
using std::map;
using std::string;
using std::cout;
using std::cerr;
using std::cin;
using std::endl;
#define DEFAULT_TEXT_WIDTH 60
#define INT_INFINITY (1<<30)
#define MIN(a,b) ((a)<(b)?(a):(b))
// trim trailing blanks from a given string
void
trim(string& s) {
int i = s.size()-1;
while (i >= 0 && s[i] == ' ')
--i;
s.erase(i+1);
}
// return the penalty associated with a given line
int line_cost(string line, int text_width) {
trim(line);
int gap = text_width - line.size();
if (gap < 0) return 1000000;
return gap*gap*gap;
}
//
// given a sequence of n words, and integer text_width
//
// find the minimum total penalty possible for
// any formatting of words[0], words[1], ...,
words[n-1]
//
// return the formatted text as a string
//
//vector<string>
string format_paragraph( vector<string> words, int
text_width) {
int i,j,n,space;
n = words.size();
//vector< vector<int> >length (n,n);
int length[n];
//for(i = 0; i < n; ++i){
//length[i] = words[i];
//for(j=i+1; j<n; ++j)
//length[i][j] = length[i][j-1] + 1;
// }
//vector< vector<int> >penalty (n,n);
int penalty[n];
for( i=0; i<n; ++i){
//for( j = i; j < n; ++j){
if(length[i] < text_width)
penalty[i] = (text_width - length[i])^3;
else
penalty[i] = INT_INFINITY;
}
//int n = words.size();
//vector< vector<int> >cost (n,n);
int cost[n];
for(int i = 0; i < n; ++i){
cost[i] = penalty[i];// could be segfault
for( i = i - 1; i >= 0; --i){
int min = penalty[i];
for(int k = i; k < n; ++k){
int temp = penalty[i] + cost[i+1];
if(temp<min)
min=temp;
}
cost[i] = min;
}
}
}
int main(int argc, char *argv[]) {
int text_width = DEFAULT_TEXT_WIDTH;
if (argc >= 2) {
text_width = atoi(argv[1]);
}
// read, format, and output a sequence of paragraphs
// (new paragraph starts with a word "<p>")
while (std::cin) {
// get paragraph
vector<string> words;
while (std::cin) {
string word;
std::cin >> word;
if (word.empty()) break;
if (word == "<p>") break;
words.push_back(word);
}
// output paragraph, formatted
if (words.empty()) continue;
cout << format_paragraph(words, text_width);
cout << endl;
}
}
