Estensione di Swift Array semplice

Question

Provare ad estendere il tipo di array per utilizzare l'ordinamento binario per inserire gli elementi nell'ordine. Ecco il mio codice parco giochi:

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

}

ottengo un errore di compilazione: "non può invocare l'insertionIndexOf con lista di argomenti di tipo (T, isOrderedBefore: (_, _) -> _)"

la cosa curiosa è, se uso invece:.

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

il compilatore si calma ma l'inserimento matrice non verrà ordinato, :(naturalmente Per favore qualche idea ?? Grazie.

(usando Xcode 6.3 beta 2 - Swift 1.2)

Answer 1

Si sta cercando di valutare a > b, ma T potrebbero non essere Comparable. Non è possibile scrivere un'estensione come questa oggi. Cosa vuoi essere in grado di dire è:

extension Array where T: Comparable { 

Ma ciò non è possibile a Swift attualmente. Il team del compilatore ha indicato che è una priorità, ma non sappiamo quando può arrivare a Swift.

Il tuo approccio migliore è quello sia rendere questa una funzione:

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

O fare un nuovo oggetto che ha-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

Come di Swift 2, questo può essere realizzato con protocollo metodi di estensione:

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

Esempio:

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

I metodi non sono definiti per struct Array direttamente, ma per qualche protocollo cui Array conforme, e che fornisce la necessaria metodi.

Per il primo metodo, cioè CollectionType perché fornisce la (lettura) accesso pedice, e l'elemento di raccolta tipo è richiesto di essere Comparable.

Il secondo metodo muta la raccolta , qui è richiesto il protocollo più restrittivo RangeReplaceableCollectionType.