Einfache Swift-Array-Erweiterung

Question

Der Versuch, den Array-Typ zu erweitern, um die binäre Sortierung zum Einfügen von Elementen in der richtigen Reihenfolge zu verwenden. Hier ist mein Spielplatz Code:

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) 
} 

}

ich einen Compiler-Fehler: "kann nicht insertionIndexOf mit Argumentliste vom Typ (T, isOrderedBefore: (_, _) -> _) aufrufen"

das merkwürdige ist, wenn ich stattdessen verwenden.

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

der Compiler beruhigt sich aber das Array Insertion nicht bestellt werden, :(natürlich Bitte irgendwelche Ideen ?? Vielen Dank.

(unter Verwendung von Xcode 6.3 beta 2 - Swift 1.2)

Answer 1

Sie versuchen a > b zu bewerten, aber T nicht Comparable sein. Es ist heute nicht möglich, eine solche Erweiterung zu schreiben. Was Sie sagen möchten, ist:

extension Array where T: Comparable { 

Aber das ist derzeit in Swift nicht möglich. Das Compiler-Team hat angegeben, dass dies eine Priorität ist, aber wir wissen nicht, wann es zu Swift kommen könnte.

Ihre beste Ansatz ist es, entweder das eine Funktion zu machen:

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

Oder ein neues Objekt machen, die HAS-A-Array:

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

Answer 2

Ab Swift 2, kann dies erreicht werden durch Protokollerweiterungsmethoden:

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) 
    } 
} 

Beispiel:

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

Die Verfahren sind nicht für struct Array direkt definiert ist, aber aus irgendeinem Protokoll an welche Array Konform und welche stellt die notwendigen Methoden.

Für das erste Verfahren, das heißt, dass, weil CollectionType die (Lese-) Subskript Zugang bereitstellt, und das Sammelelement Typ erforderlich ist Comparable zu sein.

Die zweite Methode mutiert die Sammlung, hier die restriktivere Protokoll RangeReplaceableCollectionType erforderlich.