 | PixelLight 0.9.11-R1 Copyright (C) 2002-2012 by The PixelLight Team Last modified Thu Feb 23 2012 14:08:52 |  | The content of this PixelLight
document is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported |
|
PixelLightAPI
.
|
00001 /*********************************************************\ 00002 * File: BinominalHeap.h * 00003 * 00004 * Copyright (C) 2002-2012 The PixelLight Team (http://www.pixellight.org/) 00005 * 00006 * This file is part of PixelLight. 00007 * 00008 * PixelLight is free software: you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License as published by 00010 * the Free Software Foundation, either version 3 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * PixelLight is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU Lesser General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU Lesser General Public License 00019 * along with PixelLight. If not, see <http://www.gnu.org/licenses/>. 00020 \*********************************************************/ 00021 00022 00023 #ifndef __PLCORE_CONTAINER_BINOMINALHEAP_H__ 00024 #define __PLCORE_CONTAINER_BINOMINALHEAP_H__ 00025 #pragma once 00026 00027 00028 //[-------------------------------------------------------] 00029 //[ Includes ] 00030 //[-------------------------------------------------------] 00031 #include "PLCore/Container/Heap.h" 00032 #include "PLCore/Container/Functions.h" 00033 00034 00035 //[-------------------------------------------------------] 00036 //[ Namespace ] 00037 //[-------------------------------------------------------] 00038 namespace PLCore { 00039 00040 00041 //[-------------------------------------------------------] 00042 //[ Forward declarations ] 00043 //[-------------------------------------------------------] 00044 template <class KeyType, class ValueType, class Comparer> class BinominalHeapIterator; 00045 00046 00047 //[-------------------------------------------------------] 00048 //[ Classes ] 00049 //[-------------------------------------------------------] 00050 /** 00051 * @brief 00052 * Binominal heap 00053 */ 00054 template <class KeyType, class ValueType, class Comparer = CompareFunction > 00055 class BinominalHeap : public Heap<KeyType, ValueType> { 00056 00057 00058 //[-------------------------------------------------------] 00059 //[ Friends ] 00060 //[-------------------------------------------------------] 00061 friend class BinominalHeapIterator<KeyType, ValueType, Comparer>; 00062 00063 00064 //[-------------------------------------------------------] 00065 //[ Public functions ] 00066 //[-------------------------------------------------------] 00067 public: 00068 /** 00069 * @brief 00070 * Constructor 00071 */ 00072 BinominalHeap(); 00073 00074 /** 00075 * @brief 00076 * Destructor 00077 */ 00078 virtual ~BinominalHeap(); 00079 00080 00081 //[-------------------------------------------------------] 00082 //[ Private functions ] 00083 //[-------------------------------------------------------] 00084 private: 00085 /** 00086 * @brief 00087 * Copy constructor 00088 * 00089 * @param[in] cSource 00090 * Source to copy from 00091 */ 00092 BinominalHeap(const BinominalHeap<KeyType, ValueType, Comparer> &cSource); 00093 00094 /** 00095 * @brief 00096 * Makes this heap to a copy of another heap 00097 * 00098 * @param[in] cHeap 00099 * 'BinominalHeap' to copy from 00100 * 00101 * @return 00102 * Reference to this instance 00103 */ 00104 Heap<KeyType, ValueType> &operator =(const BinominalHeap<KeyType, ValueType, Comparer> &cHeap); 00105 00106 00107 //[-------------------------------------------------------] 00108 //[ Private classes ] 00109 //[-------------------------------------------------------] 00110 private: 00111 /** 00112 * @brief 00113 * Internal binominal tree 00114 */ 00115 class Tree { 00116 00117 00118 //[-------------------------------------------------------] 00119 //[ Friends ] 00120 //[-------------------------------------------------------] 00121 friend class BinominalHeap<KeyType, ValueType, Comparer>; 00122 friend class BinominalHeapIterator<KeyType, ValueType, Comparer>; 00123 00124 00125 //[-------------------------------------------------------] 00126 //[ Public functions ] 00127 //[-------------------------------------------------------] 00128 public: 00129 /** 00130 * @brief 00131 * Constructor 00132 * 00133 * @param[in] Key 00134 * Key 00135 * @param[in] Value 00136 * Value 00137 */ 00138 Tree(KeyType Key, ValueType Value); 00139 00140 /** 00141 * @brief 00142 * Destructor 00143 */ 00144 ~Tree(); 00145 00146 /** 00147 * @brief 00148 * Union 00149 * 00150 * @param[in] cTree 00151 * Tree to union with this tree 00152 * 00153 * @return 00154 * The (new) root node 00155 */ 00156 Tree &Union(Tree &cTree); 00157 00158 00159 //[-------------------------------------------------------] 00160 //[ Private data ] 00161 //[-------------------------------------------------------] 00162 private: 00163 uint32 m_nDegree; /**< Degree of this tree node */ 00164 Tree *m_pNextSibling; /**< Next sibling tree, can be a null pointer */ 00165 Tree *m_pChild; /**< Child tree, can be a null pointer */ 00166 KeyType m_Key; /**< Key of this tree node */ 00167 ValueType m_Value; /**< Value of this tree node */ 00168 00169 00170 }; 00171 00172 00173 //[-------------------------------------------------------] 00174 //[ Private data ] 00175 //[-------------------------------------------------------] 00176 private: 00177 uint32 m_nNumOfElements; /**< Current number of elements */ 00178 Tree *m_pRoot; /**< Root binominal tree, can be a null pointer */ 00179 00180 00181 //[-------------------------------------------------------] 00182 //[ Public virtual Iterable functions ] 00183 //[-------------------------------------------------------] 00184 public: 00185 virtual Iterator<ValueType> GetIterator(uint32 nIndex = 0) const override; 00186 virtual ConstIterator<ValueType> GetConstIterator(uint32 nIndex = 0) const override; 00187 virtual Iterator<ValueType> GetEndIterator() const override; 00188 virtual ConstIterator<ValueType> GetConstEndIterator() const override; 00189 00190 00191 //[-------------------------------------------------------] 00192 //[ Public virtual Heap functions ] 00193 //[-------------------------------------------------------] 00194 public: 00195 virtual void Clear() override; 00196 virtual bool IsEmpty() const override; 00197 virtual uint32 GetNumOfElements() const override; 00198 virtual bool Add(const KeyType &Key, const ValueType &Value) override; 00199 virtual bool GetTop(ValueType *pValue = nullptr, KeyType *pKey = nullptr) const override; 00200 virtual bool ExtractTop(ValueType *pValue = nullptr, KeyType *pKey = nullptr) override; 00201 00202 00203 //[-------------------------------------------------------] 00204 //[ Private virtual Heap functions ] 00205 //[-------------------------------------------------------] 00206 private: 00207 virtual Heap<KeyType, ValueType> &operator =(const Heap<KeyType, ValueType> &cHeap) override; 00208 00209 00210 }; 00211 00212 00213 //[-------------------------------------------------------] 00214 //[ Namespace ] 00215 //[-------------------------------------------------------] 00216 } // PLCore 00217 00218 00219 //[-------------------------------------------------------] 00220 //[ Implementation ] 00221 //[-------------------------------------------------------] 00222 #include "PLCore/Container/BinominalHeap.inl" 00223 00224 00225 #endif // __PLCORE_CONTAINER_BINOMINALHEAP_H__
|