1 /* 2 Multiple Objective MetaHeuristics Library in C++ MOMHLib++ 3 Copyright (C) 2001 Andrzej Jaszkiewicz, Radoslaw Ziembinski (radekz@free.alpha.net.pl) 4 5 This library is free software; you can redistribute it and/or 6 modify it under the terms of the GNU Lesser General Public 7 License as published by the Free Software Foundation (www.gnu.org); 8 either version 2.1 of the License, or (at your option) any later 9 version. 10 11 This library is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 You should have received a copy of the GNU Lesser General Public 17 License along with this library; if not, write to the Free Software 18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19 */ 20 21 #ifndef __TBTREE_H_ 22 #define __TBTREE_H_ 23 24 #include "global.h" 25 #include "solution.h" 26 #include "tbnode.h" 27 28 class TQuadNode; 29 30 /** This class implements binary tree. 31 * 32 * This binary tree has been implemented to improve access to child node in quad 33 * tree. Thanks to tree access to next point is perform in logaritmic time. 34 **/ 35 class TBTree 36 { 37 public: 38 39 /** Remove whole tree and release every child QuadNode. 40 * 41 * This function recursively release sub tree of quad node. 42 **/ 43 void ReleaseTree(); 44 45 /** Remove QuadNode from tree but not destroy this object. 46 * 47 * This function release path in tree to element and release QuadNode placed in leaf. 48 * 49 * @param oValue path to leaf 50 * @param pPreviousNode returned node 51 * @return true - success, false - error (incorrect path to node) 52 **/ 53 bool RemoveBNode(vector<bool> &oValue, TQuadNode **pPreviousNode); 54 55 /** Add QuadNode to tree. 56 * 57 * This function release path in tree to element and release QuadNode placed in leaf. 58 * 59 * @param oValue path to leaf 60 * @param pQuadNode node that should be add 61 * @param pPreviousNode pointer to previous QuadNode in tree 62 * @return true - success, false - error 63 **/ 64 bool AddBNode(vector<bool> &oValue, TQuadNode *pQuadNode, TQuadNode **pPreviousNode); 65 66 /** Find QuadNode in Tree. 67 * 68 * This function finds QuadNode element in tree. 69 * 70 * @param oValue path to leaf 71 * @param pPreviousNode stored pointer to node if has been found or null 72 * @return true - success, false - error 73 **/ 74 bool FindNode(vector<bool> &oValue, TQuadNode **pPreviousNode); 75 76 /** Find set of nodes that contains more 'one' on path vector thet oValue. 77 * 78 * This function gets every child node that in path has more 'one' in vector and 79 * also 'one' on the same places. 80 * 81 * @param oValue path to leaf 82 * @param oNodes vector of pointers to retrieved solutions 83 * @return true - success, false - error 84 **/ 85 bool FindGreater(vector<bool> &oValue, vector<TQuadNode *> &oNodes); 86 87 /** Find set of nodes that contains more 'zero' on path vector thet oValue. 88 * 89 * This function gets every child node that in path has more 'zero' in vector and 90 * also 'zero' on the same places. 91 * 92 * @param oValue path to leaf 93 * @param oNodes vector of pointers to retrieved solutions 94 * @return true - success, false - error 95 **/ 96 bool FindLesser(vector<bool> &oValue, vector<TQuadNode *> &oNodes); 97 98 /** Retrieve every QuadNode stored in tree. 99 * 100 * This function gets every child node stored in binary tree 101 * 102 * @param oRootNode root node of tree 103 * @param oNodes vector of pointers to retrieved solutions 104 * @return true - success, false - error 105 **/ 106 bool FindAll(TBNode &oRootNode, vector<TQuadNode *> &oNodes); 107 108 109 /** Save tree to stream. 110 * 111 * This function allows to serialize binary tree structure. 112 * 113 * @param oStream output stream 114 * @param iSpace number of spaces used in indentations generation 115 * @return output stream 116 **/ 117 ostream& Save(ostream& oStream, int iSpace); 118 119 TBTree(); 120 121 virtual ~TBTree(); 122 123 /** Root node to tree **/ 124 TBNode m_oRoot; 125 126 private: 127 128 /** Recursive function to retrieve all solutions. 129 * 130 * @param pNode parent node 131 * @param oNodes vector of pointers to retrieved solutions 132 * @return true - success, false - error 133 **/ 134 bool GetRecursiveAll(TBNode *pNode, vector<TQuadNode *> &oNodes); 135 136 /** Recursive function to retrieve greater solutions. 137 * 138 * @param pNode parent node 139 * @param iLevel index of level in tree 140 * @param bEqual true - equal element will also in set 141 * @param oValue path used as a point of reference 142 * @param oNodes vector of pointers to retrieved solutions 143 * @return true - success, false - error 144 **/ 145 bool GetRecursiveGreater(TBNode *pNode, unsigned int iLevel, bool bEqual, vector<bool> &oValue, vector<TQuadNode *> &oNodes); 146 147 /** Recursive function to retrieve lesser solutions. 148 * 149 * @param pNode parent node 150 * @param iLevel index of level in tree 151 * @param bEqual true - equal element will also in set 152 * @param oValue path used as a point of reference 153 * @param oNodes vector of pointers to retrieved solutions 154 * @return true - success, false - error 155 **/ 156 bool GetRecursiveLesser(TBNode *pNode, unsigned int iLevel, bool bEqual, vector<bool> &oValue, vector<TQuadNode *> &oNodes); 157 }; 158 159 #endif 160