123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168 |
- #!/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")
|