Posted By

DrPepper on 09/22/11


Tagged


Versions (?)

[CISP430] Node 2.H


 / Published in: C++
 

  1. // FILE: node2.h (part of the namespace CISP430_A3)
  2. // PROVIDES: A template class for a node in a linked list, and list manipulation
  3. // functions. The template parameter is the type of the data in each node.
  4. // This file also defines a template class: node_iterator<Item>.
  5. // The node_iterator is a forward iterators with two constructors:
  6. // (1) A constructor (with a node<Item>* parameter) that attaches the iterator
  7. // to the specified node in a linked list, and (2) a default constructor that
  8. // creates a special iterator that marks the position that is beyond the end of a
  9. // linked list. There is also a const_node_iterator for use with
  10. // const node<Item>* .
  11. //
  12. // TYPEDEF for the node<Item> template class:
  13. // Each node of the list contains a piece of data and a pointer to the
  14. // next node. The type of the data (node<Item>::value_type) is the Item type
  15. // from the template parameter. The type may be any of the built-in C++ classes
  16. // (int, char, ...) or a class with a default constructor, an assignment
  17. // operator, and a test for equality (x == y).
  18. // NOTE:
  19. // Many compilers require the use of the new keyword typename before using
  20. // the expression node<Item>::value_type. Otherwise
  21. // the compiler doesn't have enough information to realize that it is the
  22. // name of a data type.
  23. //
  24. // CONSTRUCTOR for the node<Item> class:
  25. // node(
  26. // const Item& init_data = Item(),
  27. // node* init_link = NULL
  28. // )
  29. // Postcondition: The node contains the specified data and link.
  30. // NOTE: The default value for the init_data is obtained from the default
  31. // constructor of the Item. In the ANSI/ISO standard, this notation
  32. // is also allowed for the built-in types, providing a default value of
  33. // zero. The init_link has a default value of NULL.
  34. //
  35. // NOTE about two versions of some functions:
  36. // The data function returns a reference to the data field of a node and
  37. // the link function returns a copy of the link field of a node.
  38. // Each of these functions comes in two versions: a const version and a
  39. // non-const version. If the function is activated by a const node, then the
  40. // compiler choses the const version (and the return value is const).
  41. // If the function is activated by a non-const node, then the compiler choses
  42. // the non-const version (and the return value will be non-const).
  43. // EXAMPLES:
  44. // const node<int> *c;
  45. // c->link( ) activates the const version of link returning const node*
  46. // c->data( ) activates the const version of data returning const Item&
  47. // c->data( ) = 42; ... is forbidden
  48. // node<int> *p;
  49. // p->link( ) activates the non-const version of link returning node*
  50. // p->data( ) activates the non-const version of data returning Item&
  51. // p->data( ) = 42; ... actually changes the data in p's node
  52. //
  53. // MEMBER FUNCTIONS for the node<Item> class:
  54. // const Item& data( ) const <----- const version
  55. // and
  56. // Item& data( ) <----------------- non-const version
  57. // See the note (above) about the const version and non-const versions:
  58. // Postcondition: The return value is a reference to the data from this node.
  59. //
  60. // const node* link( ) const <----- const version
  61. // and
  62. // node* link( ) <----------------- non-const version
  63. // See the note (above) about the const version and non-const versions:
  64. // Postcondition: The return value is the link from this node.
  65. //
  66. // void set_data(const Item& new_data)
  67. // Postcondition: The node now contains the specified new data.
  68. //
  69. // void set_link(node* new_link)
  70. // Postcondition: The node now contains the specified new link.
  71. //
  72. // FUNCTIONS in the linked list toolkit: // THOSE ARE LOCATED AT SEQUENCE4.TEMPLATE
  73. // template <class Item>
  74. // void list_clear(node<Item>*& head_ptr)
  75. // Precondition: head_ptr is the head pointer of a linked list.
  76. // Postcondition: All nodes of the list have been returned to the heap,
  77. // and the head_ptr is now NULL.
  78. //
  79. // template <class Item>
  80. // void list_copy
  81. // (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
  82. // Precondition: source_ptr is the head pointer of a linked list.
  83. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for
  84. // a new list that contains the same items as the list pointed to by
  85. // source_ptr. The original list is unaltered.
  86. //
  87. // template <class Item>
  88. // void list_head_insert(node<Item>*& head_ptr, const Item& entry)
  89. // Precondition: head_ptr is the head pointer of a linked list.
  90. // Postcondition: A new node containing the given entry has been added at
  91. // the head of the linked list; head_ptr now points to the head of the new,
  92. // longer linked list.
  93. //
  94. // template <class Item>
  95. // void list_head_remove(node<Item>*& head_ptr)
  96. // Precondition: head_ptr is the head pointer of a linked list, with at
  97. // least one node.
  98. // Postcondition: The head node has been removed and returned to the heap;
  99. // head_ptr is now the head pointer of the new, shorter linked list.
  100. //
  101. // template <class Item>
  102. // void list_insert(node<Item>* previous_ptr, const Item& entry)
  103. // Precondition: previous_ptr points to a node in a linked list.
  104. // Postcondition: A new node containing the given entry has been added
  105. // after the node that previous_ptr points to.
  106. //
  107. // template <class Item>
  108. // size_t list_length(const node<Item>* head_ptr)
  109. // Precondition: head_ptr is the head pointer of a linked list.
  110. // Postcondition: The value returned is the number of nodes in the linked
  111. // list.
  112. //
  113. // template <class NodePtr, class SizeType>
  114. // NodePtr list_locate(NodePtr head_ptr, SizeType position)
  115. // The NodePtr may be either node<Item>* or const node<Item>*
  116. // Precondition: head_ptr is the head pointer of a linked list, and
  117. // position > 0.
  118. // Postcondition: The return value is a pointer that points to the node at
  119. // the specified position in the list. (The head node is position 1, the
  120. // next node is position 2, and so on). If there is no such position, then
  121. // the null pointer is returned.
  122. //
  123. // template <class Item>
  124. // void list_remove(node<Item>* previous_ptr)
  125. // Precondition: previous_ptr points to a node in a linked list, and this
  126. // is not the tail node of the list.
  127. // Postcondition: The node after previous_ptr has been removed from the
  128. // linked list.
  129. //
  130. // template <class NodePtr, class Item>
  131. // NodePtr list_search
  132. // (NodePtr head_ptr, const Item& target)
  133. // The NodePtr may be either node<Item>* or const node<Item>*
  134. // Precondition: head_ptr is the head pointer of a linked list.
  135. // Postcondition: The return value is a pointer that points to the first
  136. // node containing the specified target in its data member. If there is no
  137. // such node, the null pointer is returned.
  138. //
  139. // DYNAMIC MEMORY usage by the toolkit:
  140. // If there is insufficient dynamic memory, then the following functions throw
  141. // bad_alloc: the constructor, list_head_insert, list_insert, list_copy.
  142.  
  143. #ifndef NODE2_H
  144. #define NODE2_H
  145. #include <cstdlib> // Provides NULL and size_t
  146. #include <iterator> // Provides iterator and forward_iterator_tag
  147.  
  148. namespace CISP430_A3
  149. {
  150. template <class Item>
  151. class node
  152. {
  153. public:
  154. // TYPEDEF
  155. typedef Item value_type;
  156. // CONSTRUCTOR
  157. node(const Item& init_data=Item( ), node* init_link=NULL)
  158. { data_field = init_data; link_field = init_link; }
  159. // MODIFICATION MEMBER FUNCTIONS
  160. Item& data( )
  161. {
  162. cout << "\n ** data() ** "<<endl;
  163. return data_field;
  164. }
  165.  
  166. node* link( )
  167. {
  168. cout << "\n ** link() ** "<<endl;
  169. return link_field;
  170. }
  171.  
  172. void set_data(const Item& new_data)
  173. {
  174. cout << "\n ** set_data() ** "<<endl;
  175. data_field = new_data;
  176. }
  177. void set_link(node* new_link)
  178. {
  179. cout << "\n ** set_link() ** "<<endl;
  180. link_field = new_link;
  181. }
  182. // CONST MEMBER FUNCTIONS
  183. const Item& data( ) const
  184. {
  185. cout << "\n ** data() const ** "<<endl;
  186. return data_field;
  187. }
  188. const node* link( ) const
  189. {
  190. cout << "\n ** link() const ** "<<endl;
  191. return link_field;
  192. }
  193. private:
  194. Item data_field;
  195. node *link_field;
  196. };
  197.  
  198. // FUNCTIONS to manipulate a linked list:
  199. template <class Item>
  200. void list_clear(node<Item>*& head_ptr) // CTREA THE WHOLE LIST
  201. // Library facilities used: cstdlib
  202. // Precondition: head_ptr is the head pointer of a linked list.
  203. // Postcondition: All nodes of the list have been returned to the heap,
  204. // and the head_ptr is now NULL.
  205. {
  206. cout << "\n ** list_clear() ** "<<endl;
  207. while (head_ptr != NULL)
  208. list_head_remove(head_ptr);
  209. }
  210.  
  211. template <class Item> // COPY THE LIST
  212. void list_copy(
  213. const node<Item>* source_ptr,
  214. node<Item>*& head_ptr,
  215. node<Item>*& tail_ptr
  216. )
  217. // Library facilities used: cstdlib
  218. // Precondition: source_ptr is the head pointer of a linked list.
  219. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for
  220. // a new list that contains the same items as the list pointed to by
  221. // source_ptr. The original list is unaltered.
  222. {
  223. cout << "\n ** list_copy() ** "<<endl;
  224. head_ptr = NULL;
  225. tail_ptr = NULL;
  226.  
  227. // Handle the case of the empty list
  228. if (source_ptr == NULL)
  229. return;
  230.  
  231. // Make the head node for the newly created list, and put data in it
  232. list_head_insert(head_ptr, source_ptr->data( ));
  233. tail_ptr = head_ptr;
  234.  
  235. // Copy rest of the nodes one at a time, adding at the tail of new list
  236. source_ptr = source_ptr->link( );
  237. while (source_ptr != NULL)
  238. {
  239. list_insert(tail_ptr, source_ptr->data( ));
  240. tail_ptr = tail_ptr->link( );
  241. source_ptr = source_ptr->link( );
  242. }
  243. }
  244.  
  245. template <class Item> // INSERT TO HEAD_PTR
  246. void list_head_insert(node<Item>*& head_ptr, const Item& entry)
  247. // Precondition: head_ptr is the head pointer of a linked list.
  248. // Postcondition: A new node containing the given entry has been added at
  249. // the head of the linked list; head_ptr now points to the head of the new,
  250. // longer linked list.
  251. //
  252.  
  253. {
  254. cout << "\n ** list_head_insert() ** "<<endl;
  255. head_ptr = new node<Item>(entry, head_ptr);
  256. }
  257.  
  258. template <class Item> // REMOVE FROM HEAD_PTR
  259. void list_head_remove(node<Item>*& head_ptr)
  260. // Precondition: head_ptr is the head pointer of a linked list, with at
  261. // least one node.
  262. // Postcondition: The head node has been removed and returned to the heap;
  263. // head_ptr is now the head pointer of the new, shorter linked list.
  264. //
  265. {
  266. cout << "\n ** list_head_remove() ** "<<endl;
  267. node<Item> *remove_ptr;
  268.  
  269. remove_ptr = head_ptr;
  270. head_ptr = head_ptr->link( );
  271. delete remove_ptr;
  272. }
  273.  
  274. template <class Item>
  275. void list_insert(node<Item>* previous_ptr, const Item& entry) // LIST INSERT
  276. // Precondition: previous_ptr points to a node in a linked list.
  277. // Postcondition: A new node containing the given entry has been added
  278. // after the node that previous_ptr points to.
  279. //
  280. {
  281. cout << "\n ** list_insert() ** "<<endl;
  282. node<Item> *insert_ptr;
  283.  
  284. insert_ptr = new node<Item>(entry, previous_ptr->link( ));
  285. previous_ptr->set_link(insert_ptr);
  286. }
  287.  
  288. template <class Item>
  289. size_t list_length(const node<Item>* head_ptr) // LENGTH OF LIST
  290. // Library facilities used: cstdlib
  291. // Precondition: head_ptr is the head pointer of a linked list.
  292. // Postcondition: The value returned is the number of nodes in the linked
  293. // list.
  294. //
  295.  
  296. {
  297. cout << "\n ** list_length() ** "<<endl;
  298. const node<Item> *cursor;
  299. std::size_t answer;
  300.  
  301. answer = 0;
  302. for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
  303. ++answer;
  304.  
  305. return answer;
  306. }
  307.  
  308. template <class NodePtr, class SizeType>
  309. NodePtr list_locate(NodePtr head_ptr, SizeType position) // LOCATION OF LIST
  310. // Library facilities used: cassert, cstdlib
  311. // The NodePtr may be either node<Item>* or const node<Item>*
  312. // Precondition: head_ptr is the head pointer of a linked list, and
  313. // position > 0.
  314. // Postcondition: The return value is a pointer that points to the node at
  315. // the specified position in the list. (The head node is position 1, the
  316. // next node is position 2, and so on). If there is no such position, then
  317. // the null pointer is returned.
  318. //
  319. {
  320. cout << "\n ** list_locate() ** "<<endl;
  321. NodePtr cursor;
  322. SizeType i;
  323.  
  324. assert(0 < position);
  325. cursor = head_ptr;
  326. for (i = 1; (i < position) && (cursor != NULL); ++i)
  327. cursor = cursor->link( );
  328. return cursor;
  329. }
  330.  
  331. template <class Item>
  332. void list_remove(node<Item>* previous_ptr) //REMOVE THE LIST
  333. // Precondition: previous_ptr points to a node in a linked list, and this
  334. // is not the tail node of the list.
  335. // Postcondition: The node after previous_ptr has been removed from the
  336. // linked list.
  337. //
  338. {
  339. cout << "\n ** list_remove() ** "<<endl;
  340. node<Item> *remove_ptr;
  341.  
  342. remove_ptr = previous_ptr->link( );
  343. previous_ptr->set_link(remove_ptr->link( ));
  344. delete remove_ptr;
  345. }
  346.  
  347. template <class NodePtr, class Item>
  348. NodePtr list_search(NodePtr head_ptr, const Item& target) // SEARCH THE LIST
  349. // Library facilities used: cstdlib
  350. // The NodePtr may be either node<Item>* or const node<Item>*
  351. // Precondition: head_ptr is the head pointer of a linked list.
  352. // Postcondition: The return value is a pointer that points to the first
  353. // node containing the specified target in its data member. If there is no
  354. // such node, the null pointer is returned.
  355. //
  356. {
  357. cout << "\n ** list_search() ** "<<endl;
  358. NodePtr cursor;
  359. /*******************************************************************************
  360. HERE HAS C2446 AND C2440 ERROR
  361. *****************************************************************************/
  362. for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
  363. //if (target == cursor->data( ))
  364. return cursor;
  365. return NULL;
  366. }
  367.  
  368. // FORWARD ITERATORS to step through the nodes of a linked list
  369. // A node_iterator of can change the underlying linked list through the
  370. // * operator, so it may not be used with a const node. The
  371. // node_const_iterator cannot change the underlying linked list
  372. // through the * operator, so it may be used with a const node.
  373. // WARNING:
  374. // This classes use std::iterator as its base class;
  375. // Older compilers that do not support the std::iterator class can
  376. // delete everything after the word iterator in the second line:
  377.  
  378. template <class Item>
  379. class node_iterator
  380. // : public std::iterator<std::forward_iterator_tag, Item>
  381. {
  382. public:
  383. node_iterator(node<Item>* initial = NULL)
  384. { current = initial; }
  385. Item& operator *( ) const
  386. { return current->data( ); }
  387. node_iterator& operator ++( ) // Prefix ++
  388. {
  389. current = current->link( );
  390. return *this;
  391. }
  392. node_iterator operator ++(int) // Postfix ++
  393. {
  394. node_iterator original(current);
  395. current = current->link( );
  396. return original;
  397. }
  398. bool operator ==(const node_iterator other) const
  399. { return current == other.current; }
  400. bool operator !=(const node_iterator other) const
  401. { return current != other.current; }
  402. private:
  403. node<Item>* current;
  404. };
  405.  
  406. template <class Item>
  407. class const_node_iterator
  408. // : public std::iterator<std::forward_iterator_tag, const Item>
  409. {
  410. public:
  411. const_node_iterator(const node<Item>* initial = NULL)
  412. { current = initial; }
  413. const Item& operator *( ) const
  414. { return current->data( ); }
  415. const_node_iterator& operator ++( ) // Prefix ++
  416. {
  417. current = current->link( );
  418. return *this;
  419. }
  420. const_node_iterator operator ++(int) // Postfix ++
  421. {
  422. const_node_iterator original(current);
  423. current = current->link( );
  424. return original;
  425. }
  426. bool operator ==(const const_node_iterator other) const
  427. { return current == other.current; }
  428. bool operator !=(const const_node_iterator other) const
  429. { return current != other.current; }
  430. private:
  431. const node<Item>* current;
  432. };
  433.  
  434. }
  435. #endif

Report this snippet  

You need to login to post a comment.