    "A [[List]] which can be efficiently searched for
     occurrences of a given element, or for inclusions of a
     given sublist of elements. This interface provides
     operations for finding:

     - _occurrences_ of a single value in the list, and
     - _inclusions_ of a given sublist of values in the list.

     Occurrences and inclusions are identified by a list index
     at which the value or sublist of values occurs in the list.
     In the case of an inclusion, it is the index of the first
     matching value from the sublist.

     Inclusions may overlap. For example:

         \"yoyoyoyoyo\".inclusions(\"yoy\")

     produces the stream `{ 0, 2, 4, 6 }`.

     An empty list is considered to be included at every index,
     including the index [[size]] at the very end of the
     list. Thus:

         \"hello\".inclusions(\"\")

     produces the stream `{ 0, 1, 2, 3, 4, 5 }`, with 6
     inclusions in a string of length 5.

     In particular:

     - `\"\".inclusions(\"x\")` is the empty stream `{}`, but
     - `\"\".inclusions(\"\")` is the stream `{ 0 }`."
    see (`class String`, `class Array`)
    shared interface SearchableList<Element>
            satisfies List<Element> {

        "Determines if the given [[value|element]] occurs at the
         given index in this list."
        shared default
        Boolean occursAt(
            "The index at which the value might occur."
            Integer index,
            "The value. If null, it is considered to occur
             at any index in this list with a null element."
            Element element)
                => let (elem = getFromFirst(index))
                if (exists element, exists elem)
                then elem == element
                else element exists == elem exists;

        "The indexes in this list at which the given
         [[value|element]] occurs."
        shared default
        {Integer*} occurrences(
            "The value. If null, it is considered to occur
             at any index in this list with a null element."
            Element element,
            "The smallest index to consider."
            Integer from = 0,
            "The number of indexes to consider."
            Integer length = size-from)
                //performance of comprehension was
                //worse than hand-written iterable
                //=> { for (i in from:length)
                //     if (occursAt(i, element)) i };
                => object satisfies Iterable<Integer> {
            value len = outer.size;
            value max =
                    from+length>len
                        then len else from+length;
            iterator()
                    => object satisfies Iterator<Integer> {
                variable value index = from;
                shared actual Integer|Finished next() {
                    while (index<max) {
                        if (occursAt(index, element)) {
                            return index++;
                        }
                        else {
                            index++;
                        }
                    }
                    return finished;
                }
            };
            shared actual Integer size {
                variable value size = 0;
                for (index in from:max-from) {
                    if (occursAt(index,element)) {
                        size++;
                    }
                }
                return size;
            }
            empty => occurs(element, from, length);
            first => firstOccurrence(element, from, length);
            last => lastOccurrence(element, from, length);
        };

        "Determines if the given [[value|element]] occurs as an
         element of this list, at any index that falls within
         the segment `from:length` defined by the optional
         [[starting index|from]] and [[length]]."
        shared default
        Boolean occurs(
            "The value. If null, it is considered to occur
             at any index in this list with a null element."
            Element element,
            "The smallest index to consider."
            Integer from = 0,
            "The number of indexes to consider."
            Integer length = size-from)
                => firstOccurrence(element, from, length) exists;

        "The first index in this list at which the given
         [[value|element]] occurs, that falls within the segment
         `from:length` defined by the optional
         [[starting index|from]] and [[length]]."
        shared default
        Integer? firstOccurrence(
            "The value. If null, it is considered to occur
             at any index in this list with a null element."
            Element element,
            "The smallest index to consider."
            Integer from = 0,
            "The number of indexes to consider."
            Integer length = size-from) {
            for (index in from:length) {
                if (occursAt(index,element)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "The last index in this list at which the given
         [[value|element]] occurs, that falls within the range
         `size-length-from:length` defined by the optional
         [[starting index|from]], interpreted as a reverse index
         counting from the _end_ of the list, and [[length]]."
        shared default
        Integer? lastOccurrence(
            "The value. If null, it is considered to occur
             at any index in this list with a null element."
            Element element,
            "The smallest index to consider, interpreted as
             a reverse index counting from the _end_ of the
             list, where `0` is the last element of the list,
             and `size-1` is the first element of the list."
            Integer from = 0,
            "The number of indexes to consider."
            Integer length = size-from) {
            //TODO: refine reversed to return a SearchableList
            // => reversed.firstOccurrence(element, from, length)
            for (index in (size-length-from:length).reversed) {
                if (occursAt(index,element)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "Determine if the given [[list|sublist]] occurs as a
         sublist at the given index of this list."
        shared default
        Boolean includesAt(
            "The index at which the [[sublist]] might occur."
            Integer index,
            List<Element> sublist) {
            if (0 <= index <= size-sublist.size) {
                variable value i = index;
                for (element in sublist) {
                    if (exists element) {
                        if (!occursAt(i, element)) {
                            return false;
                        }
                    }
                    else {
                        assert (is Element null);
                        if (!occursAt(i, null)) {
                            return false;
                        }
                    }
                    i++;
                }
                else {
                    return true;
                }
            }
            else {
                return false;
            }
        }

        "The indexes in this list at which the given
         [[list|sublist]] occurs as a sublist, that are greater
         than or equal to the optional [[starting index|from]]."
        shared default
        {Integer*} inclusions(List<Element> sublist,
            "The smallest index to consider."
            Integer from = 0)
                //performance of comprehension was
                //worse than hand-written iterable
                /*=> { for (i in from:size+1-from-sublist.size)
                     if (includesAt(i, sublist)) i };*/
                => object satisfies Iterable<Integer> {
            value len = outer.size;
            iterator()
                    => object satisfies Iterator<Integer> {
                value max = len+1-sublist.size;
                variable value index = from;
                shared actual Integer|Finished next() {
                    while (index<max) {
                        if (includesAt(index, sublist)) {
                            return index++;
                        }
                        else {
                            index++;
                        }
                    }
                    return finished;
                }
            };
            shared actual Integer size {
                variable value size = 0;
                for (index in from:len-from+1-sublist.size) {
                    if (includesAt(index,sublist)) {
                        size++;
                    }
                }
                return size;
            }
            empty => includes(sublist, from);
            first => firstInclusion(sublist, from);
            last => lastInclusion(sublist, from);
        };

        "Determine if the given [[list|sublist]] occurs as a
         sublist at some index in this list, at any index that
         is greater than or equal to the optional
         [[starting index|from]]."
        shared default
        Boolean includes(List<Element> sublist,
            "The smallest index to consider."
            Integer from = 0)
                => firstInclusion(sublist, from) exists;

        "The first index in this list at which the given
         [[list|sublist]] occurs as a sublist, that is greater
         than or equal to the optional [[starting index|from]]."
        shared default
        Integer? firstInclusion(List<Element> sublist,
            "The smallest index to consider."
            Integer from = 0) {
            for (index in from:size-from+1-sublist.size) {
                if (includesAt(index,sublist)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "The last index in this list at which the given
         [[list|sublist]] occurs as a sublist, that falls within
         the range `0:size-from+1-sublist.size` defined by the
         optional [[starting index|from]], interpreted as a
         reverse index counting from the _end_ of the list."
        shared default
        Integer? lastInclusion(List<Element> sublist,
            "The smallest index to consider, interpreted as
             a reverse index counting from the _end_ of the
             list, where `0` is the last element of the list,
             and `size-1` is the first element of the list."
            Integer from = 0) {
            //TODO: refine reversed to return a SearchableList
            // => reversed.firstInclusion(element, from, length)
            for (index in (0:size-from+1-sublist.size).reversed) {
                if (includesAt(index,sublist)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

    }