Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Queue.hpp @ 26:2cbfacd2a3e9

find changesets by author, revision, files, or words in the commit message
Slight tweak to the iterator for Queue to make it return values by reference.
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 15:46:22 -0500
parents 3cdac4c29445
children 80ca1973e3bd
rev   line source
discordia@16 1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
discordia@16 2
discordia@8 3 #ifndef QUEUE_HPP
discordia@8 4 #define QUEUE_HPP
discordia@8 5
discordia@8 6 #include <cstddef>
discordia@16 7 #include <cassert>
discordia@24 8 #include <iterator>
discordia@25 9 #include <type_traits>
discordia@8 10
discordia@8 11 template <typename T>
discordia@8 12 class Queue {
discordia@8 13
discordia@9 14 private:
discordia@8 15
discordia@8 16 ////////////////////////////////////
discordia@8 17 class Node {
discordia@8 18 public:
discordia@8 19 T item;
discordia@8 20 Node *next;
discordia@8 21 };
discordia@8 22
discordia@9 23 public:
discordia@8 24
discordia@8 25 ////////////////////////////////////
discordia@25 26
discordia@25 27 template <bool is_const = true>
discordia@25 28 class generic_iterator : public std::iterator<std::forward_iterator_tag, T> {
discordia@25 29
discordia@25 30 private:
discordia@25 31 typedef typename std::conditional<is_const, const Node *, Node *>::type NodePtrType;
discordia@26 32 typedef typename std::conditional<is_const, const T&, T&>::type ValueReferenceType;
discordia@8 33
discordia@8 34 public:
discordia@8 35
discordia@25 36 generic_iterator( NodePtrType c ) :
discordia@25 37 curr (c)
discordia@25 38 {
discordia@25 39 }
discordia@8 40
discordia@25 41 generic_iterator & operator++() {
discordia@25 42 if ( this->curr != nullptr ) {
discordia@25 43 this->curr = this->curr->next;
discordia@25 44 }
discordia@25 45 return *this;
discordia@25 46 }
discordia@8 47
discordia@25 48 generic_iterator operator++( int ) {
discordia@25 49 auto t = generic_iterator( *this );
discordia@25 50
discordia@25 51 if ( this->curr != nullptr ) {
discordia@25 52 this->curr = this->curr->next;
discordia@25 53 }
discordia@25 54 return t;
discordia@25 55 }
discordia@25 56
discordia@26 57 ValueReferenceType operator*() {
discordia@25 58 return this->curr->item;
discordia@25 59 }
discordia@25 60
discordia@25 61 bool operator!=( generic_iterator other ) {
discordia@25 62 return this->curr != other.curr;
discordia@25 63 }
discordia@8 64
discordia@8 65 private:
discordia@8 66
discordia@25 67 NodePtrType curr;
discordia@8 68 };
discordia@8 69
discordia@8 70 ////////////////////////////////////
discordia@8 71
discordia@25 72 typedef generic_iterator<true> const_iterator;
discordia@25 73 typedef generic_iterator<false> iterator;
discordia@24 74
discordia@8 75 Queue( void );
discordia@8 76 ~Queue( void );
discordia@8 77
discordia@24 78 // 1.3.41 Copy constructor.
discordia@24 79 Queue( const Queue<T> &q );
discordia@24 80
discordia@8 81 void enqueue( T &item );
discordia@8 82 T dequeue( void );
discordia@8 83
discordia@8 84 bool is_empty( void );
discordia@8 85 size_t size( void );
discordia@8 86
discordia@8 87 iterator begin( void );
discordia@8 88 iterator end( void );
discordia@24 89 const_iterator begin( void ) const;
discordia@24 90 const_iterator end( void ) const;
discordia@8 91
discordia@9 92
discordia@8 93 private:
discordia@8 94
discordia@8 95 size_t N;
discordia@8 96 Node *first;
discordia@8 97 Node *last;
discordia@8 98
discordia@8 99 };
discordia@8 100
discordia@8 101
discordia@16 102 template <typename T>
discordia@16 103 Queue<T>::Queue( void ) :
discordia@16 104 N (0),
discordia@16 105 first (nullptr),
discordia@16 106 last (nullptr)
discordia@16 107 {
discordia@16 108 }
discordia@24 109
discordia@24 110 // 1.3.41
discordia@24 111 template <typename T>
discordia@24 112 Queue<T>::Queue( const Queue<T> &q ) :
discordia@24 113 N (0),
discordia@24 114 first (nullptr),
discordia@24 115 last (nullptr)
discordia@24 116 {
discordia@24 117 for ( auto it = q.begin(); it != q.end(); ++it ) {
discordia@24 118 T item = *it;
discordia@24 119 this->enqueue( item );
discordia@24 120 }
discordia@24 121 }
discordia@16 122
discordia@16 123 template <typename T>
discordia@16 124 Queue<T>::~Queue( void ) {
discordia@16 125 assert( N == 0 ); // Catch the potential memory leak.
discordia@16 126 while ( first ) {
discordia@16 127 Node *next = first->next;
discordia@16 128 delete first;
discordia@16 129 first = next;
discordia@16 130 }
discordia@16 131 }
discordia@16 132
discordia@16 133 template <typename T>
discordia@16 134 void Queue<T>::enqueue( T &item ) {
discordia@16 135 Node * node = new Node();
discordia@16 136 node->item = item;
discordia@16 137 node->next = nullptr;
discordia@16 138
discordia@16 139 if ( last ) {
discordia@16 140 last->next = node;
discordia@16 141 last = node;
discordia@16 142 }
discordia@16 143 else {
discordia@16 144 last = first = node;
discordia@16 145 }
discordia@16 146
discordia@16 147 N++;
discordia@16 148 }
discordia@16 149
discordia@16 150 template <typename T>
discordia@16 151 T Queue<T>::dequeue( void ) {
discordia@16 152 assert( N > 0 );
discordia@16 153
discordia@16 154 T item = first->item;
discordia@16 155
discordia@16 156 Node *old = first;
discordia@16 157 first = first->next;
discordia@16 158 delete old;
discordia@16 159 N--;
discordia@16 160
discordia@16 161 if ( ! first )
discordia@16 162 last = nullptr;
discordia@16 163
discordia@16 164 return item;
discordia@16 165 }
discordia@16 166
discordia@16 167 template <typename T>
discordia@16 168 bool Queue<T>::is_empty( void ) {
discordia@16 169 return N == 0;
discordia@16 170 }
discordia@16 171
discordia@16 172 template <typename T>
discordia@16 173 size_t Queue<T>::size( void ) {
discordia@16 174 return N;
discordia@16 175 }
discordia@16 176
discordia@16 177 template <typename T>
discordia@16 178 typename Queue<T>::iterator Queue<T>::begin( void ) {
discordia@16 179 return Queue<T>::iterator( first );
discordia@16 180 }
discordia@16 181
discordia@16 182 template <typename T>
discordia@16 183 typename Queue<T>::iterator Queue<T>::end( void ) {
discordia@16 184 return Queue<T>::iterator( nullptr );
discordia@16 185 }
discordia@16 186
discordia@24 187 template <typename T>
discordia@24 188 typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
discordia@24 189 return Queue<T>::const_iterator( first );
discordia@24 190 }
discordia@24 191
discordia@24 192 template <typename T>
discordia@24 193 typename Queue<T>::const_iterator Queue<T>::end( void ) const {
discordia@24 194 return Queue<T>::const_iterator( nullptr );
discordia@24 195 }
discordia@24 196
discordia@8 197 #endif
discordia@8 198