From 013df98f79866a75f367853c9e436f3c5c79f645 Mon Sep 17 00:00:00 2001 From: rubidium Date: Tue, 2 Jan 2007 19:19:48 +0000 Subject: (svn r7759) -Merge: makefile rewrite. This merge features: - A proper ./configure, so everything needs to be configured only once, not for every make. - Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies. - A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC. - Proper support for OSX universal binaries. - Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files. - Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files. Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy. --- yapf/binaryheap.hpp | 225 ---------------------------------------------------- 1 file changed, 225 deletions(-) delete mode 100644 yapf/binaryheap.hpp (limited to 'yapf/binaryheap.hpp') diff --git a/yapf/binaryheap.hpp b/yapf/binaryheap.hpp deleted file mode 100644 index 7b72a25af..000000000 --- a/yapf/binaryheap.hpp +++ /dev/null @@ -1,225 +0,0 @@ -/* $Id$ */ - -#ifndef BINARYHEAP_HPP -#define BINARYHEAP_HPP - -//void* operator new (size_t size, void* p) {return p;} -#if defined(_MSC_VER) && (_MSC_VER >= 1400) -//void operator delete (void* p, void* p2) {} -#endif - - -/** - * Binary Heap as C++ template. - * - * For information about Binary Heap algotithm, - * see: http://www.policyalmanac.org/games/binaryHeaps.htm - * - * Implementation specific notes: - * - * 1) It allocates space for item pointers (array). Items are allocated elsewhere. - * - * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we - * use indices 1..max_items instead of zero based C indexing. - * - * 3) Item of the binary heap should support these public members: - * - 'lower-then' operator '<' - used for comparing items before moving - * - */ - -template -class CBinaryHeapT { -public: - typedef Titem_ *ItemPtr; -private: - int m_size; ///< Number of items in the heap - int m_max_size; ///< Maximum number of items the heap can hold - ItemPtr* m_items; ///< The heap item pointers - -public: - explicit CBinaryHeapT(int max_items = 102400) - : m_size(0) - , m_max_size(max_items) - { - m_items = new ItemPtr[max_items + 1]; - } - - ~CBinaryHeapT() - { - Clear(); - delete [] m_items; - m_items = NULL; - } - -public: - /** Return the number of items stored in the priority queue. - * @return number of items in the queue */ - FORCEINLINE int Size() const {return m_size;}; - - /** Test if the priority queue is empty. - * @return true if empty */ - FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; - - /** Test if the priority queue is full. - * @return true if full. */ - FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; - - /** Find the smallest item in the priority queue. - * Return the smallest item, or throw assert if empty. */ - FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} - - /** Insert new item into the priority queue, maintaining heap order. - * @return false if the queue is full. */ - bool Push(Titem_& new_item); - - /** Remove and return the smallest item from the priority queue. */ - FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; - - /** Remove the smallest item from the priority queue. */ - void RemoveHead(); - - /** Remove item specified by index */ - void RemoveByIdx(int idx); - - /** return index of the item that matches (using &item1 == &item2) the given item. */ - int FindLinear(const Titem_& item) const; - - /** Make the priority queue empty. - * All remaining items will remain untouched. */ - void Clear() {m_size = 0;}; - - /** verifies the heap consistency (added during first YAPF debug phase) */ - void CheckConsistency(); -}; - - -template -FORCEINLINE bool CBinaryHeapT::Push(Titem_& new_item) -{ - if (IsFull()) return false; - - // make place for new item - int gap = ++m_size; - // Heapify up - for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2) - m_items[gap] = m_items[parent]; - m_items[gap] = &new_item; - CheckConsistency(); - return true; -} - -template -FORCEINLINE void CBinaryHeapT::RemoveHead() -{ - assert(!IsEmpty()); - - // at index 1 we have a gap now - int gap = 1; - - // Heapify down: - // last item becomes a candidate for the head. Call it new_item. - Titem_& new_item = *m_items[m_size--]; - - // now we must maintain relation between parent and its children: - // parent <= any child - // from head down to the tail - int child = 2; // first child is at [parent * 2] - - // while children are valid - while (child <= m_size) { - // choose the smaller child - if (child < m_size && *m_items[child + 1] < *m_items[child]) - child++; - // is it smaller than our parent? - if (!(*m_items[child] < new_item)) { - // the smaller child is still bigger or same as parent => we are done - break; - } - // if smaller child is smaller than parent, it will become new parent - m_items[gap] = m_items[child]; - gap = child; - // where do we have our new children? - child = gap * 2; - } - // move last item to the proper place - if (m_size > 0) m_items[gap] = &new_item; - CheckConsistency(); -} - -template -inline void CBinaryHeapT::RemoveByIdx(int idx) -{ - // at position idx we have a gap now - int gap = idx; - Titem_& last = *m_items[m_size]; - if (idx < m_size) { - assert(idx >= 1); - m_size--; - // and the candidate item for fixing this gap is our last item 'last' - // Move gap / last item up: - while (gap > 1) - { - // compare [gap] with its parent - int parent = gap / 2; - if (last < *m_items[parent]) { - m_items[gap] = m_items[parent]; - gap = parent; - } else { - // we don't need to continue upstairs - break; - } - } - - // Heapify (move gap) down: - while (true) { - // where we do have our children? - int child = gap * 2; // first child is at [parent * 2] - if (child > m_size) break; - // choose the smaller child - if (child < m_size && *m_items[child + 1] < *m_items[child]) - child++; - // is it smaller than our parent? - if (!(*m_items[child] < last)) { - // the smaller child is still bigger or same as parent => we are done - break; - } - // if smaller child is smaller than parent, it will become new parent - m_items[gap] = m_items[child]; - gap = child; - } - // move parent to the proper place - if (m_size > 0) m_items[gap] = &last; - } - else { - assert(idx == m_size); - m_size--; - } - CheckConsistency(); -} - -template -inline int CBinaryHeapT::FindLinear(const Titem_& item) const -{ - if (IsEmpty()) return 0; - for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) { - if (*ppI == &item) { - return ppI - m_items; - } - } - return 0; -} - -template -FORCEINLINE void CBinaryHeapT::CheckConsistency() -{ - // enable it if you suspect binary heap doesn't work well -#if 0 - for (int child = 2; child <= m_size; child++) { - int parent = child / 2; - assert(!(m_items[child] < m_items[parent])); - } -#endif -} - - -#endif /* BINARYHEAP_HPP */ -- cgit v1.2.3-70-g09d2