两个视图之间的共同祖先

Question

如何最有效地查找两个 UIView 实例之间的最低公共祖先？

除了实现 最低公共祖先，是否有任何可以利用的 UIKit API 来查找？

NSView 有 ancestorSharedWithView:，所以我猜这可能很快就会被添加到 iOS。

我目前正在使用这个简单粗暴的解决方案，如果给定的视图不是同级或直接祖先，则效率很低。

- (UIView*)lyt_ancestorSharedWithView:(UIView*)aView
{
    if (aView == nil) return nil;
    if (self == aView) return self;
    if (self == aView.superview) return self;
    UIView *ancestor = [self.superview lyt_ancestorSharedWithView:aView];
    if (ancestor) return ancestor;
    return [self lyt_ancestorSharedWithView:aView.superview];
}

（如果要实现类似的方法，Lyt 项目的单元测试可能会有所帮助）

- hpique

---

你唯一的选择是沿着superview链向上走，然后找到它们分叉的位置。我不知道除了superview之外还有什么API可以帮助。 - rmaddy

我不了解API，但我不会一直往上走到顶部；相反，我会交替向上走，对于每个找到的UIView保持一个计数器，并在每次访问时将该计数器增加1。第一个计数器设置为2的UIView是最低公共祖先。例如，您可以使用哈希映射将视图映射到其计数器。这是我能想到的最简单的方法，实现起来也不难。 - G. Bach

Answer 1

使用-isDescendantOfView:并不太难。

- (UIView *)my_ancestorSharedWithView:(UIView *)aView
{
    UIView *testView = self;
    while (testView && ![aView isDescendantOfView:testView])
    {
        testView = [testView superview];
    }
    return testView;
}

- Carl Lindberg

Answer 2

Swift 3:

extension UIView {
    func findCommonSuperWith(_ view:UIView) -> UIView? {

        var a:UIView? = self
        var b:UIView? = view
        var superSet = Set<UIView>()
        while a != nil || b != nil {

            if let aSuper = a {
                if !superSet.contains(aSuper) { superSet.insert(aSuper) }
                else { return aSuper }
            }
            if let bSuper = b {
                if !superSet.contains(bSuper) { superSet.insert(bSuper) }
                else { return bSuper }
            }
            a = a?.superview
            b = b?.superview
        }
        return nil

    }
} 

- Or Ron

---

除了空间复杂度，我认为是O(a+b)（其中a和b分别是视图到每个根视图的距离）之外，我认为这是最有效率的时间。除非LCA是根视图，否则该算法不必从a或b到根的整个路径上行走，它会在那之前找到LCA。太好了！ - Jaime S

Answer 3

一种功能性的替代方案：

Swift（假设使用您喜欢的OrderedSet）

extension UIView {

    func nearestCommonSuperviewWith(other: UIView) -> UIView {
        return self.viewHierarchy().intersect(other.self.viewHierarchy()).first
    }

    private func viewHierarchy() -> OrderedSet<UIView> {
        return Set(UIView.hierarchyFor(self, accumulator: []))
    }

    static private func hierarchyFor(view: UIView?, accumulator: [UIView]) -> [UIView] {
        guard let view = view else {
            return accumulator
        }
        return UIView.hierarchyFor(view.superview, accumulator: accumulator + [view])
    }
}

Objective-C（在 UIView 上实现为一个类别，假设存在一个名为firstObjectCommonWithArray的方法）

+ (NSArray *)hierarchyForView:(UIView *)view accumulator:(NSArray *)accumulator
{
    if (!view) {
        return accumulator;
    }
    else {
        return [self.class hierarchyForView:view.superview accumulator:[accumulator arrayByAddingObject:view]];
    }
}

- (NSArray *)viewHierarchy
{
    return [self.class hierarchyForView:self accumulator:@[]];
}

- (UIView *)nearestCommonSuperviewWithOtherView:(UIView *)otherView
{
    return [[self viewHierarchy] firstObjectCommonWithArray:[otherView viewHierarchy]];
}

- sam-w

Answer 4

这里提供一个稍微简短的版本，作为UIView的一个分类（Category）：

- (UIView *)nr_commonSuperview:(UIView *)otherView
{
    NSMutableSet *views = [NSMutableSet set];
    UIView *view = self;

    do {
        if (view != nil) {
            if ([views member:view])
                return view;
            [views addObject:view];
            view = view.superview;
        }

        if (otherView != nil) {
            if ([views member:otherView])
                return otherView;
            [views addObject:otherView];
            otherView = otherView.superview;
        }
    } while (view || otherView);

    return nil;
}

- Nikolai Ruhe

Answer 5

我的方法略长，但不使用UIKit的isDescendant函数。

方法1：使用树中查找LCA的方法。时间复杂度：O（N），空间复杂度：（1）

func findCommonSuper(_ view1:inout UIView, _ view2:inout UIView) -> UIView? {
    var level1 = findLevel(view1)
    var level2 = findLevel(view2)
    if level1 > level2 {
        var dif = level1-level2
        while dif > 0 {
            view1 = view1.superview!
            dif -= 1
        }
    } else if level1 < level2 {
        var dif = level2-level1
        while dif > 0 {
            view2 = view2.superview!
            dif -= 1
        }
    }
    while view1 != view2  {
        if view1.superview == nil || view2.superview == nil {
            return nil
        }
        view1 = view1.superview!
        view2 = view2.superview!
    }
    if view1 == view2 {
        return view1
    }
    return nil
}

func findLevel(_ view:UIView) -> Int {
    var level = 0
    var view = view
    while view.superview != nil {
        view = view.superview!
        level += 1
    }
    return level
}

方法二：将一个视图的祖先插入到集合中，然后迭代第二个视图的祖先。时间复杂度：O（N），空间复杂度：O（N）

func findCommonSuper2(_ view1:UIView, _ view2:UIView) -> UIView? {
    var set = Set<UIView>()
    var view = view1
    while true {
        set.insert(view)
        if view.superview != nil {
            view = view.superview!
        } else {
            break
        }
    }

    view = view2
    while true {
        if set.contains(view) {
            return view
        }
        if view.superview != nil {
            view = view.superview!
        } else {
            break
        }
    }
    return nil
}

- yalcin

Answer 6

您的实现每次迭代只检查两个视图级别。

这是我的实现：

+ (UIView *)commonSuperviewWith:(UIView *)view1 anotherView:(UIView *)view2 {
    NSParameterAssert(view1);
    NSParameterAssert(view2);
    if (view1 == view2) return view1.superview;

    // They are in diffrent window, so they wont have a common ancestor.
    if (view1.window != view2.window) return nil;

    // As we don’t know which view has a heigher level in view hierarchy,
    // We will add these view and their superview to an array.
    NSMutableArray *mergedViewHierarchy = [@[ view1, view2 ] mutableCopy];
    UIView *commonSuperview = nil;

    // Loop until all superviews are included in this array or find a view’s superview in this array.
    NSInteger checkIndex = 0;
    UIView *checkingView = nil;
    while (checkIndex < mergedViewHierarchy.count && !commonSuperview) {
        checkingView = mergedViewHierarchy[checkIndex++];

        UIView *superview = checkingView.superview;
        if ([mergedViewHierarchy containsObject:superview]) {
            commonSuperview = superview;
        }
        else if (checkingView.superview) {
            [mergedViewHierarchy addObject:superview];
        }
    }
    return commonSuperview;
}

- BB9z

Answer 7

Swift 2.0：

    let view1: UIView!
    let view2: UIView!
    let sharedSuperView = view1.getSharedSuperview(withOtherView: view2)

/**
* A set of helpful methods to find shared superview for two given views
*
* @author Alexander Volkov
* @version 1.0
*/
extension UIView {

    /**
    Get nearest shared superview for given and otherView

    - parameter otherView: the other view
    */
    func getSharedSuperview(withOtherView otherView: UIView) {
        (self.getViewHierarchy() as NSArray).firstObjectCommonWithArray(otherView.getViewHierarchy())
    }

    /**
    Get array of views in given view hierarchy

    - parameter view:        the view whose hierarchy need to get
    - parameter accumulator: the array to accumulate views in

    - returns: the list of views from given up to the top most view
    */
    class func getHierarchyForView(view: UIView?, var accumulator: [UIView]) -> [UIView] {
        if let superview = view?.superview {
            accumulator.append(view!)
            return UIView.getHierarchyForView(superview, accumulator: accumulator)
        }
        return accumulator
    }

    /**
    Get array of views in the hierarchy of the current view

    - returns: the list of views from cuurent up to the top most view
    */
    func getViewHierarchy() -> [UIView] {
        return UIView.getHierarchyForView(self, accumulator: [])
    }

}

- Alexander Volkov

Answer 8

Swift 5 版本的 Carl Lindberg 的解决方案：

func nearestCommonSuperviewWith(other: UIView) -> UIView? {
    var nearestAncestor: UIView? = self

    while let testView = nearestAncestor, !other.isDescendant(of: testView) {
        nearestAncestor = testView.superview
    }

    return nearestAncestor
}

- Palli