//============================================================================
// Name        : hash_multiset.cpp
// Author      : Kamil Halicki H6ISI
// Version     : 1.0
// Copyright   :
// Description : Demonstracja kontenera hash_multiset
//============================================================================

/* hash_multiset czyli wielozbiór haszujący jest to kontener umożliwiający przechowywanie elementów które nie muszą być unikatowe 
 *  oraz zapewniający szybkie wyszukiwanie i zliczanie elementów  
 **/ 


#include <iostream>
#include <sstream>
#include <cstring>

/* hash_multiset nie jest wchodzi w skład standardu c++ a jest rozszerzeniem dodanym przez sgi
 * dlatego w różnych kompilatorach może być zdefiniowany w innym pliku nagłówkowym i innej przestrzeni nazw.
 */
#include <ext/hash_set>


using namespace std;



/* W implementacji g++ hash_multiset zdefiniowany jest w przestrzeni nazw __gnu_cxx */
using __gnu_cxx::hash_multiset;
using __gnu_cxx::hash;



/* Implementacja g++ nie zawiera funkcji haszującej dla typu string ale możemy w łatwy sposób rozszerzyć bibliotekę */
namespace __gnu_cxx {

/* Definiujemy specjalizację szablonu hash dla typu string */
template<>
    struct hash<string>
    {
      size_t
      operator()(const string &__s) const
      { return __stl_hash_string(__s.c_str()); }  // wykorzystujemy funkcję obliczającą hash dla typu const char *
 };
}


/* definiuję nowy typ dla wielozbioru łańcuchów znaków dzięki czemu skraca się zapis i w łatwy sposób można zmienić np. funkcję haszującą */
typedef hash_multiset<string> strset;



/* Funkcja wypisuje na ekran ile razy słowo what pojawia się w wielozbiorze set */
void ile(const strset& set, const char * what) {
	cout << what << ": " ;

	/* count zwraca liczbę elementów o podanym kluczu
	 * what jest typu const char * tak więć tworzę tymczasowy obiekt string inicjowany wartością what
	 */
	cout << set.count(string(what)) << endl;
}

int main() {

	cout << "Hash MultiSet" << endl;


	stringstream lyrics;

	/* To jest tekst którego poszczególne wyrazy będą dodawane do wielozbioru */
	lyrics <<  "and in the sea there is a fish \
				a fish that has a secret wish \
				a wish to be a big cactus \
				with a pink flower on it";



	/* Tutaj tworzony jest nowy obiekt wielozbioru haszowanego */
	strset words;

	/* Obiekt word przechowuje aktualnie przetwarzane słowo */
	string word;

	cout << endl << "Kolejność dodawania: " << endl ;

	while( lyrics.eof() == false ) {
		/* operator strumienniowy przekazuje poszczególne wyrazy do obiektu word */
		lyrics >> word;


		cout << word << ", ";

		/* W tym miejscu dodajemy słowa do zbioru. Wewnątrz kontenera zostanie utworzona kopia obiektu word. */
		words.insert(word);
	}

	cout << endl;
	cout << endl << "Kolejność iterowania" << endl;

	/* Do iterowania po kolekcji wykorzystujemy stały iterator i pierwszy element pobieramy za pomocą metody begin() */
	strset::const_iterator iter = words.begin();

	/* Iterując sprawdzamy czy nie osiągnięty został koniec kolekcji */
	while( iter != words.end() ) {

		cout << *iter << ", ";

		/* Iterator wskazuje na następny element w kontenerze */
		++iter;
	}
    cout << endl;

    cout << endl << "Liczba wystąpień:" << endl;

    /* Funkcja ile wyświetla ile razy dane słowo znajduje się w wielozbiorze */
	ile(words, "fish");
	ile(words, "big");
	ile(words, "wish");
	ile(words, "a");

	return 0;
}