csutil/tree.h
00001 /* 00002 Copyright (C) 2000 by Norman Kraemer 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Library General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00017 */ 00018 00019 #ifndef __CS_CSTREENODE_H__ 00020 #define __CS_CSTREENODE_H__ 00021 00022 #include "array.h" 00023 00027 class csTreeNode 00028 { 00029 public: 00031 bool IsLeaf () 00032 { return children.Length () == 0; } 00033 00035 void RemoveChild (csTreeNode *child) 00036 { 00037 int idx = children.Find (child); 00038 if (idx != -1) children.DeleteIndex (idx); 00039 } 00040 00042 void AddChild (csTreeNode *child) 00043 { children.Push (child); child->parent = this; } 00044 00046 csTreeNode (csTreeNode *theParent=0) 00047 { parent=theParent; if (parent) parent->children.Push (this); } 00048 00049 virtual ~csTreeNode () 00050 { 00051 int i; 00052 for(i=children.Length ()-1; i>=0; i--) 00053 delete children.Get (i); 00054 if (parent) 00055 parent->RemoveChild (this); 00056 } 00057 00068 csTreeNode *DSF (bool (*TreeFunc)(csTreeNode *node, void* param, 00069 bool stopOnSuccess), 00070 bool (*SelBranch)(csTreeNode *node), void* param, 00071 bool stopOnSuccess) 00072 { 00073 csTreeNode *foundNode = 0; 00074 int i=0; 00075 bool dive; 00076 if (TreeFunc (this, param, stopOnSuccess)) 00077 foundNode = this; 00078 while (i<children.Length () && !(foundNode && stopOnSuccess)) 00079 { 00080 dive = (SelBranch == 0) || SelBranch (children[i]); 00081 if (dive) 00082 foundNode = (children[i])->DSF (TreeFunc, SelBranch, 00083 param, stopOnSuccess); 00084 i++; 00085 } 00086 return foundNode; 00087 } 00088 00099 csTreeNode *BSF (bool (*TreeFunc)(csTreeNode *node, void* param, 00100 bool stopOnSuccess), 00101 bool (*SelBranch)(csTreeNode *node), void* param, 00102 bool stopOnSuccess) 00103 { 00104 csTreeNode *node, *foundNode = 0; 00105 csArray<csTreeNode*> fifo; 00106 00107 fifo.Push (this); 00108 while (fifo.Length () > 0 && !(foundNode && stopOnSuccess)) 00109 { 00110 node = fifo[0]; fifo.DeleteIndex (0); 00111 if (TreeFunc (node, param, stopOnSuccess)) 00112 foundNode = node; 00113 if (!node->IsLeaf () && (SelBranch==0 || SelBranch (node))) 00114 { 00115 int i; 00116 for (i=0; i < node->children.Length (); i++ ) 00117 fifo.Push (node->children[i]); 00118 } 00119 } 00120 fifo.DeleteAll (); 00121 return foundNode; 00122 } 00123 00124 public: 00125 csTreeNode *parent; // parent node or 0 if toplevel 00126 csArray<csTreeNode*> children; // node children 00127 }; 00128 00129 #endif // __CS_CSTREENODE_H__
Generated for Crystal Space by doxygen 1.2.18