Software and Services, Portable Libraries  2019.Mar.01
A library for managing digital certificates
TreeSearch.hpp
1 /* Binary tree data structure.
2  * Copyright (C) 2006 Free Software Foundation, Inc.
3  *
4  * This program is free software; you can redistribute it and/or modify it
5  * under the terms of the GNU Library General Public License as published
6  * by the Free Software Foundation; either version 2, or (at your option)
7  * any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy xof the GNU Library General Public
15  * License along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
17  * USA.
18  *
19  * Copyright 2015 Douglas Mark Royer.
20  * Converted to a C++ template / object.
21  * This file still under the FSF free license.
22  */
23 
24 #ifndef DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H
25 #define DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H
26 
27 
28 #ifdef BUILDING_SAS_COMMON_LIBRARY
29 #include "strsearch.hpp"
30 #else
31 #include <SaS/Common/strsearch.hpp>
32 #endif
33 
34 namespace SoftwareAndServices
35 {
36  namespace Library
37  {
38  namespace Common
39  {
40 
41  template <class T> class Tree_t
42  : public node_t
43  {
44 
45  public:
46 
51  {
52  /*EMPTY*/
53 
54  return;
55  }
56 
60  virtual ~Tree_t<T>()
61  {
62  /*EMPTY*/
63 
64  return;
65  }
66 
70  typedef Tree_t<T> * Tree;
71 
75  typedef const Tree_t<T> * const_Tree;
76 
88  typedef int (*TreeCompare_fn_t)(const T * One, const T * Two);
89 
99  typedef void (*TreeAction_fn_t)(const Tree_t<T> **,
100  VISIT Leaf,
101  int Depth);
102 
108  typedef void (*TreeFree_fn_t)(Tree_t<T> * TreeToFree);
109 
110  /*
111  * Searches an element in the tree *VRootP that compares equal to KEY.
112  * If one is found, it is returned. Otherwise, a new element equal to
113  * KEY is inserted in the tree and is returned.
114  *
115  * @param Key The key to search for.
116  *
117  * @param VRootP A pointer to the root Tree_t<T>.
118  *
119  * @param CompareFunction To method to call to compare.
120  *
121  * @return The T Found, or the new T inserted.
122  */
123  static T ** Search(const T * Key,
124  Tree_t<T> * const * VRootP,
125  TreeCompare_fn_t CompareFunction)
126  {
127  T ** Results = (T**) strsearch(Key,
128  (node_t*const*)VRootP,
129  (strcompare_fn_t)CompareFunction);
130 
131  return(Results);
132  }
133 
134  /*
135  * Searches an element in the tree *VRootP that compares equal to Key.
136  * If one is found, it is returned. Otherwise, nullptr is returned.
137  *
138  * @param Key The key to search for.
139  *
140  * @param VRootP A pointer to the root Tree_t<T>.
141  *
142  * @param CompareFunction To method to call to compare.
143  *
144  * @return The T found, or nullptr if none.
145  */
146  static T ** Find(const T * Key,
147  Tree_t<T> * const * VRootP,
148  TreeCompare_fn_t CompareFunction)
149  {
150  T ** Results = (T**)strfind(Key,
151  (node_t*const*)VRootP,
152  (strcompare_fn_t)CompareFunction);
153 
154  return(Results);
155  }
156 
157  /*
158  * Searches an element in the tree *VRootP that compares equal to Key.
159  * If one is found, it is removed from the tree, and its parent node is
160  * returned. Otherwise, nullptr is returned.
161  *
162  * @param Key The key to search for.
163  *
164  * @param VRootP A pointer to the root Tree_t<T>.
165  *
166  * @param CompareFunction To method to call to compare.
167  *
168  */
169  static T ** Delete(const void * Key,
170  Tree_t<T> ** VRootP,
171  TreeCompare_fn_t CompareFunction)
172  {
173  T ** Results = (T**)strdelete(Key,
174  (node_t**)VRootP,
175  (strcompare_fn_t)CompareFunction);
176 
177  return(Results);
178  }
179 
180  /*
181  * Perform a depth-first, left-to-right traversal of the tree VRoot.
182  * The ACTION function is called:
183  *
184  * - for non-leaf nodes: 3 times, before the left subtree traversal,
185  * after the left subtree traversal but before the right subtree
186  * traversal, and after the right subtree traversal,
187  * - for leaf nodes: once.
188  *
189  * The arguments passed to ACTION are:
190  *
191  * 1. The node; it can be casted to a 'const void * const *', i.e.
192  * into a pointer to the key,
193  * 2. An indicator which visit of the node this is,
194  * 3. The level of the node in the tree (0 for the root).
195  *
196  * @param VRoot The root of the tree.
197  *
198  * @param Action The method to call.
199  */
200  static void Walk(const Tree_t<T> * VRoot,
201  TreeAction_fn_t Action)
202  {
203  strwalk(VRoot, (straction_fn_t)Action);
204 
205  return;
206  }
207 
208  };
209 
210 
211  }
212  }
213 }
214 
215 #endif // DOUGLAS_MARK_ROYER_LIBRARY_COMMON_NODESEARCH_H
const Tree_t< T > * const_Tree
A const_Tree is a (const Tree_t<T>*)
Definition: TreeSearch.hpp:75
void(* TreeAction_fn_t)(const Tree_t< T > **, VISIT Leaf, int Depth)
Perform action on Tree_t<T>
Definition: TreeSearch.hpp:99
Copyright Douglas Mark Royer DouglasRoyer@gmail.com.
Definition: Base.hpp:98
void(* TreeFree_fn_t)(Tree_t< T > *TreeToFree)
Free Tree_t.
Definition: TreeSearch.hpp:108
int(* TreeCompare_fn_t)(const T *One, const T *Two)
Tree compare function.
Definition: TreeSearch.hpp:88
Tree_t< T > * Tree
A Tree is a (Tree_t<T>*)
Definition: TreeSearch.hpp:70