fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // шаблонный класс, описывающий узел списка
  6.  
  7. template <typename KeyType>
  8. class ListNode
  9. {
  10. public:
  11. 	ListNode( KeyType& key, ListNode* next ) { mKey = key; mNext = next; };
  12. 	KeyType& getKey() { return mKey; };
  13. 	ListNode* getNext() { return mNext; };
  14. 	void setNext( ListNode* node ) { mNext = node; };
  15. protected:
  16. 	KeyType mKey;
  17. 	ListNode *mNext;
  18. };
  19.  
  20. // шаблонный класс, описывающий список
  21. template <typename KeyType, typename ListNodeType>
  22. class List
  23. {
  24. public:
  25. 	List() { mHead = NULL; };
  26. 	virtual ~List() { clear(); };
  27. 	void clear();
  28. 	bool find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode );
  29. 	bool remove( KeyType& key );
  30. 	void push( KeyType& key ) { mHead = new ListNodeType( key, mHead ); };
  31. 	bool pop( KeyType& key );
  32. 	ListNodeType* getHead() { return mHead; };
  33. 	bool isEmpty() { return mHead == NULL; };
  34. protected:
  35. 	ListNodeType* mHead;
  36. };
  37.  
  38. // очищает все элементы списка и высвобождает память
  39. template <typename KeyType, typename ListNodeType>
  40. void List<KeyType,ListNodeType>::clear()
  41. {
  42. 	ListNodeType *n =  mHead;
  43. 	while( NULL != n )
  44. 	{
  45. 	   ListNodeType *prev = n;
  46. 	   n = n->getNext();
  47. 	   delete prev;
  48. 	}
  49. 	mHead = NULL;
  50. };
  51.  
  52. // находит узел списка по ключу
  53. template <typename KeyType, typename ListNodeType>
  54. bool List<KeyType,ListNodeType>::find( KeyType& key, ListNodeType*& foundNode, ListNodeType*& foundPrevNode )
  55. {
  56. 	ListNodeType *n =  mHead;
  57. 	ListNodeType *prev = NULL;
  58. 	while( NULL != n )
  59. 	{
  60. 	   if ( n->getKey() == key )
  61. 	   {
  62. 	      foundNode = n;
  63. 	      foundPrevNode = prev;
  64. 	      return true;
  65. 	   }
  66. 	   prev = n;
  67. 	   n = n->getNext();
  68. 	}
  69. 	return false;
  70. }
  71.  
  72. // удаляет узел списка по ключу
  73. template <typename KeyType, typename ListNodeType>
  74. bool List<KeyType,ListNodeType>::remove( KeyType& key )
  75. {
  76. 	ListNodeType *n = NULL;
  77. 	ListNodeType *prev = NULL;
  78.  
  79. 	if ( find( key, n, prev ) )
  80. 	{
  81. 	   if ( NULL != prev )
  82. 	   {
  83. 	      prev->setNext( n->getNext() );
  84. 	   }
  85. 	   else
  86. 	   {
  87. 	      mHead = n->getNext();
  88. 	   }
  89. 	   delete n;
  90. 	   return true;
  91. 	}
  92. 	return false;
  93. };
  94.  
  95. // удаляет первый элемент
  96. template <typename KeyType, typename ListNodeType>
  97. bool List<KeyType,ListNodeType>::pop( KeyType& key )
  98. {
  99. 	if ( mHead != NULL )
  100. 	{
  101. 	   key = mHead->getKey();
  102. 	   ListNodeType* n = mHead;
  103. 	   mHead = n->getNext();
  104. 	   delete n;
  105. 	   return true;
  106. 	}
  107. 	return false;
  108. };
  109.  
  110. // Шаблонный класс, описывающий узел дерева двоичного поиска
  111.  
  112. template <typename KeyType, typename ValueType>
  113. class TreeNode {
  114. public:
  115. 	TreeNode( KeyType& key ) : mKey(key), mValue(NULL), mParent(NULL), mLeft(NULL), mRight(NULL) {};
  116. 	TreeNode( KeyType& key, ValueType& value ) : mKey(key), mValue(value), mParent(NULL), mLeft(NULL), mRight(NULL) {};
  117. 	~TreeNode() { };
  118. 	void setLeft( TreeNode* left ) { mLeft = left; };
  119. 	void setRight( TreeNode* right ) { mRight = right; };
  120. 	void setParent( TreeNode* parent ) { mParent = parent; };
  121. 	KeyType getKey() { return mKey; };
  122. 	ValueType& getValue() { return mValue; };
  123. 	void setValue( ValueType& value ) { mValue = value; };
  124. 	TreeNode* getLeft() { return mLeft; };
  125. 	TreeNode* getRight() { return mRight; };
  126. 	TreeNode* getParent() { return mParent; };
  127. 	virtual string getValueAsText() { return ""; };
  128. protected:
  129. 	KeyType mKey;
  130. 	ValueType mValue;
  131. 	TreeNode* mParent;
  132. 	TreeNode* mLeft;
  133. 	TreeNode* mRight;
  134. };
  135.  
  136. // шаблонный класс, описывающий дерево
  137. template <typename KeyType, typename NodeType>
  138. class Tree {
  139. 	NodeType* mRoot;
  140. public:
  141. 	Tree() { mRoot = NULL; };
  142. 	~Tree() { clear(); };
  143. 	void clear() { dispose( mRoot ); mRoot = NULL; };
  144. 	bool isEmpty() { return mRoot == NULL; };
  145. 	NodeType* getRoot() { return mRoot; };
  146. 	NodeType* findOrInsert( KeyType& key, bool insertIfAbsent );
  147. 	void exclude( NodeType* node );
  148. 	void remove( NodeType* node ) { exclude( node ); dispose( node ); };
  149. 	bool remove( KeyType& key, NodeType* removedNodeCopy );
  150. 	bool remove( KeyType& key ) { return( key, NULL ); };
  151. 	NodeType* findMax( NodeType* node );
  152. 	NodeType* findMax() { return findMax( mRoot ); };
  153. protected:
  154. 	void dispose( NodeType* node );
  155. };
  156.  
  157. // находит узел двоичного дерева по ключу или всталяет, если не найдено
  158. template <typename KeyType, typename NodeType>
  159. NodeType* Tree<KeyType,NodeType>::findOrInsert( KeyType& key, bool insertIfAbsent )
  160. {
  161. 	enum EInsertAction
  162. 	{
  163. 	   eNONE,
  164. 	   eROOT,
  165. 	   eLEFT,
  166. 	   eRIGHT
  167. 	};
  168.  
  169. 	EInsertAction doInsert = eNONE;
  170. 	NodeType *p = mRoot;
  171.  
  172. 	if ( p != NULL )
  173. 	{
  174. 	   for(;;)
  175. 	   {
  176. 	      if ( key < p->getKey() )
  177. 	      {
  178. 	         if ( p->getLeft() != NULL )
  179. 	         {
  180. 	            p = p->getLeft();
  181. 	         }
  182. 	         else
  183. 	         {
  184. 	            doInsert = eLEFT;
  185. 	            break;
  186. 	         }
  187. 	      }
  188. 	      else
  189. 	      if ( key > p->getKey() )
  190. 	      {
  191. 	         if ( p->getRight() != NULL )
  192. 	         {
  193. 	            p = p->getRight();
  194. 	         }
  195. 	         else
  196. 	         {
  197. 	            doInsert = eRIGHT;
  198. 	            break;
  199. 	         }
  200. 	      }
  201. 	      else
  202. 	      {
  203. 	         return p;
  204. 	      }
  205. 	   }
  206. 	}
  207. 	else
  208. 	{
  209. 	   doInsert = eROOT;
  210. 	}
  211.  
  212. 	if ( doInsert != eNONE && insertIfAbsent )
  213. 	{
  214. 	   NodeType* q = new NodeType( key );
  215. 	   switch( doInsert )
  216. 	   {
  217. 	      case eLEFT : p->setLeft( q ); break;
  218. 	      case eRIGHT: p->setRight( q ); break;
  219. 	      case eROOT : mRoot = q; break;
  220. 	      default: break;
  221. 	   }
  222. 	   q->setParent( p );
  223. 	   return q;
  224. 	}
  225.  
  226. 	return NULL;
  227. }
  228.  
  229. // находит узел двоичного дерева с максимальным значением ключа
  230. template <typename KeyType, typename NodeType>
  231. NodeType* Tree<KeyType,NodeType>::findMax( NodeType* node )
  232. {
  233. 	if ( node != NULL )
  234. 	{
  235. 	   NodeType* n = node;
  236. 	   while( NULL != n->getRight() )
  237. 	   {
  238. 	      n = n->getRight();
  239. 	   }
  240. 	   return n;
  241. 	}
  242. 	return NULL;
  243. }
  244.  
  245. // исключает узел двоичного дерева из дерева, не удаляя
  246. template <typename KeyType, typename NodeType>
  247. void Tree<KeyType,NodeType>::exclude( NodeType* node )
  248. {
  249. 	if ( NULL != node )
  250. 	{
  251. 	   NodeType* successor = NULL;
  252.  
  253. 	   if ( node->getLeft() == NULL )
  254. 	   {
  255. 	      successor = node->getRight();
  256. 	   }
  257. 	   else
  258. 	   if ( node->getRight() == NULL )
  259. 	   {
  260. 	      successor = node->getLeft();
  261. 	   }
  262. 	   else
  263. 	   {
  264. 	      successor = node->getRight();
  265. 	      NodeType* left = successor->getLeft();
  266.  
  267. 	      while( left != NULL )
  268. 	      {
  269. 	         successor = left;
  270. 	         left = successor->getLeft();
  271. 	      }
  272.  
  273. 	      if ( successor->getParent() != node )
  274. 	      {
  275. 	     	NodeType* right = successor->getRight();
  276. 	         successor->getParent()->setLeft( right );
  277. 	         if ( NULL != right)
  278. 	         {
  279. 	         	successor->getRight()->setParent( successor->getParent() );
  280. 	         }
  281. 	         successor->setRight( node->getRight() );
  282. 	         node->getRight()->setParent( successor );
  283. 	      }
  284.  
  285. 	      successor->setLeft( node->getLeft() );
  286. 	      node->getLeft()->setParent( successor );
  287. 	   }
  288.  
  289. 	   if ( node->getParent() == NULL )
  290. 	   {
  291. 	      mRoot = successor;
  292. 	   }
  293. 	   else
  294. 	   if ( node->getParent()->getLeft() == node )
  295. 	   {
  296. 	      node->getParent()->setLeft( successor );
  297. 	   }
  298. 	   else
  299. 	   if ( node->getParent()->getRight() == node )
  300. 	   {
  301. 	      node->getParent()->setRight( successor );
  302. 	   }
  303. 	   else
  304. 	   {
  305. 	      cout << "fatal error: orphaned# " 
  306. 	         << "N:" << node << ",P:" << node->getParent() << ",L:" << node->getLeft() << ",R:"<<node->getRight()
  307. 	         << endl;
  308. 	      return;
  309. 	   }
  310.  
  311. 	   if ( NULL != successor )
  312. 	   {
  313. 	      successor->setParent( node->getParent() );
  314. 	   }
  315.  
  316. 	   node->setParent( NULL );
  317. 	   node->setLeft( NULL );
  318. 	   node->setRight( NULL );
  319. 	}
  320. }
  321.  
  322. // находит и удаляет узел дерева по ключу
  323. template <typename KeyType, typename NodeType>
  324. bool Tree<KeyType,NodeType>::remove( KeyType& key, NodeType* removedNodeCopy )
  325. {
  326. 	NodeType* node = findOrInsert( key, false );
  327. 	if ( node != NULL )
  328. 	{
  329. 	   exclude( node );
  330. 	   if ( removedNodeCopy != NULL )
  331. 	   {
  332. 	      *removedNodeCopy = node;
  333. 	   }
  334. 	   dispose( node );
  335. 	   return true;
  336. 	}
  337. 	return false;
  338. }
  339.  
  340. // удаляет узел из памяти
  341. template <typename KeyType, typename NodeType>
  342. void Tree<KeyType,NodeType>::dispose( NodeType* node )
  343. {
  344. 	if ( node != NULL ) 
  345. 	{
  346. 	    dispose( node->getLeft() );
  347. 	    dispose( node->getRight() );
  348. 	    delete node;
  349. 	}
  350. }
  351.  
  352. // класы-контейнеры на основе высше описанных шаблонных классов
  353.  
  354. class PrioTreeNode;
  355. typedef TreeNode<string,PrioTreeNode*> IdTreeNodeBase;
  356. class IdTreeNode : public IdTreeNodeBase
  357. {
  358. public:
  359. 	IdTreeNode( string& id ) : IdTreeNodeBase( id ) {};
  360. 	virtual ~IdTreeNode() { mValue = NULL; };
  361. 	IdTreeNode* getLeft() { return (IdTreeNode*)mLeft; };
  362. 	IdTreeNode* getRight() { return (IdTreeNode*)mRight; };
  363. 	IdTreeNode* getParent() { return (IdTreeNode*)mParent; };
  364. };
  365. typedef Tree<string,IdTreeNode> IdTree;
  366.  
  367. typedef ListNode<IdTreeNode*> IdListNode;
  368. typedef List<IdTreeNode*,IdListNode> IdList;
  369.  
  370. typedef TreeNode<int,IdList*> PrioTreeNodeBase;
  371. class PrioTreeNode : public PrioTreeNodeBase
  372. {
  373. public:
  374. 	PrioTreeNode( int& prio ) : PrioTreeNodeBase( prio ) { mValue = new IdList(); };
  375. 	virtual ~PrioTreeNode() { delete mValue; };
  376. 	PrioTreeNode* getLeft() { return (PrioTreeNode*)mLeft; };
  377. 	PrioTreeNode* getRight() { return (PrioTreeNode*)mRight; };
  378. 	PrioTreeNode* getParent() { return (PrioTreeNode*)mParent; };
  379. };
  380. typedef Tree<int,PrioTreeNode> PrioTree;
  381.  
  382. // класс, реализующий очередь с приоритетами
  383.  
  384. class PrioQueue
  385. {
  386.  
  387. public:
  388.  
  389. 	PrioQueue() { }
  390. 	~PrioQueue() { }
  391.  
  392. 	bool add( string& id, int prio  );
  393. 	bool pop( string& id, int& prio );
  394. 	bool change( string& id, int prio );
  395. 	void clear();
  396.  
  397. private:
  398.  
  399. 	IdTree mIdTree;
  400. 	PrioTree mPrioTree;
  401.  
  402. };
  403.  
  404. bool PrioQueue::add( string& id, int prio  )
  405. {
  406. 	IdTreeNode *idNode = mIdTree.findOrInsert( id, true );
  407. 	if ( NULL != idNode )
  408. 	{
  409. 	   PrioTreeNode* prioNode = mPrioTree.findOrInsert( prio, true );
  410. 	   if ( NULL != prioNode )
  411. 	   {
  412. 	      prioNode->getValue()->push( idNode );
  413. 	      idNode->setValue( prioNode );
  414. 	      return true;
  415. 	   }
  416. 	}
  417. 	return false;
  418. }
  419.  
  420. bool PrioQueue::pop( string& id, int& prio )
  421. {
  422. 	bool result = false;
  423. 	PrioTreeNode* prioNode = mPrioTree.findMax();
  424. 	if ( NULL != prioNode )
  425. 	{
  426. 	   prio = prioNode->getKey();
  427. 	   if ( ! prioNode->getValue()->isEmpty() )
  428. 	   {
  429. 	      IdTreeNode* idNode;
  430. 	      if ( prioNode->getValue()->pop( idNode ) )
  431. 	      {
  432. 	         id = idNode->getKey();
  433. 	         mIdTree.remove( idNode );
  434. 	         if ( prioNode->getValue()->isEmpty() )
  435. 	         {
  436. 	            mPrioTree.remove( prioNode );
  437. 	         }
  438. 	         result = true;
  439. 	      }
  440. 	   }
  441. 	}
  442. 	return result;
  443. }
  444.  
  445. bool PrioQueue::change( string& id, int prio )
  446. {
  447. 	bool result = false;
  448. 	IdTreeNode* idNode = mIdTree.findOrInsert( id, false );
  449. 	if ( NULL != idNode )
  450. 	{
  451. 	   PrioTreeNode* oldPrioNode = idNode->getValue();
  452. 	   (void)oldPrioNode->getValue()->remove( idNode );
  453. 	   if ( oldPrioNode->getValue()->isEmpty() )
  454. 	   {
  455. 	      mPrioTree.remove( oldPrioNode );
  456. 	   }
  457. 	   PrioTreeNode* newPrioNode = mPrioTree.findOrInsert( prio, true );
  458. 	   idNode->setValue( newPrioNode );
  459. 	   newPrioNode->getValue()->push( idNode );
  460. 	   result = true;
  461. 	}
  462. 	return result;
  463. }
  464.  
  465. void PrioQueue::clear()
  466. {
  467. 	mIdTree.clear();
  468. 	mPrioTree.clear();
  469. }
  470.  
  471. int main( int argc, char** argv )
  472. {
  473. 	PrioQueue q;
  474.  
  475. 	string command;
  476. 	string id;
  477. 	int prio;
  478.  
  479. 	while ( cin >> command )
  480. 	{
  481. 	   if ( command.compare( 0, 1, "#" ) == 0 ) continue;
  482. 	   else
  483. 	   if ( command == "add" || command == "ADD" )
  484. 	   {
  485. 	      cin >> id;
  486. 	      cin >> prio;
  487.  
  488. 	      q.add( id, prio );
  489. 	   }
  490. 	   else
  491. 	   if ( command == "change" || command == "CHANGE" )
  492. 	   {
  493. 	      cin >> id;
  494. 	      cin >> prio;
  495.  
  496. 	      q.change( id, prio );
  497. 	   }
  498. 	   else
  499. 	   if ( command == "pop" || command == "POP" )
  500. 	   {
  501. 	      if ( q.pop( id, prio ) )
  502. 	      {
  503. 	         cout << id << " " << prio << endl;
  504. 	      }
  505. 	      else
  506. 	      {
  507. 	         cout << "error" << endl;
  508. 	      }
  509. 	   }
  510. 	   else
  511. 	   if ( command == "clear" || command == "CLEAR" )
  512. 	   {
  513. 	      q.clear();
  514. 	   }
  515. 	   else
  516. 	   if ( command == "exit" || command == "EXIT" )
  517. 	   {
  518. 	      cout << "bye" << endl;
  519. 	      return 0;
  520. 	   }
  521. 	}
  522.  
  523. 	return 0;
  524. }
  525.  
Success #stdin #stdout 0s 3148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FROADt
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!