include/Tree/FIFO.hpp

Go to the documentation of this file.

#ifndef hpp_CPP_FIFO_CPP_hpp
#define hpp_CPP_FIFO_CPP_hpp


// Need realloc
#include <malloc.h>
// Need new operator too
#include <new>

#ifdef _MSC_VER
#pragma warning (disable:4786)
#endif

namespace Stack
{
    namespace PlainOldData
    {
        template <typename T> 
        class FIFO
        {
        public:
            inline FIFO() : array(NULL), currentSize(0), currentPos(0), allocatedSize(0)    { }
            inline FIFO(const FIFO & other) : array(NULL), currentSize(0), currentPos(0), allocatedSize(0) { *this = other; }
            ~FIFO() { Clear(); }

        // Interface
        public:
            inline void Reset() { currentSize = 0; allocatedSize = 0; currentPos = 0; array = NULL; }
            inline T & Pop()    { if (currentSize == 0) return defaultElement; T& ref = *(T*)&array[currentPos]; currentPos += sizeof(T); currentSize --; return ref; }
            inline void Push(const T & ref) 
            {
                // Check if the object can be freed
                if (currentSize == 0 && currentPos) Clear();
                if (currentSize >= allocatedSize || currentPos >= (allocatedSize - currentSize) * sizeof(T))
                {
                    // Need to realloc the data
                    if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2;
                    // This will not work with type other than POD
                    array = (uint8*)realloc(array, allocatedSize*sizeof(T));
                    if (array == NULL) { Reset(); return; }
                }
                // Copy the data
                new(&array[currentSize * sizeof(T) + currentPos]) T(ref);
                currentSize ++;
            }

            inline const FIFO& operator = ( const FIFO <T>& fifo)
            {
                Clear();

                for (size_t i = 0; i < fifo.currentSize; i++)
                    Push(*(T*)&fifo.array[i * sizeof(T) + fifo.currentPos]);

                return *this;
            }
            
            inline size_t getSize() const { return currentSize; }
            inline bool Forget(const T& avoidDeleting) { return false;  }

        private:
            inline void Clear() { while (currentSize)   { currentSize --; T * pPtr = (T*)&array[currentSize * sizeof(T) + currentPos]; pPtr->~T(); }
                                  while (currentPos)    { currentPos -= sizeof(T); T * pPtr = (T*)&array[currentPos]; pPtr->~T(); }
                                    if (array != NULL) realloc(array, 0);   Reset(); }
        private:
            uint8 *                                                 array;
            size_t                                                  currentPos;
            size_t                                                  currentSize;
            size_t                                                  allocatedSize;
            static T                                                defaultElement;
        };
        template <typename T> T FIFO<T>::defaultElement = 0;
    }

    namespace WithClone
    {
        template <typename T> 
        class FIFO
        {
        private:
            enum { elementSize = sizeof(T*) };
        public:
            inline FIFO() : array(NULL), currentSize(0), currentPos(0), allocatedSize(0)    { }
            inline FIFO(const FIFO & other) : array(NULL), currentSize(0), currentPos(0), allocatedSize(0) { *this = other; }
            ~FIFO()     { Clear(); }

        // Interface
        public:
            inline void Reset() { currentSize = 0; allocatedSize = 0; currentPos = 0; array = NULL; }
            inline T * Pop()    { if (currentSize == 0) return NULL; T* ref = array[currentPos]; currentPos ++; currentSize --; return ref; }
            inline void Push(T * ref) 
            {
                // Check if the object can be freed
                if (currentSize == 0 && currentPos) Clear(ref);
                if (currentSize >= allocatedSize)
                {
                    // Need to realloc the data
                    if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2;
                    // This will not work with type other than POD
                    array = (T**)realloc(array, allocatedSize*elementSize);
                    if (array == NULL) { Reset(); return; }
                }
                // Copy the data
                array[currentSize + currentPos] = ref;
                currentSize ++;
            }

            inline const FIFO& operator = ( const FIFO <T>& fifo)
            {
                Clear();
                for (size_t i = 0; i < fifo.currentSize; i++) Push(fifo.array[i + fifo.currentPos]->clone());
                return *this;
            }
            
            inline size_t getSize() const { return currentSize; }
            inline bool Forget(T* avoidDeleting = NULL) 
            {   bool isFound = false;
                size_t pos = 0; while (pos < currentPos) { if (array[pos] == avoidDeleting) { array[pos] = NULL; isFound = true; break; } pos ++; }
                return isFound; }

        private:
            inline void Clear(T * ref = NULL) 
            {   while (currentSize) { currentSize --; T * pPtr = array[currentSize + currentPos]; if (pPtr != ref) delete pPtr; }
                while (currentPos)  { currentPos --; T * pPtr = array[currentPos]; if (pPtr != ref) delete pPtr; }
                if (array != NULL) realloc(array, 0);   Reset(); }
        private:
            T **                                                    array;
            size_t                                                  currentPos;
            size_t                                                  currentSize;
            size_t                                                  allocatedSize;
        };
    }
}


#endif

(C) An X-Ryl669 project 2007

This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is