<file_sep>template <class T>
class stackmin
{
	class Node
	{
	private: 
		T data;
	public:
		Node(T t)
		{
			data = t;			
		}
		T GetData()
		{
			return data;
		}
		Node* next;
	};
private:
	Node* top;
	Node* min;

public:
	stackmin()
	{
		top = nullptr;
		min = nullptr;
	}

	void push(T t)
	{
		Node* p = new Node(t);
		if (p == nullptr)
			throw "No memory!";
		p->next = top;
		top = p;
		if (min == nullptr || t < min->GetData())
			min = p;		
	}

	T pop()
	{
		if (top == nullptr)
			throw "empty stack";

		T tmp = top->GetData();
		Node* tmpptr = top;
		top = top->next;
	
		if (min == tmpptr)
		{  // we need to iterate through the list to find the min
			min = FindMin();
		}

		delete tmpptr;
		return tmp;
	}

	T getMin()
	{
		if (min == nullptr)
			throw "empty stack";

		return min->GetData ();
	}


	Node* FindMin()
	{
		Node* pMin = top;
		Node* tmp = top;
		while (tmp != nullptr)
		{
			if (tmp->GetData() >= pMin->GetData())
			{
				tmp = tmp->next;
			}
			else
			{
				pMin = tmp;
			}
		}

		return pMin;
	}

};<file_sep>#include "stackmin.h"
#include <iostream>
#include <cassert>


const  int testConst = 100;
void main()
{
	stackmin<int> testStack;

	for (int i = 0; i < testConst; ++i)
		testStack.push(i);

	assert (testStack.getMin() == 0);

	for (int i = testConst-1; i >=0; --i)
		assert (testStack.pop() == i);
	
	for (int i = 0; i < testConst; ++i)
		testStack.push(testConst - i);

	for (int i = 1; i < testConst; ++i)
	{
		assert(testStack.getMin() == i);
		assert(testStack.pop() == i);
	}

	std::cout << "End" << std::endl; 

}<file_sep>#include <deque>
#include <vector>


class Animal 
{
public:
	virtual void hello() {};
};

class Dog : public Animal {};

class Cat : public Animal {};


template <class U>
class  Shelter
{
private:
	std::deque<U*> m_animalQueue;

public:
	void enqueue(U* p)
	{
		m_animalQueue.push_back(p);
	}
	U* dequeueAny()
	{
		if (m_animalQueue.empty())
			return nullptr;
		U* p = m_animalQueue.front();
		m_animalQueue.pop_front();
		return p;
	}

	template <class T>  T* dequeue()
	{
		std::vector<U*>  vTmp;
		T* pFound = nullptr;
		while (!m_animalQueue.empty())
		{
			Animal* pAnimal = dequeueAny();
			if (dynamic_cast<T*> (pAnimal) != nullptr)
			{
				pFound = static_cast<T*> (pAnimal);
				break;
			}
			else
				vTmp.push_back(pAnimal);
		}

		for (auto& it = vTmp.rbegin(); it != vTmp.rend(); ++it)
		{
			m_animalQueue.push_front(*it);
		}

		return pFound;
	}
};
<file_sep>#include "AnimalShelter.h"



void Shelter::enqueue(Animal* p)
{
	m_animalQueue.push_back(p);
}


Animal* Shelter::dequeueAny()
{
	if (m_animalQueue.empty()) 
		return nullptr;
	Animal* p = m_animalQueue.front();
	m_animalQueue.pop_front();
	return p;
}






<file_sep>#include <stack>
#include <cassert>
#include <iostream>


void sort(std::stack<int>& st)
{
	std::stack<int> tmpStack;

	while (!st.empty())
	{
		int nTmp = st.top();
		st.pop();

		while (!tmpStack.empty () && tmpStack.top() > nTmp)
		{
			int n = tmpStack.top();
			tmpStack.pop();
			st.push(n);
		}
		tmpStack.push(nTmp);
	}
	
	while (!tmpStack.empty())
	{
		int n = tmpStack.top();
		tmpStack.pop();

		st.push(n);
	}
}


void main()
{
	std::stack<int> stack;

	stack.push(100);
	stack.push(101);
	stack.push(99);
	stack.push(88);
	stack.push(200);


	sort(stack);

	assert(stack.top() == 88);
	stack.pop();
	assert(stack.top() == 99);
	stack.pop();
	assert(stack.top() == 100);
	stack.pop();
	assert(stack.top() == 101);
	stack.pop();
	assert(stack.top() == 200);
	stack.pop();

	std::cout << "End!" << std::endl;

}<file_sep>#pragma once

#include <vector>
#include <stack>

template <class T,std::size_t N>
class StackPlate
{
private: std::vector <std::stack<T>> m_vPlates;

public:
	void push(T t)
	{
		if (m_vPlates.empty())
		{
			std::stack<T> mystack;
			mystack.push(t);
			m_vPlates.push_back(mystack);			
		}
		else
		{
			std::stack<T>& currentStack = m_vPlates[m_vPlates.size() - 1];

			if (currentStack.size() == N)
			{
				std::stack<T> mystack;
				mystack.push(t);
				m_vPlates.push_back(mystack);
			}
			else
			{
				currentStack.push(t);
			}

		}		
		
	}

	T pop()
	{
		if (m_vPlates.empty())
		{
			throw "Empty stack!";
		}
		else
		{
			std::stack<T>& currentStack = m_vPlates[m_vPlates.size() - 1];
			T t = currentStack.top();
			currentStack.pop();

			if (currentStack.empty())
				m_vPlates.pop_back();

			return t;
		}
	}


	T popAt(int index)
	{
		if (m_vPlates.size() < index)
			throw "No such index!";


		std::stack<T>& currentStack = m_vPlates[index];
		T t = currentStack.top();
		currentStack.pop();

		if (currentStack.empty())
			m_vPlates.erase(m_vPlates.begin() + index);

		return t;
	}



	int numOfStack()
	{
		return m_vPlates.size();
	}

};

<file_sep>#include "AnimalShelter.h"
#include <iostream>


void main()
{
	Shelter<Animal> TheShelter;

	Dog one;
	Dog a;
	Cat b;
	Dog c;
	Dog d;

	TheShelter.enqueue(&one);
	TheShelter.enqueue(&a);
	TheShelter.enqueue(&b);
	TheShelter.enqueue(&c);
	TheShelter.enqueue(&d);

	Cat* p = TheShelter.dequeue<Cat>();

	if (p == &b)
	{
		std::cout << "Great!" << std::endl;
	}
	else
	{
		std::cout << "OOPS!" << std::endl;
	}

	Dog* pDog = TheShelter.dequeue<Dog>();
	if (pDog == &one)
	{
		std::cout << "Great!" << std::endl;
	}


	std::cout << "End!" << std::endl;

}<file_sep>#include "StackPlate.h"
#include <iostream>
#include <cassert>


void main()
{
	StackPlate<int, 2> plate;

	for (int i = 0; i < 100; ++i)
	{
		plate.push(i);	
	}

	assert(plate.numOfStack() == 50);
	assert(plate.pop() == 99);
	assert(plate.numOfStack() == 50);
	assert(plate.pop() == 98);
	assert(plate.numOfStack() == 49);

	assert(plate.pop() == 97);
	assert(plate.numOfStack() == 49);

	assert(plate.popAt(0) == 1);
	assert(plate.numOfStack() == 49);


	std::cout << "Test" << std::endl;



}<file_sep>// testrange.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "pch.h"
#include <iostream>
#include <algorithm>



template <class T>
class num_iterator 
{
	T i;

public:

	explicit num_iterator(T position = 0) : i{ position } {}
	T operator*() const { return i; }
	num_iterator& operator++() 
	{
		++i;
		return *this;
	}

	bool operator!=(const num_iterator &other) const 
	{
		return i != other.i;
	}

	bool operator==(const num_iterator &other) const { return !(*this != other); }
};

template <class T>
class num_range
{
	T a;
	T b;

public:
	num_range(T from, T to)
		: a{ from }, b{ to }
	{}
	num_iterator<T> begin() const { return num_iterator<T>{ a }; }
	num_iterator<T> end()   const { return num_iterator<T>{ b }; }
};



namespace std
{
	template <class T>
	struct iterator_traits<num_iterator<T>>
	{
		using iterator_category = std::forward_iterator_tag;
		using value_type = T;
		using difference_type = T;
	};
}


int main()
{
	auto x = num_range<long long> { 1, 100000 };

	long long goal = 10000;
	auto it = std::lower_bound(std::begin(x), std::end(x), goal, [](const auto& item,const long long& goal) {
		auto result = item * item;
		return result < goal;
	});

	std::cout << *it << std::endl;


}
<file_sep>#include "stdafx.h"
#include <optional>
#include <vector>
#include <utility>
#include <array>
#include <string>
#include <iostream>
#include <cassert>





template <class T, int DefaultSize = 1024>
class SampleQueue
{
public:

	SampleQueue(): tailIndex (0),headIndex (0)
	{
	}

	bool push (const T& val)
	{	
		if (isFull())
			return false;
		else
		{
			vStorage[tailIndex++] = val;
			return true;
		}
	}

	std::optional<T> pop()
	{		
		if (isEmpty())
			return std::nullopt;
		else
		{
			auto item = vStorage[headIndex];
			headIndex ++;
			return item;
		}
	}

	std::optional<T> top()
	{
		if (isEmpty())
			return std::nullopt;
		else
			return vStorage[headIndex];
	}

	unsigned int size()
	{
		if (tailIndex > headIndex)
			return tailIndex - headIndex;
		else
			return tailIndex - headIndex + DefaultSize;
	}

	bool isEmpty()
	{
		return headIndex == tailIndex;
	}

	bool isFull()
	{
		return tailIndex == headIndex - 1;
	}

private:
	std::array<T,DefaultSize> vStorage;

	int headIndex;
	int tailIndex;
};

int main()
{
	SampleQueue <std::string> stringQ;


	std::string s1 = "This is a hash table for testing!";
	std::string s2 = "another test";
	std::string s3 = "latest test";

	stringQ.push(s1);
	stringQ.push(s2);
	stringQ.push(s3);

	
	assert(stringQ.size() == 3);
	assert(stringQ.top() == s1);
	assert(stringQ.size() == 3);

	assert(stringQ.pop() == s1);
	assert(stringQ.size() == 2);

	stringQ.pop();
	stringQ.pop();

	assert(stringQ.pop() == std::nullopt);




	return 0;
}
<file_sep>#include "stdafx.h"
#include <optional>
#include <vector>
#include <utility>
#include <array>
#include <string>
#include <iostream>
#include <cassert>





template <class T>
class SampleStack
{
public:
	SampleStack()
	{
		vStorage.reserve(1024);
	}

	void push(const T& val)
	{
		vStorage.push_back(val);
	}

	std::optional<T> pop()
	{
		if (isEmpty())
			return std::nullopt;
		else
		{
			auto item = vStorage[vStorage.size() -1];
			vStorage.pop_back();
			return item;
		}
	}

	std::optional<T> top()
	{
		if (isEmpty())
			return std::nullopt;
		else
			return vStorage[vStorage.size() - 1];
	}

	unsigned int size()
	{
		return vStorage.size();
	}

	bool isEmpty()
	{
		return vStorage.size() == 0;
	}	

private:
	std::vector<T> vStorage;
};

int main()
{
	SampleStack <std::string> stringQ;


	std::string s1 = "This is a hash table for testing!";
	std::string s2 = "another test";
	std::string s3 = "latest test";

	stringQ.push(s1);
	stringQ.push(s2);
	stringQ.push(s3);


	assert(stringQ.size() == 3);
	assert(stringQ.top() == s3);
	assert(stringQ.size() == 3);

	assert(stringQ.pop() == s3);
	assert(stringQ.size() == 2);

	stringQ.pop();
	stringQ.pop();

	assert(stringQ.pop() == std::nullopt);




	return 0;
}
<file_sep>#include "stdafx.h"
#include <optional>
#include <vector>
#include <utility>
#include <array>
#include <string>
#include <iostream>
#include <cassert>
#include <algorithm>


template <class T, class Compare>
class SamplePQueue
{
public:
	SamplePQueue()
	{
		vStorage.reserve(1024);
	}


	SamplePQueue(const std::vector<T>& q)
	{
		vStorage = q;
		std::make_heap(vStorage.begin(), vStorage.end());
	}

	void push(const T& val)
	{
		vStorage.push_back(val);
		std::push_heap(vStorage.begin(), vStorage.end(), func);
	}

	std::optional<T> pop()
	{
		if (isEmpty())
			return std::nullopt;
		else
		{
			std::pop_heap(vStorage.begin(), vStorage.end(),func);
			auto item = vStorage.back();
			vStorage.pop_back();
			return item;
		}
	}

	std::optional<T> top()
	{
		if (isEmpty())
			return std::nullopt;
		else
			return vStorage.front();
	}

	unsigned int size()
	{
		return vStorage.size();
	}

	bool isEmpty()
	{
		return vStorage.size() == 0;
	}

private:
	std::vector<T> vStorage;

	Compare func;
};

template<class T>
struct SampleLess
{
	bool operator()(const T& a, const T& b)
	{ 
		if (a.size() > b.size())
			return true;
		else 
			return false;
	}
};


int main()
{
	//auto anotherLess = [](const std::string& a, const std::string& b)
	//{
	//	if (a.length() >  b.length())
	//		return true;
	//	else
	//		return false;
	//};

	SamplePQueue <std::string, SampleLess<std::string>> stringQ;


	std::string s1 = "This is a hash table for testing!";
	std::string s2 = "I am the third";
	std::string s3 = "first";
	std::string s4 = "The second";

	stringQ.push(s1);
	stringQ.push(s2);
	stringQ.push(s3);
	stringQ.push(s4);


	assert(stringQ.size() == 4);
	assert(stringQ.top() == s3);
	assert(stringQ.size() == 4);

	assert(stringQ.pop() == s3);
	assert(stringQ.size() == 3);

	assert(stringQ.pop() == s4);
	assert(stringQ.pop() == s2);
	assert(stringQ.pop() == s1);

	assert(stringQ.pop() == std::nullopt);



	std::vector<std::string> vTest;
	vTest.push_back(s1);
	vTest.push_back(s2);
	vTest.push_back(s3);
	vTest.push_back(s4);

	SamplePQueue <std::string, SampleLess<std::string>> Q2(vTest);

	assert(Q2.top() == s3);


	return 0;
}
