From 4dedf494c242b2c4b52707441eefe2a36fbacf0f Mon Sep 17 00:00:00 2001 From: patacongo Date: Thu, 22 Mar 2012 21:22:59 +0000 Subject: First check-in of NxWidgets git-svn-id: svn://svn.code.sf.net/p/nuttx/code/trunk@4505 42af7a65-404d-4744-a932-0658087f49c3 --- NxWidgets/libnxwidgets/include/tnxarray.hxx | 437 ++++++++++++++++++++++++++++ 1 file changed, 437 insertions(+) create mode 100644 NxWidgets/libnxwidgets/include/tnxarray.hxx (limited to 'NxWidgets/libnxwidgets/include/tnxarray.hxx') diff --git a/NxWidgets/libnxwidgets/include/tnxarray.hxx b/NxWidgets/libnxwidgets/include/tnxarray.hxx new file mode 100644 index 000000000..44cb537ad --- /dev/null +++ b/NxWidgets/libnxwidgets/include/tnxarray.hxx @@ -0,0 +1,437 @@ +/**************************************************************************** + * NxWidgets/libnxwidgets/include/tnxarray.hxx + * + * Copyright (C) 2012 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. 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. + * 3. Neither the name NuttX, NxWidgets, nor the names of its contributors + * me be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "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 THE + * COPYRIGHT OWNER OR CONTRIBUTORS 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. + * + **************************************************************************** + * + * Portions of this package derive from Woopsi (http://woopsi.org/) and + * portions are original efforts. It is difficult to determine at this + * point what parts are original efforts and which parts derive from Woopsi. + * However, in any event, the work of Antony Dzeryn will be acknowledged + * in most NxWidget files. Thanks Antony! + * + * Copyright (c) 2007-2011, Antony Dzeryn + * 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 names "Woopsi", "Simian Zombie" 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 Antony Dzeryn ``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 Antony Dzeryn 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 __INCLUDE_TNXARRAY_HXX +#define __INCLUDE_TNXARRAY_HXX + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include + +#include +#include + +#include "nxconfig.hxx" + +/**************************************************************************** + * Pre-Processor Definitions + ****************************************************************************/ + +/**************************************************************************** + * Implementation Classes + ****************************************************************************/ + +#if defined(__cplusplus) + +/** + * Class providing a dynamic array; that is, an array that will automatically + * grow to accommodate new data. It provides a fast way to randomly access + * a list of data. Essentially, it provides the most important functionality + * of the STL vector class without any of the overhead of including an STL + * class. + * + * If the data to be stored will store a lot of data that will predominantly + * be read sequentially, consider using the LinkedList class instead. Resizing + * the list is an expensive operation that will occur frequently when filling + * the array with large amounts of data. Adding new data to the linked list is + * very inexpensive. + */ + +template +class TNxArray +{ +private: + T *m_data; /**< Internal array of data items */ + int m_size; /**< Number of items in the array */ + int m_reservedSize; /**< Total size of the array including unpopulated slots */ + + /** + * Re-allocate the array to this size; + */ + + void reallocate(const int newSize); + + /** + * Resize the array if it is full. + */ + + void resize(void); + +public: + + /** + * Constructor. Creates an un-allocated array. The array will + * be allocated when items are added to it or when preallocate() + * is called. + */ + + inline TNxArray(); + + /** + * Constructor. Creates an allocated array. + * + *@param initialSize The initial size of the array. + */ + + inline TNxArray(int initialSize); + + /** + * Destructor. + */ + + inline ~TNxArray(); + + /** + * Set the initial size of the array. Normally, the array is + * unallocated until the first data is pushed into the array. + * That works great for stacks and lists. But if you want a + * array of unitialized elements, then this method will + * preallocate the array for you. + * + * @return The size of the array. + */ + + void preallocate(void); + + /** + * Get the size of the array. + * + * @return The size of the array. + */ + + inline const int size(void) const; + + /** + * Add a value to the end of the array. + * + * @param value The value to add to the array. + */ + + void push_back(const T &value); + + /** + * Insert a value into the array. + * + * @param index The index to insert into. + * @param value The value to insert. + */ + + void insert(const int index, const T &value); + + /** + * Remove the last element from the array. + */ + + void pop_back(void); + + /** + * Erase a single value at the specified index + */ + + void erase(const int index); + + /** + * Get a value at the specified location. Does not perform bounds checking. + * @param index The index of the desired value. + * @return The value at the specified index. + */ + + inline T &at(const int index) const; + + /** + * Check if the array has any data. + * @return True if the array is empty. + */ + + inline bool empty(void) const; + + /** + * Remove all data. + */ + + void clear(); + + /** + * Overload the [] operator to allow array-style access. + * @param index The index to retrieve. + * @return The value at the specified index. + */ + + T& operator[](const int index) const; +}; + +template +TNxArray::TNxArray() +{ + // Don't allocate anything until the first data is added to + // the array + + m_size = 0; // Number of data items in use + m_reservedSize = 0; // Number of data items allocated + m_data = (T *)0; // Allocated memory for data items +} + +template +TNxArray::TNxArray(int initialSize) +{ + m_size = 0; // Number of data items in use + m_reservedSize = 0; // Number of data items allocated + m_data = (T *)0; // Allocated memory for data items + preallocate(initialSize); // Allocate the initial array +} + +template +TNxArray::~TNxArray() +{ + if (m_data) + { + delete [] m_data; + } +} + +template +const int TNxArray::size(void) const +{ + return m_size; +} + +template +void TNxArray::push_back(const T &value) +{ + // Ensure the array is large enough to hold one more data item + + resize(); + + // Add data to array + + m_data[m_size] = value; + + // Remember we've filled a slot + + m_size++; +} + +template +void TNxArray::pop_back(void) +{ + if (m_size >= 1) + { + // We can just reduce the used size of the array, as the value + // will get overwritten automatically + + m_size--; + } +} + +template +void TNxArray::insert(const int index, const T &value) +{ + // Bounds check + + if ((index >= m_size) || (m_size == 0)) + { + push_back(value); + return; + } + + // Ensure the array is large enough to hold one more data item + + resize(); + + // Shift all of the data back one place to make a space for the new data + + for (int i = m_size; i > index; i--) + { + m_data[i] = m_data[i - 1]; + } + + // Add data to array + + m_data[index] = value; + + // Remember we've filled a slot + + m_size++; +} + +template +void TNxArray::erase(const int index) +{ + // Bounds check + + if (index >= m_size) + { + return; + } + + // Shift all of the data back one place and overwrite the value + + for (int i = index; i < m_size - 1; i++) + { + m_data[i] = m_data[i + 1]; + } + + // Remember we've removed a slot + + m_size--; +} + +template +void TNxArray::reallocate(const int newSize) +{ + // Do we need to redim the array? + + if (m_reservedSize < newSize) + { + // Create the new array + + T *newData = new T[newSize]; + + // Copy old array contents to new the new array + + for (int i = 0; i < m_reservedSize; i++) + { + newData[i] = m_data[i]; + } + + // Delete the old array (if there was one) + + if (m_data) + { + delete [] m_data; + } + + // Update values + + m_data = newData; + m_reservedSize = newSize; + } +} + +template +void TNxArray::resize(void) +{ + // Do we need to redim the array in order to add one more entry? + + if (m_reservedSize == m_size) + { + // We have filled the array, so resize it + + int newSize = m_reservedSize; +#if CONFIG_NXWIDGETS_TNXARRAY_INITIALSIZE != CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT + newSize += m_reservedSize ? + CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT : + CONFIG_NXWIDGETS_TNXARRAY_INITIALSIZE; +#else + newSize += CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT; +#endif + + // Re-allocate the array + + reallocate(newSize); + } +} + +template +T& TNxArray::at(const int index) const +{ + // What if this is called with index > m_reservedSize? What if + // this is called before m_data is allocated? Don't do that! + + return m_data[index]; +} + +template +bool TNxArray::empty() const +{ + return (m_size == 0); +} + +template +T& TNxArray::operator[](const int index) const +{ + // What if this is called with index > m_reservedSize? What if + // this is called before m_data is allocated? Don't do that! + + return m_data[index]; +} + +template +void TNxArray::clear() +{ + // All we need to do is reset the size value + + m_size = 0; +} + +#endif // __cplusplus + +#endif // __INCLUDE_TNXARRAY_HXX -- cgit v1.2.3