SHARE
TWEET

ndoe2.h

a guest Nov 25th, 2012 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // FILE: node2.h (part of the namespace main_savitch_6B)
  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:
  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 MAIN_SAVITCH_NODE2_H  
  144. #define MAIN_SAVITCH_NODE2_H
  145. #include <cstdlib>   // Provides NULL and size_t
  146. #include <iterator>  // Provides iterator and forward_iterator_tag
  147.  
  148. namespace main_savitch_6B
  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( ) { return data_field; }
  161.         node* link( ) { return link_field; }
  162.         void set_data(const Item& new_data) { data_field = new_data; }
  163.         void set_link(node* new_link) { link_field = new_link; }
  164.         // CONST MEMBER FUNCTIONS
  165.         const Item& data( ) const { return data_field; }
  166.         const node* link( ) const { return link_field; }
  167.     private:
  168.         Item data_field;
  169.         node *link_field;
  170.     };
  171.  
  172.     // FUNCTIONS to manipulate a linked list:
  173.     template <class Item>
  174.     void list_clear(node<Item>*& head_ptr);
  175.  
  176.     template <class Item>
  177.     void list_copy
  178.         (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
  179.  
  180.     template <class Item>
  181.     void list_head_insert(node<Item>*& head_ptr, const Item& entry);
  182.  
  183.     template <class Item>
  184.     void list_head_remove(node<Item>*& head_ptr);
  185.  
  186.     template <class Item>
  187.     void list_insert(node<Item>* previous_ptr, const Item& entry);
  188.  
  189.     template <class Item>
  190.         std::size_t list_length(const node<Item>* head_ptr);
  191.  
  192.     template <class NodePtr, class SizeType>
  193.     NodePtr list_locate(NodePtr head_ptr, SizeType position);
  194.  
  195.     template <class Item>
  196.     void list_remove(node<Item>* previous_ptr);
  197.    
  198.     template <class NodePtr, class Item>
  199.     NodePtr list_search(NodePtr head_ptr, const Item& target);
  200.  
  201.     // FORWARD ITERATORS to step through the nodes of a linked list
  202.     // A node_iterator of can change the underlying linked list through the
  203.     // * operator, so it may not be used with a const node. The
  204.     // node_const_iterator cannot change the underlying linked list
  205.     // through the * operator, so it may be used with a const node.
  206.     // WARNING:
  207.     // This classes use std::iterator as its base class;
  208.     // Older compilers that do not support the std::iterator class can
  209.     // delete everything after the word iterator in the second line:
  210.  
  211.     template <class Item>
  212.     class node_iterator
  213.     : public std::iterator<std::forward_iterator_tag, Item>
  214.     {
  215.     public:
  216.         node_iterator(node<Item>* initial = NULL)
  217.             { current = initial; }
  218.         Item& operator *( ) const
  219.             { return current->data( ); }
  220.         node_iterator& operator ++( ) // Prefix ++
  221.             {
  222.                 current = current->link( );
  223.                 return *this;
  224.             }
  225.         node_iterator operator ++(int) // Postfix ++
  226.             {
  227.                 node_iterator original(current);
  228.                 current = current->link( );
  229.                 return original;         
  230.             }
  231.         bool operator ==(const node_iterator other) const
  232.             { return current == other.current; }
  233.         bool operator !=(const node_iterator other) const
  234.             { return current != other.current; }
  235.     private:
  236.         node<Item>* current;
  237.     };
  238.  
  239.     template <class Item>
  240.     class const_node_iterator
  241.     : public std::iterator<std::forward_iterator_tag, const Item>
  242.     {
  243.     public:
  244.         const_node_iterator(const node<Item>* initial = NULL)
  245.             { current = initial; }
  246.         const Item& operator *( ) const
  247.             { return current->data( ); }
  248.         const_node_iterator& operator ++( ) // Prefix ++
  249.             {
  250.                 current = current->link( );
  251.                 return *this;
  252.             }
  253.         const_node_iterator operator ++(int) // Postfix ++
  254.             {
  255.                 const_node_iterator original(current);
  256.                 current = current->link( );
  257.                 return original;
  258.             }
  259.         bool operator ==(const const_node_iterator other) const
  260.             { return current == other.current; }
  261.         bool operator !=(const const_node_iterator other) const
  262.             { return current != other.current; }
  263.     private:
  264.         const node<Item>* current;
  265.     };
  266.  
  267. }
  268.  
  269. #include "node2.template"
  270. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top