Mercurial > projects > hoofbaby
view deps/Platinum/ThirdParty/Neptune/Source/Core/NptArray.h @ 0:3425707ddbf6
Initial import (hopefully this mercurial stuff works...)
author | fraserofthenight |
---|---|
date | Mon, 06 Jul 2009 08:06:28 -0700 |
parents | |
children |
line wrap: on
line source
/***************************************************************** | | Neptune - Arrays | | Copyright (c) 2002-2008, Axiomatic Systems, LLC. | All rights reserved. | | Redistribution and use in source and binary forms, with or without | modification, are permitted provided that the following conditions are met: | * Redistributions of source code must retain the above copyright | notice, this list of conditions and the following disclaimer. | * Redistributions in binary form must reproduce the above copyright | notice, this list of conditions and the following disclaimer in the | documentation and/or other materials provided with the distribution. | * Neither the name of Axiomatic Systems nor the | names of its contributors may be used to endorse or promote products | derived from this software without specific prior written permission. | | THIS SOFTWARE IS PROVIDED BY AXIOMATIC SYSTEMS ''AS IS'' AND ANY | EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | DISCLAIMED. IN NO EVENT SHALL AXIOMATIC SYSTEMS BE LIABLE FOR ANY | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND | ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ****************************************************************/ #ifndef _NPT_ARRAY_H_ #define _NPT_ARRAY_H_ /*---------------------------------------------------------------------- | includes +---------------------------------------------------------------------*/ #include "NptConfig.h" #if defined(NPT_CONFIG_HAVE_NEW_H) #include <new> #endif #include "NptTypes.h" #include "NptResults.h" /*---------------------------------------------------------------------- | constants +---------------------------------------------------------------------*/ const int NPT_ARRAY_INITIAL_MAX_SIZE = 128; // bytes /*---------------------------------------------------------------------- | NPT_Array +---------------------------------------------------------------------*/ template <typename T> class NPT_Array { public: // types typedef T Element; typedef T* Iterator; // methods NPT_Array<T>(): m_Capacity(0), m_ItemCount(0), m_Items(0) {} explicit NPT_Array<T>(NPT_Cardinal count); NPT_Array<T>(NPT_Cardinal count, const T& item); NPT_Array<T>(const T* items, NPT_Cardinal item_count); ~NPT_Array<T>(); NPT_Array<T>(const NPT_Array<T>& copy); NPT_Array<T>& operator=(const NPT_Array<T>& copy); bool operator==(const NPT_Array<T>& other) const; bool operator!=(const NPT_Array<T>& other) const; NPT_Cardinal GetItemCount() const { return m_ItemCount; } NPT_Result Add(const T& item); T& operator[](NPT_Ordinal pos) { return m_Items[pos]; } const T& operator[](NPT_Ordinal pos) const { return m_Items[pos]; } NPT_Result Erase(Iterator which); NPT_Result Erase(NPT_Ordinal which) { return Erase(&m_Items[which]); } NPT_Result Erase(Iterator first, Iterator last); NPT_Result Erase(NPT_Ordinal first, NPT_Ordinal last) { return Erase(&m_Items[first], &m_Items[last]); } NPT_Result Insert(Iterator where, const T& item, NPT_Cardinal count = 1); NPT_Result Reserve(NPT_Cardinal count); NPT_Cardinal GetCapacity() const { return m_Capacity; } NPT_Result Resize(NPT_Cardinal count); NPT_Result Resize(NPT_Cardinal count, const T& fill); NPT_Result Clear(); bool Contains(const T& data) const; Iterator GetFirstItem() const { return m_ItemCount?&m_Items[0]:NULL; } Iterator GetLastItem() const { return m_ItemCount?&m_Items[m_ItemCount-1]:NULL; } Iterator GetItem(NPT_Ordinal n) { return n<m_ItemCount?&m_Items[n]:NULL; } // template list operations // keep these template members defined here because MSV6 does not let // us define them later template <typename X> NPT_Result Apply(const X& function) const { for (unsigned int i=0; i<m_ItemCount; i++) function(m_Items[i]); return NPT_SUCCESS; } template <typename X, typename P> NPT_Result ApplyUntil(const X& function, const P& predicate, bool* match = NULL) const { for (unsigned int i=0; i<m_ItemCount; i++) { NPT_Result return_value; if (predicate(function(m_Items[i]), return_value)) { if (match) *match = true; return return_value; } } if (match) *match = false; return NPT_SUCCESS; } template <typename X> T* Find(const X& predicate, NPT_Ordinal n=0, NPT_Ordinal* pos = NULL) const { if (pos) *pos = -1; for (unsigned int i=0; i<m_ItemCount; i++) { if (predicate(m_Items[i])) { if (pos) *pos = i; if (n == 0) return &m_Items[i]; --n; } } return NULL; } protected: // methods T* Allocate(NPT_Cardinal count, NPT_Cardinal& allocated); // members NPT_Cardinal m_Capacity; NPT_Cardinal m_ItemCount; T* m_Items; }; /*---------------------------------------------------------------------- | NPT_Array<T>::NPT_Array<T> +---------------------------------------------------------------------*/ template <typename T> inline NPT_Array<T>::NPT_Array(NPT_Cardinal count) : m_Capacity(0), m_ItemCount(0), m_Items(0) { Reserve(count); } /*---------------------------------------------------------------------- | NPT_Array<T>::NPT_Array<T> +---------------------------------------------------------------------*/ template <typename T> inline NPT_Array<T>::NPT_Array(const NPT_Array<T>& copy) : m_Capacity(0), m_ItemCount(0), m_Items(0) { Reserve(copy.GetItemCount()); for (NPT_Ordinal i=0; i<copy.m_ItemCount; i++) { new ((void*)&m_Items[i]) T(copy.m_Items[i]); } m_ItemCount = copy.m_ItemCount; } /*---------------------------------------------------------------------- | NPT_Array<T>::NPT_Array<T> +---------------------------------------------------------------------*/ template <typename T> inline NPT_Array<T>::NPT_Array(NPT_Cardinal count, const T& item) : m_Capacity(0), m_ItemCount(count), m_Items(0) { Reserve(count); for (NPT_Ordinal i=0; i<count; i++) { new ((void*)&m_Items[i]) T(item); } } /*---------------------------------------------------------------------- | NPT_Array<T>::NPT_Array<T> +---------------------------------------------------------------------*/ template <typename T> inline NPT_Array<T>::NPT_Array(const T* items, NPT_Cardinal item_count) : m_Capacity(0), m_ItemCount(item_count), m_Items(0) { Reserve(item_count); for (NPT_Ordinal i=0; i<item_count; i++) { new ((void*)&m_Items[i]) T(items[i]); } } /*---------------------------------------------------------------------- | NPT_Array<T>::~NPT_Array<T> +---------------------------------------------------------------------*/ template <typename T> inline NPT_Array<T>::~NPT_Array() { // remove all items Clear(); // free the memory ::operator delete((void*)m_Items); } /*---------------------------------------------------------------------- | NPT_Array<T>::operator= +---------------------------------------------------------------------*/ template <typename T> NPT_Array<T>& NPT_Array<T>::operator=(const NPT_Array<T>& copy) { // do nothing if we're assigning to ourselves if (this == ©) return *this; // destroy all elements Clear(); // copy all elements from the other object Reserve(copy.GetItemCount()); m_ItemCount = copy.m_ItemCount; for (NPT_Ordinal i=0; i<copy.m_ItemCount; i++) { new ((void*)&m_Items[i]) T(copy.m_Items[i]); } return *this; } /*---------------------------------------------------------------------- | NPT_Array<T>::Clear +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Clear() { // destroy all items for (NPT_Ordinal i=0; i<m_ItemCount; i++) { m_Items[i].~T(); } m_ItemCount = 0; return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Allocate +---------------------------------------------------------------------*/ template <typename T> T* NPT_Array<T>::Allocate(NPT_Cardinal count, NPT_Cardinal& allocated) { if (m_Capacity) { allocated = 2*m_Capacity; } else { // start with just enough elements to fill // NPT_ARRAY_INITIAL_MAX_SIZE worth of memory allocated = NPT_ARRAY_INITIAL_MAX_SIZE/sizeof(T); if (allocated == 0) allocated = 1; } if (allocated < count) allocated = count; // allocate the items return (T*)::operator new(allocated*sizeof(T)); } /*---------------------------------------------------------------------- | NPT_Array<T>::Reserve +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Reserve(NPT_Cardinal count) { if (count <= m_Capacity) return NPT_SUCCESS; // (re)allocate the items NPT_Cardinal new_capacity; T* new_items = Allocate(count, new_capacity); if (new_items == NULL) { return NPT_ERROR_OUT_OF_MEMORY; } if (m_ItemCount && m_Items) { for (unsigned int i=0; i<m_ItemCount; i++) { // construct the copy new ((void*)&new_items[i])T(m_Items[i]); // destroy the item m_Items[i].~T(); } } ::operator delete((void*)m_Items); m_Items = new_items; m_Capacity = new_capacity; return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Add +---------------------------------------------------------------------*/ template <typename T> inline NPT_Result NPT_Array<T>::Add(const T& item) { // ensure capacity NPT_Result result = Reserve(m_ItemCount+1); if (result != NPT_SUCCESS) return result; // store the item new ((void*)&m_Items[m_ItemCount++]) T(item); return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Erase +---------------------------------------------------------------------*/ template <typename T> inline NPT_Result NPT_Array<T>::Erase(Iterator which) { return Erase(which, which); } /*---------------------------------------------------------------------- | NPT_Array<T>::Erase +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Erase(Iterator first, Iterator last) { // check parameters if (first == NULL || last == NULL) return NPT_ERROR_INVALID_PARAMETERS; // check the bounds NPT_Ordinal first_index = (NPT_Ordinal)(NPT_POINTER_TO_LONG(first-m_Items)); NPT_Ordinal last_index = (NPT_Ordinal)(NPT_POINTER_TO_LONG(last-m_Items)); if (first_index >= m_ItemCount || last_index >= m_ItemCount || first_index > last_index) { return NPT_ERROR_INVALID_PARAMETERS; } // shift items to the left NPT_Cardinal interval = last_index-first_index+1; NPT_Cardinal shifted = m_ItemCount-last_index-1; for (NPT_Ordinal i=first_index; i<first_index+shifted; i++) { m_Items[i] = m_Items[i+interval]; } // destruct the remaining items for (NPT_Ordinal i=first_index+shifted; i<m_ItemCount; i++) { m_Items[i].~T(); } // update the item count m_ItemCount -= interval; return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Insert +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Insert(Iterator where, const T& item, NPT_Cardinal repeat) { // check bounds NPT_Ordinal where_index = where?((NPT_Ordinal)NPT_POINTER_TO_LONG(where-m_Items)):m_ItemCount; if (where > &m_Items[m_ItemCount] || repeat == 0) return NPT_ERROR_INVALID_PARAMETERS; NPT_Cardinal needed = m_ItemCount+repeat; if (needed > m_Capacity) { // allocate more memory NPT_Cardinal new_capacity; T* new_items = Allocate(needed, new_capacity); if (new_items == NULL) return NPT_ERROR_OUT_OF_MEMORY; m_Capacity = new_capacity; // move the items before the insertion point for (NPT_Ordinal i=0; i<where_index; i++) { new((void*)&new_items[i])T(m_Items[i]); m_Items[i].~T(); } // move the items after the insertion point for (NPT_Ordinal i=where_index; i<m_ItemCount; i++) { new((void*)&new_items[i+repeat])T(m_Items[i]); m_Items[i].~T(); } // use the new items instead of the current ones ::operator delete((void*)m_Items); m_Items = new_items; } else { // shift items after the insertion point to the right for (NPT_Ordinal i=m_ItemCount; i>where_index; i--) { new((void*)&m_Items[i+repeat-1])T(m_Items[i-1]); m_Items[i-1].~T(); } } // insert the new items for (NPT_Cardinal i=where_index; i<where_index+repeat; i++) { new((void*)&m_Items[i])T(item); } // update the item count m_ItemCount += repeat; return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Resize +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Resize(NPT_Cardinal size) { if (size < m_ItemCount) { // shrink for (NPT_Ordinal i=size; i<m_ItemCount; i++) { m_Items[i].~T(); } m_ItemCount = size; } else if (size > m_ItemCount) { return Resize(size, T()); } return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Resize +---------------------------------------------------------------------*/ template <typename T> NPT_Result NPT_Array<T>::Resize(NPT_Cardinal size, const T& fill) { if (size < m_ItemCount) { return Resize(size); } else if (size > m_ItemCount) { Reserve(size); for (NPT_Ordinal i=m_ItemCount; i<size; i++) { new ((void*)&m_Items[i]) T(fill); } m_ItemCount = size; } return NPT_SUCCESS; } /*---------------------------------------------------------------------- | NPT_Array<T>::Contains +---------------------------------------------------------------------*/ template <typename T> bool NPT_Array<T>::Contains(const T& data) const { for (NPT_Ordinal i=0; i<m_ItemCount; i++) { if (m_Items[i] == data) return true; } return false; } /*---------------------------------------------------------------------- | NPT_Array<T>::operator== +---------------------------------------------------------------------*/ template <typename T> bool NPT_Array<T>::operator==(const NPT_Array<T>& other) const { // we need the same number of items if (other.m_ItemCount != m_ItemCount) return false; // compare all items for (NPT_Ordinal i=0; i<m_ItemCount; i++) { if (!(m_Items[i] == other.m_Items[i])) return false; } return true; } /*---------------------------------------------------------------------- | NPT_Array<T>::operator!= +---------------------------------------------------------------------*/ template <typename T> inline bool NPT_Array<T>::operator!=(const NPT_Array<T>& other) const { return !(*this == other); } #endif // _NPT_ARRAY_H_