Queue.h

Go to the documentation of this file.

/***************************************************************
 
 Mini Grand Challenge 2010
 Pennsylvania State University - Robotics Club
 Learn more at www.psurobotics.org
 Protected by the GNU General Public License
 
 This source file is developed and maintained by:
 + Jeremy Bridon jgbridon@gmail.com
 
 File: Queue.h
 Desc: Custom-build data structure for use and support of the
 dictionary data structure.
 
***************************************************************/

// Inclusion guard
#ifndef __QUEUE_H_
#define __QUEUE_H_

// Includes
#include "Utilities.h"
#include "List.h"

template <typename Type> class Queue
{
public:

        Queue(int size = DEFAULT_PAGE_SIZE, int PageSize = DEFAULT_PAGE_SIZE)
                : data(size) // Create the list structure
        {
                // Set the page size
                pageSize = PageSize;
                if(pageSize <= 0)
                        pageSize = DEFAULT_PAGE_SIZE;

                // Set the default variables
                front = 0;
                back = data.GetSize() - 1;
                count = 0;
        }

        ~Queue()
        {
                // Nothing to do
        }

        Type Enqueue(Type newData)
        {
                // If last collides with first
                if(count >= data.GetSize())
                {
                        // Grow by a page
                        int originalSize = data.GetSize();
                        data.Resize(data.GetSize() + pageSize);

                        // Move data only if the front pointer is greater than the back pointer (wrapping)
                        if(front > back)
                        {
                                // Move all elements from the front index pointer to the end of the current page block one full new page to the right
                                for(int i = front; i < originalSize; i++)
                                        data[i + pageSize] = data[i];
                                front += pageSize;
                        }
                }

                // Find the next index
                back = (back + 1) % data.GetSize();

                // Grow the last index and insert data
                data[back] = newData;
                count++;

                // Return the element we have added
                return newData;
        }

        Type Dequeue()
        {
                // Make sure there is data
                Assert(!IsEmpty(), "Attempting to access empty queue.");

                // Return the data
                Type temp = data[front];
                front = (front + 1) % data.GetSize();
                count--; 

                // Return temp
                return temp;
        }
        
        int GetSize()
        {
                return count;
        }
        
        bool IsEmpty()
        {
                if(count <= 0)
                        return true;
                return false;
        }

private:

        static const int DEFAULT_PAGE_SIZE = 16;

        List<Type> data;        

        int front;                      
        int back;                       
        int count;                      

        int pageSize;           

};

#endif

---