Subversion Repositories phpLibraryV2

Rev

Details | 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>