कक्षाओं के संग्रह के निकटतम सामान्य सुपरक्लास (या सुपरइंटरफेस) को ढूंढना

Question

कक्षाओं के संग्रह को देखते हुए, निकटतम सामान्य सुपरक्लास खोजने का सबसे अच्छा तरीका क्या है?

उदाहरण के लिए, निम्न में दिया:

interface A {} 
interface B {} 
interface AB extends A, B {} 
interface C {} 
class AImpl implements A {} 
class ABImpl implements AB {} 
class ABImpl2 implements A, B {} 
class BCImpl implements B, C {} 

मैं निम्नलिखित (व्यापक नहीं) उम्मीद करेंगे:

commonSuperclass(A, AImpl) == A 
commonSuperclass(A, B, C) == Object or null, I'm not picky 
commonSuperclass(A, AB) == A 
commonSuperclass(AImpl, ABImpl) == A 
commonSuperclass(ABImpl, ABImpl2) == either A or B or both, I'm not picky 
commonSuperclass(AImpl, ABImpl, ABImpl2) == A 
commonSuperclass(ABImpl, ABImpl2, BCImpl) == B 
commonSuperclass(AImpl, ABImpl, ABImpl2, BCImpl) == Object 

मैं कल्पना मैं अंत में इस बाहर काम कर सकता था, लेकिन किसी को यह पहले से ही हल किया जाना चाहिए Arrays.asList(...) में टाइप अनुमान जैसे चीजों के लिए। क्या कोई मुझे एल्गोरिदम, या बेहतर अभी तक कुछ मौजूदा उपयोगिता कोड पर इंगित कर सकता है?

---

ईटीए: मैं प्रतिबिंब API के बारे में पता है। यह एल्गोरिदम (या ऐसे एल्गोरिदम का कार्यान्वयन) है जिसे मैं ढूंढ रहा हूं।

ईटीए: और मुझे पता है कि यह एक डीएजी है। धन्यवाद। तुम बहुत चालाक हो

---

ईटीए: संस्थानिक छंटाई पर (फिर EJP's answer में): संस्थानिक तरह एल्गोरिदम मैं से परिचित हूँ आप की आवश्यकता करने के लिए या तो: कोई आवक के साथ "रूट" नोड्स n से

1. शुरू किनारों (यानी, इस परिदृश्य में, अनुमानतः Object और सुपरइंटरफेस के बिना सभी इंटरफेस - जिसे किसी को पूरे सेट की जांच करनी होगी, साथ ही सभी सुपरक्लास/सुपरइंटरफेस, एकत्र करने के लिए) और सभी किनारों को (n, m) (यानी, सभी m extends/implements n), फिर से जानकारी एक होगा ई इकट्ठा करने के लिए पूरे सेट की जांच करने के लिए), या कोई बाहर जाने वाले किनारों (यानी, इस परिदृश्य में, सभी वर्गों/इंटरफेस m जिसके लिए कोई वर्ग k extends/implements m मौजूद है के साथ "पत्ता" नोड्स m है, जो फिर से एक करने के लिए होगा से
2. शुरू एकत्र करने के लिए पूरे सेट की जांच करें) और सभी किनारों को (n, m) (यानी, सभी वर्ग/इंटरफेस m विस्तार/कार्यान्वयन - हमारे पास कौन सी जानकारी है) को संसाधित करें।

यह संभव है कि इनमें से एक या अन्य बहु-पास एल्गोरिदम (ठीक है, अनुमानतः # 2) ऐसा करने का सबसे प्रभावी तरीका है, लेकिन यह निश्चित रूप से मामूली रूप से स्पष्ट नहीं है। यह भी पूरी तरह से संभव है कि एक-पास टोपोलॉजिकल सॉर्ट एल्गोरिदम है जिसे मैं परिचित नहीं हूं, या मुझे इन एल्गोरिदम को गलत मिला है, लेकिन उस मामले में, फिर से, "यह मूल रूप से एक प्रकार का स्थलीय प्रकार है" तुरंत नेतृत्व नहीं करता है उत्तर में एक।

Answer 1

पूर्ण काम कर मेरी जानकारी

• प्रत्येक वर्ग पदानुक्रम जा रहा "ऊपर की ओर 'के BFS का सबसे अच्छा करने के लिए समाधान - परिणाम LinkedHashSet में (ऑर्डर + कोई डुप्लीकेट्स को सुरक्षित रखें)
• सामान्य में कुछ भी ढूंढने के लिए अगले सेट को दोबारा डालें, फिर से लिंक 0 है।शेष "आदेश दिया गया" सेट आम पूर्वजों है, सूची में सबसे पहले "निकटतम" है, आखिरी सबसे दूर है।
• खाली सूची नहीं पूर्वजों (वस्तु से अलग) का तात्पर्य

कोड

private static Set<Class<?>> getClassesBfs(Class<?> clazz) { 
    Set<Class<?>> classes = new LinkedHashSet<Class<?>>(); 
    Set<Class<?>> nextLevel = new LinkedHashSet<Class<?>>(); 
    nextLevel.add(clazz); 
    do { 
     classes.addAll(nextLevel); 
     Set<Class<?>> thisLevel = new LinkedHashSet<Class<?>>(nextLevel); 
     nextLevel.clear(); 
     for (Class<?> each : thisLevel) { 
      Class<?> superClass = each.getSuperclass(); 
      if (superClass != null && superClass != Object.class) { 
       nextLevel.add(superClass); 
      } 
      for (Class<?> eachInt : each.getInterfaces()) { 
       nextLevel.add(eachInt); 
      } 
     } 
    } while (!nextLevel.isEmpty()); 
    return classes; 
} 

private static List<Class<?>> commonSuperClass(Class<?>... classes) { 
    // start off with set from first hierarchy 
    Set<Class<?>> rollingIntersect = new LinkedHashSet<Class<?>>(
      getClassesBfs(classes[0])); 
    // intersect with next 
    for (int i = 1; i < classes.length; i++) { 
     rollingIntersect.retainAll(getClassesBfs(classes[i])); 
    } 
    return new LinkedList<Class<?>>(rollingIntersect); 
} 

तरीकों और परीक्षण

private static void test(Class<?>... classes) { 
    System.out.println("Common ancestor for " 
      + simpleClassList(Arrays.asList(classes)) + ", Result => " 
      + simpleClassList(commonSuperClass(classes))); 
} 

private static String simpleClassList(Collection<Class<?>> classes) { 
    StringBuilder builder = new StringBuilder(); 
    for (Class<?> clazz : classes) { 
     builder.append(clazz.getSimpleName()); 
     builder.append(","); 
    } 
    return builder.toString(); 
} 

public static void main(String[] args) { 
    test(A.class, AImpl.class); 
    test(A.class, B.class, C.class); 
    test(A.class, AB.class); 
    test(AImpl.class, ABImpl.class); 
    test(ABImpl.class, ABImpl2.class); 
    test(AImpl.class, ABImpl.class, ABImpl2.class); 
    test(ABImpl.class, ABImpl2.class, BCImpl.class); 
    test(AImpl.class, ABImpl.class, ABImpl2.class, BCImpl.class); 
    test(AB.class, ABImpl.class); 
} 

आउटपुट

Common ancestor for A,AImpl,, Result => A, 
Common ancestor for A,B,C,, Result => 
Common ancestor for A,AB,, Result => A, 
Common ancestor for AImpl,ABImpl,, Result => A, 
Common ancestor for ABImpl,ABImpl2,, Result => A,B, 
Common ancestor for AImpl,ABImpl,ABImpl2,, Result => A, 
Common ancestor for ABImpl,ABImpl2,BCImpl,, Result => B, 
Common ancestor for AImpl,ABImpl,ABImpl2,BCImpl,, Result => 
Common ancestor for AB,ABImpl,, Result => AB,A,B, 

Answer 2

परावर्तन आप जानकारी आप अपने खुद के कोड लिखने की जरूरत दे सकते हैं:

Class<?> c = SomeType.class; // or someObject.getClass() 
Class<?> superClass = s.getSuperClass(); 
Class<?>[] interfaces = s.getInterfaces(); 

Answer 3

यह मैं सहायक एडम के जवाब पर आधारित है।

सबसे पहले, मैंने getClasses अनुकूलित किया ताकि यह कम अस्थायी वस्तुएं पैदा करे, यानी प्रत्येक स्तर के लिए LinkedHashSet के बजाय केवल एक ArrayDeque।

public static Set<Class<?>> getSuperclasses(Class<?> clazz) { 
    final Set<Class<?>> result = new LinkedHashSet<>(); 
    final Queue<Class<?>> queue = new ArrayDeque<>(); 
    queue.add(clazz); 
    if (clazz.isInterface()) { 
     queue.add(Object.class); // optional 
    } 
    while (!queue.isEmpty()) { 
     Class<?> c = queue.remove(); 
     if (result.add(c)) { 
      Class<?> sup = c.getSuperclass(); 
      if (sup != null) queue.add(sup); 
      queue.addAll(Arrays.asList(c.getInterfaces())); 
     } 
    } 
    return result; 
} 

आम सुपर-क्लास लगाने के लिए, retainAll(getClasses()) करने के लिए कॉल, if (!isAssignableFrom()) remove() साथ बदला जा सकता है, ताकि काफी महंगा getClasses केवल एक बार बुलाया जाएगा। यह विधि ऐसा लगता है कि नेस्टेड लूप की वजह से मूल समाधान की तुलना में इसकी जटिलता खराब है, लेकिन मूल समाधान में केवल यही कारण है, आंतरिक लूप retainAll में छिपा हुआ है।

public static Set<Class<?>> commonSuperclasses(Iterable<Class<?>> classes) { 
    Iterator<Class<?>> it = classes.iterator(); 
    if (!it.hasNext()) { 
     return Collections.emptySet(); 
    } 
    // begin with set from first hierarchy 
    Set<Class<?>> result = getSuperclasses(it.next()); 
    // remove non-superclasses of remaining 
    while (it.hasNext()) { 
     Class<?> c = it.next(); 
     Iterator<Class<?>> resultIt = result.iterator(); 
     while (resultIt.hasNext()) { 
      Class<?> sup = resultIt.next(); 
      if (!sup.isAssignableFrom(c)) { 
       resultIt.remove(); 
      } 
     } 
    } 
    return result; 
} 

अंत में, अपने प्रश्न में ऐसा लगता है कि आप केवल न्यूनतम सुपर क्लास, जिसके कारण हम एक आदेश दिया सेट का उपयोग में रुचि रखते हैं। लेकिन हम आसानी से गैर पत्ती वर्गों को भी हटा सकते हैं। यहां जटिलता ओ (एन) सर्वोत्तम मामला है (यदि केवल एक परिणाम है) और ओ (एन^2) सबसे खराब मामला है।

public static List<Class<?>> lowestCommonSuperclasses(Iterable<Class<?>> classes) { 
    Collection<Class<?>> commonSupers = commonSuperclasses(classes); 
    return lowestClasses(commonSupers); 
} 

public static List<Class<?>> lowestClasses(Collection<Class<?>> classes) { 
    final LinkedList<Class<?>> source = new LinkedList<>(classes); 
    final ArrayList<Class<?>> result = new ArrayList<>(classes.size()); 
    while (!source.isEmpty()) { 
     Iterator<Class<?>> srcIt = source.iterator(); 
     Class<?> c = srcIt.next(); 
     srcIt.remove(); 
     while (srcIt.hasNext()) { 
      Class<?> c2 = srcIt.next(); 
      if (c2.isAssignableFrom(c)) { 
       srcIt.remove(); 
      } else if (c.isAssignableFrom(c2)) { 
       c = c2; 
       srcIt.remove(); 
      } 
     } 
     result.add(c); 
    } 
    result.trimToSize(); 
    return result; 
} 

Answer 4

इसे आजमाएं।

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, T... args) { 
    return (Class<T>)args.getClass().getComponentType(); 
} 

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, Class<? extends T> c3, T... args) { 
    return (Class<T>)args.getClass().getComponentType(); 
} 

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, Class<? extends T> c3, Class<? extends T> c4, T... args) { 
    return (Class<T>)args.getClass().getComponentType(); 
} 

परिणाम

System.out.println(commonSuperClass(A.class, AImpl.class));          // -> A 
System.out.println(commonSuperClass(A.class, B.class, C.class));        // -> Object 
System.out.println(commonSuperClass(A.class, AB.class));          // -> A 
System.out.println(commonSuperClass(AImpl.class, ABImpl.class));        // -> A 
System.out.println(commonSuperClass(ABImpl.class, ABImpl2.class));        // -> A 
System.out.println(commonSuperClass(AImpl.class, ABImpl.class, ABImpl2.class));     // -> A 
System.out.println(commonSuperClass(ABImpl.class, ABImpl2.class, BCImpl.class));    // -> B 
System.out.println(commonSuperClass(AImpl.class, ABImpl.class, ABImpl2.class, BCImpl.class)); // -> Object 

Answer 5

मैं भी अभी इस समस्या का सामना करना पड़ रहा है। मुझे केवल सुपरक्लास स्तर पर उत्तर की आवश्यकता है। असल में मुझे केवल ओ (एन) चलने के लिए सबसे अच्छा लगा।

परिणाम:

आप (ए, बी) आप वर्ग एक और वर्ग बी

के निकटतम सुपर क्लास दे एक वर्ग में ही आप इस एल्गोरिथ्म का उपयोग कर सकते में Cmin परिणाम के बाद से एक ऑपरेशन Cmin को परिभाषित करने के लिए है = सीमीन एआई | (एआई तत्व कक्षाओं में)।

आपको ओ (एन) देता है।

लेकिन याद रखें कि जावा इंटरफेस या कक्षाओं के प्रकारों में एक भेद बनाता है।

Answer 6

वसंत फ्रेमवर्क उपयोगकर्ताओं के लिए org.springframework.util.ClassUtils#determineCommonAncestor है।

उदाहरण के लिए:

ClassUtils.determineCommonAncestor(Integer.class, LongAdder.class);