From af97ee9127495a237f1bf27a511fbb0d3fdd945b Mon Sep 17 00:00:00 2001 From: hama Date: Mon, 15 Aug 2016 11:51:03 +0200 Subject: [PATCH] ArrayList: + put() --- .settings/.gitignore | 1 + util/arraylist.cpp | 50 ++++++++++++-- util/arraylist.hpp | 155 +++++++++++++++++++++++++++++++++++++++++-- util/cutimeutils.cpp | 4 +- util/test.cpp | 2 +- 5 files changed, 198 insertions(+), 14 deletions(-) create mode 100644 .settings/.gitignore diff --git a/.settings/.gitignore b/.settings/.gitignore new file mode 100644 index 0000000..d81d4c4 --- /dev/null +++ b/.settings/.gitignore @@ -0,0 +1 @@ +/language.settings.xml diff --git a/util/arraylist.cpp b/util/arraylist.cpp index 5503c16..c4ecba7 100644 --- a/util/arraylist.cpp +++ b/util/arraylist.cpp @@ -91,6 +91,8 @@ BaseArrayList& BaseArrayList::operator= ( const BaseArrayList& source ) { /** * Adds an item to the list. * + * @param item item to add + * @param index insert index. If >= m_count: item is appended * @return the instance (for chaining) */ BaseArrayList& BaseArrayList::add(const void* item, int index){ @@ -253,7 +255,7 @@ void BaseArrayList::sort(){ void BaseArrayList::heapify(){ // start is assigned the index in 'a' of the last parent node) // the last element in a 0-based array is at index count-1; find the parent of that element) - int start = iParent(m_count-1); + int start = parentOf(m_count-1); while (start >= 0){ // shift down the node at index 'start' to the proper place such that all nodes below @@ -268,9 +270,9 @@ void BaseArrayList::shiftDown(int start, int end){ int root = start; // while the root has at least one child: - while (iLeftChild(root) <= end){ + while (leftChildOf(root) <= end){ // Left child of root) - int child = iLeftChild(root); + int child = leftChildOf(root); // (Keeps track of child to swap with: int swap = root; @@ -356,18 +358,52 @@ void CStringList::dump(const char* title) const{ printf("%2d: %s\n", ii, (ptr = get(ii)) == NULL ? "" : ptr); } +/** + * Creates a new item with the same content as the source. + * + * @param source the source to copy + * @return an new item with the same content as the source + */ void* CStringFactory::cloneItem(const void* source) { char* rc = strdup(reinterpret_cast(source)); TRACEF(("strdup [%llx] -> [%llx]: %s\n", (long long int) source, (long long int) rc, (char*) rc)); return rc; } +/** + * Compare two items. + * + * @param item1 the first item to compare + * @param item2 the 2nd item to compare + * @return 0: items are equal
+ * < 0: item1 < item2
+ * > 0: item1 > item2 + */ +int CStringFactory::compareItems(const void* item1, const void* item2) const{ + int rc = strcmp(reinterpret_cast(item1), + reinterpret_cast(item2)); + return rc; +} + +/** + * Destroy an item (frees the resources). + * + * Revers process of cloning. + * + * @param item the item to destroy + */ void CStringFactory::destroyItem(const void* item) { TRACE2("free [%llx]: %s\n", (long long int) item, (char*) item); // reserved with strdup() ::free((void*) item); } -int CStringFactory::compareItems(const void* item1, const void* item2) const{ - int rc = strcmp(reinterpret_cast(item1), - reinterpret_cast(item2)); - return rc; +/** + * Puts the content from one item to another. + * + * @param source the source of the transfer + * @param target OUT: the content will be set to the content of the source + * @return trueassignment successful
+ * falsetransfer failed, e.g. space not enough + */ +bool CStringFactory::putItem(const void* source, void* target){ + return false; } diff --git a/util/arraylist.hpp b/util/arraylist.hpp index 10c9b7a..6eeb2ff 100644 --- a/util/arraylist.hpp +++ b/util/arraylist.hpp @@ -14,15 +14,47 @@ class ItemFactory { public: + /** + * Creates a new item with the same content as the source. + * + * @param source the source to copy + * @return an new item with the same content as the source + */ virtual void* cloneItem(const void* source) = 0; + /** + * Compare two items. + * + * @param item1 the first item to compare + * @param item2 the 2nd item to compare + * @return 0: items are equal
+ * < 0: item1 < item2
+ * > 0: item1 > item2 + */ virtual int compareItems(const void* item1, const void* item2) const = 0; + /** + * Destroy an item (frees the resources). + * + * Revers process of cloning. + * + * @param item the item to destroy + */ virtual void destroyItem(const void* item) = 0; + /** + * Puts the content from one item to another. + * + * @param source the source of the transfer + * @param target OUT: the content will be set to the content of the source + * @return trueassignment successful
+ * falsetransfer failed, e.g. space not enough + */ + virtual bool putItem(const void* source, void* target) = 0; }; class BaseArrayList { public: - BaseArrayList(ItemFactory& factory, int capacity = 16, int blocksize = 16, int maxBlocksize = 1024*1024, - bool sorted = false); + BaseArrayList(ItemFactory& factory, int capacity = 16, + int blocksize = 16, int maxBlocksize = 1024*1024, + bool sorted = false); BaseArrayList ( const BaseArrayList& other ); virtual ~BaseArrayList(); BaseArrayList& operator= ( const BaseArrayList& other ); @@ -41,18 +73,38 @@ public: protected: void heapify(); void shiftDown(int start, int end); + /** + * Swaps two items in the buffer. + * @param index1 indes of the first item to swap + * @param index2 indes of the 2nd item to swap + */ inline void swapItems(int index1, int index2){ void* tmp = m_buffer[index1]; m_buffer[index1] = m_buffer[index2]; m_buffer[index2] = tmp; } - inline int iParent(int index){ + /** + * Calculates the parent index of an item given by its index. + * @param index the index of the item + * @return the parent index + */ + inline int parentOf(int index){ return (index-1) / 2; } - inline int iLeftChild(int index){ + /** + * Calculates the left child index of an item given by its index. + * @param index the index of the item + * @return the left child index + */ + inline int leftChildOf(int index){ return 2*index + 1; } - inline int iRightChild(int index){ + /** + * Calculates the right child index of an item given by its index. + * @param index the index of the item + * @return the right child index + */ + inline int rightChildOf(int index){ return 2*index + 2; } protected: @@ -67,57 +119,149 @@ protected: template class ArrayList : protected BaseArrayList { public: + /** + * Constructor. + * @param factory factory for cloning/destroying + * @param capacity the size of the list m_buffer + * @param blocksize the minimum count of entries to reserve + * @param maxBlocksize the blocksize is doubled during enlarging the buffer + * while blocksize is smaller than this maximum + * @param sorted true: the buffer is sorted + */ ArrayList(ItemFactory* factory, int capacity = 16, int blocksize = 16, int maxBlocksize = 1024*1024, bool sorted = false): BaseArrayList(*factory, capacity, blocksize, maxBlocksize, sorted) { } + /** + * Copy constructor. + * @param source source to copy + */ ArrayList ( const BaseArrayList& source ): BaseArrayList(source){ } public: + /** + * Adds an item to the list. + * + * @param item item to add + * @param index insert index. If >= m_count: item is appended + * @return the instance (for chaining) + */ inline ArrayList& add(const T* item, int index = 0x7ffffff){ BaseArrayList::add(reinterpret_cast(item), index); return *this; } + /** + * Returns the blocksize. + * @return the minimum count of items while expanding the buffer + */ inline int blocksize() const{ return m_blocksize; } + /** + * Returns the capacity. + * @return the count of items which can be used without expanding + */ inline int capacity() const{ return m_capacity; } + /** + * Clear all elements + */ inline ArrayList& clear(){ BaseArrayList::clear(); return *this; } public: + /** + * Returns the number of items in the buffer. + * @return the number of items + */ inline int count() const { return m_count; } + /** + * Ensures that the capacity has at least a given size. + * @param capacity the ordered capacity. If the current capacity is + * too small it will be expanded + */ inline ArrayList& ensuresSize(int capacity){ BaseArrayList::ensuresSize(capacity); return *this; } + /** + * Returns the n-th item. + * @param index the index of the item to return + * @return NULL: wrong index
+ * otherwise: the wanted item + */ inline T* get(int index) const{ return index < 0 || index >= m_count ? NULL : reinterpret_cast(m_buffer[index]); } + /** + * Finds the index of an item. + * @param item the index to search + * @return -1: not found
+ * otherwise: the index of the item + */ inline int indexOf(const T* item) const{ int rc = BaseArrayList::indexOf(reinterpret_cast(item)); return rc; } + /** + * Puts the content from one item to another. + * + * @param source the source of the transfer + * @param index the index of the item to change + * @return trueassignment successful
+ * falsewrong index + */ + bool put(const T* item, int index){ + bool rc = index >= 0 && index < m_count; + if (rc){ + if (! m_factory.putItem(reinterpret_cast(item), + m_buffer[index])){ + m_factory.destroyItem(m_buffer[index]); + m_buffer[index] = m_factory.cloneItem(item); + } + } + return rc; + } + /** + * Removes the first item which is equal to a given item. + * @param item the item to remove + * @param the instance (for chaining) + */ ArrayList& remove(const T* item){ BaseArrayList::remove(reinterpret_cast(item)); return *this; } + /** + * Removes the item at a given position. + * @param index the index of the item to remove + * @param the instance (for chaining) + */ inline ArrayList& removeAt(int index){ BaseArrayList::removeAt(index); return *this; } + /** + * Sorts the items. + */ inline void sort(){ BaseArrayList::sort(); } + /** + * Returns whether the list is sorted. + * @return true: the list is sorted + */ inline int sorted() const{ return m_sorted; } + /** + * Sets the flag which controls sorting of the list. + * @param sorted the flag to set + */ inline void setSorted(bool sorted){ m_sorted = sorted; if (m_sorted) @@ -155,5 +299,6 @@ public: virtual void* cloneItem(const void* source); virtual int compareItems(const void* item1, const void* item2) const; virtual void destroyItem(const void* item); + virtual bool putItem(const void* source, void* target); }; #endif // ARRAYLIST_H diff --git a/util/cutimeutils.cpp b/util/cutimeutils.cpp index d0cb90b..87e32a2 100644 --- a/util/cutimeutils.cpp +++ b/util/cutimeutils.cpp @@ -40,7 +40,9 @@ public: m_logger.sayf(LOG_INFO, "duration: %.3f / %.3f", durationReal, durationCpu); checkT(durationReal >= 1.0); m_logger.sayf(LOG_INFO, "diff real-cpu: %f", durationReal - durationCpu); - checkT(durationCpu <= durationReal); + double diff = durationCpu - durationReal; + if (diff != 0.0 && durationCpu != 0) + checkT(abs(diff / durationCpu) > 1E-10); checkE(1, duration); } void testTimeMeasurement(){ diff --git a/util/test.cpp b/util/test.cpp index d065f70..4e64743 100644 --- a/util/test.cpp +++ b/util/test.cpp @@ -8,8 +8,8 @@ int main(int argc, char **argv) { extern void testTimerUtils(); extern void testArrayList(); - testDynBuffer(); testArrayList(); + testDynBuffer(); testTimer(); testTimerUtils(); return 0; -- 2.39.5