Mercurial > Algorithms__Sedgewick
changeset 12:1e3c509b6ac4
Added Deque (exercise 1.3.33)
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Wed, 10 Jun 2015 15:44:42 -0500 |
parents | 846aeab17939 |
children | 5b5b5a337763 |
files | algs4-c++/src/Deque.cpp algs4-c++/src/Deque.hpp |
diffstat | 2 files changed, 286 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/src/Deque.cpp Wed Jun 10 15:44:42 2015 -0500 1.3 @@ -0,0 +1,215 @@ 1.4 +// g++ -D DEQUE_MAIN -std=c++0x Deque.cpp 1.5 +// g++ -D DEQUE_MAIN -std=c++11 Deque.cpp 1.6 + 1.7 + 1.8 +#include "Deque.hpp" 1.9 + 1.10 +#include <cassert> 1.11 +#include <cstddef> 1.12 + 1.13 +#include <iostream> 1.14 + 1.15 +template <typename T> 1.16 +Deque<T>::Deque( void ) : 1.17 + N (0), 1.18 + first (nullptr), 1.19 + last (nullptr) 1.20 + { 1.21 + } 1.22 + 1.23 +template <typename T> 1.24 +Deque<T>::~Deque( void ) { 1.25 + assert( N == 0 ); // Catch the potential memory leak. 1.26 + while ( first ) { 1.27 + Node *next = first->next; 1.28 + delete first; 1.29 + first = next; 1.30 + } 1.31 + } 1.32 + 1.33 +template <typename T> 1.34 +void Deque<T>::push_right( T &item ) { 1.35 + Node * node = new Node(); 1.36 + node->item = item; 1.37 + node->next = nullptr; 1.38 + node->prev = nullptr; 1.39 + 1.40 + if ( last ) { 1.41 + last->next = node; 1.42 + node->prev = last; 1.43 + last = node; 1.44 + } 1.45 + else { 1.46 + last = first = node; 1.47 + } 1.48 + 1.49 + N++; 1.50 + } 1.51 + 1.52 +template <typename T> 1.53 +void Deque<T>::push_left( T &item ) { 1.54 + Node * node = new Node(); 1.55 + node->item = item; 1.56 + node->next = nullptr; 1.57 + node->prev = nullptr; 1.58 + 1.59 + if ( first ) { 1.60 + node->next = first; 1.61 + first->prev = node; 1.62 + first = node; 1.63 + } 1.64 + else { 1.65 + last = first = node; 1.66 + } 1.67 + 1.68 + N++; 1.69 + } 1.70 + 1.71 +template <typename T> 1.72 +T Deque<T>::pop_left( void ) { 1.73 + assert( N > 0 ); 1.74 + 1.75 + T item = first->item; 1.76 + 1.77 + Node *old = first; 1.78 + if ( first->next ) 1.79 + first->next->prev = nullptr; 1.80 + first = first->next; 1.81 + delete old; 1.82 + N--; 1.83 + 1.84 + if ( ! first ) 1.85 + last = nullptr; 1.86 + 1.87 + return item; 1.88 + } 1.89 + 1.90 +template <typename T> 1.91 +T Deque<T>::pop_right( void ) { 1.92 + assert( N > 0 ); 1.93 + 1.94 + T item = last->item; 1.95 + 1.96 + Node *old = last; 1.97 + if ( last->prev ) 1.98 + last->prev->next = nullptr; 1.99 + last = last->prev; 1.100 + delete old; 1.101 + N--; 1.102 + 1.103 + if ( ! last ) 1.104 + first = nullptr; 1.105 + 1.106 + return item; 1.107 + } 1.108 + 1.109 +template <typename T> 1.110 +bool Deque<T>::is_empty( void ) { 1.111 + return N == 0; 1.112 + } 1.113 + 1.114 +template <typename T> 1.115 +size_t Deque<T>::size( void ) { 1.116 + return N; 1.117 + } 1.118 + 1.119 +template <typename T> 1.120 +typename Deque<T>::iterator Deque<T>::begin( void ) { 1.121 + return Deque<T>::iterator( first ); 1.122 + } 1.123 + 1.124 +template <typename T> 1.125 +typename Deque<T>::iterator Deque<T>::end( void ) { 1.126 + return Deque<T>::iterator( nullptr ); 1.127 + } 1.128 + 1.129 + 1.130 +//////////////////////////////////////////////////////////////////////////////// 1.131 + 1.132 +template <typename T> 1.133 +Deque<T>::iterator::iterator( Node *c ) : 1.134 + curr (c) 1.135 + { 1.136 + } 1.137 + 1.138 +template <typename T> 1.139 +typename Deque<T>::iterator & Deque<T>::iterator::operator++() { 1.140 + if ( this->curr != nullptr ) { 1.141 + this->curr = this->curr->next; 1.142 + } 1.143 + return *this; 1.144 + } 1.145 + 1.146 +template <typename T> 1.147 +typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) { 1.148 + auto t = Deque<T>::iterator( *this ); 1.149 + 1.150 + if ( this->curr != nullptr ) { 1.151 + this->curr = this->curr->next; 1.152 + } 1.153 + return t; 1.154 + } 1.155 + 1.156 +template <typename T> 1.157 +T Deque<T>::iterator::operator*() { 1.158 + return this->curr->item; 1.159 + } 1.160 + 1.161 +template <typename T> 1.162 +bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) { 1.163 + return this->curr != other.curr; 1.164 + } 1.165 + 1.166 + 1.167 +//////////////////////////////////////////////////////////////////////////////// 1.168 + 1.169 +#ifdef DEQUE_MAIN 1.170 + 1.171 +#include <iostream> 1.172 + 1.173 +int main ( int argc, char **argv ) { 1.174 + 1.175 + Deque<long> deque; 1.176 + bool left = true; 1.177 + 1.178 + long i; 1.179 + while ( ! std::cin.eof() ) { 1.180 + std::cin >> i; 1.181 + if ( std::cin.good() ) { 1.182 + if ( left ) { 1.183 + deque.push_left( i ); 1.184 + left = false; 1.185 + } 1.186 + else { 1.187 + deque.push_right( i ); 1.188 + left = true; 1.189 + } 1.190 + } 1.191 + } 1.192 + 1.193 + std::cout << "Deque has " << deque.size() << " entries." << std::endl; 1.194 + 1.195 + for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) { 1.196 + std::cout << *iter << std::endl; 1.197 + } 1.198 + 1.199 + std::cout << "Dequeuing entries..." << std::endl; 1.200 + 1.201 + left = true; 1.202 + while ( ! deque.is_empty() ) { 1.203 + if ( left ) { 1.204 + i = deque.pop_left(); 1.205 + left = false; 1.206 + } 1.207 + else { 1.208 + i = deque.pop_right(); 1.209 + left = true; 1.210 + } 1.211 + std::cout << i << std::endl; 1.212 + } 1.213 + 1.214 + std::cout << "Deque has " << deque.size() << " entries." << std::endl; 1.215 + 1.216 + } 1.217 + 1.218 +#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/Deque.hpp Wed Jun 10 15:44:42 2015 -0500 2.3 @@ -0,0 +1,71 @@ 2.4 +#ifndef DEQUE_HPP 2.5 +#define DEQUE_HPP 2.6 + 2.7 +#include <cstddef> 2.8 + 2.9 +// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 2.10 + 2.11 +template <typename T> 2.12 +class Deque { 2.13 + 2.14 +private: 2.15 + 2.16 + //////////////////////////////////// 2.17 + class Node { 2.18 + public: 2.19 + T item; 2.20 + Node *next; 2.21 + Node *prev; 2.22 + }; 2.23 + 2.24 +public: 2.25 + 2.26 + //////////////////////////////////// 2.27 + class iterator; 2.28 + friend class iterator; 2.29 + class iterator { 2.30 + 2.31 + public: 2.32 + 2.33 + iterator( Node *c ); 2.34 + 2.35 + iterator& operator++(); 2.36 + iterator operator++(int); 2.37 + 2.38 + T operator*(); 2.39 + bool operator!=( typename Deque<T>::iterator ); 2.40 + 2.41 + private: 2.42 + 2.43 + Node *curr; 2.44 + }; 2.45 + 2.46 + //////////////////////////////////// 2.47 + 2.48 + Deque( void ); 2.49 + ~Deque( void ); 2.50 + 2.51 + void push_left( T &item ); 2.52 + void push_right( T &item ); 2.53 + T pop_left( void ); 2.54 + T pop_right( void ); 2.55 + 2.56 + bool is_empty( void ); 2.57 + size_t size( void ); 2.58 + 2.59 + iterator begin( void ); 2.60 + iterator end( void ); 2.61 + 2.62 + 2.63 +private: 2.64 + 2.65 + size_t N; 2.66 + Node *first; 2.67 + Node *last; 2.68 + 2.69 + }; 2.70 + 2.71 + 2.72 + 2.73 +#endif 2.74 +