public extension CollectionType where Index : RandomAccessIndexType {
@warn_unused_result func matchWith<C : CollectionType where C.Index : BidirectionalIndexType, C.Generator.Element == Generator.Element>(pattern: C, @noescape isEquivalent: (Generator.Element, Generator.Element) throws -> Bool) rethrows -> Index? { let pattern_count = pattern.count.toIntMax() if count.toIntMax() < pattern_count { return nil } let reverse_pattern = pattern.reverse() var cursor = startIndex.advancedBy(numericCast(pattern_count - 1)) while cursor < endIndex { let left = startIndex...cursor let pair = zip(left.reverse(), reverse_pattern) guard let not_match = try pair.firstOf({ try !isEquivalent(self[$0], $1) }) else { return cursor.advancedBy(numericCast(1 - pattern_count)) } if let pos = try reverse_pattern.dropFirst().indexOf({ try isEquivalent(self[not_match.0], $0) }) { let offset = reverse_pattern.startIndex.distanceTo(pos). toIntMax() cursor = not_match.0.advancedBy(numericCast(offset), limit: endIndex) } else { cursor = not_match.0.advancedBy(numericCast(pattern_count), limit: endIndex) } } if try self.reverse().startsWith(reverse_pattern, isEquivalent: isEquivalent) { return endIndex.advancedBy(numericCast(-pattern_count)) } return nil } } public extension CollectionType where Index : RandomAccessIndexType, Generator.Element : Equatable { @warn_unused_result func matchWith<C : CollectionType where C.Index : BidirectionalIndexType, C.Generator.Element == Generator.Element>(pattern: C) -> Index? { return self.matchWith(pattern) { $0 == $1 } } } with this simplify version of Horspool algorithm, it can speed up searching in any random access CollectionType (better than brute force searching).
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution