Posted By

DrPepper on 10/05/11


Tagged


Versions (?)

[CISP430] pqueue.cpp


 / Published in: C++
 

  1. #include <iostream>
  2.  
  3. #include "pqueue1.h" // header file for pqueue1
  4. using namespace std;
  5.  
  6. // global prototype
  7. void list_copy(const Node* source_ptr, Node*& head_ptr, Node*& tail_ptr);
  8. void list_head_insert(Node*& head_ptr, const PriorityQueue::Item& entry, unsigned int priority);
  9. void list_insert(Node* previous_ptr, const PriorityQueue::Item& entry, unsigned int priority);
  10. void list_clear(Node*& head_ptr);
  11. void list_head_remove(Node*& head_ptr);
  12.  
  13.  
  14.  
  15.  
  16. PriorityQueue::PriorityQueue( )
  17. // Postcondition: The PriorityQueue has been initialized with no Items.
  18. { head_ptr = NULL; many_nodes = 0; }
  19.  
  20. PriorityQueue::PriorityQueue(const PriorityQueue& source)
  21. // COPY CONSTRACTOR
  22. {
  23. cout << "-------- a.1"<< endl;
  24. Node* tail_ptr;
  25. list_copy(source.head_ptr,head_ptr,tail_ptr);
  26. many_nodes = source.many_nodes;
  27. }
  28.  
  29. PriorityQueue::~PriorityQueue( )
  30.  
  31. // DESTRACTOR
  32.  
  33. {
  34. cout << "-------- a.2"<< endl;
  35. // destractor clear the data
  36. list_clear(head_ptr);
  37. head_ptr = NULL;
  38. many_nodes = 0;
  39. // I NEED TO ADD LIST_CLEAR() FROM A3 NODE.H
  40. }
  41.  
  42. void PriorityQueue::operator =(const PriorityQueue& source)
  43. // NO DESCRIPTION...
  44. {
  45. cout << "-------- a.3"<< endl;
  46. if (this != &source)
  47. {
  48. cout << "-------- a.4"<< endl;
  49. Node *tail_ptr;
  50. list_clear(head_ptr);
  51. head_ptr = NULL;
  52. many_nodes = 0;
  53.  
  54.  
  55. list_copy(source.head_ptr, head_ptr, tail_ptr);
  56. many_nodes = source.many_nodes;
  57. }
  58. cout << "-------- a.5"<< endl;
  59. }
  60. /*USING QUICKSORT-LIKE ALGORITHM*/
  61. /*if using quick sort method create cursor, the new node, and an array with
  62. all the memory locations of each node in the list */
  63. // Node *locations[many_nodes];
  64. // Node *cursor_ptr = head_ptr;
  65. // for (int i=0; i<many_nodes; ++i) {
  66. // locations[i] = cursor;
  67. // cursor_ptr = cursor_ptr->link;
  68. // }
  69.  
  70.  
  71. void PriorityQueue::insert(const Item& entry, unsigned int priority)//PUSH
  72. // Postcondition: A new copy of entry has been inserted with the specified
  73. // priority.
  74. {
  75. cout << "-------- a.6"<< endl;
  76. //bool spot = false;
  77. Node *target_ptr = new Node();
  78.  
  79.  
  80. // SOTORE THE ITEMS
  81. target_ptr->data = entry;
  82. target_ptr->priority = priority;
  83. // NODE IS EMPTY
  84. if(is_empty())
  85. {
  86. cout << "-------- a.7"<< endl;
  87. head_ptr = target_ptr;
  88. head_ptr->link = NULL;
  89. }
  90.  
  91. // NODE IS NOT EMPTY
  92. else if(!is_empty())
  93. {
  94. cout << "-------- a.8"<< endl;
  95. Node *cursor = head_ptr;
  96. int counter1=0, counter2=0;
  97. // FIND A POSITION OF THE NODE
  98. for (counter1; counter1 < size(); ++counter1)
  99. {
  100. if(cursor->priority < priority)
  101. {
  102. target_ptr->link = cursor;
  103. if(cursor == head_ptr)
  104. {
  105. head_ptr = target_ptr;
  106. }
  107. cursor = head_ptr;
  108. for(counter2; counter2<counter1;++counter2)
  109. {
  110. if(counter2==(counter1-1))
  111. {
  112. cursor->link = target_ptr;
  113. break;
  114.  
  115. }
  116. //else{
  117. cursor = cursor->link;
  118. //}
  119.  
  120. }
  121. break;
  122. }
  123. else if(counter1==(size()-1))
  124. {
  125. cursor->link = target_ptr;
  126. target_ptr -> link = NULL;
  127. }
  128. cursor = cursor->link;
  129. }
  130.  
  131. }
  132. ++many_nodes;
  133. }
  134.  
  135. PriorityQueue::Item PriorityQueue::get_front()
  136. // Precondition: size( ) > 0.
  137. // Postcondition: The highest priority item has been returned and has been
  138. // removed from the PriorityQueue. (If several items have equal priority,
  139. // then the one that entered first will come out first.)
  140. {
  141. cout << "-------- a.21"<< endl;
  142. if(!is_empty())
  143. {
  144. cout << "-------- a.22"<< endl;
  145. Node top;
  146. top.data = head_ptr->data;
  147. list_head_remove(head_ptr);
  148. --many_nodes;
  149. return top.data;
  150. }
  151. }
  152.  
  153.  
  154.  
  155. /**************************************************************
  156.  
  157. HERE ARE TOOLBOX
  158.  
  159. ***************************************************************/
  160.  
  161. void list_copy(const Node* source_ptr, Node*& head_ptr, Node*& tail_ptr)
  162. {
  163. // Library facilities used: cstdlib
  164. head_ptr = NULL;
  165. tail_ptr = NULL;
  166. // Handle the case of the empty list
  167. if (source_ptr == NULL)
  168. return;
  169.  
  170. // Make the head node for the newly created list, and put data in it
  171. list_head_insert(head_ptr, source_ptr->data, source_ptr->priority);
  172. tail_ptr = head_ptr;
  173.  
  174. // Copy rest of the nodes one at a time, adding at the tail of new list
  175. source_ptr = source_ptr->link;
  176. while (source_ptr != NULL)
  177. {
  178. list_insert(tail_ptr, source_ptr->data, source_ptr->priority);
  179. tail_ptr = tail_ptr->link;
  180. source_ptr = source_ptr->link;
  181. }
  182. }
  183.  
  184. void list_head_insert(Node*& head_ptr, const PriorityQueue::Item& entry, unsigned int priority)
  185. {
  186. Node *NewNode = new Node();
  187. NewNode->data = entry;
  188. NewNode->link = head_ptr;
  189. NewNode->priority = priority;
  190. head_ptr = NewNode;
  191. }
  192.  
  193. void list_insert(Node* previous_ptr, const PriorityQueue::Item& entry, unsigned int priority)
  194. {
  195. Node *target_ptr = new Node();
  196. target_ptr->data = entry;
  197. target_ptr->link = previous_ptr->link;
  198. target_ptr->priority = priority;
  199. previous_ptr->link = target_ptr;
  200. }
  201.  
  202. void list_clear(Node*& head_ptr)
  203. {
  204. // Library facilities used: cstdlib
  205. while (head_ptr != NULL)
  206. list_head_remove(head_ptr);
  207. }
  208.  
  209. void list_head_remove(Node*& head_ptr)
  210. {
  211. Node *remove_ptr;
  212.  
  213. remove_ptr = head_ptr;
  214. head_ptr = head_ptr->link;
  215. delete remove_ptr;
  216. }

Report this snippet  

You need to login to post a comment.