兩個視圖之間的共享祖先

Question

在兩個UIView實例之間找到最低共同祖先的最有效方式是什麼？

由於缺少實施Lowest Common Ancestor，有沒有任何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項目的單元測試可能會有所幫助）

Answer 1

你實現只在一個迭代檢查兩個視圖水平。

這裏是我的：

+ (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; 
} 

Answer 2

這裏有短一些的版本，作爲UIView的一個類別：

- (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; 
} 

Answer 3

的功能替代：

斯威夫特（假設您的使用喜歡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]) 
    } 
} 

目的-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]]; 
} 

Answer 4

夫特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: []) 
    } 

} 

Answer 5

這不是太硬，使用-isDescendantOfView :.

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

Answer 6

我相信，時間複雜度和空間複雜度會使用下面的方法

第一步最小化：計算each.Let的深度考慮v1和v2的意見和d1，d2是相應的深度

第二步：如果d1 == d2，寫一個單一的for循環（index < d1 or d2），取v1.superView和v2.superView並進行比較。返回，如果他們是平等的。

第三步：如果d1 > d2，取差(d1-d2)，執行while循環，取v1.superView和遞減D1值。 while循環應該退出，如果(d1 == d2)。之後，重複Step1。

第四步：：如果d2 > d1，走差異化(d2-d1)，執行while循環，走v2.superView和遞減d2值。 while循環應該退出，如果(d2 == d1)。之後，重複Step1。

Answer 7

斯威夫特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 

    } 
}