// Demonstrating use of multiset STL template


#include <multiset.h>
#include <list.h>
#include <algo.h>
#include <string>

// when the STL types get complicated, typedef them
// and use the typedef names where you need them

typedef multiset<int, less<int> > integer_multiset;
typedef multiset<int, less<int> >::iterator integer_multiset_ptr;

void show_int (int i)
{
  cout << i << " " ;
}

void display_collection (const integer_multiset &d, string title)
{
  cout << title << ": { ";
  for_each(d.begin(), d.end(), show_int);
  cout << "}" << endl;
}

void display_collection (const list<int> &d, string title)
{
  cout << title << ": [ ";
  for_each(d.begin(), d.end(), show_int);
  cout << "]" << endl;
}


int main()
{
  cout << "Demonstrating How MultiSets Work." << endl;

  list<int> list2;
  integer_multiset multiset1;

  // populating the list using "push_back"
  list2.push_back(89);
  list2.push_back(99);
  list2.push_back(89);
  list2.push_back(49);  
  list2.push_back(69);
  list2.push_back(59);
  list2.push_back(89);
  list2.push_back(89);
  list2.push_back(49);  

  // list can have duplicates
  display_collection(list2, "List 2");

  list<int>::iterator lp;

  // insert values from list2 into multiset1
  // multi set ALSO can have duplicated as you can see
  // in the output
  for (lp = list2.begin(); lp != list2.end(); lp++)
    multiset1.insert(*lp);

  display_collection(multiset1, "Multiset 1");

  cout << "Count of numbers > 50 is: " << 
    count_if(multiset1.begin(), multiset1.end(), 
	     bind2nd(greater<int>(), 50)) << endl;

  // because of duplicates, it can be more complicated to
  // operate with multisets

  if (multiset1.find(89) != multiset1.end())
    cout << "89 is in the multiset!!" << endl;
  else
    cout << "89 is NOT in the multiset!!" << endl;

  // use generic find algorithm to accomplish the same goals
  if (find(multiset1.begin(), multiset1.end(), 123) != multiset1.end())
    cout << "123 is in the multiset!!" << endl;
  else
    cout << "123 is NOT in the multiset!!" << endl;

  // removing items...
  multiset1.erase(49);
  cout << "After erase: ";
  if (multiset1.find(49) != multiset1.end())
    cout << "49 is in the multiset!!" << endl;
  else
    cout << "49 is NOT in the multiset!!" << endl;

  // looping for ALL the 89's:
  // position at the first 89
  cout << "Count of number of 89's in the multiset: " <<
    multiset1.count(89) << endl;
  integer_multiset_ptr mp1 = multiset1.lower_bound(89);
  integer_multiset_ptr mp2 = multiset1.upper_bound(89);

  if (mp1 != multiset1.end())
    cout << "Lower bound of 89 points to: " << *mp1 << endl;
  else
    cout << "Lower bound of 89: undefined " << endl;

  if (mp2 != multiset1.end())
    cout << "Upper bound of 89 points to: " << *mp2 << endl;
  else
    cout << "Upper bound of 89: undefined " << endl;

  cout << "Show the contents between lb and ub: " ;
  for_each(mp1, mp2, show_int);
  cout << endl;


}