CWIS Developer Documentation

- Home
- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

PersistentDoublyLinkedList.php
Go to the documentation of this file.
1 <?PHP
2
3 #
4 # FILE: PersistentDoublyLinkedList.php
5 #
6 # Part of the ScoutLib application support library
7 # Copyright 2012 Edward Almasy and Internet Scout
8 # http://scout.wisc.edu
9 #
10
22 class PersistentDoublyLinkedList {
23
24 # ---- PUBLIC INTERFACE --------------------------------------------------
25
48 function __construct($ItemTableName, $ItemIdFieldName,
49 $SqlCondition = NULL, $ItemTypeFieldName = NULL)
50 {
51 # grab our own database handle
52 $this->DB = new Database();
53
54 # save configuration
55 $this->ItemTableName = $ItemTableName;
56 $this->ItemIdFieldName = $ItemIdFieldName;
57 $this->ItemTypeFieldName = $ItemTypeFieldName;
58 $this->SqlCondition($SqlCondition);
59 }
60
72 function SqlCondition($Condition = NULL)
73 {
74 if ($Condition) { $this->SqlCondition = $Condition; }
75 return $this->SqlCondition;
76 }
77
87 function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
88 $TargetItemType = NULL, $NewItemType = NULL)
89 {
90 # retrieve item IDs
91 $NewItemId = is_object($NewItemOrItemId)
92 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
93 $TargetItemId = is_object($TargetItemOrItemId)
94 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
95
96 # remove source item from current position if necessary
97 $this->Remove($NewItemId);
98
99 # retrieve current previous item pointer for target item
100 $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
101 $TargetItemId, $TargetItemType);
102
103 # if target item not found
104 if ($TargetItemCurrentPreviousId === FALSE)
105 {
106 # add new item to beginning of list
107 $this->Prepend($NewItemId, $NewItemType);
108 }
109 else
110 {
111 # retrieve target item type if available
112 if (is_array($TargetItemCurrentPreviousId))
113 {
114 $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
115 $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
116 }
117 else
118 {
119 $TargetItemCurrentPreviousType = NULL;
120 }
121
122 # update IDs to link in new item
123 $this->SetPreviousItemId(
124 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
125 if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
126 {
127 $this->SetNextItemId($TargetItemCurrentPreviousId,
128 $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
129 }
130 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
131 $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
132 $TargetItemId, $TargetItemType);
133 }
134 }
135
145 function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
146 $TargetItemType = NULL, $NewItemType = NULL)
147 {
148 # retrieve item IDs
149 $NewItemId = is_object($NewItemOrItemId)
150 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
151 $TargetItemId = is_object($TargetItemOrItemId)
152 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
153
154 # remove new item from existing position (if necessary)
155 $this->Remove($NewItemId, $NewItemType);
156
157 # retrieve current next item pointer for target item
158 $TargetItemCurrentNextId = $this->GetNextItemId(
159 $TargetItemId, $TargetItemType);
160
161 # if target item not found
162 if ($TargetItemCurrentNextId === FALSE)
163 {
164 # add new item to end of list
165 $this->Append($NewItemId, $NewItemType);
166 }
167 else
168 {
169 # retrieve target item type if available
170 if (is_array($TargetItemCurrentNextId))
171 {
172 $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
173 $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
174 }
175 else
176 {
177 $TargetItemCurrentNextType = NULL;
178 }
179
180 # update IDs to link in new item
181 $this->SetNextItemId(
182 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
183 if ($TargetItemCurrentNextId != self::LISTEND_ID)
184 {
185 $this->SetPreviousItemId(
186 $TargetItemCurrentNextId, $TargetItemCurrentNextType,
187 $NewItemId, $NewItemType);
188 }
189 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
190 $TargetItemId, $TargetItemType,
191 $TargetItemCurrentNextId, $TargetItemCurrentNextType);
192 }
193 }
194
201 function Prepend($ItemOrItemId, $ItemType = NULL)
202 {
203 # get item ID
204 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
205
206 # remove new item from current position if necessary
207 $this->Remove($ItemId, $ItemType);
208
209 # if there are items currently in list
210 $ItemIds = $this->GetIds(FALSE);
211 if (count($ItemIds))
212 {
213 # link first item to source item
214 if ($this->ItemTypeFieldName)
215 {
216 $Row = array_shift($ItemIds);
217 $FirstItemId = $Row["ID"];
218 $FirstItemType = $Row["Type"];
219 }
220 else
221 {
222 $FirstItemId = array_shift($ItemIds);
223 $FirstItemType = NULL;
224 }
225
226 $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
227 $this->SetPreviousAndNextItemIds(
228 $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
229 $FirstItemId, $FirstItemType);
230 }
231 else
232 {
233 # add item to list as only item
234 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
235 self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID);
236 }
237 }
238
245 function Append($ItemOrItemId, $ItemType = NULL)
246 {
247 # get item ID
248 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
249
250 # remove item from current position if necessary
251 $this->Remove($ItemId, $ItemType);
252
253 # if there are items currently in list
254 $ItemIds = $this->GetIds();
255 if (count($ItemIds))
256 {
257 # link last item to source item
258 if ($this->ItemTypeFieldName)
259 {
260 $Row = array_pop($ItemIds);
261 $LastItemId = $Row["ID"];
262 $LastItemType = $Row["Type"];
263 }
264 else
265 {
266 $LastItemId = array_pop($ItemIds);
267 $LastItemType = NULL;
268 }
269 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
270 $this->SetPreviousAndNextItemIds(
271 $ItemId, $ItemType, $LastItemId, $LastItemType,
272 self::LISTEND_ID, self::LISTEND_ID);
273 }
274 else
275 {
276 # add item to list as only item
277 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
278 self::LISTEND_ID, self::LISTEND_ID,
279 self::LISTEND_ID, self::LISTEND_ID);
280 }
281 }
282
290 function GetIds()
291 {
292 # assume no items will be found in folder
293 $ItemIds = array();
294
295 # if item types are in use
296 if ($this->ItemTypeFieldName)
297 {
298 # retrieve IDs and types of all items in list and links between items
299 $this->DB->Query("SELECT * FROM ".$this->ItemTableName
300 .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
301 ." ORDER BY ".$this->ItemIdFieldName." ASC");
302
303 # build up lists of next and previous item pointers
304 $PreviousItemIds = array();
305 $NextItemIds = array();
306 while ($Record = $this->DB->FetchRow())
307 {
308 $Index = $Record[$this->ItemTypeFieldName]
309 .":".$Record[$this->ItemIdFieldName];
310 $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
311 $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
312 $PreviousItemIds[$Index] = $Record["Previous".$this->ItemTypeFieldName]
313 .":".$Record["Previous".$this->ItemIdFieldName];
314 $NextItemIds[$Index] = $Record["Next".$this->ItemTypeFieldName]
315 .":".$Record["Next".$this->ItemIdFieldName];
316 }
317
318 # find ID of first item in list
319 $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
320 $Index = array_search($ListEndIndex, $PreviousItemIds);
321
322 # if first item was found
323 if ($Index !== FALSE)
324 {
325 # traverse linked list to build list of item types and IDs
326 do
327 {
328 $ItemIds[$Index] = array(
329 "Type" => $KnownItemTypes[$Index],
330 "ID" => $KnownItemIds[$Index]);
331 $Index = $NextItemIds[$Index];
332 }
333 # (stop if we've reached the end of the list)
334 while (($Index != $ListEndIndex)
335 # (stop if link points to item not in list)
336 && array_key_exists($Index, $NextItemIds)
337 # (stop if link is circular)
338 && !array_key_exists($Index, $ItemIds));
339 }
340 }
341 else
342 {
343 # retrieve IDs of all items in list and links between items
344 $this->DB->Query("SELECT ".$this->ItemIdFieldName
345 .", Previous".$this->ItemIdFieldName
346 .", Next".$this->ItemIdFieldName
347 ." FROM ".$this->ItemTableName
348 .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
349 ." ORDER BY ".$this->ItemIdFieldName." ASC");
350
351 # build up lists of next item pointers
352 $PreviousItemIds = array();
353 $NextItemIds = array();
354 while ($Record = $this->DB->FetchRow())
355 {
356 $Index = $Record[$this->ItemIdFieldName];
357 $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
358 $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
359 }
360
361 # find ID of first item in list
362 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
363
364 # if first item was found
365 if ($ItemId !== FALSE)
366 {
367 # traverse linked list to build list of item IDs
368 do
369 {
370 $ItemIds[] = $ItemId;
371 $ItemId = $NextItemIds[$ItemId];
372 }
373 # (stop if we've reached the end of the list)
374 while (($ItemId != self::LISTEND_ID)
375 # (stop if link points to item not in list)
376 && array_key_exists($ItemId, $NextItemIds)
377 # (stop if link is circular)
378 && !in_array($ItemId, $ItemIds));
379 }
380 }
381
382 # return list of item IDs to caller
383 return $ItemIds;
384 }
385
392 function Remove($ItemId, $ItemType = NULL)
393 {
394 # retrieve item's "previous" pointer
395 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
396
397 # bail out if item was not found
398 if ($CurrentItemPreviousId === FALSE) { return; }
399
400 # retrieve item's "next" pointer
401 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
402 if ($this->ItemTypeFieldName)
403 {
404 $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
405 $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
406 $CurrentItemNextType = $CurrentItemNextId["Type"];
407 $CurrentItemNextId = $CurrentItemNextId["ID"];
408 }
409 else
410 {
411 $CurrentItemPreviousType = NULL;
412 $CurrentItemNextType = NULL;
413 }
414
415 # if item was not first in list
416 if ($CurrentItemPreviousId >= 0)
417 {
418 # link previous item to item's current next item
419 $this->SetNextItemId(
420 $CurrentItemPreviousId, $CurrentItemPreviousType,
421 $CurrentItemNextId, $CurrentItemNextType);
422 }
423
424 # if item was not last in list
425 if ($CurrentItemNextId >= 0)
426 {
427 # link next item to item's current previous item
428 $this->SetPreviousItemId(
429 $CurrentItemNextId, $CurrentItemNextType,
430 $CurrentItemPreviousId, $CurrentItemPreviousType);
431 }
432
433 # set items pointers to indicate it is not part of a list
434 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
435 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
436 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
437 }
438
439
440 # ---- PRIVATE INTERFACE -------------------------------------------------
441
442 private $DB;
443 private $ItemTableName;
444 private $ItemIdFieldName;
445 private $ItemTypeFieldName;
446 private $SqlCondition = NULL;
447
448 const UNINITIALIZED_ID = -1;
449 const LISTEND_ID = -2;
450
451 # get ordering values (return FALSE if specified item not found)
452 private function GetPreviousItemId($ItemId, $ItemType)
453 {
454 if ($this->ItemTypeFieldName)
455 {
456 $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
457 .", Previous".$this->ItemTypeFieldName
458 ." FROM ".$this->ItemTableName
459 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
460 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
461 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
462 if (!$this->DB->NumRowsSelected()) { return FALSE; }
463 $Row = $this->DB->FetchRow();
464 if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
465 { return FALSE; }
466 $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
467 $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
468 return $ReturnValue;
469 }
470 else
471 {
472 $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
473 ." FROM ".$this->ItemTableName
474 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
475 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
476 "Previous".$this->ItemIdFieldName);
477 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
478 }
479 }
480 private function GetNextItemId($ItemId, $ItemType)
481 {
482 if ($this->ItemTypeFieldName)
483 {
484 $this->DB->Query("SELECT Next".$this->ItemIdFieldName
485 .", Next".$this->ItemTypeFieldName
486 ." FROM ".$this->ItemTableName
487 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
488 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
489 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
490 if (!$this->DB->NumRowsSelected()) { return FALSE; }
491 $Row = $this->DB->FetchRow();
492 if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
493 { return FALSE; }
494 $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
495 $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
496 return $ReturnValue;
497 }
498 else
499 {
500 $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
501 ." FROM ".$this->ItemTableName
502 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
503 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
504 "Next".$this->ItemIdFieldName);
505 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
506 }
507 }
508
509 # set ordering values
510 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
511 {
512 if ($this->ItemTypeFieldName)
513 {
514 $this->DB->Query("UPDATE ".$this->ItemTableName
515 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
516 .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
517 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
518 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
519 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
520 }
521 else
522 {
523 $this->DB->Query("UPDATE ".$this->ItemTableName
524 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
525 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
526 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
527 }
528 }
529 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
530 {
531 if ($this->ItemTypeFieldName)
532 {
533 $this->DB->Query("UPDATE ".$this->ItemTableName
534 ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
535 .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
536 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
537 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
538 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
539 }
540 else
541 {
542 $this->DB->Query("UPDATE ".$this->ItemTableName
543 ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
544 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
545 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
546 }
547 }
548 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
549 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
550 {
551 if ($this->ItemTypeFieldName)
552 {
553 $this->DB->Query("UPDATE ".$this->ItemTableName
554 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
555 .", Previous".$this->ItemTypeFieldName." = "
556 .intval($NewPreviousType)
557 .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
558 .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
559 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
560 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
561 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
562 }
563 else
564 {
565 $this->DB->Query("UPDATE ".$this->ItemTableName
566 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
567 .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
568 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
569 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
570 }
571 }
572 }
573
574
575 ?>