// usesetalgs.cpp
// Glenn G. Chappell
// 2 Dec 2009
// 
// For CS 311 Fall 2009
// Example using set algorithms and "exotic" iterators

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <set>
using std::set;
#include <algorithm>
using std::set_intersection;
using std::copy;
#include <iterator>
using std::inserter;
using std::ostream_iterator;


// printEvenFibos
// Prints all even Fibonacci numbers in [0, limit].
// Uses sets, set algorithms, inserters, and ostream iterators.
// Pre:
//     limit is less than the greatest Fibonacci number
//      representable as an int.
// Post:
//     All numbers in [0, limit] that are even Fibonacci numbers,
//      have been printed to cout, with a separator/terminator
//      of " ".
// May throw std::bad_alloc on out-of-memory
// Strong Guarantee
//
// NOTE: This code is merely an illustration of how to use
//  various STL components. This is NOT the best way to do the
//  computation. In particular, this function requires O(n log n)
//  steps, where n = limit, and O(n) space (both primarily for
//  the computation of evenSet), while the obvious loop uses only
//  O(log n) steps and O(1) space.
//
void printEvenFibos(int limit)
{
    // fiboSet is set of Fibonacci numbers in [0, limit].
    set<int> fiboSet;
    int prev = 1;
    int curr = 0;
    while (curr <= limit)
    {
        fiboSet.insert(curr);
        int next = prev + curr;
        prev = curr;
        curr = next;
    }

    // evenSet is set of even integers in [0, limit].
    set<int> evenSet;
    int i = 0;
    for (int i = 0; i <= limit; i += 2)
    {
        evenSet.insert(i);
    }

    // resultSet is intersection of fiboSet and evenSet,
    //  that is, the set of all even Fibonacci numbers in [0, limit].
    set<int> resultSet;
    set_intersection(fiboSet.begin(), fiboSet.end(),
                     evenSet.begin(), evenSet.end(),
                     inserter(resultSet, resultSet.begin()));

    // Print the items in resultSet
    copy(resultSet.begin(), resultSet.end(),
              ostream_iterator<int>(cout, " "));
    cout << endl;
}


int main()
{
    const int limit = 10000;  // We print even Fibos in [0, limit]
    cout << "All even Fibonacci numbers in ";
    cout << "[0, " << limit << "]:" << endl;
    printEvenFibos(limit);
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}