// librarytools.cpp - demonstrates some C++ standard library tools,
//      specifically: class string, and assorted STL tools.
//      string example is from Nagler, pp. 485-6; STL examples
//      are mostly from Deitel & Deitel, C++ How to Program, 2nd
//      edition, 1998, chapter 20 (abbreviated as D&D below)
// cmc, 8/22/03

/*
    lots of library header files to include, starting with the usual
*/
    #include <iostream>
// class string - which is actually basic_string<char>
    #include <string>
// some STL containers
    #include <vector>
    #include <list>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
// iterators, algorithms and numeric tools
    #include <iterator>
    #include <algorithm>
    #include <numeric>

// fortunately, they all share the same namespace ;-)
    using namespace std;

/*
    some global data to use for various demos
*/
int const integerData[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
double const doubleData[] = { 10.1, 20.2, 30.3, 40.4, 50.5,
                              60.6, 70.7, 80.8 };
int const integerCount = sizeof integerData / sizeof(int),
          doubleCount = sizeof doubleData / sizeof(double);

/*
    demonstration of some string functions - from Nagler pp. 485-6
*/
void stringDemo() {
    void displayString(char const *, string const &); // print utility
    string str1("Typical string");
    displayString("str1", str1);
    str1 += "s";                                  // use operator+=
    displayString("str1 after +=", str1);
    string str2(str1, 8);                         // copy position 8 to end
    displayString("str2", str2);
    str2.append(" are here");                     // use append
    displayString("str2 after append", str2);
    str2.clear();                                 // make str2 empty
    displayString("str2 after clear", str2);
    str2 = str1 + 's';                            // use operators + and =
    displayString("str2", str2);
    str2.swap(str1);                              // swap the strings
    displayString("str2 after swap", str2);
    str2[0] = 't';                                // use mutator operator[]
    displayString("str2 after set 1st char", str2);
    cout << "Enter a new string: ";
    getline(cin, str2);                           // use getline function
    displayString("new str2", str2);
}
void displayString(char const *label, string const &str) {
    char const quote = '\"';
    cout << label << " --> " << quote << str << quote
         << " Length: " << str.length()     // also shows current length
         << ", Capacity: " << str.capacity() << '\n';    // and capacity
}

/*
    demonstrations of some STL containers and related iterators
*/

// demo of vector<typename> - sequence container for random element access
//      also demonstrates ostream_iterator<typename>
// adapted from D&D, Fig. 20.15, pp. 945-6
void vectorDemo() {
    vector<int> v;
    cout << "initial vector size: " << v.size()
         << "\ninitial capacity: " << v.capacity();

    // push some values on the end
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    cout << "\nafter 3 push_back calls - "
         << "\n  size: " << v.size()
         << "\n  capacity: " << v.capacity();

    // use a constant iterator to display the contents
    cout << "\nvector contents: ";
    vector<int>::const_iterator it;
    for (it = v.begin(); it != v.end(); ++it)
        cout << *it << ' ';

    // use a reverse iterator to display the contents in reverse
    cout <<"\nreversed contents: ";
    vector<int>::reverse_iterator rit;
    for (rit = v.rbegin(); rit != v.rend(); ++rit)
        cout << *rit << ' ';

    // create another vector using overloaded ctor for iterators
    // note: pointers into arrays can be used as iterators
    vector<int> v2(integerData, integerData + integerCount);

    // use an ostream_iterator to display the contents
    ostream_iterator<int> output(cout, " ");
    cout << "\ncontents of a new vector: ";
    copy(v2.begin(), v2.end(), output);  // copy one iterator to another

    // access some vector elements
    cout << "\nfirst element: " << v2.front()
         << "\nlast element: " << v2.back();
    v2[0] = 7;                       // set first element to 7
    // v2.at(2) = 10; // should set element at position 2 to 10 - error in g++
    v2[2] = 10;       // so do it with operator[] instead
    v2.insert(v2.begin() + 1, 22);   // insert 22 as new 2nd element
    cout << "\ncontents after some changes: ";
    copy(v2.begin(), v2.end(), output);

    // remove (erase) the first element
    v2.erase(v2.begin());
    cout << "\ncontents after erasing first element: ";
    copy(v2.begin(), v2.end(), output);

    // clear the container
    v2.clear();
    cout << "\ncontents after clear: ";
    copy(v2.begin(), v2.end(), output);
    
    cout << endl;
}

// demo of list<typename> - sequence container featuring quick insert/erase
// adapted from D&D, Fig. 20.17, pp. 949-51
void listDemo() {
    list<int> values, otherValues;

    // push some values at the beginning, then the end of one list
    values.push_front(1);
    values.push_front(2);
    values.push_back(4);
    values.push_back(3);

    // set up output stream iterator and display current list
    ostream_iterator<int> output(cout, " ");
    cout << "values contains: ";
    copy(values.begin(), values.end(), output);

    // insert array into the other list
    otherValues.insert(otherValues.begin(),
                       integerData, integerData + integerCount);
    cout << "\notherValues contains: ";
    copy(otherValues.begin(), otherValues.end(), output);

    // splice the other values on to the end of values list
    values.splice(values.end(), otherValues);
    cout << "\nafter splice, values contains: ";
    copy(values.begin(), values.end(), output);

    // sort values and display again
    values.sort();
    cout << "\nsorted: ";
    copy(values.begin(), values.end(), output);

    // merge the lists into values (leaves otherValues empty)
    values.merge(otherValues);
    cout << "\nafter merge -\n   values: ";
    copy(values.begin(), values.end(), output);
    cout << "\n   otherValues: ";
    copy(otherValues.begin(), otherValues.end(), output);

    // remove a specific value and redisplay
    values.remove(4);
    cout << "\nafter remove(4): ";
    copy(values.begin(), values.end(), output);

    // eliminate duplicates with unique() and redisplay
    values.unique();
    cout << "\nafter unique(): ";
    copy(values.begin(), values.end(), output);

    // pop the front and back elements and redisplay
    values.pop_front();
    values.pop_back();
    cout << "\nafter pop_front and pop_back: ";
    copy(values.begin(), values.end(), output);

    cout << endl;
}

// demo of deque<typename> - sequence container combining features of
//      both a vector and a list (random access and quick insert/erase)
// adapted from D&D, Fig. 20.15, pp. 945-6
void dequeDemo() {
    deque<double> values;
    ostream_iterator<double> output(cout, " ");

    // push values at front and back, and display using operator[]
    values.push_front(2.2);
    values.push_front(3.5);
    values.push_back(1.1);
    cout << "values: ";
    for (unsigned i=0; i<values.size(); i++)
        cout << values[i] << ' ';

    // pop front and redisplay (using ostream iterator)
    values.pop_front();
    cout << "\nafter pop_front(): ";
    copy(values.begin(), values.end(), output);

    // set a value using operator[] and redisplay
    values[1] = 5.4;
    cout << "\nafter changing values[1]: ";
    copy(values.begin(), values.end(), output);

    // insert array of values and redisplay
    values.insert(values.begin(), doubleData, doubleData + doubleCount);
    cout << "\nafter inserting array of values: ";
    copy(values.begin(), values.end(), output);
    
    cout << endl;
}

// demo of stack<typename>, queue<typename>, and priority_queue<typename>
//      - typical stack, queue, and priority queue
//      all are actually "adapters" of underlying sequence containers
// adapted from D&D, Figs. 20.23-20.25, pp. 965, 967, and 969
void stackAndQueuesDemo() {
    stack<double> s;
    queue<double> q;
    priority_queue<double> pq;

    // fill stack and queues with values from same array - use push() for all
    for (int i=0; i<doubleCount; i++) {
        s.push(doubleData[i]);
        q.push(doubleData[i]);
        pq.push(doubleData[i]);
    }
    // also push a couple a couple of values that are not in sorted order
    s.push(35); q.push(35); pq.push(35);
    s.push(5); q.push(5); pq.push(5);

    // use ostream iterator to display array contents
    cout << "pushed these values: ";
    ostream_iterator<double> output(cout, " ");
    copy(doubleData, doubleData + doubleCount, output);
    cout << 35. << ' ' << 5. << endl;

    cout << "popping from stack: ";
    while (!s.empty()) {
        cout << s.top() << ' ';   // top() "peeks" - does not remove
        s.pop();                  // pop() removes element (all 3 containers)
    }
    cout << endl;

    cout << "popping from queue: ";
    while (!q.empty()) {
        cout << q.front() << ' '; // front() peeks
        q.pop();
    }
    cout << endl;

    cout << "popping from priority queue: ";
    while (!pq.empty()) {
        cout << pq.top() << ' ';   // top() peeks
        pq.pop();
    }
    cout << endl;
}

// demo of set<typename, functor> and multiset<typename, functor> -
//      associative containers ("search key" access) where the values are
//      the keys; functor - a comparator function object to specify key order;
//      a set does not allow duplicate values, but a multiset does
// adapted from D&D, Figs. 20.19, p. 956, and 20.20, p. 959
void setDemo() {
    // define types - both will use ascending order
    typedef multiset<int, less<int> > int_multiset;  // a multiset for integers
    typedef set<double, less<double> > double_set;   // a set for doubles

    // create some int and double data to use
    double const ad[] = {2.1, 4.2, 9.5, 2.1, 3.7};
    int const sized = sizeof ad / sizeof(double);
    int const ai[] = {7, 22, 9, 1, 18, 30, 100, 22, 85, 13};
    int const sizei = sizeof ai / sizeof(int);

    // create output iterators
    ostream_iterator<int> outi(cout, " ");
    ostream_iterator<double> outd(cout, " ");

    // fool around with a multiset of integers
    int_multiset intMultiset;

    cout << "count of values equal to 15 in empty multiset: "
         << intMultiset.count(15);
    intMultiset.insert(15);
    intMultiset.insert(15);
    cout << "\ncount after two inserts of 15: " << intMultiset.count(15);

    int_multiset::const_iterator result;
    result = intMultiset.find(15);  // find returns iterator
    if (result != intMultiset.end())
        cout << "\nfound value 15";
    result = intMultiset.find(20);
    if (result == intMultiset.end())
        cout << "\ndid not find 20";

    intMultiset.insert(ai, ai + sizei);  // add array of ints
    cout << "\nmultiset contents after insert array: ";
    copy(intMultiset.begin(), intMultiset.end(), outi);

    cout << "\nlower bound of 22: " << *(intMultiset.lower_bound(22));
    cout << "\nupper bound of 22: " << *(intMultiset.upper_bound(22));

    // the equal_range function returns a pair of iterators (pair is in STL too)
    pair<int_multiset::const_iterator, int_multiset::const_iterator> pims;
    pims = intMultiset.equal_range(22);
    cout << "\nusing equal_range of 22 -"
         << "\n   lower bound: " << *(pims.first)
         << "\n   upper bound: " << *(pims.second);

    // fool around with the set
    double_set doubleSet(ad, ad + sized);      // note: duplicate 2.1 not inserted
    cout << "\n\ninitial set contents: ";
    copy(doubleSet.begin(), doubleSet.end(), outd);

    pair<double_set::const_iterator, bool> pds;
    pds = doubleSet.insert(13.8);  // insert value not in set
    cout << '\n' << *(pds.first)
         << (pds.second ? " was" : " was not") << " inserted";
    pds = doubleSet.insert(9.5);   // try to insert value that is already in set
    cout << '\n' << *(pds.first)
         << (pds.second ? " was" : " was not") << " inserted";
    cout << "\nset contains: ";
    copy(doubleSet.begin(), doubleSet.end(), outd);

    cout << endl;
}

// demo of map<keyT, valueT, functor> and multimap<keyT, valueT, functor> -
//      associative containers ("search key" access) for key/value pairs;
//      functor - a comparator function object to specify key order;
//      a map does not allow duplicate keys, but a multimap does
// adapted from D&D, Figs. 20.21, p. 961, and 20.22, p. 963
void mapDemo() {
    // define types for int-double pairs, both ascending order
    typedef     multimap<int, double, less<int> >       mmid;
    typedef     map<int, double, less<int> >            mid;

    // create some key-value pairs to insert in both containers
    typedef     pair<int, double>   pid;
    pid sampleData[] = {
        pid(15, 2.7), pid(30, 111.11), pid(5, 1010.1), pid(10, 22.22),
        pid(25, 33.333), pid(5, 77.54), pid(20, 9.345), pid(15, 99.3)
    };  // notice two duplicate keys: 5 and 15
    int sizeData = sizeof sampleData / sizeof sampleData[0];

    // play with a multimap first
    mmid multPairs;

    cout << "count of pairs with key equal to 15 in empty multimap: "
         << multPairs.count(15);
    for (int i=0; i<sizeData; i++)
        multPairs.insert(sampleData[i]);
    cout << "\nafter inserts - count of pairs with key equal to 15: "
         << multPairs.count(15);

    cout << "\ncontents of multimap:\nKey\tValue\n";
    for (mmid::const_iterator it = multPairs.begin();
                              it != multPairs.end(); ++it)
        cout << it->first << '\t' << it->second << '\n';

    cout << "\n...enter to continue...";
    char c;
    while ( (c=cin.get()) != '\n' );

    // now play with a map
    mid pairs;
    for (int i=0; i<sizeData; i++)
        pairs.insert(sampleData[i]);  // will ignore duplicate inserts

    cout << "\n\ncontents of map:\nKey\tValue\n";
    for (mid::const_iterator it = pairs.begin(); it != pairs.end(); ++it)
        cout << it->first << '\t' << it->second << '\n';

    pairs[25] = 9999.99;       // change existing value for 25
    pairs[40] = 8765.43;       // insert new value, with key equal to 40
    cout << "\ncontents of map after subscript operations:\nKey\tValue\n";
    for (mid::const_iterator it = pairs.begin(); it != pairs.end(); ++it)
        cout << it->first << '\t' << it->second << '\n';

    cout << endl;
}

/*
    demonstrations of some STL algorithms
*/

// demo of various algorithms to remove and replace container elements
// adapted from D&D, Figs. 20.28, pp. 975-6, and 20.29, pp. 978-9
void removeAndReplace() {
    // use a vector of ints for example
    vector<int> v(integerData, integerData + integerCount);
    ostream_iterator<int> output(cout, " ");
    v.push_back(5);
    v.push_back(5); // added two extra 5s to the vector
    cout << "initial vector contents: ";
    copy(v.begin(), v.end(), output);

    // remove all the 5s
    vector<int>::iterator newLastElement = remove(v.begin(), v.end(), 5);
    cout << "\nvector contents after removing the 5s: ";
    copy(v.begin(), newLastElement, output);

    // copy from array to c, removing any 5s
    vector<int> c(integerCount, 0);  // first fill the copy vector with 0s
    remove_copy(integerData, integerData + integerCount, c.begin(), 5);
    cout << "\nnew copy of array, 5s removed: ";
    copy(c.begin(), c.end(), output);

    // remove elements greater than 6 from copy
    bool greater6(int x); // utility function defined below
    newLastElement = remove_if(c.begin(), c.end(), greater6);
    cout << "\nnew copy after removing values greater than 6: ";
    copy(c.begin(), newLastElement, output);

    // also available: remove_copy_if()

    // make a new copy of the array to start using replace functions
    vector<int> v1(integerData, integerData + integerCount);
    v1.push_back(5);
    v1.push_back(5); // added two extra 5s to the vector
    cout << "\n\nnew initial vector contents: ";
    copy(v1.begin(), v1.end(), output);

    // replace every 5 with 500
    replace(v1.begin(), v1.end(), 5, 500);
    cout << "\ncontents after replacing 5s with 500: ";
    copy(v1.begin(), v1.end(), output);

    // replace values greater than 6 with -12
    replace_if(v1.begin(), v1.end(), greater6, -12);
    cout << "\ncontents after replacing values > 6 with -12: ";
    copy(v1.begin(), v1.end(), output);

    // also available: replace_copy() and replace_copy_if()

    cout << endl;
}
bool greater6(int x) { return x > 6; }

// demo of various mathematical algorithms:
//      random_shuffle, count, count_if, min_element, max_element,
//      accumulate (in <numeric>), for_each, and transform
// adapted from D&D, Fig. 20.30, pp. 981-2
void mathAlgs() {
    vector<int> v(integerData, integerData + integerCount);
    ostream_iterator<int> output(cout, " ");
    
    cout << "initial vector v: ";
    copy(v.begin(), v.end(), output);

    #include <time.h> // to seed the generator for random_shuffle
    srand(time(0));    
    random_shuffle(v.begin(), v.end());
    cout << "\nvector v after random_shuffle: ";
    copy(v.begin(), v.end(), output);

    int a2[] = { 100, 2, 8, 1, 50, 3, 8, 8, 9, 10 };
    int const size = sizeof a2 / sizeof a2[0];
    vector<int> v2(a2, a2 + size);
    cout << "\n\ninitial vector v2: ";
    copy(v2.begin(), v2.end(), output);

    int result = count(v2.begin(), v2.end(), 8);
    cout << "\nnumber of elements in v2 matching 8: " << result;
    result = count_if(v2.begin(), v2.end(), greater6);
    cout << "\nnumber of elements in v2 greater than 6: " << result;

    cout << "\nminimum element in v2: " << *(min_element(v2.begin(), v2.end()));
    cout << "\nmaximum element in v2: " << *(max_element(v2.begin(), v2.end()));
    cout << "\nsum of elements in v2: " << accumulate(v2.begin(), v2.end(), 0);
    
    // declare utility functions (defined below)
    void outputSquare(int);  // used with for_each
    int calculateCube(int);  // used with transform
    
    cout << "\n\nthe square of every value in v is:\n";
    for_each(v.begin(), v.end(), outputSquare);

    vector<int> cubes(integerCount);
    transform(v.begin(), v.end(), cubes.begin(), calculateCube);
    cout << "\n\nThe cube of every value in v is:\n";
    copy(cubes.begin(), cubes.end(), output);

    cout << endl;
}
void outputSquare(int value) { cout << value * value << ' '; }
int calculateCube(int value) { return value * value * value; }

// demo of basic searching and sorting algorithms:
//      find, find_if, sort, and binary_search
// adapted from D&D, Fig 20.31, pp. 985-6
void searchAndSort() {
    int a[] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 };
    int const size = sizeof a / sizeof a[0];
    vector<int> v(a, a + size);
    ostream_iterator<int> output(cout, " ");
    bool greater10(int); // utility function defined below

    cout << "contents of vector v: ";
    copy(v.begin(), v.end(), output);

    vector<int>::iterator location;
    location = find(v.begin(), v.end(), 16);
    if (location != v.end())
        cout << "\nfound 16 at location " << (location - v.begin());
    else
        cout << "\n16 not found";

    location = find_if(v.begin(), v.end(), greater10);
    if (location != v.end())
        cout << "\nfirst value greater than 10 is " << *location
             << " found at location " << (location - v.begin());
    else
        cout << "\nno values greater than 10 were found";

    sort(v.begin(), v.end());
    cout << "\nvector v after sort: ";
    copy(v.begin(), v.end(), output);

    if (binary_search(v.begin(), v.end(), 13))
        cout << "\n13 was found in v";
    else
        cout << "\n13 was not found in v";

    if (binary_search(v.begin(), v.end(), 100))
        cout << "\n100 was found in v";
    else
        cout << "\n100 was not found in v";

    cout << endl;
}
bool greater10(int x) { return x > 10; }

/*
    main lets the user choose the demonstration
*/
int main() {
    struct {
        string name;   // note: string objects used here too
        void (*func)();
    } demos[] = {
        { "string", &stringDemo },
        { "vector", &vectorDemo },
        { "list", &listDemo },
        { "deque", &dequeDemo },
        { "stack and queues", &stackAndQueuesDemo },
        { "set and multiset", &setDemo },
        { "map and multimap", &mapDemo },
        { "remove and replace", &removeAndReplace },
        { "math algorithms", &mathAlgs },
        { "search and sort", &searchAndSort }
    };
    int size = sizeof demos / sizeof demos[0];
                      
    cout << "\nChoice of tools to demonstrate:\n";
    for (int i = 0; i < size; i++)
        cout << "  " << i + 1 << ". " << demos[i].name << '\n';

    int choice;
    cout << "Enter choice number --> ";
    cin >> choice;
    cout << '\n';
    if (cin.good() && choice > 0 && choice <= size) {
        // first discard rest of input line in case demo needs user input
        int c;
        while ((c = cin.get()) != '\n')
            ;
        // then invoke the chosen function
        demos[choice-1].func();
    }
    else
        cerr << "bad choice\n";
}