3 # FILE: PersistentDoublyLinkedList.php
5 # Part of the ScoutLib application support library
6 # Copyright 2012-2013 Edward Almasy and Internet Scout Research Group
7 # http://scout.wisc.edu
23 # ---- PUBLIC INTERFACE --------------------------------------------------
48 $SqlCondition = NULL, $ItemTypeFieldName = NULL)
50 # grab our own database handle
54 $this->ItemTableName = $ItemTableName;
55 $this->ItemIdFieldName = $ItemIdFieldName;
56 $this->ItemTypeFieldName = $ItemTypeFieldName;
57 $this->ItemTypesInUse = ($ItemTypeFieldName === NULL) ? FALSE : TRUE;
75 return $this->SqlCondition;
88 $TargetItemType = NULL, $NewItemType = NULL)
91 $NewItemId = is_object($NewItemOrItemId)
92 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
93 $TargetItemId = is_object($TargetItemOrItemId)
94 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
96 # remove source item from current position if necessary
99 # retrieve current previous item pointer for target item
100 $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
101 $TargetItemId, $TargetItemType);
103 # if target item not found
104 if ($TargetItemCurrentPreviousId === FALSE)
106 # add new item to beginning of list
107 $this->
Prepend($NewItemId, $NewItemType);
111 # retrieve target item type if available
112 if (is_array($TargetItemCurrentPreviousId))
114 $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId[
"Type"];
115 $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId[
"ID"];
119 $TargetItemCurrentPreviousType = NULL;
122 # update IDs to link in new item
123 $this->SetPreviousItemId(
124 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
125 if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
127 $this->SetNextItemId($TargetItemCurrentPreviousId,
128 $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
130 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
131 $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
132 $TargetItemId, $TargetItemType);
146 $TargetItemType = NULL, $NewItemType = NULL)
149 $NewItemId = is_object($NewItemOrItemId)
150 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
151 $TargetItemId = is_object($TargetItemOrItemId)
152 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
154 # remove new item from existing position (if necessary)
155 $this->
Remove($NewItemId, $NewItemType);
157 # retrieve current next item pointer for target item
158 $TargetItemCurrentNextId = $this->GetNextItemId(
159 $TargetItemId, $TargetItemType);
161 # if target item not found
162 if ($TargetItemCurrentNextId === FALSE)
164 # add new item to end of list
165 $this->
Append($NewItemId, $NewItemType);
169 # retrieve target item type if available
170 if (is_array($TargetItemCurrentNextId))
172 $TargetItemCurrentNextType = $TargetItemCurrentNextId[
"Type"];
173 $TargetItemCurrentNextId = $TargetItemCurrentNextId[
"ID"];
177 $TargetItemCurrentNextType = NULL;
180 # update IDs to link in new item
181 $this->SetNextItemId(
182 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
183 if ($TargetItemCurrentNextId != self::LISTEND_ID)
185 $this->SetPreviousItemId(
186 $TargetItemCurrentNextId, $TargetItemCurrentNextType,
187 $NewItemId, $NewItemType);
189 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
190 $TargetItemId, $TargetItemType,
191 $TargetItemCurrentNextId, $TargetItemCurrentNextType);
201 function Prepend($ItemOrItemId, $ItemType = NULL)
204 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
206 # remove new item from current position if necessary
207 $this->
Remove($ItemId, $ItemType);
209 # if there are items currently in list
210 $ItemIds = $this->
GetIds(FALSE);
213 # link first item to source item
214 if ($this->ItemTypesInUse)
216 $Row = array_shift($ItemIds);
217 $FirstItemId = $Row[
"ID"];
218 $FirstItemType = $Row[
"Type"];
222 $FirstItemId = array_shift($ItemIds);
223 $FirstItemType = NULL;
226 $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
227 $this->SetPreviousAndNextItemIds(
228 $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
229 $FirstItemId, $FirstItemType);
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);
248 function Append($ItemsOrItemIds, $ItemTypes = NULL)
250 # check that item types were supplied if needed
251 if ($this->ItemTypesInUse && ($ItemTypes === NULL))
253 throw new Exception(
"Item type(s) not supplied.");
256 # make incoming values into arrays if they aren't already
257 if (!is_array($ItemsOrItemIds))
259 $ItemsOrItemIds = array($ItemsOrItemIds);
261 if (!is_array($ItemTypes))
263 $NewItemTypes = array();
264 foreach ($ItemsOrItemIds as $Id)
266 $NewItemTypes[] = $ItemTypes;
268 $ItemTypes = $NewItemTypes;
273 foreach ($ItemsOrItemIds as $ItemOrId)
275 $ItemIds[] = is_object($ItemOrId) ? $ItemOrId->Id() : $ItemOrId;
278 # lock database to prevent anyone from mucking up our changes
279 $this->DB->Query(
"LOCK TABLES `".$this->ItemTableName.
"` WRITE");
282 $ItemIdList = $this->
GetIds();
283 foreach ($ItemIds as $Index => $ItemId)
286 $ItemType = $ItemTypes[$Index];
288 # if there are items currently in list
289 if (count($ItemIdList))
291 # remove item from current position if necessary
292 $ItemWasRemoved = $this->
Remove($ItemId, $ItemType);
294 # reload item ID list if necessary
297 $ItemIdList = $this->
GetIds();
301 # if there are still items currently in list
302 if (count($ItemIdList))
304 # find ID and type of last item in list
305 if ($this->ItemTypesInUse)
307 $Row = array_pop($ItemIdList);
308 $LastItemId = $Row[
"ID"];
309 $LastItemType = $Row[
"Type"];
310 array_push($ItemIdList, $Row);
314 $LastItemId = array_pop($ItemIdList);
315 $LastItemType = NULL;
316 array_push($ItemIdList, $LastItemId);
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);
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);
333 # add item to our local ID list
334 array_push($ItemIdList,
335 $this->ItemTypesInUse
336 ? array(
"ID" => $ItemId,
"Type" => $ItemType)
341 $this->DB->Query(
"UNLOCK TABLES");
353 # assume no items will be found in folder
356 # if item types are in use
357 if ($this->ItemTypesInUse)
359 # retrieve IDs and types of all items in list and links between items
360 $this->DB->Query(
"SELECT * FROM ".$this->ItemTableName
362 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
364 # build up lists of next and previous item pointers
365 $PreviousItemIds = array();
366 $NextItemIds = array();
367 while ($Record = $this->DB->FetchRow())
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];
379 # find ID of first item in list
380 $ListEndIndex = self::LISTEND_ID.
":".self::LISTEND_ID;
381 $Index = array_search($ListEndIndex, $PreviousItemIds);
383 # if first item was found
384 if ($Index !== FALSE)
386 # traverse linked list to build list of item types and IDs
389 $ItemIds[$Index] = array(
390 "Type" => $KnownItemTypes[$Index],
391 "ID" => $KnownItemIds[$Index]);
392 $Index = $NextItemIds[$Index];
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));
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
410 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
412 # build up lists of next item pointers
413 $PreviousItemIds = array();
414 $NextItemIds = array();
415 while ($Record = $this->DB->FetchRow())
417 $Index = $Record[$this->ItemIdFieldName];
418 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemIdFieldName];
419 $NextItemIds[$Index] = $Record[
"Next".$this->ItemIdFieldName];
422 # find ID of first item in list
423 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
425 # if first item was found
426 if ($ItemId !== FALSE)
428 # traverse linked list to build list of item IDs
431 $ItemIds[] = $ItemId;
432 $ItemId = $NextItemIds[$ItemId];
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));
443 # return list of item IDs to caller
453 # retrieve count of items
454 return $this->DB->Query(
"SELECT COUNT(DISTINCT `".$this->ItemIdFieldName
455 .
"`) AS ItemCount FROM ".$this->ItemTableName
467 function Remove($ItemId, $ItemType = NULL)
469 # retrieve item's "previous" pointer
470 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
472 # bail out if item was not found
473 if ($CurrentItemPreviousId === FALSE) {
return FALSE; }
475 # retrieve item's "next" pointer
476 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
477 if ($this->ItemTypesInUse)
479 $CurrentItemPreviousType = $CurrentItemPreviousId[
"Type"];
480 $CurrentItemPreviousId = $CurrentItemPreviousId[
"ID"];
481 $CurrentItemNextType = $CurrentItemNextId[
"Type"];
482 $CurrentItemNextId = $CurrentItemNextId[
"ID"];
486 $CurrentItemPreviousType = NULL;
487 $CurrentItemNextType = NULL;
490 # if item was not first in list
491 if ($CurrentItemPreviousId >= 0)
493 # link previous item to item's current next item
494 $this->SetNextItemId(
495 $CurrentItemPreviousId, $CurrentItemPreviousType,
496 $CurrentItemNextId, $CurrentItemNextType);
499 # if item was not last in list
500 if ($CurrentItemNextId >= 0)
502 # link next item to item's current previous item
503 $this->SetPreviousItemId(
504 $CurrentItemNextId, $CurrentItemNextType,
505 $CurrentItemPreviousId, $CurrentItemPreviousType);
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);
513 # report that item was removed
518 # ---- PRIVATE INTERFACE -------------------------------------------------
522 private $ItemTableName;
524 private $ItemIdFieldName;
526 private $ItemTypeFieldName;
528 private $ItemTypesInUse;
530 private $SqlCondition = NULL;
542 private function GetPreviousItemId($ItemId, $ItemType)
544 if ($this->ItemTypesInUse)
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)
552 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
553 $Row = $this->DB->FetchRow();
554 if ($Row[
"Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
556 $ReturnValue[
"Type"] = $Row[
"Previous".$this->ItemTypeFieldName];
557 $ReturnValue[
"ID"] = $Row[
"Previous".$this->ItemIdFieldName];
562 $ReturnVal = $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
563 .
" FROM ".$this->ItemTableName
564 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
566 "Previous".$this->ItemIdFieldName);
567 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
578 private function GetNextItemId($ItemId, $ItemType)
580 if ($this->ItemTypesInUse)
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)
588 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
589 $Row = $this->DB->FetchRow();
590 if ($Row[
"Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
592 $ReturnValue[
"Type"] = $Row[
"Next".$this->ItemTypeFieldName];
593 $ReturnValue[
"ID"] = $Row[
"Next".$this->ItemIdFieldName];
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;
614 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
616 if ($this->ItemTypesInUse)
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 :
""));
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 :
""));
641 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
643 if ($this->ItemTypesInUse)
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 :
""));
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 :
""));
670 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
671 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
673 if ($this->ItemTypesInUse)
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 :
""));
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 :
""));
SQL database abstraction object with smart query caching.
__construct($ItemTableName, $ItemIdFieldName, $SqlCondition=NULL, $ItemTypeFieldName=NULL)
Object constructor.
SqlCondition($Condition=NULL)
Get or set/update SQL condition for referencing items in database.
Prepend($ItemOrItemId, $ItemType=NULL)
Add item to beginning of list.
GetIds()
Retrieve array of IDs of items in list, in the order that they appear in the list.
Remove($ItemId, $ItemType=NULL)
Remove item from list.
InsertBefore($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list before specified item.
GetCount()
Get number of items in list.
InsertAfter($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list after specified item.
Persistent doubly-linked-list data structure, with its data stored in a specified database table...
Append($ItemsOrItemIds, $ItemTypes=NULL)
Add item(s) to end of list.