CrystalSpace

Public API Reference

csutil/tree.h

Go to the documentation of this file.
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 
00026 #include "csextern.h"
00027 #include "array.h"
00028 
00032 class csTreeNode
00033 {
00034 public:
00036   bool IsLeaf ()
00037   { return children.GetSize () == 0; }
00038 
00040   void RemoveChild (csTreeNode *child)
00041   {
00042     size_t idx = children.Find (child);
00043     if (idx != csArrayItemNotFound) children.DeleteIndex (idx);
00044   }
00045 
00047   void AddChild (csTreeNode *child)
00048   { children.Push (child); child->parent = this; }
00049 
00051   csTreeNode (csTreeNode *theParent=0)
00052   { parent=theParent; if (parent) parent->children.Push (this); }
00053 
00054   virtual ~csTreeNode ()
00055   {
00056     size_t i;
00057     for(i=children.GetSize (); i>0; i--)
00058       delete children.Get (i - 1);
00059     if (parent)
00060       parent->RemoveChild (this);
00061   }
00062 
00073   csTreeNode *DSF (bool (*TreeFunc)(csTreeNode *node, void* param,
00074                                         bool stopOnSuccess),
00075                    bool (*SelBranch)(csTreeNode *node), void* param,
00076                                         bool stopOnSuccess)
00077   {
00078     csTreeNode *foundNode = 0;
00079     size_t i=0;
00080     bool dive;
00081     if (TreeFunc (this, param, stopOnSuccess))
00082       foundNode = this;
00083     while (i<children.GetSize () && !(foundNode && stopOnSuccess))
00084     {
00085       dive = (SelBranch == 0) || SelBranch (children[i]);
00086       if (dive)
00087         foundNode = (children[i])->DSF (TreeFunc, SelBranch,
00088                 param, stopOnSuccess);
00089       i++;
00090     }
00091     return foundNode;
00092   }
00093 
00104   csTreeNode *BSF (bool (*TreeFunc)(csTreeNode *node, void* param,
00105                                 bool stopOnSuccess),
00106                    bool (*SelBranch)(csTreeNode *node), void* param,
00107                                 bool stopOnSuccess)
00108   {
00109     csTreeNode *node, *foundNode = 0;
00110     csArray<csTreeNode*> fifo;
00111 
00112     fifo.Push (this);
00113     while (fifo.GetSize () > 0 && !(foundNode && stopOnSuccess))
00114     {
00115       node = fifo[0]; fifo.DeleteIndex (0);
00116       if (TreeFunc (node, param, stopOnSuccess))
00117         foundNode = node;
00118       if (!node->IsLeaf () && (SelBranch==0 || SelBranch (node)))
00119       {
00120         size_t i;
00121         for (i=0; i < node->children.GetSize (); i++ )
00122           fifo.Push (node->children[i]);
00123       }
00124     }
00125     fifo.DeleteAll ();
00126     return foundNode;
00127   }
00128 
00129  public:
00130   csTreeNode *parent; // parent node or 0 if toplevel
00131   csArray<csTreeNode*> children; // node children
00132 };
00133 
00134 #endif // __CS_CSTREENODE_H__

Generated for Crystal Space 1.2.1 by doxygen 1.5.3