From 30edad3557c32cac331821d94d053e991b545820 Mon Sep 17 00:00:00 2001 From: Patrik Gornicz Date: Tue, 4 Aug 2009 00:07:38 -0400 Subject: [PATCH] fixed many missed cases in Queue --- lib/include/bear/Queue.h | 207 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 147 insertions(+), 60 deletions(-) diff --git a/lib/include/bear/Queue.h b/lib/include/bear/Queue.h index d224cd8..cbfe641 100644 --- a/lib/include/bear/Queue.h +++ b/lib/include/bear/Queue.h @@ -17,43 +17,46 @@ namespace bear { - /// ***** Header Class ***** + /// ***** Header Class ***** - template < class Item > - class Queue - { - public: - Queue(); - ~Queue() {} + template < class Item > + class Queue + { + public: + Queue(); + ~Queue() {} + + void init(unsigned int uiStartSize = 2, unsigned int uiSizeMultiplier = 2); + void fini(); - void init(unsigned int uiStartSize = 2, unsigned int uiSizeMultiplier = 2); - void fini(); + void alloc(unsigned int uiSize); + void trim(); - void alloc(unsigned int uiSize); - void trim(); + bool isEmpty() const; - bool isEmpty() const; + const Item& getFront() const; + const Item& getBack() const; - const Item& getFront() const; - const Item& getBack() const; + void pushFront(const Item& i); + void pushBack(const Item& i); - void pushFront(const Item& i); - void pushBack(const Item& i); + void popFront(); + void popBack(); - private: - unsigned int getLength() const; - unsigned int getSpaceNeeded(unsigned int uiSize) const; + private: + unsigned int getLength() const; + unsigned int getSpaceNeeded(unsigned int uiSize) const; - unsigned int m_uiStartSize; - unsigned int m_uiSizeMultiplier; + unsigned int m_uiStartSize; + unsigned int m_uiSizeMultiplier; - unsigned int m_uiAllocated; - Item* m_pArrayItems; - bool m_fIsEmpty; + unsigned int m_uiAllocated; + Item* m_pArrayItems; + bool m_fIsEmpty; - unsigned int m_uiHead; - unsigned int m_uiTail; - }; + unsigned int m_uiHead; + unsigned int m_uiTail; + }; } // namespace bear @@ -73,38 +76,38 @@ bear::Queue::Queue() template < class Item > void bear::Queue::init ( - unsigned int uiStartSize, - unsigned int uiSizeMultiplier + unsigned int uiStartSize, + unsigned int uiSizeMultiplier ) { - m_uiStartSize = uiStartSize; - m_uiSizeMultiplier = uiSizeMultiplier; + m_uiStartSize = uiStartSize; + m_uiSizeMultiplier = uiSizeMultiplier; - m_uiAllocated = 0; + m_uiAllocated = 0; - bear::DASSERT(NULL == m_pArrayItems); // this better be the case - m_pArrayItems = NULL; + bear::DASSERT(NULL == m_pArrayItems); // this better be the case + m_pArrayItems = NULL; - m_fIsEmpty = true; + m_fIsEmpty = true; - m_uiHead = 0; - m_uiTail = 0; + m_uiHead = 0; + m_uiTail = 0; } template < class Item > void bear::Queue::fini() { - m_uiStartSize = 0; - m_uiSizeMultiplier = 0; + m_uiStartSize = 0; + m_uiSizeMultiplier = 0; - m_uiAllocated = 0; + m_uiAllocated = 0; - delete m_pArrayItems; - m_pArrayItems = NULL; + if(NULL != m_pArrayItems) delete m_pArrayItems; + m_pArrayItems = NULL; - m_fIsEmpty = true; + m_fIsEmpty = true; - m_uiHead = 0; - m_uiTail = 0; + m_uiHead = 0; + m_uiTail = 0; } template < class Item > @@ -115,28 +118,45 @@ void bear::Queue::alloc(unsigned int uiSize) unsigned int uiOldLength = getLength(); unsigned int uiOldAllocated = m_uiAllocated; - Item* pOldArrayItems = m_pArrayItems; + Item * pOldArrayItems = m_pArrayItems; unsigned int uiOldHead = m_uiHead; - unsigned int uiOldTail = m_uiTail; + //unsigned int uiOldTail = m_uiTail; m_uiAllocated = 0; m_pArrayItems = NULL; - m_uiHead = -1; - m_uiTail = -1; + m_uiHead = 0; + m_uiTail = 0; unsigned int uiNewAllocated = uiSize; - Item* pNewArrayItems = new Item[uiNewAllocated]; + Item * pNewArrayItems = new Item[uiNewAllocated]; unsigned int uiNewHead = 0; unsigned int uiNewTail = uiOldLength - 1; - for(unsigned int uiNewIndex = uiNewHead; uiNewIndex <= uiNewTail; uiNewIndex++) + if(NULL == pOldArrayItems) { - unsigned int iOldIndex = mod(uiNewIndex + uiOldHead, uiOldAllocated); - bear::DASSERT(iOldIndex <= uiOldTail); + // santiy check + bear::DASSERT(0 == uiOldLength); + bear::DASSERT(true == m_fIsEmpty); - pNewArrayItems[uiNewIndex] = pOldArrayItems[iOldIndex]; + uiNewTail = 0; + + // Nothing to copy over } + else + { + // Copy old items into new array + for(unsigned int uiNewIndex = uiNewHead; uiNewIndex <= uiNewTail; uiNewIndex++) + { + unsigned int uiOldIndex = mod(uiNewIndex + uiOldHead, uiOldAllocated); + bear::DASSERT(uiOldIndex <= uiOldAllocated); + + bear::DASSERT(NULL != pOldArrayItems); + pNewArrayItems[uiNewIndex] = pOldArrayItems[uiOldIndex]; + } + delete pOldArrayItems; + } + m_uiAllocated = uiNewAllocated; m_pArrayItems = pNewArrayItems; m_uiHead = uiNewHead; @@ -148,20 +168,23 @@ void bear::Queue::alloc(unsigned int uiSize) template < class Item > void bear::Queue::trim() { - + bear::DASSERT(false); // Not Implemented } template < class Item > bool bear::Queue::isEmpty() const { - return m_fIsEmpty; + return m_fIsEmpty; } template < class Item > const Item& bear::Queue::getFront() const { // This is very bad. Fix your code - DASSERT(!isEmpty()); + bear::DASSERT(!isEmpty()); + + // sanity check + bear::DASSERT(m_uiHead <= m_uiAllocated); return m_pArrayItems[m_uiHead]; } @@ -170,7 +193,10 @@ template < class Item > const Item& bear::Queue::getBack() const { // This is very bad. Fix your code - DASSERT(!isEmpty()); + bear::DASSERT(!isEmpty()); + + // sanity check + bear::DASSERT(m_uiTail <= m_uiAllocated); return m_pArrayItems[m_uiTail]; } @@ -181,7 +207,17 @@ void bear::Queue::pushFront(const Item& i) // Make sure we have the space to add an item alloc( getSpaceNeeded( getLength() + 1 ) ); - m_uiHead = mod( m_uiHead + 1, m_uiAllocated ); + if(isEmpty()) + { + m_fIsEmpty = false; + + m_uiHead = 0; + m_uiTail = 0; + } + else + { + m_uiHead = mod( m_uiHead - 1, m_uiAllocated ); + } m_pArrayItems[m_uiHead] = i; } @@ -192,11 +228,57 @@ void bear::Queue::pushBack(const Item& i) // Make sure we have the space to add an item alloc( getSpaceNeeded( getLength() + 1 ) ); - m_uiTail = mod( m_uiTail + 1, m_uiAllocated ); + if(isEmpty()) + { + m_fIsEmpty = false; + + m_uiHead = 0; + m_uiTail = 0; + } + else + { + m_uiTail = mod( m_uiTail + 1, m_uiAllocated ); + } m_pArrayItems[m_uiTail] = i; } +template < class Item > +void bear::Queue::popFront() +{ + bear::DASSERT(!isEmpty()); + + if( m_uiHead == m_uiTail ) + { + m_fIsEmpty = true; + + m_uiHead = 0; + m_uiTail = 0; + } + else + { + m_uiHead = mod( m_uiHead + 1, m_uiAllocated ); + } +} + +template < class Item > +void bear::Queue::popBack() +{ + bear::DASSERT(!isEmpty()); + + if( m_uiHead == m_uiTail ) + { + m_fIsEmpty = true; + + m_uiHead = 0; + m_uiTail = 0; + } + else + { + m_uiTail = mod( m_uiTail - 1, m_uiAllocated ); + } +} + template < class Item > unsigned int bear::Queue::getLength() const @@ -216,6 +298,11 @@ unsigned int bear::Queue::getSpaceNeeded(unsigned int uiSize) const { unsigned int uiNewSize = m_uiAllocated; + if(0 == uiNewSize) + { + uiNewSize = m_uiStartSize; + } + while ( uiNewSize < uiSize ) { uiNewSize *= m_uiSizeMultiplier; -- 2.10.2