How do you implement linear search in Swift as a generic protocol extension?

Answer 1

Lets give this a shot

extension Collection {

  func firstIndex(of element: Element) -> Index? {

    for index in indices {

      if self[index] == element {

        return index

      }

    }

    return nil

  }

}

Here we are just iterating over the array until we find a match. However, the compiler gives you an error stating:

Binary operator '==' cannot be applied to two 'Self.Element' operands

We can resolve that by enforcing conditional conformance to the Equatable protocol for Collection.Element.

extension Collection where Element: Equatable {

  func firstIndex(of element: Element) -> Index? {

    for index in indices {

      if self[index] == element {

        return index

      }

    }

    return nil

  }

}

Now let's try with a custom type:

struct Person {

  let name: String

}

let personArray = [

  Person(name: "bob"),

  Person(name: "tom"),

  Person(name: "joe"),

]

if let index = personArray.firstIndex(of: Person(name: "tom")) {

  print(index)

}

The compiler gives us an error stating:

Referencing instance method 'firstIndex(of:)' on 'Collection' requires that 'Person' conform to 'Equatable'

struct Person: Equatable {

  let name: String

}

There, that solves it.

Since person is a value type the compiler implements the Equatable methods for us since all of its properties conform to Equatable (String). Now let's try with a class.

class Person: Equatable {

  let name: String

  init(name: String) {

    self.name = name

  }

}

The compiler gives us another error:

Type 'Person' does not conform to protocol 'Equatable'

This is because the compiler doesn't synthesize the methods for us when it comes to classes. So let's conform to Equatable manually.

class Person: Equatable {

  let name: String

  init(name: String) {

    self.name = name

  }

  static func == (lhs: Person, rhs: Person) -> Bool {

    return lhs.name == rhs.name

  }

}

let personArray = [

  Person(name: "bob"),

  Person(name: "tom"),

  Person(name: "joe"),

]

if let index = personArray.firstIndex(of: Person(name: "tom")) {

  print(index)

}

And there you have it.