Вычисление обратного индекса для коллекции Swift, которая объединяет две другие отсортированные коллекции

Question

Я взял на себя чей-то квест, чтобы создать последовательность, которая оборачивает данную отсортированную последовательность и отфильтровывает элементы, принадлежащие второй данной отсортированной последовательности, и предикат, используемый для сортировки, также предоставляется.Я написал нетерпеливые и ленивые версии.Ленивая версия поддерживает Collection, если и основная, и фильтрующая последовательности также являются коллекциями.

public struct LazyPresortedSubtractionSequence<Base: Sequence, Filter: Sequence> where Base.Element == Filter.Element {
    /// The sequence where the vended elements come from.
    var base: Base
    /// The sequence where matches to be filtered come from.
    var filters: Filter
    /// The closure for determining the relative order of elements.
    let areInIncreasingOrder: (Base.Element, Base.Element) -> Bool
    /// Creates a sequence vending elements of a given base sequence minus the elements that are also in another sequence.
    init(_ base: Base, filter: Filter, by areInIncreasingOrder: @escaping (Base.Element, Base.Element) -> Bool) {
        self.base = base
        filters = filter
        self.areInIncreasingOrder = areInIncreasingOrder
    }
}

//...

public typealias LazyPresortedSubtractionCollection<Base: Collection, Filter: Collection> = LazyPresortedSubtractionSequence<Base, Filter> where Base.Element == Filter.Element

extension LazyPresortedSubtractionCollection: Collection {
    public struct Index: Comparable {
        /// The targeted element in the base collection.
        public let index: Base.Index
        /// The next unused filter element when the target element is chosen.  Meant to be a cache to calculate the next index, not significant for direct use.
        let filterIndex: Filter.Index
        public static func == (lhs: Index, rhs: Index) -> Bool {
            return lhs.index == rhs.index
        }
        public static func < (lhs: Index, rhs: Index) -> Bool {
            return lhs.index < rhs.index
        }
    }

    /// Find the first element of `base`'s suffix to not be filtered out by elements in `filter`'s suffix, without using loops.
    private func nextIndex(baseStart: Base.Index, filterStart: Filter.Index) -> Index {
        guard baseStart < base.endIndex, filterStart < filters.endIndex, !areInIncreasingOrder(base[baseStart], filters[filterStart]) else {
            return Index(index: baseStart, filterIndex: filterStart)
        }

        let incrementBase = !areInIncreasingOrder(filters[filterStart], base[baseStart])
        let nextBaseIndex = base.index(baseStart, offsetBy: incrementBase ? +1 : 0)
        return nextIndex(baseStart: nextBaseIndex, filterStart: filters.index(after: filterStart))
    }

    /**
     The position of the first element in a nonempty collection.

     If the collection is empty, `startIndex` is equal to `endIndex`.

     - Warning: Since the collection filters elements and can't cache the result (since the properties involved are conditional), the computation is linear instead of constant.

     - Complexity: O(_n_ + _k_), where *n* is the element count of the wrapped collection and *k* is the element count of the filter collection.
     */
    public var startIndex: Index {
        return nextIndex(baseStart: base.startIndex, filterStart: filters.startIndex)
    }
    public var endIndex: Index {
        // The value for `filterIndex` may be wrong for some collections, but it's not used in comparisons.
        // (By wrong, I mean `index(after: indices.last).filterIndex` may be before `filters.endIndex`.  This may happen when `base.last` is less than `filters.last`.)
        return Index(index: base.endIndex, filterIndex: filters.endIndex)
    }
    public subscript(position: Index) -> Base.Element {
        return base[position.index]
    }
    public func index(after i: Index) -> Index {
        return nextIndex(baseStart: base.index(after: i.index), filterStart: i.filterIndex)
    }
}

Теперь я хочу сделать его обратимым, если две внутренние коллекции обратимы.

extension LazyPresortedSubtractionCollection: BidirectionalCollection where Base: BidirectionalCollection, Filter: BidirectionalCollection {
    public func index(before i: Index) -> Index {
        // What goes here?
    }
}

Когда вы идете перед индексированным элементом, вам нужно выяснить, сколько дублирующих значений существует в обеих внутренних коллекциях и включать предыдущую, только если основная коллекция имеет больше, чем коллекция фильтров, в противном случае переходите к следующему.Мне становится трудно обдумать это, по крайней мере, часть, которая мне нужна для синхронизации индексов коллекции фильтров с основными индексами коллекции, но в обратном направлении!Это вообще возможно?Помните, что обе внутренние коллекции уже отсортированы по сохраненному предикату порядка.