arrays - for - ¿Extendiendo Array para verificar si está ordenado en Swift?

string array in swift 3

Question

Quiero extender la clase Array para que pueda saber si está ordenada (ascendente) o no. Quiero agregar una propiedad computada llamada isSorted . ¿Cómo puedo establecer que los elementos de la matriz sean comparables?

Mi implementación actual en Playground

extension Array {
  var isSorted: Bool {
    for i in 1..self.count {
      if self[i-1] > self[i] { return false }
    }
    return true
  }
}

// The way I want to get the computed property
[1, 1, 2, 3, 4, 5, 6, 7, 8].isSorted //= true
[2, 1, 3, 8, 5, 6, 7, 4, 8].isSorted //= false

El error Could not find an overload for ''>'' that accepts the supplied arguments

Por supuesto, todavía tengo un error porque Swift no sabe cómo comparar los elementos. ¿Cómo puedo implementar esta extensión en Swift? ¿O estoy haciendo algo mal aquí?

Answer 1

¡En Swift 2.0 ahora puedes extender los protocolos!

extension CollectionType where Generator.Element: Comparable {

    public var isSorted: Bool {

        var previousIndex = startIndex
        var currentIndex = startIndex.successor()

        while currentIndex != endIndex {

            if self[previousIndex] > self[currentIndex] {
                return false
            }

            previousIndex = currentIndex
            currentIndex = currentIndex.successor()
        }

        return true
    }

}

[1, 2, 3, 4].isSorted // true
["a", "b", "c", "e"].isSorted // true
["b", "a", "c", "e"].isSorted // false
[/* Anything not implementing `Comparable` */].isSorted // <~~ Type-error

Tenga en cuenta que debido a que estamos utilizando Indexable.Index lugar de un Int simple como un índice, en su lugar tenemos que usar un ciclo while, que se ve un poco menos bonito y claro.

Answer 2

Adaptación, una solution que funcionará en Swift 4.

extension Array where Iterator.Element: Comparable {
    func isSorted(isOrderedBefore: (Iterator.Element, Iterator.Element) -> Bool) -> Bool  {
        for i in 1 ..< self.count {
            if isOrderedBefore(self[i], self[i-1]) {
                return false
            }
        }
        return true
    }
}

Answer 3

Aquí hay una solución en Swift 4 que no se bloqueará cuando self.count sea ​​igual o menor que 1:

extension Array where Element: Comparable {
    func isSorted(by isOrderedBefore: (Element, Element) -> Bool) -> Bool {
        for i in stride(from: 1, to: self.count, by: 1) {
            if !isOrderedBefore(self[i-1], self[i]) {
                return false
            }
        }
        return true
    }
}

Este fragmento supone que una matriz de 1 o 0 elementos ya está ordenada.

La razón para comenzar con 1 en el rango de for-loop es: En el caso de self.count <= 1, el bucle se omitirá, un pequeño aumento de rendimiento. El uso de stride lugar de ..< evita el bloqueo cuando el límite superior es <que el límite inferior de un rango.

Aquí hay unos ejemplos:

[1, 2, 3].isSorted(by: >) // true
[3, 2, 2].isSorted(by: >=) // true
[1, 4, 7].isSorted(by: {x, y in
    return x + 2 < y * y
}) // true

let a: [Int] = [1]
a.isSorted(by: <) // true


let b: [Int] = []
b.isSorted(by: >) // true

Answer 4

En realidad, puede extender el protocolo de Sequence para una solución más genérica:

extension Sequence {
    func isSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        var iterator = makeIterator()

        guard var previous = iterator.next() else {
            // Sequence is empty
            return true
        }

        while let current = iterator.next() {
            guard try areInIncreasingOrder(previous, current) else {
                return false
            }

            previous = current
        }

        return true
    }
}

extension Sequence where Element : Comparable {
    func isSorted() -> Bool {
        return isSorted(by: <)
    }
}

Answer 5

Ha encontrado un problema con los genéricos de Swift que no pueden resolverse de la forma que le gusta ahora (tal vez en una futura versión de Swift). Ver también el tema Swift Generics .

Actualmente, deberá definir una función (por ejemplo, en el ámbito global):

func isSorted<T: Comparable>(array: Array<T>) -> Bool {
    for i in 1..<array.count {
        if array[i-1] > array[i] {
            return false
        }
    }

    return true
}

let i = [1, 2, 3]
let j = [2, 1, 3]
let k = [UIView(), UIView()]
println(isSorted(i)) // Prints "true"
println(isSorted(j)) // Prints "false"
println(isSorted(k)) // Error: Missing argument for parameter #2 in call

El mensaje de error es engañoso, IMHO, ya que el error real es algo así como "UIView no cumple la restricción de tipo Comparable".

Answer 6

La función genérica, zip() , puede proporcionar un acceso directo para la implementación.

extension Collection where Element: Comparable {
    var isSorted: Bool {
        guard count > 1 else { return true }
        let pairs = zip(prefix(count - 1), suffix(count - 1))
        return !pairs.contains { previous, next in !(previous <= next) }
    }
}

[0, 1, 1, 2].isSorted  // true
[0, 2, 2, 1].isSorted  // false

Answer 7

La solución alternativa a una función gratuita es hacer lo que hacen los métodos Array.sort y Array.sorted incorporados de Swift, y requieren que pase un comparador adecuado al método:

extension Array {
    func isSorted(isOrderedBefore: (T, T) -> Bool) -> Bool {
        for i in 1..<self.count {
            if !isOrderedBefore(self[i-1], self[i]) {
                return false
            }
        }
        return true
    }
}

[1, 5, 3].isSorted(<) // false
[1, 5, 10].isSorted(<) // true
[3.5, 2.1, -5.4].isSorted(>) // true

Answer 8

La solución más flexible para mí es una combinación de la respuesta de NSAddict y Wes Campaigne. Es decir, combinar la ventaja de poder extender protocolos y pasar funciones de comparación como argumentos. Esto elimina las restricciones tanto para usarlo solo con matrices como para restringirlo a elementos que cumplan con el protocolo Comparable .

extension CollectionType
{
    func isSorted(isOrderedBefore: (Generator.Element, Generator.Element) -> Bool) -> Bool
    {
        var previousIndex = startIndex
        var currentIndex = startIndex.successor()

        while currentIndex != endIndex
        {
            if isOrderedBefore(self[previousIndex], self[currentIndex]) == false
            {
                return false
            }

            previousIndex = currentIndex
            currentIndex = currentIndex.successor()
        }

        return true
    }
}

Esto se puede utilizar en cualquier tipo de Collection y los criterios de clasificación se pueden definir de acuerdo con sus necesidades.

Answer 9

Si desea una función simple sin argumentos, como sort () o sorted () en Swift:

extension Array where Element : Comparable {
    func isSorted() -> Bool {
        guard self.count > 1 else {
            return true
        }

        for i in 1..<self.count {
            if self[i-1] > self[i] {
                return false
            }
        }
        return true
    }
}