#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Longest_common_prefix#Sidef
#

# Finds the first point where the tree bifurcates
func find_common_prefix(hash, acc) {
    if (hash.len == 1) {
        var pair = hash.to_a[0]
        return __FUNC__(pair.value, acc+pair.key)
    }
    return acc
}

# Creates a tree like: {a => {b => {c => {}}}}
func lcp(*strings) {
    var hash = Hash()

    for str in (strings.sort_by{.len}) {
        var ref = hash
        str.is_empty && return ''
        for char in str {
            if (ref.contains(char)) {
                ref = ref{char}
                ref.len == 0 && break
            }
            else {
                ref = (ref{char} = Hash())
            }
        }
    }

    return find_common_prefix(hash, '')
}

func is(a, b) {
    a == b || die "error: #{a} != #{b}";
}

is(lcp("interspecies","interstellar","interstate"), "inters");
is(lcp("throne","throne"),                          "throne");
is(lcp("throne","dungeon"),                         "");
is(lcp("throne","","throne"),                       "");
is(lcp("cheese"),                                   "cheese");
is(lcp(""),                                         "");
is(lcp(),                                           "");
is(lcp("prefix","suffix"),                          "");
is(lcp("foo","foobar"),                             "foo");
is(lcp("foobar","foo"),                             "foo");

say "** Test passed!";