sidef/scripts/unique_prefixes.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 28 September 2014
# Website: https://github.com/trizen

# Find the unique prefixes for an array of arrays of strings

func abbrev(array, code=nil) {

    var END  = "#{{}}";              # some unique value
    var CALL = (code != nil && code.is_a(Block));

    var table = Hash.new;
    array.each { |sub_array|
        var ref = table;
        sub_array.each { |item|
            ref = (ref{item} \\= Hash.new);
        };
        ref{END} = sub_array;
    }

    var abbrevs = [];
    func(hash) {
        var keys = hash.keys.sort;
        keys.each { |key|
            key == END && next;
            __FUNC__(hash{key});

            if (keys.len > 1) {
                var count = 0;
                var ref = hash.delete(key);
                while (var key = ref.keys[0]) {
                    key.is_a(String) || next;
                    key == END && do {
                        var arr = ref{key}.flip.slice(count).flip;
                        CALL ? code.call(arr) : abbrevs.append(arr);
                        break;
                    };
                    ref = ref{key};
                    count++;
                }
            }
        }
      }(table);

    return abbrevs;
}

#
## Example: find the common directory from a list of dirs
#

var dirs = %w(
  /home/user1/tmp/coverage/test
  /home/user1/tmp/covert/operator
  /home/user1/tmp/coven/members
);

var uniq = abbrev(dirs.map{.split('/')}).min_by{.len};
var dir = [uniq.pop, uniq.join('/')][1];
assert_eq('/home/user1/tmp', dir);

var words = %w(
    deodorant
    decor
    decorat
    decadere
    plecare
    placere
    plecat
    jaguar
);

assert_eq(
    gather {
        abbrev(words.map{.split(1)}, func(a) { say take(a.join) });
    },
    %w(deca decora deco deo j pla plecar plecat)
)