CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

tree.h

00001 /*
00002     Copyright (C) 2000 by Norman Krämer
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 "csutil/csvector.h"
00023 
00027 class csTreeNode
00028 {
00029  public:
00030 
00032   bool IsLeaf ()
00033   { return children.Length () == 0; }
00034 
00036   void RemoveChild (csTreeNode *child)
00037   { int idx = children.Find (child); if (idx != -1) children.Delete (idx); }
00038 
00040   void AddChild (csTreeNode *child)
00041   { children.Push (child); child->parent = this; }
00042 
00044   csTreeNode (csTreeNode *theParent=NULL)
00045   { parent=theParent; if (parent) parent->children.Push (this); }
00046 
00047   virtual ~csTreeNode ()
00048   {
00049         int i;
00050     for(i=children.Length ()-1; i>=0; i--)
00051       delete (csTreeNode*)children.Get (i);
00052     if (parent)
00053       parent->RemoveChild (this);
00054   }
00055 
00063   csTreeNode *DSF (bool (*TreeFunc)(csTreeNode *node, void* param, bool stopOnSuccess),
00064                    bool (*SelBranch)(csTreeNode *node), void* param, bool stopOnSuccess)
00065   {
00066     csTreeNode *foundNode = NULL;
00067     int i=0;
00068     bool dive;
00069     if (TreeFunc (this, param, stopOnSuccess))
00070       foundNode = this;
00071     while (i<children.Length () && !(foundNode && stopOnSuccess))
00072     {
00073       dive = (SelBranch == NULL) || SelBranch ((csTreeNode*)children.Get (i));
00074       if (dive)
00075         foundNode = ((csTreeNode*)children.Get (i))->DSF (TreeFunc, SelBranch,
00076                                                           param, stopOnSuccess);
00077         i++;
00078     }
00079     return foundNode;
00080   }
00081 
00089   csTreeNode *BSF (bool (*TreeFunc)(csTreeNode *node, void* param, bool stopOnSuccess),
00090                    bool (*SelBranch)(csTreeNode *node), void* param, bool stopOnSuccess)
00091   {
00092     csTreeNode *node, *foundNode = NULL;
00093     csVector fifo;
00094 
00095     fifo.Push (this);
00096     while (fifo.Length () > 0 && !(foundNode && stopOnSuccess))
00097     {
00098       node = (csTreeNode*)fifo.Get (0); fifo.Delete (0);
00099       if (TreeFunc (node, param, stopOnSuccess))
00100         foundNode = node;
00101       if (!node->IsLeaf () && (SelBranch==NULL || SelBranch (node)))
00102           {
00103                 int i;
00104         for (i=0; i < node->children.Length (); i++ )
00105           fifo.Push (node->children.Get (i));
00106           }
00107     }
00108     fifo.DeleteAll ();
00109     return foundNode;
00110   }
00111 
00112  public:
00113   csTreeNode *parent; // parent node or NULL if toplevel
00114   csVector children; // node children
00115 };
00116 
00117 #endif // __CS_CSTREENODE_H__

Generated for Crystal Space by doxygen 1.2.14