Open64 (mfef90, whirl2f, and IR tools)
TAG: version-openad; SVN changeset: 916
|
00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 // -*-C++-*- 00037 00062 #ifndef bin_tree_INCLUDED 00063 #define bin_tree_INCLUDED 00064 00065 00066 00067 #ifndef defs_INCLUDED 00068 #include "defs.h" 00069 #endif 00070 #ifndef ERRORS_INCLUDED 00071 #include "errors.h" 00072 #endif 00073 #ifndef CXX_MEMORY_INCLUDED 00074 #include "cxx_memory.h" 00075 #endif 00076 00077 00078 template <class BINARY_NODE> 00079 class BINARY_TREE_NODE { 00080 BINARY_TREE_NODE<BINARY_NODE> *_left; 00081 BINARY_TREE_NODE<BINARY_NODE> *_right; 00082 BINARY_NODE _data; 00083 public: 00084 // create a new element 00085 BINARY_TREE_NODE(BINARY_NODE data) { 00086 _data = data; 00087 _left = _right = NULL; 00088 }; 00089 BINARY_TREE_NODE<BINARY_NODE>* Enter(BINARY_NODE node, MEM_POOL *pool); 00090 BINARY_TREE_NODE<BINARY_NODE>* Find(BINARY_NODE node) const; 00091 ~BINARY_TREE_NODE() { 00092 if (_left) CXX_DELETE(_left,Default_Mem_Pool); 00093 if (_right) CXX_DELETE(_right,Default_Mem_Pool); 00094 }; 00095 BINARY_NODE* Get_Data() { return &_data; } 00096 const BINARY_NODE* Get_Data() const { return &_data; } 00097 }; 00098 00099 template <class BINARY_NODE> 00100 class BINARY_TREE { 00101 BINARY_TREE_NODE<BINARY_NODE> *_binary_tree_node; 00102 MEM_POOL *_pool; 00103 public: 00104 BINARY_TREE(MEM_POOL *pool) { _pool = pool; _binary_tree_node = NULL; } 00105 BINARY_TREE_NODE<BINARY_NODE>* Enter(BINARY_NODE node) { 00106 typedef BINARY_TREE_NODE<BINARY_NODE> THIS_BINARY_TREE_NODE; 00107 if (!_binary_tree_node) { 00108 _binary_tree_node = CXX_NEW(THIS_BINARY_TREE_NODE(node),_pool); 00109 return(_binary_tree_node); 00110 } else { 00111 return(_binary_tree_node->Enter(node,_pool)); 00112 } 00113 } 00114 BINARY_TREE_NODE<BINARY_NODE>* Find(BINARY_NODE element) const { 00115 if (!_binary_tree_node) { 00116 return(FALSE); 00117 } else { 00118 return(_binary_tree_node->Find(element)); 00119 } 00120 } 00121 ~BINARY_TREE() { 00122 MEM_POOL_Set_Default(_pool); 00123 if (_binary_tree_node) CXX_DELETE(_binary_tree_node,Default_Mem_Pool); 00124 } 00125 }; 00126 00127 00128 #ifdef __GNUC__ 00129 // Implementation stuff included here because g++ 00130 // (rightly) doesn't do implicit .cxx file inclusion. 00131 00132 template <class BINARY_NODE> 00133 BINARY_TREE_NODE<BINARY_NODE>* BINARY_TREE_NODE<BINARY_NODE>:: 00134 Enter(BINARY_NODE node, MEM_POOL *pool) 00135 { 00136 //typedef BINARY_TREE_NODE<BINARY_NODE> THIS_NODE; 00137 //typedef BINARY_TREE_NODE<BINARY_NODE> *THIS_NODEP; 00138 //THIS_NODEP nodep = this; 00139 BINARY_TREE_NODE<BINARY_NODE> *nodep = this; 00140 BOOL found = FALSE; 00141 while (!found) { 00142 if (nodep->_data == node) { 00143 found = TRUE; 00144 } else if (node < nodep->_data) { 00145 if (!nodep->_left) { 00146 nodep->_left = CXX_NEW(BINARY_TREE_NODE<BINARY_NODE>(node),pool); 00147 found = TRUE; 00148 } 00149 nodep = nodep->_left; 00150 } else { 00151 if (!nodep->_right) { 00152 nodep->_right = CXX_NEW(BINARY_TREE_NODE<BINARY_NODE>(node),pool); 00153 found = TRUE; 00154 } 00155 nodep = nodep->_right; 00156 } 00157 } 00158 return nodep; 00159 } 00160 00161 00162 template <class BINARY_NODE> 00163 BINARY_TREE_NODE<BINARY_NODE>* BINARY_TREE_NODE<BINARY_NODE>:: 00164 Find(BINARY_NODE node) const 00165 { 00166 //typedef BINARY_TREE_NODE<BINARY_NODE> *THIS_NODEP; 00167 BINARY_TREE_NODE<BINARY_NODE> *nodep = (BINARY_TREE_NODE<BINARY_NODE> *)this; 00168 while (1) { 00169 if (nodep->_data == node) { 00170 return nodep; 00171 } else if (node < nodep->_data) { 00172 if (nodep->_left) { 00173 nodep = nodep->_left; 00174 } else { 00175 return NULL; 00176 } 00177 } else { 00178 if (nodep->_right) { 00179 nodep = nodep->_right; 00180 } else { 00181 return NULL; 00182 } 00183 } 00184 } 00185 } 00186 00187 #endif 00188 00189 #endif