Jump to content
  • Advertisement
Sign in to follow this  
Concentrate

Any hint or ideas on how to full-justify a given text

This topic is 2563 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Given Text = word[sub]1[/sub] word[sub]2[/sub] ... word[sub]n[/sub]
WIDTH = maximum number of character per line

Output a fully-justified version of Text.


Any hints on this problem?

Share this post


Link to post
Share on other sites
Advertisement
Roughly, you have a maximum width, and you can calculate the total width of the text you have been given. If the text isn't as wide as the maximum, then you need to justify it: in other words, evenly add spaces between words until you hit the maximum width.

Share this post


Link to post
Share on other sites
I'm curious why left-aligned isn't sufficient.

Be careful with justified text: sometimes the combination of width and text can lead to a line with ridiculously wide spaces between words. Every time I see that (which is more common than you might think) I wish the typesetter had been satisfied with left-aligned.

Share this post


Link to post
Share on other sites

I'm curious why left-aligned isn't sufficient.

Be careful with justified text: sometimes the combination of width and text can lead to a line with ridiculously wide spaces between words. Every time I see that (which is more common than you might think) I wish the typesetter had been satisfied with left-aligned.


Its a requirement. Thanks for the hint swiftcoder. I realize that for each space I need to pad by some amount of extra space. Now I just need to workout the math that calculates it. Will report back today if I have the time to work on it.

Share this post


Link to post
Share on other sites

Roughly, you have a maximum width, and you can calculate the total width of the text you have been given. If the text isn't as wide as the maximum, then you need to justify it: in other words, evenly add spaces between words until you hit the maximum width.


Easy enough. This is what I ended up doing.

Input: A string of words[separated by spaces] such that its width is less than MAX_WIDTH_PER_LINE
1) Calculate the difference between MAX_WIDTH_PER_LINE and the width of the string, call it P.
2) Use the difference to evenly distribute between each word, i.e add P/(numOfWords-1) spaces between words
3) Also calculate P % (numOfWords-1) and 'evenly' distribute that space between the line.


That works ok for the given assumption. But if the assumption does not hold, for example I was given a really long line, then I would need to break the line apart. The
way I am doing the breaking is to get as much as words possible such that its size is the closest to the limit. Then call the above algorithm. And repeat for next line.
But I'm not sure if this is entirely a good approach, because usually when using such greedy approach and knowing that a words length on average is not high, the sum of the words length used for the above
algorithm will close to the limit. Hence usually in step 2, P/(numOfWords-1) is 0 and so we are only left with the padding in step 3. Any advice? I hope it was clear enough. If not I can show an example.

Share this post


Link to post
Share on other sites
A relatively clean way to do this is to write a class JustifiedOutput where you can push words and paragraph breaks and which will buffer words internally until the line width is reached.

I gave it a quick try and the code is a bit messier than I would like, but the basic idea seems to work:
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

class JustifiedOutput {
std::ostream &os;
unsigned width;
std::vector<std::string> word_buffer;
unsigned buffer_length;
bool brand_new_paragraph;

public:
JustifiedOutput(std::ostream &os, unsigned width)
: os(os),
width(width),
brand_new_paragraph(true) {
}

void push_word(std::string word) {
brand_new_paragraph = false;

if (word.length() > width) {
// We'll have to break this word across lines
for (unsigned i=0, n_words = word_buffer.size(); i<n_words; ++i)
os << word_buffer << ' ';
word_buffer.clear();

do {
unsigned space_left = width - buffer_length - (buffer_length > 0);
buffer_length = 0;

for (unsigned j=0; j<space_left; ++j)
os << word[j];

os << '\n';
word = word.substr(space_left);
} while (word.length() > width);
}

if (buffer_length + (buffer_length > 0) + word.length() > width) {
// We have exceeded the line width, so flush out the buffer
unsigned extra_space= width - buffer_length;
unsigned extra_space_printed = 0;
for (unsigned i=0, n_words = word_buffer.size(); i<n_words; ++i) {
if (i>0) {
os << ' ';
unsigned extra_space_desired =
(1 + 2 * extra_space * i) / (2 * (n_words-1));
for (; extra_space_printed < extra_space_desired;
++extra_space_printed) {
os << ' ';
}
}
os << word_buffer;
}
os << '\n';
word_buffer.clear();
buffer_length = 0;
}

// Store the word for later use
buffer_length += word.length() + !word_buffer.empty();
word_buffer.push_back(word);
}

void paragraph_break() {
if (brand_new_paragraph)
return;

for (unsigned i=0, n_words = word_buffer.size(); i<n_words; ++i) {
if (i>0)
os << ' ';
os << word_buffer;
}
if (!word_buffer.empty())
os << '\n';
os << '\n';
word_buffer.clear();
buffer_length = 0;
brand_new_paragraph = true;
}

~JustifiedOutput() {
paragraph_break();
}
};

int main() {
JustifiedOutput output(std::cout, 78);

std::string line;
while (std::getline(std::cin, line)) {
std::istringstream iss(line);
unsigned num_words;
std::string word;
for (num_words = 0; iss >> word; ++num_words)
output.push_word(word);
if (num_words==0)
output.paragraph_break();
}
}

Share this post


Link to post
Share on other sites

This is for my compiler class so we are only allowed to use C.

That's a non sequitur. You can write compilers in any language, not only in C. It sounds like an arbitrary restriction to me.

You can also organize your code using objects in C. I just happened to write my example in C++, but you can use the same idea in C.

Share this post


Link to post
Share on other sites

[quote name='D.Chhetri' timestamp='1322934570' post='4890173']
This is for my compiler class so we are only allowed to use C.

That's a non sequitur. You can write compilers in any language, not only in C. It sounds like an arbitrary restriction to me.

You can also organize your code using objects in C. I just happened to write my example in C++, but you can use the same idea in C.
[/quote]


I hear you. We were given a base code and it was in pure C( bad C for that matter ), and we have to expand the C code to handle more cases/features. I wish we were allowed to use C++.

Share this post


Link to post
Share on other sites

That's a non sequitur. You can write compilers in any language, not only in C. It sounds like an arbitrary restriction to me.

Of course it's an arbitrary restriction. But when the professor says 'you may only use C', you bloody well only use C... It's just how the world works.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!