LinkedList: The functional approach (WIP)

linked-list-fn.js

{
    /*
    Who-when: Krazov 2019
    LinkedList object creator.
    Instead of storing a list in array or other linear container, the data
    is organized in a chain of linked items:
    ```
        LinkedListCell {
            value: any;
            next:  LinkedListCell | null;
            prev:  LinkedListCell | null;
        }
    ```
    */

    const FIRST = Symbol('A value before the first element');
    const LAST = Symbol('A value after the last element');

    const isBefore = (head) => head == FIRST;
    const isNotBefore = (head) => !isBefore(head);
    const isAfter = (head) => head == LAST;
    const isNotAfter = (head) => !isAfter(head);
    const isOutside = (head) => isBefore(head) || isAfter(head);
    const isInside = (head) => head !== null && !isOutside(head);

    const isEmpty = (start) => start === null;
    const isNotEmpty = (start) => !isEmpty(start);

    const NEXT = 'next';
    const PREV = 'prev';
    const step = (goForth) => goForth ? 'next' : 'prev';

    const safePrev = (head, end) =>
        isBefore(head)
            ? FIRST
            : isAfter(head)
                ? end
                : head.prev;

    const safeNext = (head, start) =>
        isAfter(head)
            ? LAST
            : isBefore(head)
                ? start
                : head.next;

    const positionHead = (newHead, distance) => {
        let finalHead = newHead;

        for (let i = 0; i < distance; i += 1) {
            newHead = newHead.next;
        }

        return newHead;
    };

    const isAtStart = (head) => head.prev == FIRST;
    const isAtEnd = (head) => head.next == LAST;

    // inner list utils
    const createCell = (data) => ({
        data,
        [PREV]: null,
        [NEXT]: null,
    });

    const copyCell = ({ data }) => createCell(data);

    const createList = (...items) => items.reduce(
        ({ latest, start }, current) => {
            const cell = createCell(current);

            cell.next = LAST;

            if (latest == null) {
                start = cell;
                cell.prev = FIRST;
            } else {
                cell.prev = latest;
                latest.next = cell;
            }

            return { latest: cell, start };
        },
        { latest: null, start: null }
    );

    const resolveStep = (head, start, end, step) =>
        isInside(head)
            ? head[step]
            : isBefore(head)
                ? step == NEXT
                    ? start
                    : FIRST
                : step == PREV
                    ? end
                    : LAST;

    const extractValuesFrom = (head, start, end, goForth = true) => {
        const conditionIsMet = goForth
            ? isNotAfter
            : isNotBefore;
        const STEP = step(goForth);

        const values = [];

        for (
            let localHead = resolveStep(head, start, end, STEP);
            conditionIsMet(localHead);
            localHead = localHead[STEP]
        ) {
            values.push(localHead.data);
        }

        if (!goForth) {
            values.reverse();
        }

        return values;
    }

    const copyList = (head, start, end) => {
        let newStart = null;
        let newEnd = null;

        const listBefore = isBefore(head)
            ? {}
            : createList(...extractValuesFrom(head, start, end, false));

        let newHead = isInside(head)
            ? copyCell(head)
            : head;

        const listAfter = isAfter(head)
            ? {}
            : createList(...extractValuesFrom(head, start, end));

        if (listBefore.start) {
            newStart = listBefore.start;
            listBefore.latest.next = newHead;
            newHead.prev = listBefore.latest;
            newEnd = listBefore.latest;
        } else if (isInside(newHead)) {
            newEnd = newStart = newHead;
            newHead.prev = FIRST;
        }

        if (listAfter.start) {
            listAfter.start.prev = newHead;

            if (isInside(newHead)) {
                newHead.next = listAfter.start;
            } else {
                newStart = listAfter.start;
            }

            newEnd = listAfter.latest;
        } else if(isInside(newHead)) {
            newHead.next = LAST;
        }

        if(isInside(newHead) && head == end) {
            newEnd = newHead;
        }

        return {
            head: newHead,
            start: newStart,
            end: newEnd,
        };
    };

    // methods
    const moveHead = (head, start, end, api, linkedList) =>
        api({
            ...copyList(head, start, end),
            linkedList,
        });

    const withPrev = ({ head, start, end, api, linkedList }) => () =>
        moveHead(safePrev(head, end), start, end, api, linkedList);

    const withNext = ({ head, start, end, api, linkedList }) => () =>
        moveHead(safeNext(head, start), start, end, api, linkedList);

    const withGotoStart = ({ start, end, api, linkedList }) => () =>
        moveHead(start, start, end, api, linkedList);

    const withGotoEnd = ({ start, end, api, linkedList }) => () =>
        moveHead(end, start, end, api, linkedList);

    const withClone = ({ start, end, api, linkedList }) => () =>
        moveHead(start, start, end, api, linkedList);

    const withMap = ({ start, linkedList }) => (fn) => {
        if (typeof fn != 'function') {
            throw Error('Mapper has to be a function.');
        }

        if (isEmpty(start)) {
            return undefined;
        }

        const values = [];

        for (let localHead = start; isInside(localHead); localHead = localHead.next) {
            values.push(fn(localHead.data));
        }

        return linkedList(...values);
    };

    const withFilter = ({ start, linkedList }) => (fn) => {
        if (typeof fn != 'function') {
            throw Error('Predicate has to be a function.');
        }

        if (isEmpty(start)) {
            return undefined;
        }

        const values = [];

        for (let localHead = start; isInside(localHead); localHead = localHead.next) {
            if (fn(localHead.data)) {
                values.push(localHead.data);
            }
        }

        return linkedList(...values);
    };

    const withWithReduce = (goForth) => ({ start, end }) => (...args) => {
        const [fn] = args;
        if (typeof fn != 'function') {
            throw Error('Reducer has to be a function.');
        }

        const STEP = step(goForth);

        const initial = goForth ? start : end;
        if (isEmpty(initial)) {
            return null;
        }

        let [localHead, value] = args.length == 1
            ? [initial[STEP], initial.data]
            : [initial, args[1]];

        for (/* above, for readability */; isInside(localHead); localHead = localHead[STEP]) {
            value = fn(value, localHead.data)
        }

        return value;
    };

    const withReduce = withWithReduce(true);
    const withReduceRight = withWithReduce(false);

    // TODO: change `item` to `...items`

    const withAppend = ({ head, start, end, api, linkedList }) => (item) => {
        const copy = copyList(head, start, end);

        const cell = createCell(item);
        cell.prev = copy.end;
        copy.end.next = cell;
        cell.next = LAST;

        return api({ ...copy, linkedList });
    };

    const withPrepend = ({ head, start, end, api, linkedList }) => (item) => {
        const copy = copyList(head, start, end);

        const cell = createCell(item);
        cell.next = copy.start;
        copy.start = copy.head = copy.start.prev = cell;
        cell.prev = FIRST;

        return api({ ...copy, linkedList });
    };

    const withInsertAfter = ({ head, start, end, api, linkedList }) => (item) => {
        const copy = copyList(head, start, end);

        const cell = createCell(item);
        cell.prev = copy.head;
        copy.head.next.prev = cell;
        cell.next = copy.head.next;
        copy.head.next = cell;
        copy.head = cell;

        return api({ ...copy, linkedList });
    };

    const withInsertBefore = ({ head, start, end, api, linkedList }) => (item) => {
        const copy = copyList(head, start, end);

        const cell = createCell(item);
        cell.next = copy.head;
        copy.head.prev.next = cell;
        cell.prev = copy.head.prev;
        copy.head.prev = cell;
        copy.head = cell;

        return api({ ...copy, linkedList });
    };

    const withReplaceAfter = ({ head, start, end, api, linkedList }) => (...items) => {
        const itemsBefore = extractValuesFrom(head, start, end, false);
        const { start: newStart, latest: newEnd } = createList(...itemsBefore, head.data, ...items);

        return api({
            start: newStart,
            head: positionHead(newStart, itemsBefore.length),
            end: newEnd,
            linkedList,
        });
    };

    const withReplaceBefore = ({ head, start, end, api, linkedList }) => (...items) => {
        const itemsAfter = extractValuesFrom(head, start, end, true);
        const { start: newStart, latest: newEnd } = createList(...items, head.data, ...itemsAfter);

        return api({
            start: newStart,
            head: positionHead(newStart, items.length),
            end: newEnd,
            linkedList,
        });
    }

    // TODO: could be taking a count of elements to remove, to avoid creating intermediary lists
    const withRemove = ({ head, start, end, api, linkedList }) => () => {
        const copy = copyList(head, start, end);

        [copy.head.prev.next, copy.head.next.prev] = [copy.head.next, copy.head.prev];

        return api({ ...copy, linkedList });
    };

    const withInspect = ({ start, head, end }) => (label = '') => {
        console.groupCollapsed(label ? `Full inspection: ${label}` : 'Full inspection');

        const iterateOver = (start, fn) => {
            for (let localHead = start, index = 1; isInside(localHead); localHead = localHead.next, index += 1) {
                fn(index, localHead);
            }
        }

        iterateOver(start, (index, localHead) => {
            console.log(`#${index}:`, localHead.data);
        })

        iterateOver(start, (index, localHead) => {
            console.log(`#${index}:`, localHead);
        });

        try {
            console.log(`Structure: ${JSON.stringify(start)}`);
        } catch(error) {
            console.info('Circular structure.');
        }
        console.log('start', start);
        console.log('end', end);
        console.log('head', head);
        if (start === null) {
            console.log('List is empty');
        } else {
            console.log('next', head.next);
            console.log('prev', head.prev);
            console.log('is head at start:', head == start);
        }
        console.groupEnd();
    };

    const withIterator = ({ start }) => function* ({ finite = false } = {}) {
        for (let localHead = start; isInside(localHead); localHead = localHead.next) {
            yield localHead.data;

            if (finite && localHead == start) {
                break;
            }
        }
    };

    const headIsOutOfList = () => {
        throw Error('The head is out of list! Operation not possible.');
    };

    // api builder
    const enumerableValue = (value, enumerable) => ({ value, enumerable });
    const enumerable = (value) => enumerableValue(value, true);
    const nonEnumerable = (value) => enumerableValue(value, false);

    const api = ({ head, start, end, linkedList }) => {
        const prev = nonEnumerable(withPrev({ head, start, end, api, linkedList }));
        const next = nonEnumerable(withNext({ head, start, end, api, linkedList }));
        const gotoStart = nonEnumerable(withGotoStart({ start, end, api, linkedList }));
        const gotoEnd = nonEnumerable(withGotoEnd({ start, end, api, linkedList }));
        const map = nonEnumerable(withMap({ start, linkedList }));
        const filter = nonEnumerable(withFilter({ start, linkedList }));
        const reduce = nonEnumerable(withReduce({ start }));
        const reduceRight = nonEnumerable(withReduceRight({ end }));
        // reverse
        const append = nonEnumerable(withAppend({ head, start, end, api, linkedList }));
        const prepend = nonEnumerable(withPrepend({ head, start, end, api, linkedList }));
        // insertAfterValue
        // insertBeforeValue
        const insertAfter = isAfter(head)
            ? headIsOutOfList
            : isEmpty(start)
                ? linkedList
                : isAtEnd(head)
                    ? append
                    : nonEnumerable(withInsertAfter({ head, start, end, api, linkedList }));
        const insertBefore = isBefore(head)
            ? headIsOutOfList
            : isEmpty(start)
                ? linkedList
                : isAtStart(head)
                    ? prepend
                    : nonEnumerable(withInsertBefore({ head, start, end, api, linkedList }));
        // replaceAfterValue
        // replaceBeforeValue
        const replaceAfter = isOutside(head)
            ? headIsOutOfList
            : isEmpty(start)
                ? linkedList
                : isAtEnd(head)
                    ? append
                    : nonEnumerable(withReplaceAfter({ head, start, end, api, linkedList }));
        const replaceBefore = isOutside(head)
            ? headIsOutOfList
            : isEmpty(start)
                ? linkedList
                : isAtStart(head)
                    ? prepend
                    : null;
        // removeValue
        const remove = nonEnumerable(withRemove({ head, start, end, api, linkedList }));
        const iterator = nonEnumerable(withIterator({ start }));
        const toStringTag = { get: () => 'LinkedList' };
        const inspect = nonEnumerable(withInspect({ start, head, end }));

        return Object.defineProperties({}, {
            value: enumerable(isNotEmpty(start) && isInside(head)? head.data : undefined),
            isEmpty: enumerable(isEmpty(start)),
            isOutside: enumerable(isOutside(head)),
            isBefore: enumerable(isBefore(head)),
            isAfter: enumerable(isAfter(head)),
            isInside: enumerable(isInside(head)),
            prev,
            next,
            gotoStart,
            gotoEnd,
            clone: gotoStart,
            map,
            // mapRight
            filter,
            // filterRight
            reduce,
            reduceRight,
            // reverse
            append,
            prepend,
            // insertAfterValue
            // insertBeforeValue
            insertAfter,
            insertBefore,
            // replaceAfterValue
            // replaceBeforeValue
            replaceAfter,
            // replaceBefore
            // removeValue
            remove,
            [Symbol.iterator]: iterator,
            [Symbol.toStringTag]: toStringTag,
            inspect,
        });
    }

    // export
    const linkedList = (...items) => {
        const { start, start: head, latest: end } = createList(...items);
        return api({ head, start, end, linkedList });
    }

    const LinkedList = {
        of: linkedList,
        // from linkedList-like
    };

    // demos
    function demo(name, fn) {
        console.groupCollapsed(name);
        fn();
        console.groupEnd();
    }

    function demo1() {
        // General demo
        console.log('LinkedList.of(1, 2, 3, 4, 5, 6)');
        const list1 = LinkedList.of(1, 2, 3, 4, 5, 6)
        console.log('Item will be stringified as ' + list1);
        console.log(list1);
        list1.inspect();
        console.groupEnd();
    }

    function demo2() {
        // Iterator demo
        console.info('const list2 = LinkedList.of(1987, 1988, 1989, 1990, 1991, 1992);')
        const list2 = LinkedList.of(1987, 1988, 1989, 1990, 1991, 1992);
        console.log(list2);
        console.info('[...list2]');
        console.log([...list2])
    }

    function demo3() {
        // Next prev
        console.info('const list2 = LinkedList.of(1999, 2000, 2001, 2002, 2003, 2004);')
        const list3 = LinkedList.of(1999, 2000, 2001, 2002, 2003, 2004);
        console.log(list3);
        console.log('list3.value', list3.value);
        console.log('list3.next().value', list3.next().value);
        console.log('list3.next().value', list3.next().value);
        console.log('list3.next().next().value', list3.next().next().value);
        console.log('list3.next().value == list3.next().value', list3.next().value == list3.next().value);
        console.log('list3.next() == list3.next()', list3.next() == list3.next());
    }

    function demo4() {
        // Empty list
        const list4 = LinkedList.of();
        console.info('const list4 = LinkedList.of();');
        console.log(list4);
        console.log('list4.isEmpty', list4.isEmpty);
        list4.inspect();
    }

    function demo5() {
        // Map / filter / reduce
        const list5 = LinkedList.of(1, 2, 3, 4, 5, 6);
        console.info('const list5 = LinkedList.of(1, 2, 3, 4, 5, 6);');
        console.log('Original', [...list5]);
        console.log('Mapped (doubled)', [...list5.map((value) => value * 2)]);
        console.log('Filtered (odd)', [...list5.filter((value) => value % 2)]);
        console.log('Reduced (summed)', list5.reduce((a, b) => a + b, 0));
        console.log('Reduced right (concatenated)', list5.reduceRight((a,b) => `${a}${b}`, ''));
    }

    function demo6() {
        // Cloning
        const list6 = LinkedList.of(42, 63, 97);
        console.info('const list6.of(42, 63, 97);');
        console.log(list6);

        const list6b = list6.clone();
        console.info('const list6b = list6.clone();');
        console.log(list6b);

        console.log('list6.next().value', list6.next().value);
        console.log('list6b.next().value', list6b.next().value);
        console.log('list6 == list6b', list6 == list6b);
    }

    function demo7() {
        // Object.assign
        const list7 = LinkedList.of(324, 23,765, 435, 987);
        console.info('const list7 = Object.of(324, 23,765, 435, 987);');
        console.log([...list7]);
        console.log('{ ...list7 }', { ...list7 });
        console.log('Object.assign({}, list7)', Object.assign({}, list7));
    }

    function demo8() {
        // List boundaries
        const list8 = LinkedList.of(1, 2, 3, 4, 5, 6);
        console.info('const list8 = LinkedList.of(1, 2, 3, 4, 5, 6);');
        console.log([...list8]);
        console.log('Current', list8.value);
        console.log('Previous', list8.prev().value);
        console.log('Current again', list8.prev().next().value);

        const list8last = list8.next().next().next().next().next();
        list8last.inspect();
        console.log('The last', list8last.value);

        const list8beyond = list8last.next();
        list8beyond.inspect();
        console.log('After the last', list8beyond.value);

        console.log('The last again', list8.next().next().next().next().next().next().prev().value);

        console.log(
            'Back and forth',
            list8
                .next().next().next().next().next().next() // <-- after end
                .prev().prev().prev().prev().prev().prev() // <-- back to start
                .value
       );
    }

    function demo9() {
        // go to start and end
        const list9 = LinkedList.of(42, 63, 97);
        console.log('const list9 = LinkedList.of(42, 63, 97);');
        console.log('Current', list9.value);
        console.log('Go to end', list9.gotoEnd().value);
        console.log('Go to end and back', list9.gotoEnd().gotoStart().value);
    }

    function demo10() {
        // append, prepend, insertAfter, insert after demo
        const list10 = LinkedList.of(1, 2, 3);
        console.log('const list10 = LinkedList.of(1, 2, 3);', [...list10]);
        console.log('[...list10.append(14)]', [...list10.append(14)]);
        console.log('[...list10.prepend(14)]', [...list10.prepend(666)]);
        console.log('[...list10.next().insertAfter(15)]', [...list10.next().insertAfter(15)]);
        console.log('[...list10.next().insertBefore(15)]', [...list10.next().insertBefore(15)]);
        try {
            list10.prev().insertBefore(15);
        } catch(error) {
            console.log(`[...list10.prev().insertBefore(15)]: ${error}`);
        }
    }

    function demo11() {
        // remove
        const list11 = linkedList(1, 2, 3);
        console.log('const list11 = linkedList(1, 2, 3);', [...list11]);
        console.log('list11.next().remove()', [...list11.next().remove()]);
    }

    function demo12() {
        // replace after
        const list12 = linkedList(1, 2, 3, 4, 5, 6);
        console.log('const list12 = linkedList(1, 2, 3, 4, 5, 6);', [...list12]);
        const list12nextnext = list12.next().next();
        list12nextnext.inspect('list12nextnext');
        console.log('list12nextnext.value', list12nextnext.value);
        console.log('list12nextnext.next().value', list12nextnext.next().value);
        const list12replaced = list12nextnext.replaceAfter(42, 63, 97);
        console.log('list12.next().next().replaceAfter(42, 63, 97)', [...list12replaced]);
        console.log('list12replaced.value', list12replaced.value);
        console.log('list12replaced.next().value', list12replaced.next().value);
    }

    // main
    console.clear();

    demo('General demo', demo1);
    demo('Iterator demo', demo2);
    demo('Prev/next demo', demo3);
    demo('Empty list demo', demo4);
    demo('Map / filter / reduce functions demo', demo5);
    demo('Cloning demo', demo6);
    demo('Object.assign demo', demo7);
    demo('List boundaries demo', demo8);
    demo('Go to start and end demo', demo9);
    demo('Append, prepend, insertBefore, and insertAfter demo', demo10);
    demo('Remove demo', demo11);
    demo('Replace demo', demo12);

    console.info('The end.')
}