# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1435005505 18000
# Node ID 86281e8f24ba8e17985b8ba90468f85118da5e26
# Parent  60fb857124823c5b07c69ba3aa489d7b9909fb45
1.3.39 CircularQueue (ring buffer)

diff -r 60fb85712482 -r 86281e8f24ba algs4-c++/1.3.39
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/1.3.39	Mon Jun 22 15:38:25 2015 -0500
@@ -0,0 +1,1 @@
+src/CircularQueue.hpp
\ No newline at end of file
diff -r 60fb85712482 -r 86281e8f24ba algs4-c++/src/CircularQueue.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/CircularQueue.cpp	Mon Jun 22 15:38:25 2015 -0500
@@ -0,0 +1,37 @@
+// g++ -std=c++11 CircularQueue.cpp
+
+#include <cstddef>
+#include <cstdlib>
+#include <iostream>
+
+#include "CircularQueue.hpp"
+
+int main( int argc, char **argv ) {
+    size_t max;
+    std::cin >> max;
+    if ( ! std::cin.good() ) {
+        std::cerr << "You must enter a size for the queue." << std::endl;
+        exit( EXIT_FAILURE );
+        }
+    
+    CircularQueue<long> queue( max );
+
+    long i;
+    while ( ! std::cin.eof() ) {
+        std::cin >> i;
+        if ( std::cin.good() ) {
+            if ( queue.full() )
+                std::cout << "Queue is full: old data lost" << std::endl;
+            queue.enqueue(i);
+            }
+        }
+
+    std::cout << "Queue has " << queue.size() << " entries." << std::endl;
+
+    std::cout << "Dequeuing entries:" << std::endl;
+    while ( ! queue.empty() ) {
+        long i = queue.dequeue();
+        std::cout << i << std::endl;
+        }
+
+    }
diff -r 60fb85712482 -r 86281e8f24ba algs4-c++/src/CircularQueue.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/CircularQueue.hpp	Mon Jun 22 15:38:25 2015 -0500
@@ -0,0 +1,85 @@
+#ifndef CIRCULARQUEUE_HPP
+
+#define CIRCULARQUEUE_HPP
+
+#include <cassert>
+#include <cstddef>
+#include <vector>
+
+template <typename T>
+class CircularQueue {
+public:
+    CircularQueue ( size_t max );
+
+    void enqueue( T &item);
+    T dequeue( void );
+
+    bool empty( void );
+    bool full( void );
+    size_t size( void );
+
+private:
+    std::vector<T> data;
+    size_t first;
+    size_t end;
+    size_t N;
+    };
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+CircularQueue<T>::CircularQueue( size_t max ) :
+    first (0),
+    end (0),
+    N (0)
+    {
+    data.resize( max );
+    }
+
+template <typename T>
+void CircularQueue<T>::enqueue( T &item ) {
+    data[end] = item;
+    if ( N < data.size() )
+        ++N;
+    else {
+        ++first;
+        if ( first > data.size() )
+            first = 0;
+        }
+    ++end;
+    if ( end == data.size()  )
+        end = 0;
+    }
+
+template <typename T>
+T CircularQueue<T>::dequeue( void ) {
+    assert( N > 0 );
+    T item = data[first];
+    if ( N > 0 )
+        --N;
+    ++first;
+    if ( first == data.size() )
+        first = 0;
+
+    return item;
+    }
+
+template <typename T>
+bool CircularQueue<T>::empty( void ) {
+    return ( N == 0 );
+    }
+
+template <typename T>
+bool CircularQueue<T>::full( void ) {
+    return ( N == data.size() );
+    }
+
+template <typename T>
+size_t CircularQueue<T>::size( void ) {
+    return N;
+    }
+
+
+
+#endif