swift - 具有可选、泛型和可比较性的函数确实满足编译器要求

Question

我正在阅读一些算法并正在研究二叉搜索树。我做了以下内容

class TreeNode<T: Comparable>{
    var value: T
    var parent: TreeNode?
    var leftChild: TreeNode?
    var rightChild: TreeNode?

    init(value: T) {
        self.value = value
    }
    // ... more stuff ...

效果很好。我已启动并运行搜索、插入和打印，但是当我尝试实现 isSame 以判断两棵树是否相同时，编译器不会接受我的任何函数声明:

首先我尝试:

func isSame(leftNode: TreeNode?, rightNode: TreeNode?) -> Bool {

编译器告诉我“对泛型类型‘TreeNode’的引用需要参数”

并建议添加 ，然后我这样做了，但现在编译器要我在最后一个参数后插入一个 ','

func isSame(leftNode: TreeNode?, rightNode: TreeNode<T: Comparable>?) -> Bool {

如果我这样做，它建议我添加另一个 :D

结果类似

func isSame(leftNode: TreeNode?, rightNode: TreeNode<T: Comparable>?,,,) -> Bool {

编译器，我已经服从了你的每一个命令。你还想从我这里得到什么？

我可以像这样剥离通用部分的功能来解决这个问题:

func isSame(leftNode: TreeNode<Int>?, rightNode: TreeNode<Int>?) -> Bool {

但我很好奇我必须做些什么才能使函数适用于泛型类型？

TLDR:如何让 isSame 函数接受这两个通用参数？

完整代码:

import UIKit

class TreeNode<T: Comparable>{
    var value: T
    var parent: TreeNode?
    var leftChild: TreeNode?
    var rightChild: TreeNode?

    init(value: T) {
        self.value = value
    }

    convenience init(array: [T]){
        precondition(array.count > 0) // test denne

        self.init(value: array.first!)

        for item in array.dropFirst(){
            self.insert(item)
        }
    }

    func insert(_ newValue: T){
        if newValue < self.value {

            if leftChild == nil {
                leftChild = TreeNode(value: newValue)
                leftChild?.parent = self
            } else {
                leftChild!.insert(newValue)
            }
        }
        else {

            if rightChild == nil {
                rightChild = TreeNode(value: newValue)
                rightChild?.parent = self
            } else {
                rightChild!.insert(newValue)
            }
        }
    }

    func search(_ targetValue: T) -> Bool{

        if targetValue < self.value{
            if let leftChild = leftChild{
                return leftChild.search(targetValue)
            }
        }
        if targetValue > self.value{
            if let rightChild = rightChild{
                return rightChild.search(targetValue)
            }
        }
        if targetValue == value{
            print("found \(targetValue)")
            return true
        }
        print("did not find \(targetValue)")
        return false
    }
}

// MARK: - Extensions

extension TreeNode: CustomStringConvertible{
    var description: String {

        var s = ""

        if let left = self.leftChild {
            s += "(\(left.description)) <-"
        }
        s += " \(value) "

        if let right = self.rightChild {
            s += "-> (\(right.description))"
        }
        return s
    }
}

// isSame

func isSame(leftNode: TreeNode<Int>?, rightNode: TreeNode<Int>?) -> Bool {

        if ((leftNode != nil && rightNode == nil) || (rightNode == nil && leftNode != nil)){
            print("xor check returned false")
            return false
        }

        if leftNode?.value != rightNode?.value {
            return false
        }

        if isSame(leftNode: leftNode?.leftChild, rightNode: rightNode?.leftChild){
            return isSame(leftNode: leftNode?.rightChild, rightNode: rightNode?.rightChild)
        } else {
            return false
        }
}


// MARK: - Testing

var smallTree: TreeNode<Int> = TreeNode(value: 13)
var rootNodeFromArray = TreeNode(array: [7, 2, 5, 10, 9, 1])

// isSame test

let treeA: TreeNode<Int> = TreeNode(array: [7, 2, 5, 10, 9, 1])
let treeB: TreeNode<Int> = TreeNode(array: [7, 2, 5, 10, 9, 1])

Answer 1

如果函数是一个全局函数，你可以把它变成一个泛型函数:

func isSame<T>(leftNode: TreeNode<T>?, rightNode: TreeNode<T>?) -> Bool {

这正是 Equatable 协议(protocol)的实现方式:

func == <T: Equatable>(lhs: TreeNode<T>, rhs: TreeNode<T>) -> Bool {
    return lhs.value == rhs.value
       && lhs.leftChild == rhs.leftChild
       && lhs.rightChild == rhs.rightChild
}

请注意，Equatable 协议(protocol)不需要可选参数。与 nil 的比较是自动处理的。

然后您可以使用 leftNode == rightNode 进行简单比较。