Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Steque.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
Bag and RandomBag (1.3.34) classes. There are not really robust enough to use as they will leak memory on destruction if you use them to store dynamically allocated objects.
author Eris Caffee <discordia@eldalin.com>
date Thu, 11 Jun 2015 16:30:14 -0500
parents
children a149b424b4e2
line source
1 // g++ -D STEQUE_MAIN -std=c++0x Steque.cpp
2 // g++ -D STEQUE_MAIN -std=c++11 Steque.cpp
3
4
5 #include "Steque.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 Steque<T>::Steque( void ) :
14 N (0),
15 list (nullptr)
16 {
17 }
18
19 template <typename T>
20 Steque<T>::~Steque( void ) {
21 assert( N == 0 ); // Catch the potential memory leak.
22 while ( list ) {
23 Node * next = list->next;
24 delete list;
25 list = next;
26 }
27 }
28
29 template <typename T>
30 void Steque<T>::push( T &item ) {
31 Node * node = new Node();
32 node->item = item;
33 node->next = list;
34 list = node;
35 N++;
36 }
37
38 template <typename T>
39 T Steque<T>::pop( void ) {
40 assert( N > 0 );
41
42 T item = list->item;
43
44 Node *old = list;
45 list = list->next;
46 delete old;
47 N--;
48
49 return item;
50 }
51
52 template <typename T>
53 void Steque<T>::enqueue( T &item ) {
54 Node *curr = list;
55
56 Node *node = new Node();
57 node->item = item;
58 node->next = nullptr;
59
60 if ( ! curr ) {
61 list = node;
62 N++;
63 return;
64 }
65
66 while ( curr->next ) {
67 curr = curr->next;
68 }
69
70 curr->next = node;
71 N++;
72
73 return;
74 }
75
76 template <typename T>
77 bool Steque<T>::is_empty( void ) {
78 return N == 0;
79 }
80
81 template <typename T>
82 size_t Steque<T>::size( void ) {
83 return N;
84 }
85
86 template <typename T>
87 typename Steque<T>::iterator Steque<T>::begin( void ) {
88 return Steque<T>::iterator( list );
89 }
90
91 template <typename T>
92 typename Steque<T>::iterator Steque<T>::end( void ) {
93 return Steque<T>::iterator( nullptr );
94 }
95
96
97 ////////////////////////////////////////////////////////////////////////////////
98
99 template <typename T>
100 Steque<T>::iterator::iterator( Node *c ) :
101 curr (c)
102 {
103 }
104
105 template <typename T>
106 typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
107 if ( this->curr != nullptr ) {
108 this->curr = this->curr->next;
109 }
110 return *this;
111 }
112
113 template <typename T>
114 typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
115 auto t = Steque<T>::iterator( *this );
116
117 if ( this->curr != nullptr ) {
118 this->curr = this->curr->next;
119 }
120 return t;
121 }
122
123 template <typename T>
124 T Steque<T>::iterator::operator*() {
125 return this->curr->item;
126 }
127
128 template <typename T>
129 bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
130 return this->curr != other.curr;
131 }
132
133 ////////////////////////////////////////////////////////////////////////////////
134
135
136
137 #ifdef STEQUE_MAIN
138
139 #include <iostream>
140
141 int main ( int argc, char **argv ) {
142
143 Steque<long> steque;
144 bool push_it = true;
145
146 long i;
147 while ( ! std::cin.eof() ) {
148 std::cin >> i;
149 if ( std::cin.good() ) {
150 if ( push_it ) {
151 steque.push( i );
152 push_it = false;
153 }
154 else {
155 steque.enqueue( i );
156 push_it = true;
157 }
158 }
159 }
160
161 std::cout << "Steque has " << steque.size() << " entries." << std::endl;
162
163 for ( auto iter = steque.begin(); iter != steque.end(); ++iter ) {
164 std::cout << *iter << std::endl;
165 }
166
167 std::cout << "Popping entries..." << std::endl;
168
169 while ( ! steque.is_empty() ) {
170 i = steque.pop();
171 std::cout << i << std::endl;
172 }
173
174 std::cout << "Steque has " << steque.size() << " entries." << std::endl;
175
176 }
177
178 #endif