#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
using namespace std;

template<typename T>
struct ISort{
	/* oh god these diagrams suck level */
	virtual vector<T> sort(T *, size_t) const = 0;
};

template<typename T>
struct BubbleSortAsc: ISort<T>{
	virtual vector<T> sort(T *array, size_t size) const override{
		vector<T> vec(array, array+size);
		for(auto i = vec.begin(); i != vec.end(); ++i)
			for(auto j = vec.begin(); j < i; ++j)
				if(*i > *i)
					iter_swap(i, j);
		return vec;
	}
};

template<typename T>
struct BubbleSortDesc: ISort<T>{
	virtual vector<T> sort(T *array, size_t size) const override{
		vector<T> vec(array, array+size);
		for(auto i = vec.begin(); i != vec.end(); ++i)
			for(auto j = vec.begin(); j < i; ++j)
				if(*i < *i)
					iter_swap(i, j);
		return vec;
	}
};

/* second parameter is not in the diagram, but it should be there */
template<typename T, typename TSort>
class Collection{
public:
	Collection(const TSort &sort): _sort(sort){}
	/* hell no level of diagram */
	virtual void push(T) = 0; 
	/* should be named "pop" */
	virtual T peek() = 0;
	/* should be named just "sort" */
	void sortCollection(){
		_data = _sort.sort(_data.data(), _data.size());
	}
private:
	vector<T> _data;
	const TSort &_sort;
protected:
	vector<T> &data(){ return _data; }
};

template<typename T, typename TSort>
class LIFO: public Collection<T, TSort>{
	using Collection<T, TSort>::data;
public:
	LIFO(const TSort &sort): Collection<T, TSort>(sort){}
	virtual void push(T element) override{
		data().push_back(element);
	}
	virtual T peek() override{
		auto result = data().front();
		data().erase(data().begin());
		return result;
	}
};

template<typename T, typename TSort>
class FIFO: public Collection<T, TSort>{
	using Collection<T, TSort>::data;
public:
	FIFO(const TSort &sort): Collection<T, TSort>(sort){}
	virtual void push(T element) override{
		data().insert(data().begin(), element);
	}
	virtual T peek() override{
		auto result = data().front();
		data().erase(data().begin());
		return result;
	}
};


int main(){
	BubbleSortDesc<double> bsDesc;
	FIFO<double, BubbleSortDesc<double>> fifo(bsDesc);
	
	fifo.push(1.3);
	fifo.push(1.2);
	fifo.push(1.1);
	cout << std::fixed << fifo.peek() << " " << fifo.peek() << " " << fifo.peek() << endl;
	
	fifo.push(1.1);
	fifo.push(1.3);
	fifo.push(1.2);
	fifo.sortCollection();
	cout << std::fixed << fifo.peek() << " " << fifo.peek() << " " << fifo.peek() << endl;
	
	BubbleSortAsc<int> bsAsc;
	LIFO<int, BubbleSortAsc<int>> lifo(bsAsc);
	
	lifo.push(3);
	lifo.push(2);
	lifo.push(1);
	cout << std::fixed << lifo.peek() << " " << lifo.peek() << " " << lifo.peek() << endl;
	
	lifo.push(1);
	lifo.push(3);
	lifo.push(2);
	lifo.sortCollection();
	cout << std::fixed << lifo.peek() << " " << lifo.peek() << " " << lifo.peek() << endl;
	
	return 0;
}