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 # FILE: PersistentDoublyLinkedList.php
4 #
5 # Part of the ScoutLib application support library
6 # Copyright 2012-2013 Edward Almasy and Internet Scout Research Group
7 # http://scout.wisc.edu
8 #
9
21 class PersistentDoublyLinkedList {
22
23 # ---- PUBLIC INTERFACE --------------------------------------------------
24
47 function __construct($ItemTableName, $ItemIdFieldName,
48 $SqlCondition = NULL, $ItemTypeFieldName = NULL)
49 {
50 # grab our own database handle
51 $this->DB = new Database();
52
53 # save configuration
54 $this->ItemTableName = $ItemTableName;
55 $this->ItemIdFieldName = $ItemIdFieldName;
56 $this->ItemTypeFieldName = $ItemTypeFieldName;
57 $this->ItemTypesInUse = ($ItemTypeFieldName === NULL) ? FALSE : TRUE;
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->ItemTypesInUse)
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
248 function Append($ItemsOrItemIds, $ItemTypes = NULL)
249 {
250 # check that item types were supplied if needed
251 if ($this->ItemTypesInUse && ($ItemTypes === NULL))
252 {
253 throw new Exception("Item type(s) not supplied.");
254 }
255
256 # make incoming values into arrays if they aren't already
257 if (!is_array($ItemsOrItemIds))
258 {
259 $ItemsOrItemIds = array($ItemsOrItemIds);
260 }
261 if (!is_array($ItemTypes))
262 {
263 $NewItemTypes = array();
264 foreach ($ItemsOrItemIds as $Id)
265 {
266 $NewItemTypes[] = $ItemTypes;
267 }
268 $ItemTypes = $NewItemTypes;
269 }
270
271 # get item IDs
272 $ItemIds = array();
273 foreach ($ItemsOrItemIds as $ItemOrId)
274 {
275 $ItemIds[] = is_object($ItemOrId) ? $ItemOrId->Id() : $ItemOrId;
276 }
277
278 # lock database to prevent anyone from mucking up our changes
279 $this->DB->Query("LOCK TABLES `".$this->ItemTableName."` WRITE");
280
281 # for each item
282 $ItemIdList = $this->GetIds();
283 foreach ($ItemIds as $Index => $ItemId)
284 {
285 # retrieve item type
286 $ItemType = $ItemTypes[$Index];
287
288 # if there are items currently in list
289 if (count($ItemIdList))
290 {
291 # remove item from current position if necessary
292 $ItemWasRemoved = $this->Remove($ItemId, $ItemType);
293
294 # reload item ID list if necessary
295 if ($ItemWasRemoved)
296 {
297 $ItemIdList = $this->GetIds();
298 }
299 }
300
301 # if there are still items currently in list
302 if (count($ItemIdList))
303 {
304 # find ID and type of last item in list
305 if ($this->ItemTypesInUse)
306 {
307 $Row = array_pop($ItemIdList);
308 $LastItemId = $Row["ID"];
309 $LastItemType = $Row["Type"];
310 array_push($ItemIdList, $Row);
311 }
312 else
313 {
314 $LastItemId = array_pop($ItemIdList);
315 $LastItemType = NULL;
316 array_push($ItemIdList, $LastItemId);
317 }
318
319 # link last item to source item
320 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
321 $this->SetPreviousAndNextItemIds(
322 $ItemId, $ItemType, $LastItemId, $LastItemType,
323 self::LISTEND_ID, self::LISTEND_ID);
324 }
325 else
326 {
327 # add item to list as only item
328 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
329 self::LISTEND_ID, self::LISTEND_ID,
330 self::LISTEND_ID, self::LISTEND_ID);
331 }
332
333 # add item to our local ID list
334 array_push($ItemIdList,
335 $this->ItemTypesInUse
336 ? array("ID" => $ItemId, "Type" => $ItemType)
337 : $ItemId);
338 }
339
340 # unlock database
341 $this->DB->Query("UNLOCK TABLES");
342 }
343
351 function GetIds()
352 {
353 # assume no items will be found in folder
354 $ItemIds = array();
355
356 # if item types are in use
357 if ($this->ItemTypesInUse)
358 {
359 # retrieve IDs and types of all items in list and links between items
360 $this->DB->Query("SELECT * FROM ".$this->ItemTableName
361 .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
362 ." ORDER BY ".$this->ItemIdFieldName." ASC");
363
364 # build up lists of next and previous item pointers
365 $PreviousItemIds = array();
366 $NextItemIds = array();
367 while ($Record = $this->DB->FetchRow())
368 {
369 $Index = $Record[$this->ItemTypeFieldName]
370 .":".$Record[$this->ItemIdFieldName];
371 $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
372 $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
373 $PreviousItemIds[$Index] = $Record["Previous".$this->ItemTypeFieldName]
374 .":".$Record["Previous".$this->ItemIdFieldName];
375 $NextItemIds[$Index] = $Record["Next".$this->ItemTypeFieldName]
376 .":".$Record["Next".$this->ItemIdFieldName];
377 }
378
379 # find ID of first item in list
380 $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
381 $Index = array_search($ListEndIndex, $PreviousItemIds);
382
383 # if first item was found
384 if ($Index !== FALSE)
385 {
386 # traverse linked list to build list of item types and IDs
387 do
388 {
389 $ItemIds[$Index] = array(
390 "Type" => $KnownItemTypes[$Index],
391 "ID" => $KnownItemIds[$Index]);
392 $Index = $NextItemIds[$Index];
393 }
394 # (stop if we've reached the end of the list)
395 while (($Index != $ListEndIndex)
396 # (stop if link points to item not in list)
397 && array_key_exists($Index, $NextItemIds)
398 # (stop if link is circular)
399 && !array_key_exists($Index, $ItemIds));
400 }
401 }
402 else
403 {
404 # retrieve IDs of all items in list and links between items
405 $this->DB->Query("SELECT ".$this->ItemIdFieldName
406 .", Previous".$this->ItemIdFieldName
407 .", Next".$this->ItemIdFieldName
408 ." FROM ".$this->ItemTableName
409 .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
410 ." ORDER BY ".$this->ItemIdFieldName." ASC");
411
412 # build up lists of next item pointers
413 $PreviousItemIds = array();
414 $NextItemIds = array();
415 while ($Record = $this->DB->FetchRow())
416 {
417 $Index = $Record[$this->ItemIdFieldName];
418 $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
419 $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
420 }
421
422 # find ID of first item in list
423 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
424
425 # if first item was found
426 if ($ItemId !== FALSE)
427 {
428 # traverse linked list to build list of item IDs
429 do
430 {
431 $ItemIds[] = $ItemId;
432 $ItemId = $NextItemIds[$ItemId];
433 }
434 # (stop if we've reached the end of the list)
435 while (($ItemId != self::LISTEND_ID)
436 # (stop if link points to item not in list)
437 && array_key_exists($ItemId, $NextItemIds)
438 # (stop if link is circular)
439 && !in_array($ItemId, $ItemIds));
440 }
441 }
442
443 # return list of item IDs to caller
444 return $ItemIds;
445 }
446
451 function GetCount()
452 {
453 # retrieve count of items
454 return $this->DB->Query("SELECT COUNT(DISTINCT `".$this->ItemIdFieldName
455 ."`) AS ItemCount FROM ".$this->ItemTableName
456 .($this->SqlCondition ? " WHERE ".$this->SqlCondition : ""),
457 "ItemCount");
458 }
459
467 function Remove($ItemId, $ItemType = NULL)
468 {
469 # retrieve item's "previous" pointer
470 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
471
472 # bail out if item was not found
473 if ($CurrentItemPreviousId === FALSE) { return FALSE; }
474
475 # retrieve item's "next" pointer
476 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
477 if ($this->ItemTypesInUse)
478 {
479 $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
480 $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
481 $CurrentItemNextType = $CurrentItemNextId["Type"];
482 $CurrentItemNextId = $CurrentItemNextId["ID"];
483 }
484 else
485 {
486 $CurrentItemPreviousType = NULL;
487 $CurrentItemNextType = NULL;
488 }
489
490 # if item was not first in list
491 if ($CurrentItemPreviousId >= 0)
492 {
493 # link previous item to item's current next item
494 $this->SetNextItemId(
495 $CurrentItemPreviousId, $CurrentItemPreviousType,
496 $CurrentItemNextId, $CurrentItemNextType);
497 }
498
499 # if item was not last in list
500 if ($CurrentItemNextId >= 0)
501 {
502 # link next item to item's current previous item
503 $this->SetPreviousItemId(
504 $CurrentItemNextId, $CurrentItemNextType,
505 $CurrentItemPreviousId, $CurrentItemPreviousType);
506 }
507
508 # set items pointers to indicate it is not part of a list
509 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
510 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
511 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
512
513 # report that item was removed
514 return TRUE;
515 }
516
517
518 # ---- PRIVATE INTERFACE -------------------------------------------------
519
520 private $DB;
522 private $ItemTableName;
524 private $ItemIdFieldName;
526 private $ItemTypeFieldName;
528 private $ItemTypesInUse;
530 private $SqlCondition = NULL;
531
532 const UNINITIALIZED_ID = -1;
533 const LISTEND_ID = -2;
534
542 private function GetPreviousItemId($ItemId, $ItemType)
543 {
544 if ($this->ItemTypesInUse)
545 {
546 $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
547 .", Previous".$this->ItemTypeFieldName
548 ." FROM ".$this->ItemTableName
549 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
550 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
551 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
552 if (!$this->DB->NumRowsSelected()) { return FALSE; }
553 $Row = $this->DB->FetchRow();
554 if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
555 { return FALSE; }
556 $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
557 $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
558 return $ReturnValue;
559 }
560 else
561 {
562 $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
563 ." FROM ".$this->ItemTableName
564 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
565 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
566 "Previous".$this->ItemIdFieldName);
567 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
568 }
569 }
570
578 private function GetNextItemId($ItemId, $ItemType)
579 {
580 if ($this->ItemTypesInUse)
581 {
582 $this->DB->Query("SELECT Next".$this->ItemIdFieldName
583 .", Next".$this->ItemTypeFieldName
584 ." FROM ".$this->ItemTableName
585 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
586 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
587 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
588 if (!$this->DB->NumRowsSelected()) { return FALSE; }
589 $Row = $this->DB->FetchRow();
590 if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
591 { return FALSE; }
592 $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
593 $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
594 return $ReturnValue;
595 }
596 else
597 {
598 $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
599 ." FROM ".$this->ItemTableName
600 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
601 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
602 "Next".$this->ItemIdFieldName);
603 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
604 }
605 }
606
614 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
615 {
616 if ($this->ItemTypesInUse)
617 {
618 $this->DB->Query("UPDATE ".$this->ItemTableName
619 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
620 .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
621 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
622 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
623 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
624 }
625 else
626 {
627 $this->DB->Query("UPDATE ".$this->ItemTableName
628 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
629 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
630 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
631 }
632 }
633
641 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
642 {
643 if ($this->ItemTypesInUse)
644 {
645 $this->DB->Query("UPDATE ".$this->ItemTableName
646 ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
647 .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
648 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
649 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
650 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
651 }
652 else
653 {
654 $this->DB->Query("UPDATE ".$this->ItemTableName
655 ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
656 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
657 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
658 }
659 }
660
670 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
671 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
672 {
673 if ($this->ItemTypesInUse)
674 {
675 $this->DB->Query("UPDATE ".$this->ItemTableName
676 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
677 .", Previous".$this->ItemTypeFieldName." = "
678 .intval($NewPreviousType)
679 .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
680 .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
681 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
682 ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
683 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
684 }
685 else
686 {
687 $this->DB->Query("UPDATE ".$this->ItemTableName
688 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
689 .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
690 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
691 .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
692 }
693 }
694 }
695
696
Database
SQL database abstraction object with smart query caching.
Definition: Axis--Database.php:22
PersistentDoublyLinkedList\__construct
__construct($ItemTableName, $ItemIdFieldName, $SqlCondition=NULL, $ItemTypeFieldName=NULL)
Object constructor.
Definition: PersistentDoublyLinkedList.php:47
PersistentDoublyLinkedList\SqlCondition
SqlCondition($Condition=NULL)
Get or set/update SQL condition for referencing items in database.
Definition: PersistentDoublyLinkedList.php:72
PersistentDoublyLinkedList\UNINITIALIZED_ID
const UNINITIALIZED_ID
Definition: PersistentDoublyLinkedList.php:532
PersistentDoublyLinkedList\LISTEND_ID
const LISTEND_ID
Definition: PersistentDoublyLinkedList.php:533
PersistentDoublyLinkedList\Prepend
Prepend($ItemOrItemId, $ItemType=NULL)
Add item to beginning of list.
Definition: PersistentDoublyLinkedList.php:201
PersistentDoublyLinkedList\GetIds
GetIds()
Retrieve array of IDs of items in list, in the order that they appear in the list.
Definition: PersistentDoublyLinkedList.php:351
PersistentDoublyLinkedList\Remove
Remove($ItemId, $ItemType=NULL)
Remove item from list.
Definition: PersistentDoublyLinkedList.php:467
PHP
PHP
Definition: RSSClient--Test.php:12
PersistentDoublyLinkedList\InsertBefore
InsertBefore($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list before specified item.
Definition: PersistentDoublyLinkedList.php:87
PersistentDoublyLinkedList\GetCount
GetCount()
Get number of items in list.
Definition: PersistentDoublyLinkedList.php:451
PersistentDoublyLinkedList\InsertAfter
InsertAfter($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list after specified item.
Definition: PersistentDoublyLinkedList.php:145
PersistentDoublyLinkedList
Persistent doubly-linked-list data structure, with its data stored in a specified database table...
Definition: PersistentDoublyLinkedList.php:21
PersistentDoublyLinkedList\Append
Append($ItemsOrItemIds, $ItemTypes=NULL)
Add item(s) to end of list.
Definition: PersistentDoublyLinkedList.php:248