#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 15th October 2013
# https://trizenx.blogspot.com
# https://trizenx.blogspot.com/2013/11/smart-word-wrap.html

# Smart word wrap algorithm
# See: https://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

class SmartWordWrap(width=80) {

    # This is the ugliest method! It, recursively,
    # prepares the words for the combine() function.
    method prepare_words(array) {

        var root = []
        var len = 0

        for (var(i, limit) = (0, array.end); i <= limit; ++i) {
            len += (var word_len = array[i].len)

            if (len > width) {
                if (word_len > width) {
                    len -= word_len;
                    array.insert(i-1, array[i].split(width)...)
                    array.delete_at(i)
                    limit = array.end
                    --i; next
                }
                break
            }

            root << [
                array.first(i+1).join(' '),
                self.prepare_words(array.slice(i+1))
            ]
            break if (++len >= width)
        }

        root || nil
    }

    # This function combines the
    # the parents with the children.
    method combine(root, path) {

        var row = []
        var key = path.shift
        path.each { |value|
            root << key
            if (defined(value)) {
                value.each { |item|
                    row += self.combine(root, item)
                }
            }
            else {
                row = [root + []]
            }
            root.pop
        }

        row;
    }

    # This function finds the best
    # combination available and returns it.
    method find_best(arrays) {

        var best = Hash(score => Inf);

        arrays.each { |array|
            var score = 0;
            array.each { |line|
                score += sqr(width - line.len);
            }

            if (score < best{:score}) {
                best{:score} = score;
                best{:value} = array;
            }
        }

        best{:value};
    }

    # This is the main function of the algorithm
    # which calls all the other functions and
    # returns the best possible wrapped string.
    method smart_wrap(text, width) {

        local self{:width} = width;
        var words = (text.is_a(Array) ? text : text.words);

        var lines = [];
        self.prepare_words(words).each { |path|
            lines += self.combine([], path);
        }

        var best = self.find_best(lines);
        best == nil && return nil;
        return best.join("\n");
    }
}

#
## Usage examples
#

var obj = SmartWordWrap();

var text = 'aaa bb cc ddddd';
var t1 = obj.smart_wrap(text, 6);
say t1;

assert_eq(t1, <<'EOT'.chomp)
aaa
bb cc
ddddd
EOT

say '-'*80;

text = 'As shown in the above phases (or steps), the algorithm does many useless transformations';
var t2 = obj.smart_wrap(text, 20);
say t2;

assert_eq(t2, <<'EOT'.chomp)
As shown in the
above phases
(or steps), the
algorithm does
many useless
transformations
EOT

say '-'*80;

text = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit.';
var t3 = obj.smart_wrap(text, 20);
say t3;

assert_eq(t3, <<'EOT'.chomp)
Lorem ipsum
dolor sit amet,
consectetur
adipiscing elit.
EOT