#include <iostream>
using namespace std;
// шаблонный класс, описывающий узел списка
template <typename KeyType>
class ListNode
{
public:
ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };
KeyType& getKey() { return mKey; };
ListNode* getNext() { return mNext; };
void setNext( ListNode* node ) { mNext = node; };
protected:
KeyType mKey;
ListNode *mNext;
};
// шаблонный класс, описывающий список
template <typename KeyType, typename ListNodeType>
class List
{
public:
List() { mHead = NULL; };
virtual ~List() { clear(); };
void clear();
bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );
bool remove( KeyType& key );
void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };
bool pop( KeyType& key );
ListNodeType* getHead() { return mHead; };
bool isEmpty() { return mHead == NULL; };
protected:
ListNodeType* mHead;
};
// очищает все элементы списка и высвобождает память
template <typename KeyType, typename ListNodeType>
void List<KeyType,ListNodeType>::clear()
{
ListNodeType *n = mHead;
while( NULL != n )
{
ListNodeType *prev = n;
n = n->getNext();
delete prev;
}
mHead = NULL;
};
// находит узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )
{
ListNodeType *n = mHead;
ListNodeType *prev = NULL;
while( NULL != n )
{
if ( n->getKey() == key )
{
foundNode = n;
foundPrevNode = prev;
return true;
}
prev = n;
n = n->getNext();
}
return false;
}
// удаляет узел списка по ключу
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::remove( KeyType& key )
{
ListNodeType *n = NULL;
ListNodeType *prev = NULL;
if ( find( key, n, prev ) )
{
if ( NULL != prev )
{
prev->setNext( n->getNext() );
}
else
{
mHead = n->getNext();
}
delete n;
return true;
}
return false;
};
// удаляет первый элемент
template <typename KeyType, typename ListNodeType>
bool List<KeyType,ListNodeType>::pop( KeyType& key )
{
if ( mHead != NULL )
{
key = mHead->getKey();
ListNodeType* n = mHead;
mHead = n->getNext();
delete n;
return true;
}
return false;
};
// Шаблонный класс, описывающий узел дерева двоичного поиска
template <typename KeyType, typename ValueType>
class TreeNode {
public:
TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};
TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};
~TreeNode() { };
void setLeft( TreeNode* left ) { mLeft = left; };
void setRight( TreeNode* right ) { mRight = right; };
void setParent( TreeNode* parent ) { mParent = parent; };
KeyType getKey() { return mKey; };
ValueType& getValue() { return mValue; };
void setValue( ValueType& value ) { mValue = value; };
TreeNode* getLeft() { return mLeft; };
TreeNode* getRight() { return mRight; };
TreeNode* getParent() { return mParent; };
virtual string getValueAsText() { return ""; };
protected:
KeyType mKey;
ValueType mValue;
TreeNode* mParent;
TreeNode* mLeft;
TreeNode* mRight;
};
// шаблонный класс, описывающий дерево
template <typename KeyType, typename NodeType>
class Tree {
NodeType* mRoot;
public:
Tree() { mRoot = NULL; };
~Tree() { clear(); };
void clear() { dispose( mRoot ); mRoot = NULL; };
bool isEmpty() { return mRoot == NULL; };
NodeType* getRoot() { return mRoot; };
NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );
void exclude( NodeType* node );
void remove( NodeType* node ) { exclude( node ); dispose( node ); };
bool remove( KeyType& key, NodeType* removedNodeCopy );
bool remove( KeyType& key ) { return( key, NULL ); };
NodeType* findMax( NodeType* node );
NodeType* findMax() { return findMax( mRoot ); };
protected:
void dispose( NodeType* node );
};
// находит узел двоичного дерева по ключу или всталяет, если не найдено
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )
{
enum EInsertAction
{
eNONE,
eROOT,
eLEFT,
eRIGHT
};
EInsertAction doInsert = eNONE;
NodeType *p = mRoot;
if ( p != NULL )
{
for(;;)
{
if ( key < p->getKey() )
{
if ( p->getLeft() != NULL )
{
p = p->getLeft();
}
else
{
doInsert = eLEFT;
break;
}
}
else
if ( key > p->getKey() )
{
if ( p->getRight() != NULL )
{
p = p->getRight();
}
else
{
doInsert = eRIGHT;
break;
}
}
else
{
return p;
}
}
}
else
{
doInsert = eROOT;
}
if ( doInsert != eNONE && insertIfAbsent )
{
NodeType* q = new NodeType( key );
switch( doInsert )
{
case eLEFT : p->setLeft( q ); break;
case eRIGHT: p->setRight( q ); break;
case eROOT : mRoot = q; break;
default: break;
}
q->setParent( p );
return q;
}
return NULL;
}
// находит узел двоичного дерева с максимальным значением ключа
template <typename KeyType, typename NodeType>
NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )
{
if ( node != NULL )
{
NodeType* n = node;
while( NULL != n->getRight() )
{
n = n->getRight();
}
return n;
}
return NULL;
}
// исключает узел двоичного дерева из дерева, не удаляя
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::exclude( NodeType* node )
{
if ( NULL != node )
{
NodeType* successor = NULL;
if ( node->getLeft() == NULL )
{
successor = node->getRight();
}
else
if ( node->getRight() == NULL )
{
successor = node->getLeft();
}
else
{
successor = node->getRight();
NodeType* left = successor->getLeft();
while( left != NULL )
{
successor = left;
left = successor->getLeft();
}
if ( successor->getParent() != node )
{
NodeType* right = successor->getRight();
successor->getParent()->setLeft( right );
if ( NULL != right)
{
successor->getRight()->setParent( successor->getParent() );
}
successor->setRight( node->getRight() );
node->getRight()->setParent( successor );
}
successor->setLeft( node->getLeft() );
node->getLeft()->setParent( successor );
}
if ( node->getParent() == NULL )
{
mRoot = successor;
}
else
if ( node->getParent()->getLeft() == node )
{
node->getParent()->setLeft( successor );
}
else
if ( node->getParent()->getRight() == node )
{
node->getParent()->setRight( successor );
}
else
{
cout << "fatal error: orphaned# "
<< "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()
<< endl;
return;
}
if ( NULL != successor )
{
successor->setParent( node->getParent() );
}
node->setParent( NULL );
node->setLeft( NULL );
node->setRight( NULL );
}
}
// находит и удаляет узел дерева по ключу
template <typename KeyType, typename NodeType>
bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )
{
NodeType* node = findOrInsert( key, false );
if ( node != NULL )
{
exclude( node );
if ( removedNodeCopy != NULL )
{
*removedNodeCopy = node;
}
dispose( node );
return true;
}
return false;
}
// удаляет узел из памяти
template <typename KeyType, typename NodeType>
void Tree<KeyType,NodeType>::dispose( NodeType* node )
{
if ( node != NULL )
{
dispose( node->getLeft() );
dispose( node->getRight() );
delete node;
}
}
// класы-контейнеры на основе высше описанных шаблонных классов
class PrioTreeNode;
typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;
class IdTreeNode : public IdTreeNodeBase
{
public:
IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};
virtual ~IdTreeNode() { mValue = NULL; };
IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };
IdTreeNode* getRight() { return (IdTreeNode*)mRight; };
IdTreeNode* getParent() { return (IdTreeNode*)mParent; };
};
typedef Tree<string,IdTreeNode> IdTree;
typedef ListNode<IdTreeNode*> IdListNode;
typedef List<IdTreeNode*,IdListNode> IdList;
typedef TreeNode<int,IdList*> PrioTreeNodeBase;
class PrioTreeNode : public PrioTreeNodeBase
{
public:
PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };
virtual ~PrioTreeNode() { delete mValue; };
PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };
PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };
PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };
};
typedef Tree<int,PrioTreeNode> PrioTree;
// класс, реализующий очередь с приоритетами
class PrioQueue
{
public:
PrioQueue() { }
~PrioQueue() { }
bool add( string& id, int prio );
bool pop( string& id, int& prio );
bool change( string& id, int prio );
void clear();
private:
IdTree mIdTree;
PrioTree mPrioTree;
};
bool PrioQueue::add( string& id, int prio )
{
IdTreeNode *idNode = mIdTree.findOrInsert( id, true );
if ( NULL != idNode )
{
PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );
if ( NULL != prioNode )
{
prioNode->getValue()->push( idNode );
idNode->setValue( prioNode );
return true;
}
}
return false;
}
bool PrioQueue::pop( string& id, int& prio )
{
bool result = false;
PrioTreeNode* prioNode = mPrioTree.findMax();
if ( NULL != prioNode )
{
prio = prioNode->getKey();
if ( ! prioNode->getValue()->isEmpty() )
{
IdTreeNode* idNode;
if ( prioNode->getValue()->pop( idNode ) )
{
id = idNode->getKey();
mIdTree.remove( idNode );
if ( prioNode->getValue()->isEmpty() )
{
mPrioTree.remove( prioNode );
}
result = true;
}
}
}
return result;
}
bool PrioQueue::change( string& id, int prio )
{
bool result = false;
IdTreeNode* idNode = mIdTree.findOrInsert( id, false );
if ( NULL != idNode )
{
PrioTreeNode* oldPrioNode = idNode->getValue();
(void)oldPrioNode->getValue()->remove( idNode );
if ( oldPrioNode->getValue()->isEmpty() )
{
mPrioTree.remove( oldPrioNode );
}
PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );
idNode->setValue( newPrioNode );
newPrioNode->getValue()->push( idNode );
result = true;
}
return result;
}
void PrioQueue::clear()
{
mIdTree.clear();
mPrioTree.clear();
}
int main( int argc, char** argv )
{
PrioQueue q;
string command;
string id;
int prio;
while ( cin >> command )
{
if ( command.compare( 0, 1, "#" ) == 0 ) continue;
else
if ( command == "add" || command == "ADD" )
{
cin >> id;
cin >> prio;
q.add( id, prio );
}
else
if ( command == "change" || command == "CHANGE" )
{
cin >> id;
cin >> prio;
q.change( id, prio );
}
else
if ( command == "pop" || command == "POP" )
{
if ( q.pop( id, prio ) )
{
cout << id << " " << prio << endl;
}
else
{
cout << "error" << endl;
}
}
else
if ( command == "clear" || command == "CLEAR" )
{
q.clear();
}
else
if ( command == "exit" || command == "EXIT" )
{
cout << "bye" << endl;
return 0;
}
}
return 0;
}
