new object $list: $libraries;

var $root inited = 1;

private method ._merge_sort() {
    arg list, keys;
    var i, j, l1, k1, l2, k2, n1, n2, n;
    
    n = listlen(list);
    if (n == 1)
        return [list, keys];
    n1 = n / 2;
    n2 = n - n1;
    l1 = ._merge_sort(list.subrange(1, n1), keys.subrange(1, n1));
    k1 = l1[2];
    l1 = l1[1];
    l2 = ._merge_sort(list.subrange(n1 + 1, n2), keys.subrange(n1 + 1, n2));
    k2 = l2[2];
    l2 = l2[1];
    list = [];
    keys = [];
    i = 1;
    j = 1;
    if (n > 30)
        pause();
    while (i <= n1 && j <= n2) {
        if (k1[i] <= k2[j]) {
            list = [@list, l1[i]];
            keys = [@keys, k1[i]];
            i = i + 1;
        } else {
            list = [@list, l2[j]];
            keys = [@keys, k2[j]];
            j = j + 1;
        }
    }
    return [[@list, @l1.subrange(i), @l2.subrange(j)], [@keys, @k1.subrange(i), @k2.subrange(j)]];
};

public method ._swap_compare() {
    arg elem1, elem2, compare, [elem];
    
    elem = [@elem, 1][1];
    switch (compare) {
        case 'lt:
            return elem1[elem] < elem2[elem];
        case 'gt:
            return elem1[elem] > elem2[elem];
        default:
            return 0;
    }
};

public method ._vcolumnize() {
    arg list, lines, cols, width, [other];
    var outlist, line, i, j, sep;
    
    sep = [@other, " "][1];
    width -= sep.length();
    lines = lines > list.length() ? list.length() : lines;
    outlist = [];
    for i in [1 .. lines] {
        line = list[i].pad(width);
        for j in [1 .. cols]
            (| (line = line + sep + list[i + j * lines].pad(width)) |);
        outlist = [@outlist, line];
    }
    return outlist;
};

public method .add() {
    arg list, element;
    
    return (> list.setadd(element) <);
};

public method .addkey() {
    arg l, key, val;
    var i;
    
    find i in [1 .. l.length()] where (l[i][1] == key);
    return i ? l.replace(i, [key, val]) : [@l, [key, val]];
};

public method .affix() {
    arg l1, l2;
    var last, first;
    
    // Combines l1 and l2 by appending the first element of l2 to the last
    // of l1.
    if (type(l2) != 'list)
        l2 = [l2];
    last = (| l1.last() |) || "";
    first = (| l2[1] |) || "";
    l1 = [@l1.chop(), last + first];
    if (l2.length() > 1)
        l1 = l1 + l2.subrange(2);
    return l1;
};

public method .alphabet() {
    //returns the alphabet in a list
    return ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
};

public method .center_lines() {
    arg lines, width, [args];
    var line;
    
    return map line in (lines) to ($string.center(line, width, @args));
};

public method .chop() {
    arg list, [count];
    
    // chops the last <count> elements off the list.
    // return [] if count is longer then the list.
    count = count || 1;
    return (| list.subrange(1, list.length() - count) |) || [];
};

public method .columnize() {
    arg list, cols, [rest];
    var width, lines, line, separator, linelength, curcol;
    
    // turn [...] into ".   .   ."
    // rest[1]==separator; rest[2]==linelength
    separator = [@rest, "   "][1];
    linelength = [@rest, 78, 78][2];
    width = linelength / cols - separator.length();
    lines = [];
    while (list) {
        line = list[1].pad(width);
        list = list.subrange(2);
        for curcol in [2 .. cols] {
            if (list) {
                line = line + separator + list[1].pad(width);
                list = list.subrange(2);
            }
        }
        lines = [@lines, line];
    }
    return lines;
};

public method .compress() {
    arg list;
    var x;
    
    // [a,a,b,b,c,c,d,d] => [a,b,c,d]
    // removes duplicate entries in a list
    return hash x in (list) to ([x, 1]).keys();
};

public method .count() {
    arg list, elem;
    var count;
    
    // count of elem in list
    while (elem in list) {
        count = count + 1;
        list = list.subrange((elem in list) + 1);
    }
    return count;
};

public method .del() {
    arg list, element;
    
    return (> list.setremove(element) <);
};

public method .delkey() {
    arg l, key;
    var i;
    
    find i in [1 .. l.length()] where (l[i][1] == key);
    return i ? l.delete(i) : l;
};

public method .element_maxlength() {
    arg list;
    var elm;
    
    return map elm in (list) to (tostr(elm).length()).max();
};

public method .flatten() {
    arg list;
    var toret, elem;
    
    // [[[x], x], x]   =>   [x, x, x]
    toret = [];
    for elem in (list) {
        if (type(elem) == 'list)
            toret += .flatten(elem);
        else
            toret = toret + [elem];
    }
    return toret;
};

public method .fold() {
    arg list, object, method, [args];
    var i, out;
    
    // apply object.method to a current result and the next element, return the
    // result
    switch (list.length()) {
        case 0:
            return 0;
        case 1:
            return list[1];
    }
    out = list[1];
    for i in (list.subrange(2, list.length() - 1))
        out = object.(method)(out, i, @args);
    return out;
};

public method .getkey() {
    arg l, key;
    var i;
    
    find i in [1 .. l.length()] where (l[i][1] == key) || throw(~keynf, "Key not found.");
    return l[i][2];
};

public method .getkey_index() {
    arg l, key;
    var i;
    
    find i in [1 .. l.length()] where (l[i][1] == key) || throw(~keynf, "Key not found.");
    return i;
};

public method .grep() {
    arg lines, regexp;
    var line, result, out, reg;
    
    out = [];
    for line in [1 .. lines.length()] {
        reg = lines[line].match_regexp(regexp);
        if (reg)
            out = out + [[line, reg, lines[line]]];
    }
    return out;
};

public method .heapsort() {
    arg list, [sort_by];
    var heap, sort_type, sort_elem;
    
    sort_elem = [@sort_by, 1][1];
    sort_type = [@sort_by, 'gt, 'gt][2];
    switch (sort_type) {
        case 'gt:
            heap = $small_first_heap_class.new(list, sort_elem);
        default:
            return list;
    }
    list = [];
    while (heap.length()) {
        list = heap.element(1);
        heap = heap.del(1);
    }
    return list;
};

public method .intersection() {
    arg l1, l2;
    var i, out;
    
    // set intersection if the arguments
    out = [];
    for i in (l1) {
        if (i in l2)
            out = out.setadd(i);
    }
    return out;
};

public method .last() {
    arg list;
    
    return list[list.length()];
};

public method .lcolumnize() {
    arg list, [args];
    var line, part, lines, max, cols, col, width, len, sep;
    
    len = [@args, (| sender().linelen() |) || 79][1];
    sep = [@args, "", ""][2];
    lines = [];
    line = "";
    max = .element_maxlength(list) + sep.length();
    cols = len > max ? len / max : 1;
    width = len / cols - sep.length();
    col = cols;
    for part in (list) {
        col = col - 1;
        if (!col) {
            lines = lines + [line + part];
            line = "";
            col = cols;
            continue;
        }
        line = line + part.pad(width);
    }
    if (line)
        return lines + [line];
    return lines;
};

public method .lmap() {
    arg list, method, [args];
    var x, s;
    
    //call methods for each thing in list on sender()
    s = sender();
    return map x in (list) to (s.(method)(x, @args));
};

public method .make() {
    arg n, [elt];
    var i;
    
    elt = [@elt, 0][1];
    return map i in [1 .. n] to (elt);
};

public method .to_dict() {
  arg list;
  var a;

  return hash a in (list) to (a);
};

public method .map_to_english() {
    arg list, method, [args];
    
    // because I (Lynx) am lazy
    return .to_english(.mmap(list, method, @args));
};

public method .map_to_string() {
    arg list, method, [args];
    
    // because I (Lynx) am lazy
    return .join(.mmap(list, method, @args));
};

public method .max() {
    arg list;
    
    return (| max(@list) |) || 0;
};

public method .mfilter() {
    arg list, method, [args];
    var x;
    
    // similar to .mmap, but returns a list of objects which returned a
    // true value from 'method.
    return filter x in (list) where (x.method(@args));
};

public method .min() {
    arg list;
    
    return (| min(@list) |) || 0;
};

public method .mmap() {
    arg list, method, [args];
    var x;
    
    // call 'method on each object, return results.
    return map x in (list) to (x.(method)(@args));
};

public method .msort() {
    arg list, [keys];
    
    keys = keys ? keys[1] : list;
    if (listlen(list) != listlen(keys))
        throw(~invarg, "Invalid key list - the list lengths must be the same.");
    if (!list)
        return [];
    return (._merge_sort(list, keys))[1];
};

public method .non_alphanumeric() {
    // returns nun-alphanumeric in a list of characters
    return ["!", "@", "#", "$", "%", "^", "&", "*", "(", ")", "_", "+", "-", "=", "~", "`", "'", "{", "}", "[", "]", "|", "/", "?", "\"", "\\", ",", ".", "<", ">", ";", ":", " "];
};

public method .nth_element_maxlength() {
    arg lists, element;
    var list;
    
    // Returns longest string whose index is element in one of the lists in
    // lists.
    if (type(element) != 'integer)
        throw(~type, "Second argument is not an integer");
    if (type(lists) != 'list)
        throw(~type, "First argument is not a list");
    return map list in (lists) to (tostr(list[element]).length()).max();
};

public method .numbered_text() {
    arg text;
    var line;
    
    // receives a list of strings, returns that list with line numbers
    // prepended
    return map line in [1 .. text.length()] to ("%3r: %l".format(line, text[line]));
};

public method .numbers() {
    // returns a list of numbers
    return ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];
};

public method .omap() {
    arg list, object, method, [args];
    var obj;
    
    // calls object.method(obj, @args) for each obj in list
    return map obj in (list) to (object.(method)(obj, @args));
};

public method .prefix() {
    arg list, prefix;
    var elem;
    
    return map elem in (list) to (prefix + elem);
};

public method .random() {
    arg list;
    
    return list[random(listlen(list))];
};

public method .reverse() {
    arg list;
    var i, len;
    
    // .reverse(list)
    // -> list with its elements reversed
    len = list.length() + 1;
    return map i in [1 .. len - 1] to (list[len - i]);
};

public method .set_contains() {
    arg [args];
    var super, list, element;
    
    // True if the first list given is a superset of all subsequent lists.
    // False otherwise.  [] is a superset of [] and nothing else; anything is
    // a superset of [].  If only one list is given, return true.
    super = args ? args[1] : [];
    for list in (args.delete(1)) {
        for element in (list) {
            if (!(element in super))
                return 0;
        }
    }
    return 1;
};

public method .set_difference() {
    arg [args];
    var set, list, element;
    
    // Usage:  diff(set 1, set 2, ..., set n)
    // Returns all elements of set 1 that are not in sets 2..n
    if (!args)
        return [];
    set = args[1];
    for list in (args.delete(1)) {
        for element in (list)
            set = set.setremove(element);
    }
    return set;
};

public method .set_equal() {
    arg set1, set2;
    var element;
    
    // True if the two lists given contain the same elements.
    // False otherwise.
    while (set1) {
        element = set1[1];
        if (!element in set2)
            return 0;
        while (element in set2)
            set2 = set2.setremove(element);
        while (element in set1)
            set1 = set1.setremove(element);
    }
    return set2 == [];
};

public method .setremove_all() {
    arg list, remove;
    
    while (remove in list)
        list = .setremove(list, remove);
    return list;
};

public method .slice() {
    arg big_list, element;
    var list;
    
    // Return elementh' element of all lists in big_list
    // No type or length checking done for speed purposes.
    return map list in (big_list) to (list[element]);
};

public method .sum() {
    arg data;
    var ret, i;
    
    // returns a sum of each element in the list.
    ret = data[1];
    for i in (data.subrange(2))
        ret += i;
    return ret;
};

public method .swap() {
    arg list, a, b;
    var holder;
    
    // swap elements at indexes a and b
    holder = (> list[a] <);
    list = (> list.replace(a, list[b]) <);
    list = list.replace(b, holder);
    return list;
};

public method .swapsort() {
    arg list, [sort_by];
    var bot_elem, cur_elem, elem, compare;
    
    // note: iterative implementation allows sorts of extra-long lists
    elem = [@sort_by, 1];
    compare = [@sort_by, 'gt, 'lt][2];
    for bot_elem in [1 .. list.length()] {
        for cur_elem in [bot_elem + 1 .. list.length()] {
            if (._swap_compare(list[bot_elem], list[cur_elem], compare, elem))
                list = $list.swap(list, bot_elem, cur_elem);
        }
    }
    return list;
};

public method .to_buffer() {
    arg [args];
    
    return (> $buffer.from_strings(@args) <);
};

public method .to_english() {
    arg list, [options];
    var empty, and, sep;
    
    empty = [@options, "nothing"][1];
    switch (list.length()) {
        case 0:
            return empty;
        case 1:
            return tostr(list[1]);
    }
    and = [@options, ", and ", ", and "][2];
    sep = [@options, ", ", ", ", ", "][3];
    return join(list.delete(list.length()), sep) + and + tostr(list[list.length()]);
};

public method .valid_objects() {
    arg list;
    var obj;
    
    return filter obj in (list) where (valid(obj));
};

public method .vcolumnize() {
    arg list, cols, [rest];
    var linelength, sep, width, lines, i, j, line, outlist;
    
    linelength = [@rest, (| sender().linelen() |) || 79][1];
    sep = [@rest, " ", " "][2];
    lines = list.length() / cols + (list.length() % cols ? 1 : 0);
    width = linelength / cols;
    return ._vcolumnize(list, lines, cols, width, sep);
};

public method .vcolumnize2() {
    arg list, lines, [rest];
    var linelength, sep, cols, width, i, j, line, outlist;
    
    linelength = [@rest, (| sender().linelen() |) || 79][1];
    sep = [@rest, " ", " "][2];
    cols = list.length() / lines + (list.length() % lines ? 1 : 0);
    width = linelength / cols;
    return ._vcolumnize(list, lines, cols, width, sep);
};

public method .vcolumnize3() {
    arg list, lines, [rest];
    var linelength, cols, width, i, j, line, outlist;
    
    linelength = [@rest, (| sender().linelen() |) || 79][1];
    cols = list.length() / lines + (list.length() % lines ? 1 : 0);
    width = linelength / cols;
    outlist = [];
    for i in [1 .. lines] {
        line = "";
        for j in [0 .. cols]
            (| (line = line + list[i + j * lines].pad(width)) |);
        outlist = [@outlist, line];
    }
    return outlist;
};

public method .vcolumnize4() {
    arg list, [args];
    var linelength, sep, lines, cols, width, max;
    
    linelength = [@args, (| sender().linelen() |) || 79][1];
    sep = [@args, "", ""][2];
    max = .element_maxlength(list) + sep.length();
    cols = linelength > max ? linelength / max : 1;
    width = linelength / cols;
    lines = list.length() / cols + (list.length() % cols ? 1 : 0);
    return ._vcolumnize(list, lines, cols, width, sep);
};