[swift-evolution] [Proposal]Simple pattern matching with Horspool algorithm

[Susan Cheng]

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160517/ddd6e7dd/attachment.html>