Rozszerzenie Simple Swift Array

Question

Próba rozszerzenia typu Array w celu użycia sortowania binarnego do wstawiania elementów w kolejności. Oto mój kod zabaw:

extension Array { 

     func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int { 
     var lo = 0 
     var hi = self.count - 1 
     while lo <= hi { 
     let mid = (lo + hi)/2 
     if isOrderedBefore(self[mid], elem) { 
      lo = mid + 1 
     } else if isOrderedBefore(elem, self[mid]) { 
      hi = mid - 1 
     } else { 
      return mid 
     } 
    } 
     return 0 
} 


    mutating func insertOrdered(elem: T){ 
    let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b)  in return (a > b) }) 
    return insert(elem, atIndex: index) 
} 

}

otrzymuję błąd kompilatora: "nie można powoływać się insertionIndexOf z listy argumentów typu (T, isOrderedBefore: (_, _) -> _)"

Ciekawą rzeczą jest, jeśli mogę użyć zamiast.

mutating func insertOrdered(elem: T){ 
     let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b) in return false }) 
     return insert(elem, atIndex: index) 
     } 

kompilator uspokaja jednak wstawiania tablica nie zostanie uporządkowane, :(oczywiście Proszę wszelkie pomysły? Dziękuję Ci.

(używając Xcode 6.3 beta 2 - Swift 1.2)

Answer 1

Próbujesz ocenić a > b, ale T nie może być Comparable. Nie można dzisiaj napisać takiego rozszerzenia. To, co chcesz powiedzieć, to:

extension Array where T: Comparable { 

Ale obecnie nie jest to możliwe w Swift. Zespół kompilatorów wskazał, że jest to priorytet, ale nie wiemy, kiedy może dojść do Swift.

Najlepszym rozwiązaniem jest albo zrobić to funkcja:

func insertOrdered<T: Comparable>(inout xs: [T], x: T) 

Albo zrobić nowy obiekt, który ma w swoim łańcuchu:

struct OrderedArray<T: Comparable> : ... { 
    var values: [T] 
    func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int 
    mutating func inserOrdered(elem: T) 
    ... 
} 

Answer 2

Od Swift 2, można to osiągnąć protokołu metody rozszerzeń:

extension CollectionType where Generator.Element : Comparable, Index == Int { 

    func insertionIndexOf(elem: Generator.Element) -> Int { 
     var lo = 0 
     var hi = self.count - 1 
     while lo <= hi { 
      let mid = (lo + hi)/2 
      if self[mid] < elem { 
       lo = mid + 1 
      } else if elem < self[mid] { 
       hi = mid - 1 
      } else { 
       return mid // found at position mid 
      } 
     } 
     return lo // not found, would be inserted at position lo 
    } 
} 

extension RangeReplaceableCollectionType where Generator.Element : Comparable, Index == Int { 

    mutating func insertOrdered(elem: Generator.Element) { 
     let index = self.insertionIndexOf(elem) 
     self.insert(elem, atIndex: index) 
    } 
} 

przykład:

var ar = [1, 3, 5, 7] 
ar.insertOrdered(6) 
print(ar) // [1, 3, 5, 6, 7] 

Sposoby te są określone dla struct Array bezpośrednio, ale z jakiegoś protokołu, którego Array zgodny, który dostarcza niezbędnych metod.

W pierwszym sposobie, który jest CollectionType ponieważ zapewnia dostęp (odczyt) indeksu, a element pobierający typu nie wymaga się Comparable.

Druga metoda mutuje kolekcji, tutaj wymagany jest bardziej restrykcyjny protokół RangeReplaceableCollectionType.