tFixedSizeDeque.h

Engine/source/core/util/tFixedSizeDeque.h

More...

Classes:

Detailed Description

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _TFIXEDSIZEDEQUE_H_
 25#define _TFIXEDSIZEDEQUE_H_
 26
 27#ifndef _PLATFORM_H_
 28#  include "platform/platform.h"
 29#endif
 30
 31
 32/// A double-ended queue with a fixed number of entries set at
 33/// construction time.  Implemented as an array.
 34///
 35/// @param T Element type of the queue.
 36template< typename T >
 37class FixedSizeDeque
 38{
 39   public:
 40
 41      /// Type for elements stored in the deque.
 42      typedef T ValueType;
 43
 44   protected:
 45
 46      ///
 47      U32 mBufferSize;
 48
 49      ///
 50      U32 mSize;
 51
 52      /// Index
 53      U32 mStart;
 54
 55      ///
 56      U32 mEnd;
 57
 58      ///
 59      ValueType* mBuffer;
 60
 61   public:
 62
 63      ///
 64      FixedSizeDeque( U32 bufferSize )
 65         : mBufferSize( bufferSize ), mSize( 0 ), mStart( 0 ), mEnd( 0 )
 66      {
 67         // Don't use new() so we don't get a buffer full of instances.
 68         mBuffer = ( ValueType* ) dMalloc( sizeof( ValueType ) * bufferSize );
 69      }
 70      
 71      ~FixedSizeDeque()
 72      {
 73         // Destruct remaining instances.
 74
 75         while( mSize )
 76         {
 77            destructInPlace( &mBuffer[ mStart ] );
 78            mStart ++;
 79            if( mStart == mBufferSize )
 80               mStart = 0;
 81            mSize --;
 82         }
 83
 84         // Free buffer.
 85         dFree( mBuffer );
 86      }
 87
 88      ///
 89      bool isEmpty() const { return !size(); }
 90
 91      ///
 92      U32 size() const
 93      {
 94         return mSize;
 95      }
 96
 97      ///
 98      U32 capacity() const
 99      {
100         return ( mBufferSize - size() );
101      }
102      
103      ///
104      void clear()
105      {
106         while( size() )
107            popFront();
108      }
109
110      /// Return the leftmost value in the queue.
111      ValueType front() const
112      {
113         AssertFatal( !isEmpty(), "FixedSizeDeque::front() - queue is empty" );
114         return mBuffer[ mStart ];
115      }
116
117      /// Return the rightmost value in the queue.
118      ValueType back() const
119      {
120         AssertFatal( !isEmpty(), "FixedSizeDeque::back() - queue is empty" );
121         if( !mEnd )
122            return mBuffer[ mBufferSize - 1 ];
123         else
124            return mBuffer[ mEnd - 1 ];
125      }
126
127      /// Prepend "value" to the left end of the queue.
128      void pushFront( const ValueType& value )
129      {
130         AssertFatal( capacity() != 0, "FixedSizeDeque::pushFront() - queue is full" );
131         if( mStart == 0 )
132            mStart = mBufferSize - 1;
133         else
134            mStart --;
135         mBuffer[ mStart ] = value;
136         mSize ++;
137      }
138
139      /// Append "value" to the right end of the queue.
140      void pushBack( const ValueType& value )
141      {
142         AssertFatal( capacity() != 0, "FixedSizeDeque::pushBack() - queue is full" );
143         mBuffer[ mEnd ] = value;
144         mEnd ++;
145         if( mEnd == mBufferSize )
146            mEnd = 0;
147         mSize ++;
148      }
149
150      /// Remove and return the leftmost value in the queue.
151      ValueType popFront()
152      {
153         AssertFatal( !isEmpty(), "FixedSizeDeque::popFront() - queue is empty" );
154         ValueType value = mBuffer[ mStart ];
155         destructInPlace( &mBuffer[ mStart ] );
156         
157         mStart ++;
158         if( mStart == mBufferSize )
159            mStart = 0;
160
161         mSize --;
162         return value;
163      }
164
165      /// Remove and return the rightmost value in the queue.
166      ValueType popBack()
167      {
168         AssertFatal( !isEmpty(), "FixedSizeDeque::popBack() - queue is empty" );
169         
170         U32 idx;
171         if( !mEnd )
172            idx = mBufferSize - 1;
173         else
174            idx = mEnd - 1;
175
176         ValueType value = mBuffer[ idx ];
177         destructInPlace( &mBuffer[ idx ] );
178
179         mEnd = idx;
180
181         mSize --;
182         return value;
183      }
184};
185
186#endif // _TFIXEDSIZEDEQUE_H_
187