Optimize take, takeRight, drop, dropRight

[danieldietrich]

Note: This should have been done already in #1800.

Catalyst:

List.drop(int) is usually O(n):

@Override
default List<T> drop(int n) {
    List<T> list = this;
    for (long i = n; i > 0 && !list.isEmpty(); i--) {
        list = list.tail();
    }
    return list;
}

For finite-sized collections like List we store the size, so we can do better:

@Override
default List<T> drop(int n) {
    if (n >= size()) {
        return empty();
    } else {
        List<T> list = this;
        for (long i = n; i > 0 && !list.isEmpty(); i--) {
            list = list.tail();
        }
        return list;
    }
}

In other words, when we drop all elements, we can take a shortcut in O(1).

Possible Optimizations

Op	Opt (empty)	Opt (no-op)
drop, dropRight	n >= size() -> empty()	n <= 0 -> this
take, takeRight	n >= size() -> this	n <= 0 -> empty()

Note: First check n <= 0 before n >= size() to omit method call if possible.

[NataliiaPrivezentseva]

@danieldietrich hi! Why this issue is still open? Maybe we need to make sure that all methods take, takeRight, drop, dropRight were optimized?

[danieldietrich]

@NataliiaPrivezentseva Hi! I don't know exactly. Maybe we only have to take a look at all implementations. I think then we can close this issue.

[danieldietrich]

Will close this now. We will check benchmarks before 1.0 final.