11_min_1_2.html

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<title>11. Smallest and second-smallest element</title>
<link rel="stylesheet" href="template/style.css">
</head>
<body>


<span style="float: right">
[
<a href="10_binary_counter.html">previous</a>, 
<a href="index.html">contents</a>, 
<a href="12_merge_sort.html">next</a>
]
</span>


<a name="L11.-Smallest-and-second-2d-smallest-element"></a>
<h1>11. Smallest and second-smallest element</h1>

<a name="Write-code-backward"></a>
<h2>Write code backward</h2>

<p>You all learned that the first thing you do when programming is define abstract things,
then do specific things.
I am teaching you intentionally the opposite approach.
I am not smart enough to write interfaces first.
First you write the code.
You write the algorithm.
Then you figure out what you need for the algorithm.
The interface comes out of the use,
not from contemplation.</p>

<p>I prefer to write code backward.
Then everything just falls out.
Delay thinking.
Be lazy.
For most algorithms you also need objects.
So you can design those after.
All the best programmers are lazy.
If they were not lazy, they would do work with their hands.
They invented programming languages to be lazy. Imitate them.</p>

<a name="Overview"></a>
<h2>Overview</h2>

<p>We will call the function which finds the smallest and second smallest element <code>min_element1_2</code>.
Note that I picked this algorithm not because it is of paramount importance
for your future work.
I pick this algorithm because it allows us to learn how to do decomposition
and learn these components like <code>list_pool</code> and <code>binary_counter</code> along the way.</p>

<p>Let me sketch the grand plan of the whole algorithm.</p>

<ol>
<li><p>We already showed that we want to arrange our comparisons like a tennis tournament,
and <code>binary_counter</code> helps us do this.
Instead of comparing by left reduction, we compare by balanced reduction.</p></li>
<li><p>We also want to keep a history for each element of all
the other elements which they have beat.
This history will be used to determine the second-place guy.</p>

<p>We will store this history in a list (using <code>list_pool</code>)
along with each element in the binary counter.
Note that the counter works on generic elements, so it doesn&rsquo;t
need to be modified to know about this history tracking.</p></li>
</ol>


<p>From where we are now, it should only take 4-5 lines of code
to write <code>min_element_1_2</code> along with type scaffolding.</p>

<a name="Combining-binary-counter-and-list-pool"></a>
<h2>Combining binary counter and list pool</h2>

<a name="Inner-loop"></a>
<h3>Inner loop</h3>

<p>To start, let us imagine you have all the materials to build it (we don&rsquo;t)
and discuss the main loop:</p>

<ol>
<li><p>Do a <code>while</code> loop over a range of elements and add them to a <code>binary_counter</code>.</p>

<p>Actually we will store iterators pointing to the elements, rather than the elements themselves
so we can return all the useful information.</p></li>
<li><p>Reduce the counter. The result will be the minimum element.</p></li>
<li><p>The winner will also have a list of other elements it was compared with.
Use <code>std::min_element</code> to find the second place element in the list of losers.</p></li>
<li><p>Take the result of 2 and 3 and combine them in a pair. Return it.</p></li>
</ol>


<p>Now let&rsquo;s start writing it,
even though we don&rsquo;t have all the parts.
It&rsquo;s programming with smoke and mirrors<sup id="fnref:1"><a href="#fn:1" rel="footnote">1</a></sup>.</p>

<pre><code>while (first != last) counter.add(std::make_pair(first++, pool.empty_queue()));
result_type min1_list = counter.reduce();
I min1 = min1_list.first;
I min2 = *std::min_element(iterator(pool, min1_list.second.first), iterator(pool), cmp);
return std::make_pair(min1, min2);
</code></pre>

<p>We will have to adjust it, but
these are the only instruction generating lines<sup id="fnref:2"><a href="#fn:2" rel="footnote">2</a></sup>:</p>

<p>Before the loop we need to define these objects and types.
Let&rsquo;s construct our counter. Do we know its type? No.
That&rsquo;s ok, call it <code>counter_type</code>.</p>

<pre><code>counter_type counter(op, std::make_pair(last, pool.empty_queue()));
</code></pre>

<p>We need a counter operation.
Do we know its type? No.
Do the lazy thing, call it <code>op_type</code>.</p>

<pre><code>op_type op(cmp, pool);
</code></pre>

<p>Now define the pool. We do know its type:</p>

<pre><code>list_pool&lt;I, std::size_t&gt; pool;
</code></pre>

<p>Notice that we use <code>std::min_element</code> on our list pool.
Will that work?
Yes, because we added iterators to our list pool.
Define our <code>iterator</code> type:</p>

<pre><code>typedef typename list_pool&lt;I, std::size_t&gt;::iterator iterator;
</code></pre>

<p>We are almost done.
There are bunch of <code>typedef</code> and a bunch of little classes
to write, but we are sort of done.</p>

<a name="Comparing-iterator-values"></a>
<h3>Comparing iterator values</h3>

<p>We will be storing <code>list_pool</code> iterators,
We don&rsquo;t want to compare iterators, we want to compare
their values.
Let&rsquo;s write a type function
which takes any comparison operation on type <code>T</code>,
and returns a comparison for <code>iterator&lt;T&gt;</code>.</p>

<pre><code>template &lt;typename Compare&gt;
class compare_dereference
{
private:
  Compare cmp;
public:
  compare_dereference(const Compare&amp; cmp) : cmp(cmp) {}
  template &lt;typename I&gt;
  bool operator() (const I&amp; x, const I&amp; y) const {
    return cmp(*x, *y);
  }
};
</code></pre>

<p>So in the main loop replace <code>cmp</code> with <code>cmp_deref</code> and add the following
lines:</p>

<pre><code>typedef compare_dereference&lt;Compare&gt; compare_type;
compare_type cmp_deref(cmp);
</code></pre>

<a name="Reduction-operation"></a>
<h3>Reduction operation</h3>

<p>We will define a reduction function object
to be used in the binary counter to find the <code>min</code>.
What it will do is apply a comparison operation between two elements <code>cmp(a, b)</code>.
When an element wins a comparison, the loser will be added
to a list of elements which have lost to <code>a</code>.
In other words, it will keep track of the elements which each element has beaten.
This list of &ldquo;losers&rdquo; associated with each element is stored in a <code>list_pool</code>.</p>

<pre><code>template &lt;typename T, typename N, typename Compare&gt;
class op_min1_2 
{
private:
  Compare cmp;
  list_pool&lt;T, N&gt;* p;
public:
  typedef typename list_pool&lt;T, N&gt;::list_type list_type;
  typedef std::pair&lt;T, std::pair&lt;list_type, list_type&gt; &gt; argument_type;

  op_min1_2(const Compare&amp; cmp, list_pool&lt;T, N&gt;&amp; pool) : cmp(cmp), p(&amp;pool) {}

  argument_type operator()(const argument_type&amp; x, 
                           const argument_type&amp; y) {
    if (!cmp(y.first, x.first)) {
      p-&gt;free(y.second);
      return std::make_pair(x.first, p-&gt;push_back(x.second, y.first));
    } else {
      p-&gt;free(x.second);
      return std::make_pair(y.first, p-&gt;push_front(y.second, x.first));
    }
  }
};
</code></pre>

<p>When an element wins, we can combine its list of losers
with the element it beat, due to transitivity.
We want this operation to be stable, so we need to be careful with the order
in which the losers are stored.
Note that one uses <code>push_back</code> and the other <code>push_front</code>.</p>

<a name="Finishing-the-scaffolding"></a>
<h3>Finishing the scaffolding</h3>

<p>Now that we have all the parts,
we can define the final missing types and the signature:</p>

<pre><code>template &lt;typename I, typename Compare&gt;
// requires I is a ForwardIterator
// and Compare is a StrictWeakOrdering on ValueType(I)
std::pair&lt;I, I&gt; min_element1_2(I first, I last, Compare cmp) {
  if (first == last || successor(first) == last) {
    return std::make_pair(first, last);
  }

  typedef op_min1_2&lt;I, size_t, compare_type&gt; op_type;
  typedef binary_counter&lt;op_type&gt; counter_type;
  typedef typename op_type::argument_type result_type;

  // ...
}
</code></pre>

<p>If you put all these components together, and get it to compile
it should work<sup id="fnref:3"><a href="#fn:3" rel="footnote">3</a></sup>.
The fact that you can do that, is to me a miracle.
There is quite a lot of complexity going on.
This sense of wonder does not disappear.</p>

<p><strong>Exercise:</strong> Implement this algorithm in another language.
    It will help you see language limitations and understand the algorithm better.</p>

<a name="Why-do-we-need-the-typename-keyword-3f-"></a>
<h2>Why do we need the typename keyword?</h2>

<p>Once upon a time there were
templates, there was STL, people were writing code,
but there was no <code>typename</code> and everything worked.
Of course, clever people (all the clever people reside in the standard committee (joke))
brought up this example:</p>

<pre><code>template &lt;class T&gt;
class foo {
    typedef T::value_type value_type;
};
</code></pre>

<p>Obviously what you are trying to do is extract <code>T</code>&rsquo;s <code>value_type</code>
and use it here.
Let us try to follow the committees logic.
The logic says maybe <code>T::value_type</code> refers to a static variable
in <code>T</code>, which it could be of course.
But, don&rsquo;t you know from the context that it&rsquo;s supposed to be a type?
Since they are very well educated, they say, &ldquo;but that will
make our grammar <a href="https://en.wikipedia.org/wiki/Context-free_grammar">context-sensitive</a><sup id="fnref:4"><a href="#fn:4" rel="footnote">4</a></sup>.
We need to figure out the meaning of
a token without referring to the context in which it appears&rdquo;.</p>

<p>So they came up with the following rule:
If you don&rsquo;t put <code>typename</code>, the compiler must assume it is a variable,
even if it is a type.
This is done to maintain the property that you don&rsquo;t need to know outside context.
Of course, the problem here does not really relate to <code>typename</code>.
The problem exists because <code>T</code> is not specified.
The language has no concepts.
For example if we said <code>Container T</code>
instead of <code>class T</code>, and had a concept <code>Container</code>, the definition of <code>Container</code> would say that it is required to have an affiliated type <code>value_type</code>.
Then the compiler could figure out what we really mean.</p>

<p>What often happens is that instead of
solving the real problem, a partial problem is solved.
We still do not have concepts.
One of the great things about C++
is the language has been evolving for 40 years which is also one of the terrible
problems.
All its features have been added over time.
So, it works with all kinds of quirks.</p>

<p>The advice Bjarne gives right now, is use <code>typename</code> whenever you can,
even in the context when it&rsquo;s not absolutely required.</p>

<a name="Code"></a>
<h2>Code</h2>

<ul>
<li><a href="code/min_element1_2.h">min_element1_2.h</a></li>
<li><a href="code/test_min1_2.cpp">test_min1_2.cpp</a></li>
</ul>

<div class="footnotes">
<hr/>
<ol>
<li id="fn:1">
In the lectures Alex goes through several rounds
of defining and renaming types.
I included this section to illustrate the process.
If you are confused refer to the final code
at the end of the lesson.<a href="#fnref:1" rev="footnote">&#8617;</a></li>
<li id="fn:2">
These are the only lines of code which generate
assembly instructions for the CPU to execute.
All other lines of code are just to make the C++ type system work.<a href="#fnref:2" rev="footnote">&#8617;</a></li>
<li id="fn:3">
<p>Much of the scaffolding can be removed in modern C++.
Most of the ugly <code>typename ...</code> definitions
could be replaced by <code>auto</code>, which was introduced in C++11.
A few of the function objects (such as <code>compare_dereference</code>)
may also make more sense as C++ lambdas.</p><a href="#fnref:3" rev="footnote">&#8617;</a></li>
<li id="fn:4">
This terminology is specific to compilers and theory
of computation. It refers to a classification
of formal languages based on their complexity to parse.<a href="#fnref:4" rev="footnote">&#8617;</a></li>
</ol>
</div>


<span style="float: right">
[
<a href="10_binary_counter.html">previous</a>, 
<a href="index.html">contents</a>, 
<a href="12_merge_sort.html">next</a>
]
</span>


</body>
</html>