Mercurial > Algorithms__Sedgewick
changeset 22:c2cbfdf528f6
1.3.44 Ugh. I would never use this in real life but it seems to be what they want.
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 23 Jun 2015 11:02:31 -0500 |
parents | ec700842d182 |
children | 1198fe3684a6 |
files | algs4-c++/1.3.44 algs4-c++/src/Buffer.cpp algs4-c++/src/Buffer.hpp |
diffstat | 3 files changed, 119 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/1.3.44 Tue Jun 23 11:02:31 2015 -0500 1.3 @@ -0,0 +1,1 @@ 1.4 +src/Buffer.hpp 1.5 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/Buffer.cpp Tue Jun 23 11:02:31 2015 -0500 2.3 @@ -0,0 +1,84 @@ 2.4 +// Sedgewick and Wayne, Algorithms, 4th ed. problem 1.3.44 2.5 + 2.6 +// I would never use this in real life. It's far too inefficient. 2.7 + 2.8 +#include "Buffer.hpp" 2.9 + 2.10 +Buffer::Buffer( void ) : 2.11 + cursor (0), 2.12 + use_s1 (true) 2.13 + { 2.14 + } 2.15 + 2.16 +void Buffer::insert( char c ) { 2.17 + if ( use_s1 ) { 2.18 + size_t i = 0; 2.19 + size_t max = s1.size(); 2.20 + while ( i != cursor ) 2.21 + s2.push( s1.pop() ); 2.22 + s2.push( c ); 2.23 + while ( i < max ) 2.24 + s2.push( s1.pop() ); 2.25 + } 2.26 + else { 2.27 + size_t i = 0; 2.28 + size_t max = s2.size(); 2.29 + while ( i != cursor ) 2.30 + s1.push( s2.pop() ); 2.31 + s1.push( c ); 2.32 + while ( i < max ) 2.33 + s1.push( s2.pop() ); 2.34 + } 2.35 + } 2.36 + 2.37 +char Buffer::get( void ) { 2.38 + if ( use_s1 ) 2.39 + return s1.find( cursor ); // Need to add overloaded T find( size_t k) to Stack 2.40 + else 2.41 + return s2.find( cursor ); 2.42 + } 2.43 + 2.44 +char Buffer::delete( void ) { 2.45 + if ( use_s1 ) { 2.46 + size_t i = 0; 2.47 + size_t max = s1.size(); 2.48 + while ( i != cursor ) 2.49 + s2.push( s1.pop() ); 2.50 + ++i; 2.51 + while ( i < max ) 2.52 + s2.push( s1.pop() ); 2.53 + } 2.54 + else { 2.55 + size_t i = 0; 2.56 + size_t max = s2.size(); 2.57 + while ( i != cursor ) 2.58 + s1.push( s2.pop() ); 2.59 + ++i; 2.60 + while ( i < max ) 2.61 + s1.push( s2.pop() ); 2.62 + } 2.63 + 2.64 + if ( cursor > size() ) 2.65 + cursor = size(); 2.66 + } 2.67 + 2.68 +void Buffer::left( size_t k ) { 2.69 + if ( cursor < k ) 2.70 + cursor = 0; 2.71 + else 2.72 + cursor -= k; 2.73 + } 2.74 + 2.75 +void Buffer::right( size_t k ) { 2.76 + if ( size() - cursor < k ) 2.77 + cursor = size(); 2.78 + else 2.79 + cursor += k; 2.80 + } 2.81 + 2.82 +size_t Buffer::size( void ) { 2.83 + if ( use_s1 ) 2.84 + return s1.size(); 2.85 + else 2.86 + return s2.size(); 2.87 + }
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/algs4-c++/src/Buffer.hpp Tue Jun 23 11:02:31 2015 -0500 3.3 @@ -0,0 +1,34 @@ 3.4 +// Sedgewick and Wayne, Algorithms, 4th ed. problem 1.3.44 3.5 + 3.6 +// Two stack implementation. I don't know why anyone would actually want to use 3.7 +// an implmentation like this, but it's what they suggested in the problem. I 3.8 +// guess it's just an "exercise" after all. 3.9 + 3.10 + 3.11 +#ifndef BUFFER_HPP 3.12 +#define BUFFER_HPP 3.13 + 3.14 +#include <cstddef> 3.15 + 3.16 +#include "Stack.hpp" 3.17 + 3.18 +class Buffer { 3.19 +public: 3.20 + Buffer( void ); 3.21 + 3.22 + void insert( char c ); 3.23 + char get( void ); 3.24 + char delete( void ); 3.25 + void left( size_t k ); 3.26 + void right( size_t k ); 3.27 + size_t size( void ); 3.28 + 3.29 +private: 3.30 + size_t cursor; 3.31 + 3.32 + bool use_s1; 3.33 + Stack<char> s1; 3.34 + Stack<char> s2; 3.35 + }; 3.36 + 3.37 +#endif