/////////////////////////////////////////////////////////////////////////
// Invalid_Iterators.cpp - Iterators into contiguous containters bite  //
//                                                                     //
// Jim Fawcett, CSE687 - Object Oriented Programming, Spring 2014      //
/////////////////////////////////////////////////////////////////////////

#include <vector>
#include <iostream>
#include <algorithm>

template <typename Cont>
void showCont(Cont& cont)
{
  std::cout << "\n  ";
  bool first = true;
  for (auto item : cont)
  {
    if (!first) { 
      std::cout << ", " << item; 
    }
    else
    {
      first = false;
      std::cout << item;
    }
  }
}

int main()
{
  std::cout << "\n  Demonstrating that Iterators into contiguous containers Bite";
  std::cout << "\n ==============================================================\n";

  using Collection = std::vector<int>;
  using Iterator = Collection::iterator;
  Collection coll { 5, 1, 0, -1, 0, 3, 0, 0, -4, 0 };
  Collection master = coll;
  showCont(coll);

  // attempt to remove all elements with value "0"

  // first attempt
  // Iterator iter;
  // for (iter = begin(coll); iter != end(coll); ++iter)
  // {
  //   if (*iter == 0)
  //     coll.erase(iter);  // error here because erase invalidates iter
  // }                      // debug build asserts, release build silently stops
  std::cout << "\n  Ooooppphs - uncomment to get assert!";

  // second attempt
  // coll = master;
  // Iterator iter, tempIt;
  // for (iter = begin(coll); iter != end(coll); ++iter)
  // {
  //   tempIt = iter;
  //   if (*tempIt == 0)
  //     coll.erase(tempIt);  // error here because erase invalidates every
  // }                        // interator into the vector (at and above the erase)
  std::cout << "\n  Ooooppphs - uncomment to get another assert!";

  // third attempt
  coll = master;
  Iterator iter = begin(coll);
  while (iter != end(coll))
  {
    if (*iter == 0)
      iter = coll.erase(iter);  // this works but isn't very efficient
    else                        // because each erase ripples higher
      ++iter;                   // elements down by one => n*n complexity
  }
  showCont(coll);
  std::cout << "\n  Ooooppphs - works but turned order n into order n*n!";

  // fourth attempt
  coll = master;
  Iterator dest = begin(coll), src;
  for (src = begin(coll); src != end(coll); ++src)
  {
    if (*src != 0)
      *dest++ = *src;             // works with order n removal
  }
  coll.erase(dest, end(coll));    // truncate to valid items
  showCont(coll);
  std::cout << "\n  OK - efficient but that took three attempts!";

  // fifth attempt
  coll = master;
  Iterator junk_start;
  junk_start = std::remove(begin(coll), end(coll), 0);  // compresses, doesn't remove anything
  coll.erase(junk_start, end(coll));                    // uses algorithm to do what fourth attempt does
  showCont(coll);
  std::cout << "\n  STL algorithm to the rescue!";

  std::cout << "\n\n";
}