Swift中的共同父视图

Question

给定一个包含2个或以上视图（UIView）的任意集合，我想要确定这些视图的最近公共父视图。在Swift中，最有效的算法是什么？

基于以下层次结构：

                    ┌─────┐                                                  
                    │  A  │                                                  
                    └─────┘                                                  
                       ▲                                                     
          ┌────────────┴────────────┐                                        
          │                         │                                        
       ┌─────┐                   ┌─────┐                ┌─────┐              
       │  B  │                   │  C  │                │  X  │              
       └─────┘                   └─────┘                └─────┘              
          ▲                         ▲                      ▲                 
   ┌──────┴──────┐           ┌──────┴──────┐               │                 
   │             │           │             │               │                 
┌─────┐       ┌─────┐     ┌─────┐       ┌─────┐         ┌─────┐       ┌─────┐
│  D  │       │  E  │     │  F  │       │  G  │         │  Y  │       │  Z  │
└─────┘       └─────┘     └─────┘       └─────┘         └─────┘       └─────┘

• 如果没有提供视图，则返回 nil。
• 如果提供了 1 个视图，则返回 superview 或 nil。
• 如果任何视图没有superview（例如"A"，"X"或"Z"），则返回 nil。
• 如果视图不属于同一层次结构（例如"A"或"X"层次结构），则返回 nil。

示例：

// no views
[].commonParent()      // nil
// 1 view
[D].commonParent()     // B
// siblings
[D,E].commonParent()   // B
// child/parent
[D,B].commonParent()   // A
// cousins
[D,F].commonParent()   // A
// > 2 views
[D,E,F].commonParent() // A
// with root view
[D,A].commonParent()   // nil
// unrelated hierarchies
[D,Y].commonParent()   // nil
// unrelated view
[D,Z].commonParent()   // nil

- David James

---

是的，UIView。虽然同样适用于NSView。 - David James

具体来说，我正在寻找一种使用Swift编写的算法（即不使用Objective-C）。据我所知，在UIKit中没有任何东西可以帮助确定共同的父视图。 - David James

为什么不使用Objective-C呢？由于涉及到UIKit，可以采用类似的方法。UIView有一个名为isDescendantOfView:的方法，可以用于此目的。因此，通过迭代/while循环遍历第一个视图的superView，检查另一个视图是否是其子孙节点。 - Larme

@Larme Swift有一个isDescendant方法subview.isDescendant(of: self.view)。 - RajeshKumar R

谢谢@Larme！我在我的答案中采纳了你的建议。“为什么不用Objective-C？”：因为我使用Swift编码，它与Obj-C之间的惯用差异很大——例如，受限扩展、高阶函数和可选项等，如下面的示例所示。 :) - David James

Answer 1

我知道这篇文章已经老旧了，但是我听说了这个面试题并进行了一些搜索以了解其设置情况，找到了这篇文章。对于那些在我之后来到这里的人，我认为重要的是让您知道当前的解决方法还不够高效，是O(n^2)的。如果您使用这种算法，面试可能会不通过。我用Objective-C做了一个示例，但是任何使用Swift的人都应该能够轻松理解。使用记忆化技术可以避免您需要搜索'n'个元素'm'次，从而实现O(n)的效率。祝好运！

- (UIView *)commonParentIn:(UIView *)v1 view:(UIView *)v2 {
    // key all parent views of one view
    NSMutableSet *parentSet = [[NSMutableSet alloc] init];
    while (v2) {
        [parentSet addObject:v2];
        v2 = [v2 superview];
    }

    // search for all parent views of other view in set and return first found
    while (v1) {
        if ([parentSet containsObject:v1]) {
            return v1;
        }
        v1 = [v1 superview];
    }

    return nil;
}

这里有一些测试代码：

UIView *v1 = [[UIView alloc] init];
UIView *v2 = [[UIView alloc] init];
UIView *v3 = [[UIView alloc] init];
UIView *v4 = [[UIView alloc] init];
UIView *v5 = [[UIView alloc] init];
UIView *v6 = [[UIView alloc] init];
UIView *v7 = [[UIView alloc] init];
UIView *v8 = [[UIView alloc] init];
UIView *v9 = [[UIView alloc] init];
UIView *v10 = [[UIView alloc] init];
UIView *v11 = [[UIView alloc] init];
UIView *singleParent = [[UIView alloc] init];
UIView *onlyChild = [[UIView alloc] init];

[v1 addSubview:v2];
[v1 addSubview:v3];
[v1 addSubview:v4];
[v2 addSubview:v5];
[v2 addSubview:v9];
[v5 addSubview:v6];
[v5 addSubview:v10];
[v10 addSubview:v11];
[v4 addSubview:v7];
[v4 addSubview:v8];
[singleParent addSubview:onlyChild];

UIView *found = [self commonParentIn:v11 view:onlyChild];

可以画出视图的树形结构，这样你就知道它们何时以及在哪里应该有共享的父视图。然后，只需更改传入的视图以进行测试。

- Nick Sinklier

---

不幸的是，在while块内执行[parentSet containsObject:v1]会使其成为O(n^2)。要实现O(n)，您需要记忆化两个超级视图，然后同时循环这两个数组，它们分叉后的视图是共同的父视图。 - B K

Answer 2

根据@Larme的建议，这就是我想出来的。应该涵盖所有情况。欢迎评论。

extension Collection where Iterator.Element:UIView {    
    
    func commonParent() -> UIView? {
        
        // Must be at least 1 view
        guard let firstView = self.first else {
            return nil
        }
        
        // If only 1 view, return it's superview, or nil if already root
        guard self.count > 1 else {
            return firstView.superview
        }
        
        // Find the common parent
        var parent = firstView.superview
        let otherItems = dropFirst()
        while parent != nil {
            if otherItems.contains(where:{ !$0.isDescendant(of:parent!) || $0 == parent! }) {
                // Go to next super view and test that
                parent = parent?.superview
            } else {
                // All (other) items are descendants of the first item's
                // super item so return it – it's the common parent.
                return parent
            }
        }
        // else, there is no common parent
        return nil
    }
}

修改

将reduce()更改为contains()，这样可以使程序短路运算，从而提高速度。

- David James

---

我已经测试了它的性能，非常快。（使用>10个节点，执行了10,000个查询=0.022秒。） - David James

你在哪里声明了parent？当我尝试运行你的代码时，它显示错误，因为parent没有被声明。 - Newbie