Subversion Repositories phpLibraryV2

Rev

Rev 1 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1 rodolico 1 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"
2 
>
3 
<html>
4 
  <head>
5 
    <title>Hierarchical Howto</title>
6 
    <meta name="GENERATOR" content="Quanta Plus">
7 
    <meta name="AUTHOR" content="R. W. Rodolico">
8 
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
9 
  </head>
10 
  <body>
11 
    <h1>
12 
       Hierarchical Hash Documentation
13 
    </h1>
14 
    <p>
15 
       An Hierarchical Hash is a hash where a parent node may have one or more "chilren", which in turn may act as parent nodes for additional children. This is most commonly seen with a menu, or it could be seen as clients with one or more sites, with each site containing one or more computers, which are made up of components. This can easily be stored in a hash where the top elements are clients, each of which have child nodes that are sites, each of which have child nodes that are computers, etc...
16 
    </p>
17 
    <p>
18 
       The problem with this is storing it the hierarchy in a database table. The most common way to do this is to have a unique id for each node and a second column that points to the parent node (ie, stores the unique id of the parent, if a parent exists)
19 
    </p>
20 
    <p>
21 
       The class DBHierarchicalHash performs the one way function from database table to Hierarchical Hash. As an exercise in usefulness, the class DBMenu extends DBHierarchicalHash to allow an html menu to be stored in a database table.
22 
    </p>
23 
    <h3>
24 
       class DBHierarchicalHash
25 
    </h3>
26 
    <p>
27 
       class reads a database table and converts it to an Hierarchical hash (aka, parent/child).
28 
    </p>
29 
    <p>
30 
       Table structure is assume to be:
31 
    </p>
32 
    <pre> create table menu (
33 
         id        int unsigned not null,
34 
         parent_id int unsigned not null default 0,
35 
         other columns below
36 
      )
37 
    </pre>
38 
    <p>
39 
       where id is a unique identifier and parent_id is points to id in another row (zero indicating it is a top level)
40 
    </p>
41 
    <p>
42 
       NOTE: column names may be changed. Also, while it is assumed id and parent_id are int's, it is quite likely it will work with other column types, including varchar
43 
    </p>
44 
    <p>
45 
       Uses include any parent/child relationship, to an arbitrary depth. See class DBMenu for one example
46 
    </p>
47 
    <p>
48 
       This class was written to be generic. The algorithm used attempts to not take advantage of any special language capabilities, and should be generic. However, various languages can optimize this capability by using capabilities unique to the language in question. For an example, see David North's PERL implementation which utilizes references to allow for a single pass to convert from an array to a Hierarchical structure. Taking advantage of this allows his script to run use no additional memory (this algorithm will double the amount of memory used for the initial array) and does in a single iterative pass what the recursive function copyChildren does.
49 
    </p>
50 
    <table border="1">
51 
      <caption>
52 
         Members
53 
      </caption>
54 
      <thead>
55 
        <tr>
56 
          <th>
57 
             Visibility
58 
          </th>
59 
          <th>
60 
             Variable
61 
          </th>
62 
          <th>
63 
             Description
64 
          </th>
65 
        </tr>
66 
      </thead>
67 
      <tbody>
68 
        <tr>
69 
          <td>
70 
             protected
71 
          </td>
72 
          <td>
73 
             $tableName
74 
          </td>
75 
          <td>
76 
             table name that data will be read from
77 
          </td>
78 
        </tr>
79 
        <tr>
80 
          <td>
81 
             protected
82 
          </td>
83 
          <td>
84 
             $keyField
85 
          </td>
86 
          <td>
87 
             name of the primary id field in table
88 
          </td>
89 
        </tr>
90 
        <tr>
91 
          <td>
92 
             protected
93 
          </td>
94 
          <td>
95 
             $parentFieldName
96 
          </td>
97 
          <td>
98 
             name of the field used to point to the parent of the current row
99 
          </td>
100 
        </tr>
101 
        <tr>
102 
          <td>
103 
             protected
104 
          </td>
105 
          <td>
106 
             $rootNodevalue
107 
          </td>
108 
          <td>
109 
             the value (default 0) of the indicator that a row has no parent. THIS MUST NOT EXIST in the id column of the table
110 
          </td>
111 
        </tr>
112 
        <tr>
113 
          <td>
114 
             protected
115 
          </td>
116 
          <td>
117 
             $inputRecords
118 
          </td>
119 
          <td>
120 
             storage for the records read in.
121 
          </td>
122 
        </tr>
123 
      </tbody>
124 
    </table>
125 
    <table border="1">
126 
      <caption>
127 
         Functions
128 
      </caption>
129 
      <thead>
130 
        <tr>
131 
          <th>
132 
             Visibility
133 
          </th>
134 
          <th>
135 
             Name
136 
          </th>
137 
          <th>
138 
             Parameters
139 
          </th>
140 
          <th>
141 
             Description
142 
          </th>
143 
        </tr>
144 
      </thead>
145 
      <tbody>
146 
        <tr>
147 
          <td>
148 
             public
149 
          </td>
150 
          <td>
151 
             __construct
152 
          </td>
153 
          <td>
154 
             $tableName
155 
            <br>
156 
             $keyField = 'id'
157 
            <br>
158 
             $parentFieldName = 'parent_id'
159 
            <br>
160 
             $rootNodeValue = 0
161 
          </td>
162 
          <td>
163 
             Constructor: Initializes the data, reads from database, and creates the hash
164 
          </td>
165 
        </tr>
166 
        <tr>
167 
          <td>
168 
             private
169 
          </td>
170 
          <td>
171 
             findChildren
172 
          </td>
173 
          <td>
174 
          </td>
175 
          <td>
176 
             Goes through each node and reverses the "who is my parent" to the parent's "who are my children". It does not populate the children; it simply creates an empty array for each child to be processed later.
177 
          </td>
178 
        </tr>
179 
        <tr>
180 
          <td>
181 
             public
182 
          </td>
183 
          <td>
184 
             toHash
185 
          </td>
186 
          <td>
187 
          </td>
188 
          <td>
189 
             simply returns inputRecords for processing by calling routine. This is the goal of this class, to create this structure from the database structure defined above
190 
          </td>
191 
        </tr>
192 
        <tr>
193 
          <td>
194 
             private
195 
          </td>
196 
          <td>
197 
             loadData
198 
          </td>
199 
          <td>
200 
          </td>
201 
          <td>
202 
             loads data from database. The column defined in $this->keyField will become the index into the hash, and all additional columns will simply be added to the array pointed by it. An additional entry in the table will be created with $this->rootNodeValue as its index, to allow root level items to have a parent.
203 
          </td>
204 
        </tr>
205 
        <tr>
206 
          <td>
207 
             private
208 
          </td>
209 
          <td>
210 
             copyChildren
211 
          </td>
212 
          <td>
213 
             $currentNode
214 
          </td>
215 
          <td>
216 
             populates the hiearchy created in load <strong>NOTE</strong>: if the current node also has children, it will recursively do those main call is &amp;copyChildren( rootNode )
217 
          </td>
218 
        </tr>
219 
      </tbody>
220 
    </table>
221 
    <h3>
222 
       class DBMenu extends DBHierarchicalHash
223 
    </h3>
224 
    <p>
225 
       simple extension of DBHierarchicalHash allowing a menu structure to be stored in a database.
226 
    </p>
227 
    <p>
228 
       the structure for the database is simple:
229 
    </p>
230 
    <pre> create table menu (
231 
      menu_id     int unsigned not null auto_increment,
232 
      parent_id   int unsigned not null default 0,
233 
      caption     varchar(20) not null,
234 
      url         varchar(64),
235 
      primary key (menu_id)
236 
   )
237 
    </pre>
238 
    <p>
239 
       where caption is the string displayed on the menu, and url is the (possibly null) url to be called when the link is clicked by the user. The resulting line is something like:
240 
      <br>
241 
      <em>&lt;a href="url"&gt;caption&lt;/a&gt;</em>
242 
    </p>
243 
    <p>
244 
       though this can be modified by changing $menuItemString and $menuHeaderString (see below)
245 
    </p>
246 
    <p>
247 
       menu_id is a unique identifier for a single row, and parent_id points to the menu that it is a submenu of (0 indicates a root menu item)
248 
    </p>
249 
    <p>
250 
      <strong>Note</strong>: I tried to avoid any constants in the class, so column names, menu_id data type, root menu indicator are all modifiable
251 
    </p>
252 
    </pre>
253 
    <table border="1">
254 
      <caption>
255 
         Members
256 
      </caption>
257 
      <thead>
258 
        <tr>
259 
          <th>
260 
             Visibility
261 
          </th>
262 
          <th>
263 
             Variable
264 
          </th>
265 
          <th>
266 
             Description
267 
          </th>
268 
        </tr>
269 
      </thead>
270 
      <tbody>
271 
        <tr>
272 
          <td>
273 
             protected
274 
          </td>
275 
          <td>
276 
             $captionName = 'caption'
277 
          </td>
278 
          <td>
279 
             column name for display string in database
280 
          </td>
281 
        </tr>
282 
        <tr>
283 
          <td>
284 
             protected
285 
          </td>
286 
          <td>
287 
             $urlName = 'url'
288 
          </td>
289 
          <td>
290 
             column name for URL field in database
291 
          </td>
292 
        </tr>
293 
        <tr>
294 
          <td>
295 
             protected
296 
          </td>
297 
          <td>
298 
             $menuItemString = '&lt;li class="menu_item_&lt;level&gt;"&gt;&lt;a href="&lt;url&gt;"&gt;&lt;caption&gt;&lt;/a&gt;&lt;/li&gt;'
299 
          </td>
300 
          <td>
301 
             string which is searched/replaced for a menu item that has a URL (&lt;url&gt; and &lt;caption&gt; are replaced)
302 
          </td>
303 
        </tr>
304 
        <tr>
305 
          <td>
306 
             protected
307 
          </td>
308 
          <td>
309 
             $menuHeaderString = '&lt;li class="menu_header_&lt;level&gt;"&gt;&lt;caption&gt;&lt;/li&gt;'
310 
          </td>
311 
          <td>
312 
             string which is searched/replaced for a menu item that has no URL (&lt;caption&gt; and &lt;level&gt; are replaced)
313 
          </td>
314 
        </tr>
315 
        <tr>
316 
          <td>
317 
             protected
318 
          </td>
319 
          <td>
320 
             $menuBlockString = '&lt;ul class="menu"&gt;&lt;menublock&gt;&lt;/ul&gt;'
321 
          </td>
322 
          <td>
323 
             string which is placed around &lt;menublock&gt;, ie this goes around a menu/submenu. &lt;level&gt; can be used to determine. which level (zero based) we are in the menu (level = 0 is top menu)
324 
          </td>
325 
        </tr>
326 
        <table border="1">
327 
          <caption>
328 
             Functions
329 
          </caption>
330 
          <thead>
331 
            <tr>
332 
              <th>
333 
                 Visibility
334 
              </th>
335 
              <th>
336 
                 Name
337 
              </th>
338 
              <th>
339 
                 Parameters
340 
              </th>
341 
              <th>
342 
                 Description
343 
              </th>
344 
            </tr>
345 
          </thead>
346 
          <tbody>
347 
            <tr>
348 
              <td>
349 
                 public
350 
              </td>
351 
              <td>
352 
                 __construct
353 
              </td>
354 
              <td>
355 
                 $tableName = 'menu'
356 
                <br>
357 
                 $idFieldName = 'id'
358 
                <br>
359 
                 $parentFieldName = 'parent_id'
360 
              </td>
361 
              <td>
362 
                 simply pass fields on to DBHierarchicalHash so it can load and parse the table
363 
              </td>
364 
            </tr>
365 
            <tr>
366 
              <td>
367 
                 public
368 
              </td>
369 
              <td>
370 
                 captionColumnName
371 
              </td>
372 
              <td>
373 
                 $newValue = ''
374 
              </td>
375 
              <td>
376 
                 simple setter/getter for the caption column name in table
377 
              </td>
378 
            </tr>
379 
            <tr>
380 
              <td>
381 
                 public
382 
              </td>
383 
              <td>
384 
                 urlColumnName
385 
              </td>
386 
              <td>
387 
                 $newValue = ''
388 
              </td>
389 
              <td>
390 
                 simple setter/getter for the url column name in table
391 
              </td>
392 
            </tr>
393 
            <tr>
394 
              <td>
395 
                 public
396 
              </td>
397 
              <td>
398 
                 menuItemString
399 
              </td>
400 
              <td>
401 
                 $newValue = ''
402 
              </td>
403 
              <td>
404 
                 simple setter/getter for menuItemString for output
405 
              </td>
406 
            </tr>
407 
            <tr>
408 
              <td>
409 
                 public
410 
              </td>
411 
              <td>
412 
                 menuHeaderString
413 
              </td>
414 
              <td>
415 
                 $newValue = ''
416 
              </td>
417 
              <td>
418 
                 simple setter/getter for menuHeaderString for output
419 
              </td>
420 
            </tr>
421 
            <tr>
422 
              <td>
423 
                 public
424 
              </td>
425 
              <td>
426 
                 menuBlockString
427 
              </td>
428 
              <td>
429 
                 $newValue = ''
430 
              </td>
431 
              <td>
432 
                 simple setter/getter for menu block string for output
433 
              </td>
434 
            </tr>
435 
            <tr>
436 
              <td>
437 
              </td>
438 
              <td>
439 
                 DBMenu2String
440 
              </td>
441 
              <td>
442 
              </td>
443 
              <td>
444 
                 just an entry point to displayMenu, with root of inputRecords and level 0
445 
              </td>
446 
            </tr>
447 
            <tr>
448 
              <td>
449 
                 private
450 
              </td>
451 
              <td>
452 
                 htmlMenu
453 
              </td>
454 
              <td>
455 
                 $menu
456 
                <br>
457 
                 $level=0
458 
              </td>
459 
              <td>
460 
                 function takes a menu level and creates an HTML Menu items from it. If a node has children, will recursively call itself for each child node
461 
              </td>
462 
            </tr>
463 
          </tbody>
464 
        </table>
465 
        </body>
466 
        </html>