#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 15th October 2013
# Translated to Sidef in 06th September 2014
# https://trizenx.blogspot.com

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

class SmartWordWrap(WIDTH=80) {

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

        var root = [];
        var len  = 0;

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

            len > self.WIDTH && (
                wordLen > self.WIDTH && (
                    len -= wordLen;
                    array.splice(i, 1, array[i].split(self.WIDTH)...);
                    i--, next;
                );
                break;
            );

            root.append(array.slice(0, i+1) + __METHOD__(self, array.slice(i + 1, array.end)));
            (++len >= self.WIDTH) && break;
        }

        root.len  && return root;
        array.len && return [array];
                     return [];
    }

    ## This function creates all the
    ## avaible paths, for further processing.
    method make_paths(array) {

        var head = [];
        while (array.len) {
            array[0].is_a(Array) && break;
            head.push(array.shift);
        }

        var row = [];
        array.each { |path|
            row.push(Hash.new(head.join(' ') =>  __METHOD__(self, path)));
        }

        return(row.len ? row : head.join(' '));
    }

    ## This function combines the
    ## the parents with the childrens.
    method combine(root, hash) {

        var row = [];
        hash.each_pair { |key, value|
            root.append(key);

            if (value.is_a(Array)) {
                value.each { |item|
                    row.append(__METHOD__(self, root, item));
                }
            }
            else { row.append(root..., value) };
            root.pop;
        };

        return row;
    }

    ## This function normalizez the combinations.
    ## Example: [[["abc"]]] is normalized to ["abc"];
    method normalize(array_ref) {

        var strings = [];
        array_ref.each { |item|
            if (item.is_a(Array)) {
                strings += __METHOD__(self, item);
            }
            else {
                strings.append(array_ref);
                break;
            }
        }

        return strings;
    }

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

        var best = Hash.new('score' => Inf);

        arrays.each { |array_ref|
            var score = 0;

            array_ref.each { |string|
                score += ::pow(self.WIDTH - string.len, 2);
            }

            score < best{:score} && (
                best{:score} = score;
                best{:value} = array_ref;
            );
        }

        best.exists(:value) ? best{:value} : '';
    }

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

        # Temporarily modify the width
        local WIDTH = width;

        # Split the text into words
        text.is_a(String) && (
            text = text.words;
        );

        # Prepare words
        var pwords = self.prepare_words(text);

        # Make the paths
        var paths = [];
        pwords.each { |group|
            paths.append(self.make_paths(group));
        };

        # Create the combinations
        var combinations = [];
        while(paths.len) {

            if (paths[0].is_a(Array)) {
                paths += paths.shift;
                next;
            }

            var path = paths.shift;
            combinations.append(path.is_a(Hash) ? [self.combine([], path)] : [path]);
        }

        # Return the best result
        self.find_best(self.normalize(combinations)).join("\n");
    }
}

var sww = SmartWordWrap(6);

var words = %w(aaa bb cc ddddd);
var wrapped = sww.wrap(words);

say wrapped;
assert_eq(wrapped, "aaa\nbb cc\nddddd")