diff options
Diffstat (limited to '')
-rw-r--r-- | src/3rdparty/adaptagrams/libvpsc/pairing_heap.h | 394 |
1 files changed, 394 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h b/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h new file mode 100644 index 0000000..479519a --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/pairing_heap.h @@ -0,0 +1,394 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005 Mark Allen Weiss + * Copyright (C) 2005-2008 Monash University + * + * ---------------------------------------------------------------------------- + * Pairing heap datastructure implementation: + * Based on example code in "Data structures and Algorithm Analysis in C++" + * by Mark Allen Weiss, used and released under the LGPL by permission + * of the author. + * No promises about correctness. Use at your own risk! + * ---------------------------------------------------------------------------- + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Mark Allen Weiss + * Tim Dwyer +*/ + +#ifndef VPSC_PAIRING_HEAP_H +#define VPSC_PAIRING_HEAP_H + +#include <cstdlib> +#include <fstream> +#include <vector> +#include <list> + +#include "libvpsc/assertions.h" + +class Underflow { }; + +// Pairing heap class +// +// CONSTRUCTION: with no parameters +// +// ******************PUBLIC OPERATIONS********************* +// PairNode & insert( x ) --> Insert x +// deleteMin( minItem ) --> Remove (and optionally return) smallest item +// T findMin( ) --> Return smallest item +// bool isEmpty( ) --> Return true if empty; else false +// void makeEmpty( ) --> Remove all items +// void decreaseKey( PairNode p, newVal ) +// --> Decrease value in node p +// ******************ERRORS******************************** +// Throws Underflow as warranted + + +template <class T> +struct PairNode +{ + T element; + PairNode *leftChild; + PairNode *nextSibling; + PairNode *prev; + + PairNode( const T & theElement ) : + element( theElement ), + leftChild(nullptr), nextSibling(nullptr), prev(nullptr) + { } +}; + +template <class T, class TCompare> +class PairingHeap; + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b); + +template <class T, class TCompare = std::less<T> > +class PairingHeap +{ +#ifndef SWIG + friend std::ostream& operator<< <T,TCompare> (std::ostream &os, const PairingHeap<T,TCompare> &b); +#endif +public: + PairingHeap() : root(nullptr), counter(0), siblingsTreeArray(5) { } + PairingHeap(const PairingHeap & rhs) { + // uses operator= to make deep copy + *this = rhs; + } + ~PairingHeap() { makeEmpty(); } + const PairingHeap & operator=( const PairingHeap & rhs ); + bool isEmpty() const { return root == nullptr; } + unsigned size() const { return counter; } + PairNode<T> *insert( const T & x ); + const T & findMin( ) const; + void deleteMin( ); + const T extractMin( ) { + T v = findMin(); + deleteMin(); + return v; + } + void makeEmpty() { + reclaimMemory(root); + root = nullptr; + counter = 0; + } + void decreaseKey( PairNode<T> *p, const T & newVal ); + void merge( PairingHeap<T,TCompare> *rhs ); +protected: + // Destructively gets the root for merging into another heap. + PairNode<T> * removeRootForMerge(unsigned& size) { + PairNode<T> *r=root; + root=nullptr; + size=counter; + counter=0; + return r; + } + TCompare lessThan; +private: + PairNode<T> *root; + unsigned counter; + + // Used by PairingHeap::combineSiblings(). We keep this as member + // variable to save some vector resize operations during subsequent uses. + std::vector<PairNode<T> *> siblingsTreeArray; + + void reclaimMemory( PairNode<T> *t ) const; + void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const; + PairNode<T> * combineSiblings( PairNode<T> *firstSibling ); + PairNode<T> * clone( PairNode<T> * t ) const; +}; + + +/** +* Insert item x into the priority queue, maintaining heap order. +* Return a pointer to the node containing the new item. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::insert( const T & x ) +{ + PairNode<T> *newNode = new PairNode<T>( x ); + + if( root == nullptr ) + root = newNode; + else + compareAndLink( root, newNode ); + counter++; + return newNode; +} + +/** +* Find the smallest item in the priority queue. +* Return the smallest item, or throw Underflow if empty. +*/ +template <class T,class TCompare> +const T & PairingHeap<T,TCompare>::findMin( ) const +{ + if( isEmpty( ) ) + throw Underflow( ); + return root->element; +} +/** + * Remove the smallest item from the priority queue. + * Throws Underflow if empty. + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::deleteMin( ) +{ + if( isEmpty( ) ) + throw Underflow( ); + + PairNode<T> *oldRoot = root; + + if( root->leftChild == nullptr ) + root = nullptr; + else + root = combineSiblings( root->leftChild ); + COLA_ASSERT(counter); + counter--; + delete oldRoot; +} + +/** +* Deep copy. +*/ +template <class T,class TCompare> +const PairingHeap<T,TCompare> & +PairingHeap<T,TCompare>::operator=( const PairingHeap<T,TCompare> & rhs ) +{ + if( this != &rhs ) + { + makeEmpty( ); + root = clone( rhs.root ); + counter = rhs.size(); + } + + return *this; +} + +/** +* Internal method to make the tree empty. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::reclaimMemory( PairNode<T> * t ) const +{ + if( t != nullptr ) + { + reclaimMemory( t->leftChild ); + reclaimMemory( t->nextSibling ); + delete t; + } +} + +/** +* Change the value of the item stored in the pairing heap. +* Does nothing if newVal is larger than currently stored value. +* p points to a node returned by insert. +* newVal is the new value, which must be smaller +* than the currently stored value. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::decreaseKey( PairNode<T> *p, + const T & newVal ) +{ + COLA_ASSERT(!lessThan(p->element,newVal)); // newVal cannot be bigger + p->element = newVal; + if( p != root ) + { + if( p->nextSibling != nullptr ) + p->nextSibling->prev = p->prev; + if( p->prev->leftChild == p ) + p->prev->leftChild = p->nextSibling; + else + p->prev->nextSibling = p->nextSibling; + + p->nextSibling = nullptr; + compareAndLink( root, p ); + } +} + +/** + * Merges rhs into this pairing heap by inserting its root + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::merge( PairingHeap<T,TCompare> *rhs ) +{ + unsigned rhsSize; + PairNode<T> *broot=rhs->removeRootForMerge(rhsSize); + if (root == nullptr) { + root = broot; + } else { + compareAndLink(root, broot); + } + counter+=rhsSize; +} + +/** +* Internal method that is the basic operation to maintain order. +* Links first and second together to satisfy heap order. +* first is root of tree 1, which may not be nullptr. +* first->nextSibling MUST be nullptr on entry. +* second is root of tree 2, which may be nullptr. +* first becomes the result of the tree merge. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>:: +compareAndLink( PairNode<T> * & first, + PairNode<T> *second ) const +{ + if( second == nullptr ) + return; + + if( lessThan(second->element,first->element) ) + { + // Attach first as leftmost child of second + second->prev = first->prev; + first->prev = second; + first->nextSibling = second->leftChild; + if( first->nextSibling != nullptr ) + first->nextSibling->prev = first; + second->leftChild = first; + first = second; + } + else + { + // Attach second as leftmost child of first + second->prev = first; + first->nextSibling = second->nextSibling; + if( first->nextSibling != nullptr ) + first->nextSibling->prev = first; + second->nextSibling = first->leftChild; + if( second->nextSibling != nullptr ) + second->nextSibling->prev = second; + first->leftChild = second; + } +} + +/** +* Internal method that implements two-pass merging. +* firstSibling the root of the conglomerate; +* assumed not nullptr. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::combineSiblings( PairNode<T> *firstSibling ) +{ + if( firstSibling->nextSibling == nullptr ) + return firstSibling; + + // Store the subtrees in an array + int numSiblings = 0; + for( ; firstSibling != nullptr; numSiblings++ ) + { + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings * 2 ); + siblingsTreeArray[ numSiblings ] = firstSibling; + firstSibling->prev->nextSibling = nullptr; // break links + firstSibling = firstSibling->nextSibling; + } + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings + 1 ); + siblingsTreeArray[ numSiblings ] = nullptr; + + // Combine subtrees two at a time, going left to right + int i = 0; + for( ; i + 1 < numSiblings; i += 2 ) + compareAndLink( siblingsTreeArray[ i ], siblingsTreeArray[ i + 1 ] ); + + int j = i - 2; + + // j has the result of last compareAndLink. + // If an odd number of trees, get the last one. + if( j == numSiblings - 3 ) + compareAndLink( siblingsTreeArray[ j ], siblingsTreeArray[ j + 2 ] ); + + // Now go right to left, merging last tree with + // next to last. The result becomes the new last. + for( ; j >= 2; j -= 2 ) + compareAndLink( siblingsTreeArray[ j - 2 ], siblingsTreeArray[ j ] ); + return siblingsTreeArray[ 0 ]; +} + +/** +* Internal method to clone subtree. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::clone( PairNode<T> * t ) const +{ + if( t == nullptr ) + return nullptr; + else + { + PairNode<T> *p = new PairNode<T>( t->element ); + if( ( p->leftChild = clone( t->leftChild ) ) != nullptr ) + p->leftChild->prev = p; + if( ( p->nextSibling = clone( t->nextSibling ) ) != nullptr ) + p->nextSibling->prev = p; + return p; + } +} + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b) +{ + os<<"Heap:"; + if (b.root != nullptr) { + PairNode<T> *r = b.root; + std::list<PairNode<T>*> q; + q.push_back(r); + while (!q.empty()) { + r = q.front(); + q.pop_front(); + if (r->leftChild != nullptr) { + os << *r->element << ">"; + PairNode<T> *c = r->leftChild; + while (c != nullptr) { + q.push_back(c); + os << "," << *c->element; + c = c->nextSibling; + } + os << "|"; + } + } + } + return os; +} + +#endif /* VPSC_PAIRING_HEAP_H */ |