Saturday, May 8, 2021

Moore's Law

I think many people interested in technology are familiar with Moore's law.

It's basically the observation that the number of transistors that can be fitted on chips doubles about every two years. This density of transisters per square millimeter is related to the process size, for example the latest generation of high end CPUs and GPUs are using 7 nanometer technology, with 5 nm in development.

The assumption or perhaps implied implication of Moore's Law is that you would expect that this means the price per transistor would be proportionally getting less. For every square millimeter of silicon wafer you have, you are over time able to make more and more transistors on there. It was as if Moore's Law was a proxy for the price per transistor.

You could be forgiven for thinking that it means that year after year for a given amount of money you can buy an ever more powerful computer. I previously thought that was what it meant in practice.

However shinking the process size has slowly been getting more and more expensive to do. This has been the case since 28 nm. Since then the price per transistor has been going up for smaller and smaller process sizes. Let that sink in for a moment, the price per transistor has been going up, not down.

So for a 7nm chip, with more transistors, and with a higher price per transistor, it is no wonder newer CPUs and GPUs are costing more. And add to that some inflation happening in the economy as well as some supply chain issues due to COVID, it's no wonder that various products are seeing some pretty high prices at the moment.

Also it's worth trying to appreciate the supply side. One of the main suppliers is TSMC, based in Taiwan. There are fewer and fewer fabrication facilities for the smaller and smaller process sizes as the required investment increases. There are constraints on finding large enough areas of industrial land with ready access to the large amounts of water and electricity, this requires years of planning with consultation with government to have these facilities.

With fewer places able to make the newer process size chips, obviously supply is an issue. There is more fagility with fewer suppliers. https://en.wikipedia.org/wiki/Antifragility This makes the production sensitive to any stressors/failures leading to high volitility. And there have been stressors in the form of COVID and also crypto mining demand.

Intel announced recently that they will create a new plant in Arizona:

https://newsroom.intel.com/wp-content/uploads/sites/11/2021/03/Intel-Arizona-manufacturing-15073363.pdf

It will probably be several years until it will be able to produce anything, but they did this with consultation and cooperation from the Arizona government and also the Biden administration. It's a $20 billion dollar investment that will help provide production security for the US and US companies like Intel, Nvidia and Apple.


Thursday, December 5, 2019

Ranges, views, pipes

Something I've always liked about UNIX systems is the idea of a collection of tools which can be combined together using pipes to do all kinds of interesting things relatively easily.

For example:

     cat wordlist.txt | sort | uniq | wc -l

This takes a list of words on each line from the input file, pipes it through a command to sort the input and then filters out any repeated lines and finally counts the number of lines, which will tell you the number of unique words/lines in the input file. You can also filter these with commands like grep and sed, as well as use sed and tr to translate the input and so on.

Under the hood, UNIX starts a process for each of these commands. Each process reads from stdin and writes to stdout, however when piped, these are joined together where the output of ones becomes the input of the next in the chain. When they are waiting for input and none is currently available, the OS will not schedule that process and schedule another which is ready to run. One that is ready will read from its stdin and write to its stdout which will then have the effect of making another process ready to run again because it now has input that can be read. So it is actually the scheduler of the OS which is making some of the magic happen. A not so smart OS implementation might allow the first process to run to completion and buffer all of its output to then start the next process and feed it all of the buffered output from the first command in to it. This obviously will work for simple cases, but doesn't scale to long running chains of commands or ones where there is a very large amount of data processed which can not all fit in memory.

I've often thought, it would be neat to do something like this in C++ code to express how a chain of processes could be linked up together. You can always chain up function calls in C++, and it has always been possible to override the pipe operator. Chaining function calls together is something you can do with an API designed for being used in that way such as this example using Qt:

     QString("Format : %1 %2 %2").arg(1).arg(2).arg(3);

This though is along the lines of the 2nd type of OS implementation strategy for pipes where each command is run to completion one at a time without doing the smart thing. Examples where the pipe operator are used can also be found in Qt, such as how flags are combined. See the documentation for https://doc.qt.io/qt-5/qflags.html#Q_DECLARE_OPERATORS_FOR_FLAGS which generates the operator for combining flags.

Putting it together, and it should be possible to define a pipe operator which joins together things which are iterable, and have something similar to UNIX style pipes in C++ code, for example:

     cat("wordlist.txt") | sort() | uniq()

More idiomatic for C++ would be:

     cat("wordlist.txt").sort().uniq();

And that is the way you would join up things in C# also when using LINQ and iterables.
However if really want to push onwards towards replicating UNIX pipes and adding syntactic sugar to replicate the syntax of a UNIX shell, then it may be even possible to drop the round braces in places, such as from the sort and uniq:

     cat("wordlist.txt") | sort | uniq > out;

Where 'sort', 'uniq' and 'out' would need to be objects instead of functions. But the pipe operator for the particular pair of types can be made to call specific functions on the objects, which is then how these can be glued together. Specifically:

// A class which does sorting
class SortClass { public: SortClass(); };

// An object called 'sort'
SortClass sort;

// A class which does uniq
class UniqClass { public: UniqClass(); };

// An object called 'uniq'
UniqClass uniq;

//  A pipe operator to combine these
operator|(SortClass&, UniqClass&);

sort | uniq;

And it seems like something like this is coming to C++ in the form of the Ranges Library:


Co-routines immediately come to mind as something else which would be nice, such as having the yield feature that exists in C#. This would make it easier to have something more similar to the first type of smart OS implementation strategy for pipes, but without necessarily using threads/processes.

Some other things I've seen in other contexts that I've liked are the map/reduce/filter types of expressions in languages like javascript and python. It's more the syntax and ways in which these easily combine that is nice about them, much like what it is I like about UNIX pipes.

It seems like with the Ranges Library it will be possible to have map/reduce/filter kinds of operations such as is given on the cppreference web page for the ranges library:


int main()
{
    std::vector<int> ints{0,1,2,3,4,5};
    auto even = [](int i){ return 0 == i % 2; };
    auto square = [](int i) { return i * i; };
 
    for (int i : ints | std::views::filter(even) | std::views::transform(square)) {
        std::cout << i << ' ';
    }
}


The yield keyword in C# for expressing iteration over something and returning the elements without having to turn the code inside out to make it an iterator is nice, and the general way iterables and LINQ can be used in C# to do interesting things. This is along the lines of co-routines, and C++ looks to be adding them. From what I understand of how yield is implemented in C#, using threads isn't required for making yield work.

If a language is designed to support co-routines, essentially the execution of a function can be suspended by jumping to another location if the state of the stack is preserved, and then the function resumed by jumping back if the stack and execution continues where it was previously. Typically you would think a thread is how you might do this because each thread has its own stack. If manually turning a function inside-out to make it in to a co-routine, the manual procedure is to turn all stack allocations in to something contained in a structure which represents the state to be preserved. This state also needs to track where in the function it was, so when it resumes being executed, it can jump to the previous location. When recursion is involved, the solution is that this structure is an array of this state to the maximum recursion depth and the current depth is also tracked. You can manually convert a function in C/C++ to be able to be used this way, but it is ugly and the resulting code is not as elegant when compared to the same code in C# written using yield. And it looks like in C++20 this will become an option which is quite exciting:

https://en.cppreference.com/w/cpp/language/coroutines

It appears as though the state which is preserved which would have otherwise been on the stack is dynamically allocated using new. I wonder how it deals with recursive functions. Possibly dynamically allocating the state isn't always needed, if hand rolling a conversion of a function to act similar to a co-routine, it is possible to allocate that state on the stack at the call-site and pass that down to the call of the co-routine as an input parameter, and then what you want is the language which supports co-routines to do that for you, and if not possible to allocate it from the stack to otherwise allocate it from the heap, but this is a pretty minor issue compared with the bigger problem which will be solved. Compared with the ranges library, I'm more excited about the addition of the coroutines, as trying to emulate coroutines without actual language support for them is hacky at best, or if not hacky, very inelegant.

About emulating the ranges library, that is something I've attempted with my own flavour on things. For example, the example given using ranges is this:

    for (int i : ints | std::views::filter(even) | std::views::transform(square)) {
        std::cout << i << ' ';
    }

Why is there the need to expose the for loop, and why isn't there a terminal print object to pipe in to which can do the output as above. My take on this would be to have a syntax like this:

    ints | filter(even) | transform(square) | print;

So below is my implementation of my flavour of something similar to the C++20 ranges library that will however work with C++14 now, or with some effort could be made to work with C++11 if you don't mind making the code more verbose. I'm personally happy to target C++14 as my minimum, so have designed this code to require C++14. Here it is:




//
//  C++ Views and Pipes
//  by John Ryland
//  (c) Copyright 2019
//


///////////
// BRIEF //
///////////

/*

  Requires C++14, but would not be impossible to support C++11 with effort.

  Compile with:

      g++ --std=c++14 pipe-tests.cpp -o pipe-tests

  Examples of what it can do:

      to_array({"one","two","three","four","five"}) | reverse
              | filter([](std::string a){ return a == "two"; }) | print;
    
    This is C++ code, and it takes the list of strings and turns them in to a
    std::array, then pipes it through a reverse function which causes the
    iteration to happen in reverse, then pipes this through a filter which
    is defined with an inline lambda which removes any items which equal "two",
    and finally it prints out the result.
      
    The lambdas don't need to be inline, it can be nicer to define a function
    like this:

      auto odd = [](int x) -> bool { return (x & 1) == 1; };

    Then it can be used like this:
        
      std::vector v = {1,2,3,4,5};
      container_view(v) | match(odd) | print;

    This takes as input a std::vector of items, and wraps it in a view which is
    piped to a matching function which will only pass through items where the
    lambda returns true for the item. Internally the vector is not copied, simply
    the iteration is what is varied. Next it prints out the result.

    More complicated examples can be made:

      range(1,101) | reverse | filter(odd) | first(5) | print;

    This one uses the range function which generates items. At no point is an
    actual list or vector of numbers made in memory. However it will print the
    last 5 odd numbers working backwards from 101 as might be expected from
    the commands.

*/


//////////////
// INCLUDES //
//////////////

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <sstream>
#include <array>
#include <regex>
#include <functional>


/////////////////
// TYPE TRAITS //
/////////////////

// Container Traits ///////////////////////////////////////////////////////////

template <typename T, typename _ = void>
struct has_container_traits : std::false_type {};


template <typename... Ts>
struct has_container_traits_helper {};


template <typename T>
struct has_container_traits<T, std::conditional_t<false, has_container_traits_helper<
       // Const Container Trails:
       typename T::value_type,
       typename T::const_iterator,
       typename T::const_reverse_iterator,
       decltype(std::declval<T>().crbegin()),
       decltype(std::declval<T>().crend()),
       decltype(std::declval<T>().cbegin()),
       decltype(std::declval<T>().cend())
>, void>> : public std::true_type {};


template <typename Container,
          typename std::enable_if<has_container_traits<Container>{}, bool>::type = true>
struct is_container
{
  using type = bool;
};


template <typename Container>
using is_container_t = typename is_container<Container>::type;


// View Traits ////////////////////////////////////////////////////////////////

template <typename T, typename _ = void>
struct has_view_traits : std::false_type {};


template <typename... Ts>
struct has_view_traits_helper {};


template <typename T>
struct has_view_traits<T, std::conditional_t<false, has_view_traits_helper<
       // View Traits:
       typename T::element_type,
       decltype(std::declval<T>().first()),
       decltype(std::declval<T>().last()),
       decltype(std::declval<T>().next()),
       decltype(std::declval<T>().previous()),
       decltype(std::declval<T>().current())
>, void>> : public std::true_type {};


template <typename View,
          typename std::enable_if<has_view_traits<View>{}, bool>::type = true>
struct is_view
{
  using type = bool;
};


template <typename View>
using is_view_t = typename is_view<View>::type;


////////////////
// VIEW TYPES //
////////////////

// Container View /////////////////////////////////////////////////////////////

template <typename Container, typename BaseType, is_container_t<BaseType> = true>
class container_wrapper_view
{
public:
  container_wrapper_view(Container a_container)
    : m_container(a_container)
  {
  }

  // implements View
  using element_type = typename BaseType::value_type;
  bool first() { m_it = m_container.cbegin();    return !m_container.empty(); }
  bool last()  { m_it = std::prev(m_container.cend()); return !m_container.empty(); }
  bool next()  { m_it = std::next(m_it);         return m_it != m_container.cend(); }
  bool previous() { if (m_it != m_container.cbegin()) { m_it = std::prev(m_it); return true; } return false; }
  const element_type& current() { return *m_it; }
private:
  Container                                 m_container;
  typename BaseType::const_iterator         m_it;
};


// Range View /////////////////////////////////////////////////////////////////

template <typename T>
class range_view
{
public:
  range_view(T start, T end)
    : m_start(start)
    , m_end(end)
  {
  }

  // implements View
  using element_type = T;
  bool first()         { m_current = m_start; return m_start <= m_end; }
  bool last()          { m_current = m_end;   return m_start <= m_end; }
  bool next()          { ++m_current; return m_current <= m_end;       }
  bool previous()      { --m_current; return m_current >= m_start;     }
  const T& current()   { return m_current; }
private:
  T m_current;
  T m_start;
  T m_end;
};


// Match View ////////////////////////////////////////////////////////////////

template <typename ParentView, typename Functor, is_view_t<ParentView> = true>
class match_view
{
public:
  using element_type = typename ParentView::element_type;
  match_view(const ParentView& a_parentView, const Functor& a_match)
    : m_parentView(a_parentView)
    , m_match(a_match)
  {
  }

  // implements View
  bool first()                  { if (!m_parentView.first())    return false; return nextValid();     }
  bool last()                   { if (!m_parentView.last())     return false; return previousValid(); }
  bool next()                   { if (!m_parentView.next())     return false; return nextValid();     }
  bool previous()               { if (!m_parentView.previous()) return false; return previousValid(); }
  const element_type& current() { return m_parentView.current(); }
private:
  bool nextValid()              { while (!m_match(m_parentView.current())) { if (!m_parentView.next())     return false; } return true; }
  bool previousValid()          { while (!m_match(m_parentView.current())) { if (!m_parentView.previous()) return false; } return true; }
  ParentView    m_parentView;
  Functor       m_match;
};


// Filter View ////////////////////////////////////////////////////////////////

template <typename ParentView, is_view_t<ParentView> = true>
class filter_view : public match_view<ParentView, std::function<bool(typename ParentView::element_type)>>
{
public:
  // inherits View
  using element_type = typename ParentView::element_type;
  using function_type = std::function<bool(element_type)>;

  filter_view(const ParentView& a_parentView, const function_type& a_filter)
    : match_view<ParentView, function_type>(a_parentView, [a_filter](element_type a_item) { return !a_filter(a_item); })
  {
  }
};


// Transform View /////////////////////////////////////////////////////////////

template <typename ParentView, typename Functor, typename ReturnType, is_view_t<ParentView> = true>
class transform_view
{
public:
  using parent_element_type = typename ParentView::element_type;
  transform_view(const ParentView& a_parentView, const Functor& a_transform)
    : m_parentView(a_parentView)
    , m_transform(a_transform)
  {
  }

  // implements View
  using element_type = ReturnType;
  bool first()                  { return m_parentView.first(); }
  bool last()                   { return m_parentView.last(); }
  bool next()                   { return m_parentView.next(); }
  bool previous()               { return m_parentView.previous(); }
  element_type current()        { return m_transform(m_parentView.current()); }   // NOTE: Transformed elements are returned by value
private:
  ParentView       m_parentView;
  Functor          m_transform;
};


// Reverse View ///////////////////////////////////////////////////////////////

template <typename ParentView, is_view_t<ParentView> = true>
class reverse_view
{
public:
  reverse_view(const ParentView& view)
    : m_parent(view)
  {
  }

  // implements View
  using element_type = typename ParentView::element_type;
  bool first()                  { return m_parent.last(); }
  bool last()                   { return m_parent.first(); }
  bool next()                   { return m_parent.previous(); }
  bool previous()               { return m_parent.next(); }
  const element_type& current() { return m_parent.current(); }
private:
  element_type m_current;
  ParentView   m_parent;
};


// Skip View //////////////////////////////////////////////////////////////////

template <typename ParentView, is_view_t<ParentView> = true>
class skip_view
{
public:
  using element_type = typename ParentView::element_type;
  skip_view(const ParentView& a_parentView, size_t a_count)
    : m_parentView(a_parentView)
    , m_count(a_count)
  {
  }

  // implements View
  bool first()                  { if (!m_parentView.first()) return false; return nextValid();     }
  bool last()                   { if (!m_parentView.last())  return false; return previousValid(); }
  bool next()                   { return m_parentView.next();     }
  bool previous()               { return m_parentView.previous(); }
  const element_type& current() { return m_parentView.current();  }
private:
  bool nextValid()              { while (m_count >= 1) { if (!m_parentView.next())     return false; m_count--; } return true; }
  bool previousValid()          { while (m_count >= 1) { if (!m_parentView.previous()) return false; m_count--; } return true; }
  ParentView      m_parentView;
  size_t          m_count;
};


// Take View //////////////////////////////////////////////////////////////////

template <typename ParentView, is_view_t<ParentView> = true>
class take_view
{
public:
  using element_type = typename ParentView::element_type;
  take_view(const ParentView& a_parentView, size_t a_count)
    : m_parentView(a_parentView)
    , m_count(a_count)
  {
  }

  // implements View
  bool first()                  { return m_parentView.first(); }
  bool last()                   {
                                  size_t count = m_count - 1;
                                  if (count <= 0 || !m_parentView.first()) return false;
                                  while (count)
                                  {
                                    if (!m_parentView.next()) return false;
                                    count--;
                                  }
                                  return true;
                                } 
  bool next()                   { m_count--; return (m_count > 0) ? m_parentView.next()     : false; }
  bool previous()               { m_count--; return (m_count > 0) ? m_parentView.previous() : false; }
  const element_type& current() { return m_parentView.current();  }
private:
  ParentView      m_parentView;
  size_t          m_count;
};


//////////////
// WRAPPERS //
//////////////

// Container Wrapper //////////////////////////////////////////////////////////

// creates a const reference container view
template <typename Container, is_container_t<Container> = true>
auto container_view(const Container& a_container)
{
  return container_wrapper_view<const Container&, Container>(a_container);
}


// creates a container view by value
template <typename Container, is_container_t<Container> = true>
auto container_copy_view(const Container& a_container)
{
  return container_wrapper_view<Container, Container>(a_container);
}


// Range Wrapper //////////////////////////////////////////////////////////////

template <typename T>
auto range(T start, T end)
{
  return range_view<T>(start, end);
}


// Array Wrapper //////////////////////////////////////////////////////////////

template <class T, std::size_t N, std::size_t... I>
constexpr auto to_array_impl(T (&a)[N], std::index_sequence<I...>)
{
  return std::array<std::remove_cv_t<T>, N>{ { a[I]... } };
}

  
template <class T, std::size_t N, std::size_t... I>
constexpr auto to_array_impl(T (&&a)[N], std::index_sequence<I...>)
{
  return std::array<std::remove_cv_t<T>, N>{ { std::move(a[I])... } };
}


template <class T, std::size_t N>
constexpr auto to_array(T (&a)[N])
{
  return to_array_impl(a, std::make_index_sequence<N>{});
}


template <class T, std::size_t N>
constexpr auto to_array(T (&&a)[N])
{
  return to_array_impl(std::move(a), std::make_index_sequence<N>{});
}


// Print Wrapper /////////////////////////////////////////////////////////////

class print_class
{
  // No state, just the class as a tag
};


// Reverse Wrapper ////////////////////////////////////////////////////////////

class reverse_class
{
  // No state, just the class as a tag
};


// Match Wrapper //////////////////////////////////////////////////////////////

template <typename Functor>
class match_class
{
public:
  match_class(Functor&& a_m)
    : m_m(a_m)
  {
  }
  Functor m_m;
};


// Filter Wrapper /////////////////////////////////////////////////////////////

template <typename Functor>
class filter_class
{
public:
  filter_class(Functor&& a_f)
    : m_f(a_f)
  {
  }
  Functor m_f;
};


// Transform Wrapper //////////////////////////////////////////////////////////

template <typename Functor>
class transform_class
{
public:
  transform_class(Functor&& t)
    : m_t(t)
  {
  }
  Functor m_t;
};


//////////////
// COMMANDS //
//////////////

// Print Command //////////////////////////////////////////////////////////////

print_class print;


// Reverse Command ////////////////////////////////////////////////////////////

reverse_class reverse;


// Match Command //////////////////////////////////////////////////////////////

template <typename Functor>
auto match(Functor&& a_m)
{
  return match_class<Functor>(std::forward<Functor>(a_m));
}


// Grep Command ///////////////////////////////////////////////////////////////

// Match a regular expression
auto grep(const std::string& a_re)
{
  std::regex re(a_re);
  auto f = [re](const std::string& a_s) { return std::regex_search(a_s, re); };
  return match_class<decltype(f)>(std::move(f));
}


// Filter Command /////////////////////////////////////////////////////////////

template <typename Functor>
auto filter(Functor&& a_f)
{
  return filter_class<Functor>(std::forward<Functor>(a_f));
}


// Take Command ///////////////////////////////////////////////////////////////

class take
{
public:
  take(size_t a_count)
    : m_count(a_count)
  {
  }
  size_t m_count;
};


// Head Command ///////////////////////////////////////////////////////////////

using head = take;


// First Command //////////////////////////////////////////////////////////////

using first = take;


// Last Command ///////////////////////////////////////////////////////////////

class last
{
public:
  last(size_t a_count)
    : m_count(a_count)
  {
  }
  size_t m_count;
};


// Tail Command ///////////////////////////////////////////////////////////////

using tail = last;


// Skip Command ///////////////////////////////////////////////////////////////

class skip
{
public:
  skip(size_t a_count)
    : m_count(a_count)
  {
  }
  size_t m_count;
};


// Drop Command ///////////////////////////////////////////////////////////////

using drop = skip;


// Transform Command //////////////////////////////////////////////////////////

template <typename Functor>
auto transform(Functor&& a_f)
{
  return transform_class<Functor>(std::forward<Functor>(a_f));
}


// Convert Command ////////////////////////////////////////////////////////////

template <typename Functor>
auto convert(Functor&& a_f)
{
  return transform_class<Functor>(std::forward<Functor>(a_f));
}


// Join Command ///////////////////////////////////////////////////////////////

class join
{
public:
  join(const std::string& s)
    : m_s(s)
  {
  }
  std::string m_s;
};


// Split Command //////////////////////////////////////////////////////////////

class split
{
public:
  split(const std::string& a_delimiters)
    : m_delimiters(a_delimiters)
  {
  }
  std::string m_delimiters;
};


///////////
// PIPES //
///////////

// Container Pipe /////////////////////////////////////////////////////////////
  
template <typename Container, typename View, is_container_t<Container> = true>
auto operator|(const Container& c, const View& v)
{
  return container_view(c) | v;
}


// Array Pipe /////////////////////////////////////////////////////////////////

template <typename ArrayT, std::size_t ArrayN, typename View>
auto operator|(const ArrayT (&a)[ArrayN], const View& v)
{
  auto c = to_array(a);
  return container_view(c) | v;
}


// Reverse Pipe ///////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
auto operator|(const View& v1, const reverse_class& r)
{
  return reverse_view<View>(v1);
}


// Match Pipe ////////////////////////////////////////////////////////////////

template <typename View, typename Functor, is_view_t<View> = true>
auto operator|(const View& v1, const match_class<Functor>& m)
{
  return match_view<View, Functor>(v1, m.m_m);
}


// Filter Pipe ////////////////////////////////////////////////////////////////

template <typename View, typename Functor, is_view_t<View> = true>
auto operator|(const View& v1, const filter_class<Functor>& f)
{
  return filter_view<View>(v1, f.m_f);
}


// Take Pipe //////////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
auto operator|(const View& v1, const take& t)
{
  return take_view<View>(v1, t.m_count);
}


// Last Pipe //////////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
auto operator|(const View& v1, const last& l)
{
  return v1 | reverse | take(l.m_count) | reverse;
}


// Skip Pipe //////////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
auto operator|(const View& v1, const skip& s)
{
  return skip_view<View>(v1, s.m_count);
}


// Transform Pipe /////////////////////////////////////////////////////////////

template <typename View, typename Functor, is_view_t<View> = true>
auto operator|(const View& v1, const transform_class<Functor>& t)
{
  return transform_view<View, Functor, decltype(t.m_t(typename View::element_type()))>(v1, t.m_t);
}


// Join Pipe //////////////////////////////////////////////////////////////////

std::string operator|(const std::string& s, const join& j)
{
  return s;
}


std::string operator|(const char* s, const join& j)
{
  return s;
}


template <typename View, is_view_t<View> = true>
std::string operator|(const View& c, const join& j)
{
  std::stringstream ss;
  std::string deliminator = j.m_s;
  apply(c, [&ss, deliminator](const auto& a, bool f, bool l) { ss << a; if (!l) ss << deliminator; } );
  return ss.str();
}


// Split Pipe /////////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
auto operator|(const View& v1, const split& s)
{
  // https://stackoverflow.com/questions/236129/how-do-i-iterate-over-the-words-of-a-string
  std::string str = v1 | join("");
  std::string delimiters = s.m_delimiters;
  std::vector<std::string> tokens;
  std::size_t start = 0, end, length = str.length();
  while (length && start < length + 1)
  {
    end = str.find_first_of(delimiters, start);
    if (end == std::string::npos)
    {
      end = length;
    }
    std::string token = std::string(str.data() + start, end - start);
    tokens.push_back(token);
    start = end + 1;
  }

  // Unfortunately we need to make a copy here as 'tokens' is on the stack. Possibly this
  // could be improved if have a string_spans implementation as a 'view' in to the original data.
  return container_copy_view<std::vector<std::string>>(tokens);
}


// Print Pipe /////////////////////////////////////////////////////////////////

template <typename View, is_view_t<View> = true>
void operator|(const View& v1, const print_class& r)
{
  apply(v1, [](const auto& a, bool f, bool l) { std::cout << a; if (!l) std::cout << ","; } );
  std::cout << std::endl;
}


void operator|(const std::string& s, const print_class& r)
{
  std::cout << s << std::endl;
}


// Apply Pipe /////////////////////////////////////////////////////////////////

template <typename View, typename Functor, is_view_t<View> = true>
void for_each(const View& a_iterable, Functor&& f)
{
  View it = a_iterable; // takes a copy of the view, views should be cheap to copy
  if (it.first())
  {
    do
    {
      f(it.current());
    } while (it.next());
  }
}


template <typename View, typename Functor, is_view_t<View> = true>
void apply(const View& a_iterable, Functor&& f)
{
  bool first = true;
  bool last = false;
  View it = a_iterable; // takes a copy of the view, views should be cheap to copy
  if (it.first())
  {
    do
    {
      auto current = it.current();
      last = !it.next();
      f(current, first, last);
      first = false;
    } while (!last);
  }
}


template <typename View, is_view_t<View> = true>
void operator|(const View& v, const std::function<void(typename View::element_type)>& f)
{
  for_each(v, f);
}


template <typename Container, is_container_t<Container= true>
void operator|(const Container& c, const std::function<void(typename Container::value_type)>& f)
{
  std::for_each(c.begin(), c.end(), f);
}


///////////
// DEMOS //
///////////

void demo1()
{
  std::cout << "Demo" << std::endl;

  auto strings = to_array({"one","two","three","four","five"});

  std::cout << "Printing strings" << std::endl;
  strings | print;

  std::cout << "Reversing strings" << std::endl;
  strings | reverse | print;

  std::cout << "Matching strings with 'o'" << std::endl;
  strings | match([](std::string a){ return a.find("o") != std::string::npos; }) | print;

  std::cout << "Grepping strings for 'one|two|four'" << std::endl;
  strings | grep("one|two|four") | print;

  std::cout << "Filtering strings without 'o'" << std::endl;
  strings | filter([](std::string a){ return a.find("o") == std::string::npos; }) | print;

  std::cout << "Taking 3 strings" << std::endl;
  strings | take(3) | print;
  
  std::cout << "Head 3 strings" << std::endl;
  strings | head(3) | print;

  std::cout << "First 3 strings" << std::endl;
  strings | first(3) | print;

  std::cout << "Last 3 strings" << std::endl;
  strings | last(3) | print;

  std::cout << "Tail 3 strings" << std::endl;
  strings | tail(3) | print;

  std::cout << "Skipping 2 strings" << std::endl;
  strings | skip(2) | print;

  std::cout << "Dropping 2 strings" << std::endl;
  strings | drop(2) | print;

  std::cout << "Transforming strings to lengths" << std::endl;
  strings | transform([](std::string a) { return a.length(); }) | print;

  std::cout << "Converting strings to lengths" << std::endl;
  strings | convert([](std::string a) { return a.size(); }) | print;

  std::cout << "Joining strings with '.'" << std::endl;
  strings | join(".") | print;

  std::cout << "Splitting strings with '.'" << std::endl;
  strings | join(".") | split(".") | print;
}


void demo2()
{
  // Functions
  auto printer = [](auto x) { std::cout << x << ","; };
  auto newline = []() { std::cout << std::endl; };

  // Input
  std::vector<int> v = {1,2,3,4,5};

  // Normal way
  for (auto i : v)
    printer(i);
  std::cout << std::endl;

  // C++11 functional way
  std::for_each(v.begin(), v.end(), printer);
  std::cout << std::endl;

  // Improved way
  v | printer;
  newline();

  // Best way
  v | print;

  // More interesting options 
  v | reverse | print;
}


//////////
// MAIN //
//////////

int main()
{
  demo1();
  demo2();


  std::stringstream ss;
  auto printer = [](auto x) { std::cout << x << ","; };
  auto newline = []() { std::cout << std::endl; };
  auto odd = [](int x) -> bool { return (x & 1) == 1; };
  auto as_string = [](auto x) -> std::string { return std::to_string(x); };

  
  int v2[] = {1,2,3,4,5};
  v2 | print;

  int v3[]{1,2,3,4,5};
  v3 | print;
  
  auto v4 = to_array<int>({1,2,3,4,5});
  v4 | print;
  
  to_array({1,2,3,4,5}) | print;

  std::string("13,15,66,42,23") | split(",") | join(".") | print;
  "13,15,66,42,23" | split(",") | join(".") | print;
  "13,15,66,42,23" | split(",") | grep("3") | join(".") | print;

  auto sl = "13,15,66,42,23,123" | split(",");
  auto s = sl | join(".");
  std::cout << s << std::endl;
  newline();

  range(10,15) | print;
  
  std::cout << (range(10,15) | transform(as_string) | join(",")) << std::endl;


  for_each(range(10,15), printer);
  newline();
  for_each(reverse_view<range_view<int>>(range(10,15)), printer);
  newline();
  for_each(range(10,14) | reverse | filter(odd), printer);
  newline();

  
  std::vector<int> v = {1,2,3,4,5};
  container_view(v) | print;
  container_view(v) | match(odd) | print;
  container_view(v) | filter(odd) | print;
  container_view(v) | reverse | print;
  container_view(v) | reverse | reverse | print;
  container_view(v) | reverse | reverse | filter(odd) | reverse | reverse | print;
  container_view(v) | reverse | filter(odd) | reverse | print;
  container_view(v) | filter(odd) | reverse | print;
  container_view(v) | reverse | filter(odd) | print;

  
  range(10,14) | reverse | filter(odd) | print;
  range(10,15) | reverse | print;
  range(10,15) | reverse | reverse | print;
  range(10,15) | filter(odd) | print;
  range(10,15) | reverse | filter(odd) | print;
  range(10,15) | reverse | filter(odd) | reverse | print;
  range(10,14) | reverse | filter(odd) | print;
  range(1,101) | reverse | filter(odd) | take(5) | print;
  range(1,101) | reverse | filter(odd) | head(5) | print;
  range(1,101) | reverse | filter(odd) | first(5) | print;
  range(1,101) | reverse | first(5) | reverse | print;
  range(1,101) | last(5) | print;
  range(1,101) | tail(5) | print;
  range(1,6) | print;
  range(1,6) | skip(3) | print;

  auto filt = [](std::string a){ return a == "BAD"; };

  to_array({"five","BAD","four","three","BAD","two","one"}) | reverse | filter(filt) | print;
  to_array({"one","two","three","four","five"}) | reverse | filter([](std::string a){ return a == "two"; }) | print;
}