template <typename T>
class Array
{
public:
Array(const size_t capasity) : _size(0), _capacity(capasity) {}
virtual ~Array() = default;
int Size() const { return _size; }
bool IsEmpty() const { return _size == 0; }
virtual void Pop() = 0;
protected:
size_t _size, _capacity;
virtual void Resize(const int size) = 0;
};
template <typename T>
class IContainer
{
protected:
virtual void Add(const T& item, const unsigned priority = 0) = 0;
virtual void Remove() = 0;
virtual const T& Show(const bool isFront = true) = 0;
virtual bool IsContainerEmpty() const = 0;
friend class Menu;
template<typename Type>
friend void UseQueue(IContainer<Type>& container);
};
template <typename T>
class Queue: public Array<T> , public IContainer<T>
{
public:
Queue() : Array<T>(4), _data(new T[_capacity]), _firstItemShift(0) {}
~Queue() { delete[] _data; }
void Push(const T& item)
{
int size = _size + 1;
if (size > _capacity) Resize(_size);
_data[_size] = item;
_size = size;
}
void Pop() override
{
if (_size - 1 >= 0)
{
_size--;
_firstItemShift++;
}
}
T& Front() const { return _data[_firstItemShift]; }
T& Back() const { return _data[_size - 1]; }
private:
void Resize(const int size) override
{
_capacity *= 1.5;
auto data = new T[_capacity];
for (auto i = 0; i < size; i++)
data[i] = _data[i + _firstItemShift];
delete[] _data;
_data = data;
}
//IContainer interface
void Add(const T& item, const unsigned priority = 0) override { Push(item); }
void Remove() override { Pop(); }
const T& Show(const bool isFront = true) override { return isFront ? Front() : Back(); }
bool IsContainerEmpty() const override { return Array<T>::IsEmpty(); }
using Array<T>::_size;
using Array<T>::_capacity;
T* _data;
int _firstItemShift = 0;
};
template <typename T>
class PriorityQueue : public Array<T>, public IContainer<T>
{
public:
PriorityQueue() : Array<T>(1), _node(new Node[_capacity]), _level(0) {}
~PriorityQueue() { delete[] _node; }
struct Node
{
T Data;
uint32_t Priority;
Node() :Data(T{}), Priority(uint32_t{}) {}
Node(const T& data, const unsigned int priority) :Data(data), Priority(priority) {}
bool operator>(const Node& other)
{
return Priority > other.Priority;
}
bool operator<(const Node& other)
{
return Priority < other.Priority;
}
};
void Push(const T& item, const int priority)
{
int size = _size + 1;
auto node = Node(item, priority);
if (size > _capacity)
{
_level++;
_capacity += 1 << _level;
Resize(_size);
}
if (size > 1) SiftUp(node);
else if (size == 1) _node[_size] = node;
_size = size;
}
void Pop() override
{
_size--;
if (_size == 0) return;
int size = _size;
if (size < _capacity - (1 << _level))
{
_capacity -= 1 << _level;
_level--;
Resize(_size + 1);
}
auto node = _node[0];
_node[0] = _node[_size];
_node[_size] = node;
if (_size > 1) SiftDown();
}
T& Top() { return _node[0].Data; }
private:
const auto TopPriority() { return _node[0].Priority; }
void Resize(int size) override
{
auto node = new Node[_capacity];
for (auto i = 0; i < size; i++)
node[i] = _node[i];
delete[] _node;
_node = node;
}
void SiftUp(Node& node)
{
int parent;
_node[_size] = node;
for (auto position = _size; position > 0; position = parent)
{
parent = position % 2 == 0 ? (position - 2) / 2 : (position - 1) / 2;
if (Node tempNode;_node[position] > _node[parent])
{
tempNode = _node[position];
_node[position] = _node[parent];
_node[parent] = tempNode;
}
else return;
}
}
void SiftDown()
{
int child, left, right, lastNode = _size % 2 == 0 ? (_size - 1) / 2 : (_size - 2) / 2;
auto TryChangePriority = [this](int child, int parent)
{
if (auto node = Node(); _node[child] > _node[parent])
{
node = _node[child];
_node[child] = _node[parent];
_node[parent] = node;
return true;
}
else return false;
};
for (auto parent = 0; parent < lastNode; parent = child)
{
left = 1 + parent * 2;
right = left + 1;
child = _node[left] > _node[right] ? left : right;
if(!TryChangePriority(child,parent)) return;
}
left = 1 + lastNode * 2;
right = left + 1;
child = _size - right == 0 ? left : _node[left] > _node[right] ? left : right;
TryChangePriority(child, lastNode);
}
//IContainer interface
void Add(const T& item, const unsigned priority = 0) override { Push(item, priority); }
void Remove() override { Pop(); }
const T& Show(const bool isFront = true) override { std::cout << TopPriority() << " "; return Top(); }
bool IsContainerEmpty() const override { return Array<T>::IsEmpty(); }
using Array<T>::_size;
using Array<T>::_capacity;
Node* _node;
int _level;
};
struct Processor
{
Processor(std::string _name = "", double _clockFrequecny = 0, int _coreAmount = 0) :
Name(_name), ClockFrequecny(_clockFrequecny), CoreAmount(_coreAmount) {}
void GenerateRandom()
{
auto random = Random();
int randomValue = random.GenerateNumber(1, 15);
Name = "AMD Ryzen " + std::to_string(random.GenerateNumber(1, 9));
ClockFrequecny = 3 + (double)(random.GenerateNumber(1, 100)) / 100;
CoreAmount = randomValue % 2 == 0 ? randomValue : randomValue + 1;
}
friend std::ostream& operator<<(std::ostream& os, const Processor& processor)
{
os << processor.Name << ": " << processor.ClockFrequecny <<
" Hz " << processor.CoreAmount << " Cores " << std::endl;
return os;
}
std::string Name;
double ClockFrequecny;
unsigned int CoreAmount;
};
class Menu
{
public:
void Show()
{
enum Status { Disable, Enable };
enum Mode { QueueMode = 1, PriorityQueueMode = 2, Exit = 3 };
int mode;
bool menuAvailable = Enable;
while (menuAvailable)
{
std::system("cls");
std::cout << "Выберете режим работы:\n1.Очередь\n2.Очередь с приоритетом.\n3.Выйти\n";
std::cin >> mode;
switch (mode)
{
case QueueMode:
{
UseContainer(new Queue<Processor>());
break;
}
case PriorityQueueMode:
{
UseContainer(new PriorityQueue<Processor>());
break;
}
case Exit:
{
menuAvailable = Disable;
break;
}
default: break;
}
}
}
private:
void UseContainer(IContainer<Processor>* items)
{
auto random = Random();
auto item = Processor();
int itemsAmount = random.GenerateNumber(5, 10);
std::system("cls");
for (auto i = 0; i < itemsAmount; i++)
{
item.GenerateRandom();
items->Add(item, i + 1);
std::cout << items->Show(false);
}
std::cout << std::endl;
while (!items->IsContainerEmpty())
{
std::cout << items->Show();
items->Remove();
}
std::cout << "\nОчередь пуста!\n";
delete items;
std::system("Pause");
}
};
class Random
{
public:
int GenerateNumber(int min, int max)
{
std::random_device device;
auto range = std::uniform_int_distribution<int>(min, max);
return range(device);
}
private:
};
