function list_compare(a, b) {

    var length = Math.min(a.length, b.length);
    for (var i=0; i<length; i++) {
        if (a[i] > b[i]) {
            return 1;
        }
        if (a[i] < b[i]) {
            return -1;
        }
    }
    return 0;
}


function list_add(list, bucket, key) {
    if (list == null) {
        return list_create(bucket, key);
    }

    if (list_compare(key, list.k) == 0) {
        list.b.push(bucket);
        return list;
    }

    if (list_compare(key, list.k) == 1) {
        while (list.s != null) {
            list = list.s;
            if (list_compare(key, list.k) == 0) {
                list.b.push(bucket);
                return list;
            }
            if (list_compare(key, list.k) == -1) {
                // create a new element between list.p and list.
                var temp = list_create(bucket, key);
                temp.p = list.p;
                temp.s = list;
                list.p.s = temp;
                list.p = temp;
                return temp;
            }
        }
        if (list.s == null) {
            list.s = list_create(bucket, key);
            list.s.p = list;
            return list.s;
        }

    } else if (list_compare(key, list.k) == -1) {
        while (list.p != null) {
            list = list.p;
            if (list_compare(key, list.k) == 0) {
                list.b.push(bucket);
                return list;
            }
            if (list_compare(key, list.k) == 1) {
                // create a new element between list.s and list.
                var temp = list_create(bucket, key);
                temp.p = list;
                temp.s = list.s;
                list.s.p = temp;
                list.s = temp;
                return temp;
            }

        }
        if (list.p == null) {
            list.p = list_create(bucket, key);
            list.p.s = list;
            return list.p;
        }
    }
}

// In diesem Code ist scheinbar noch ein Bug...
//function list_add(list, bucket, key) {
//    if (list == null) {
//        return list_create(bucket, key);
//    }
//
//    if (key == list.k) {
//        list.b.push(bucket);
//        return list;
//    }
//
//    var temp;
//    if (list_compare(key, list.k) == 1) {
//        if (list.s == null) {
//            list.s = list_create(bucket, key);
//            list.s.p = list;
//            return list.s;
//        }
//        if (list_compare(key, list.s.k) == 1) {
//            return list_add(list.s, bucket, key);
//        }
//        if (list_compare(key, list.s.k) == 0) {
//            list.s.b.push(bucket);
//            return list;
//        }
//
//        temp = list_create(bucket, key);
//        temp.s = list.s;
//        temp.p = list;
//        list.s = temp;
//        temp.s.p = temp;
//        return temp;
//    }
//
//    if (list.p == null) {
//        list.p = list_create(bucket, key);
//        list.p.s = list;
//        return list.p;
//    }
//    if (list_compare(key, list.p.k) == -1) {
//        return list_add(list.p, bucket, key);
//    }
//    if (list_compare(key, list.p.k) == 0) {
//        list.p.b.push(bucket);
//        return list;
//    }
//    temp = list_create(bucket, key);
//    temp.s = list;
//    temp.p = list.p;
//    list.p = temp;
//    temp.p.s = temp;
//    return temp;
//}

function list_create(bucket, key) {
    return {
        "k" : key,
        "b" : [bucket],
        "p" : null,    // predecessor
        "s" : null     // successor
    }
}

function list_first(list) {
    if (list.p == null) {
        return list;
    }
    return list_first(list.p);
}

function list_last(list) {
    if (list.s == null) {
        return list;
    }
    return list_last(list.s);
}

function list_display(list) {
    list_display_rec(list_first(list));
}

function list_display_rec(list) {
//    _debug("DUMP: "+list.k+" - "+list.b.length);
    if (list.s != null) {
        list_display_rec(list.s);
    }
}

function list_to_array(list) {
    return list_to_array_asc(list);
}

function list_to_array_desc(list) {
    var current = list_first(list);
    var back = [];
    do {
        back.push(current.b);
        current = current.s;
    } while (current != null);

    return back;
}

function list_to_array_asc(list) {
    if (list == null) {
        return [];
    }
    var current = list_last(list);
    var back = [];
    do {
        back.push(current.b);
        current = current.p;
    } while (current != null);

    return back;
}