title: Lowest common ancestor in a linear lineage of types
body: <h2>Intro</h2>
  
  <p>Let's suppose that we have a <strong>linear hierarchy of types</strong> like the following:</p>
  
  <p><img src="https://i.stack.imgur.com/iZxuN.png" alt="toy linear hierarchy"></p>
  
  <p>Then what I want is <strong>a mechanism to return the lowest common ancestor</strong> out of an arbitrary number of types in that lineage. </p>
  
  <h2>Attempted Code</h2>
  
  <pre><code>template&lt;typename...Ts&gt;
  struct LCA;
  
  template&lt;typename T1, typename T2, typename...Ts&gt;
  struct LCA&lt;T1, T2, Ts...&gt;
  {
      using base = typename std::conditional
      &lt;
          std::is_base_of&lt;T1, T2&gt;::value, T1,
          typename std::conditional &lt;
              std::is_base_of&lt;T2, T1&gt;::value, T2, void
          &gt;::type
      &gt;::type;
  
      using type = typename LCA&lt;base, Ts...&gt;::type;
  };
  
  template&lt;typename T&gt;
  struct LCA&lt;T&gt;
  {
      using type = T;
  };
  </code></pre>
  
  <p><a href="http://ideone.com/0cFAMa" rel="nofollow noreferrer"><strong>Live Demo</strong></a></p>
  
  <h2>Use Case</h2>
  
  <p>My use case is rather typical: In making some <code>iterator</code> tools I want to extract the "most restrictive" iterator type, so since there's (kind of) a linear hierarchy in iterators I should to able to ascent the hierarchy as much as it's needed:</p>
  
  <pre><code>LCA&lt;Bidirectional, RandomAccess, RandomAccess&gt; -&gt; Bidirectional
  LCA&lt;RandomAccess, Input, Forward&gt;              -&gt; Input
  </code></pre>
  
  <h2>Questions</h2>
  
  <ol>
  <li><p>Is there a more concise / idiomatic way of <strong>handling of the error case</strong> where two or more types are strangers to the hierarchy? The current approach is to return <code>void</code> which hopefully will give failure in most contexts where the type is actually used. </p></li>
  <li><p>Is the use of an extra <code>base</code> member in the first specialization problematic? Should I extract that functionality in a separate class and use it inline in <code>type</code> to <strong>maintain uniformity</strong>?</p></li>
  <li><p>Is there an algorithm that would <strong>reduce the number of instantiations</strong>? Is there a better way than pairwise comparisons, so that the complexity of the algorithm can be reduced? </p></li>
  <li><p>Can anyone scale to <strong>non linear hierarchies</strong> and query by depth a hierarchy tree? What would be a good "tie breaker" in that case (for types in the same level)?</p></li>
  </ol>