3 # FILE: PersistentDoublyLinkedList.php 5 # Part of the ScoutLib application support library 6 # Copyright 2012-2015 Edward Almasy and Internet Scout Research Group 7 # http://scout.wisc.edu 24 # ---- PUBLIC INTERFACE -------------------------------------------------- 49 $SqlCondition = NULL, $ItemTypeFieldName = NULL)
51 # grab our own database handle 55 $this->ItemTableName = $ItemTableName;
56 $this->ItemIdFieldName = $ItemIdFieldName;
57 $this->ItemTypeFieldName = $ItemTypeFieldName;
58 $this->ItemTypesInUse = ($ItemTypeFieldName === NULL) ? FALSE : TRUE;
76 return $this->SqlCondition;
88 public function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
89 $TargetItemType = NULL, $NewItemType = NULL)
91 # verify item types supplied or omitted as appropriate 92 $this->CheckItemTypeParameter($TargetItemType);
93 $this->CheckItemTypeParameter($NewItemType);
96 $NewItemId = is_object($NewItemOrItemId)
97 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
98 $TargetItemId = is_object($TargetItemOrItemId)
99 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
101 # remove source item from current position if necessary 102 $this->
Remove($NewItemId, $NewItemType);
104 # retrieve current previous item pointer for target item 105 $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
106 $TargetItemId, $TargetItemType);
108 # if target item not found 109 if ($TargetItemCurrentPreviousId === FALSE)
111 # add new item to beginning of list 112 $this->
Prepend($NewItemId, $NewItemType);
116 # retrieve target item type if available 117 if (is_array($TargetItemCurrentPreviousId))
119 $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId[
"Type"];
120 $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId[
"ID"];
124 $TargetItemCurrentPreviousType = NULL;
127 # update IDs to link in new item 128 $this->SetPreviousItemId(
129 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
130 if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
132 $this->SetNextItemId($TargetItemCurrentPreviousId,
133 $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
135 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
136 $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
137 $TargetItemId, $TargetItemType);
150 public function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
151 $TargetItemType = NULL, $NewItemType = NULL)
153 # verify item types supplied or omitted as appropriate 154 $this->CheckItemTypeParameter($TargetItemType);
155 $this->CheckItemTypeParameter($NewItemType);
158 $NewItemId = is_object($NewItemOrItemId)
159 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
160 $TargetItemId = is_object($TargetItemOrItemId)
161 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
163 # remove new item from existing position (if necessary) 164 $this->
Remove($NewItemId, $NewItemType);
166 # retrieve current next item pointer for target item 167 $TargetItemCurrentNextId = $this->GetNextItemId(
168 $TargetItemId, $TargetItemType);
170 # if target item not found 171 if ($TargetItemCurrentNextId === FALSE)
173 # add new item to end of list 174 $this->
Append($NewItemId, $NewItemType);
178 # retrieve target item type if available 179 if (is_array($TargetItemCurrentNextId))
181 $TargetItemCurrentNextType = $TargetItemCurrentNextId[
"Type"];
182 $TargetItemCurrentNextId = $TargetItemCurrentNextId[
"ID"];
186 $TargetItemCurrentNextType = NULL;
189 # update IDs to link in new item 190 $this->SetNextItemId(
191 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
192 if ($TargetItemCurrentNextId != self::LISTEND_ID)
194 $this->SetPreviousItemId(
195 $TargetItemCurrentNextId, $TargetItemCurrentNextType,
196 $NewItemId, $NewItemType);
198 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
199 $TargetItemId, $TargetItemType,
200 $TargetItemCurrentNextId, $TargetItemCurrentNextType);
210 public function Prepend($ItemOrItemId, $ItemType = NULL)
212 # verify item types supplied or omitted as appropriate 213 $this->CheckItemTypeParameter($ItemType);
216 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
218 # remove new item from current position if necessary 219 $this->
Remove($ItemId, $ItemType);
221 # if there are items currently in list 222 $ItemIds = $this->
GetIds(FALSE);
225 # link first item to source item 226 if ($this->ItemTypesInUse)
228 $Row = array_shift($ItemIds);
229 $FirstItemId = $Row[
"ID"];
230 $FirstItemType = $Row[
"Type"];
234 $FirstItemId = array_shift($ItemIds);
235 $FirstItemType = NULL;
238 $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
239 $this->SetPreviousAndNextItemIds(
240 $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
241 $FirstItemId, $FirstItemType);
245 # add item to list as only item 246 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
247 self::LISTEND_ID, self::LISTEND_ID,
248 self::LISTEND_ID, self::LISTEND_ID);
261 public function Append($ItemsOrItemIds, $ItemTypes = NULL)
263 # verify item types supplied or omitted as appropriate 264 $this->CheckItemTypeParameter($ItemTypes);
266 # make incoming values into arrays if they aren't already 267 if (!is_array($ItemsOrItemIds))
269 $ItemsOrItemIds = array($ItemsOrItemIds);
271 if (!is_array($ItemTypes))
273 $NewItemTypes = array();
274 foreach ($ItemsOrItemIds as $Id)
276 $NewItemTypes[] = $ItemTypes;
278 $ItemTypes = $NewItemTypes;
283 foreach ($ItemsOrItemIds as $ItemOrId)
285 $ItemIds[] = is_object($ItemOrId) ? $ItemOrId->Id() : $ItemOrId;
288 # lock database to prevent anyone from mucking up our changes 289 $this->DB->Query(
"LOCK TABLES `".$this->ItemTableName.
"` WRITE");
292 $ItemIdList = $this->
GetIds();
293 foreach ($ItemIds as $Index => $ItemId)
296 $ItemType = $ItemTypes[$Index];
298 # if there are items currently in list 299 if (count($ItemIdList))
301 # remove item from current position if necessary 302 $ItemWasRemoved = $this->
Remove($ItemId, $ItemType);
304 # reload item ID list if necessary 307 $ItemIdList = $this->
GetIds();
311 # if there are still items currently in list 312 if (count($ItemIdList))
314 # find ID and type of last item in list 315 if ($this->ItemTypesInUse)
317 $Row = array_pop($ItemIdList);
318 $LastItemId = $Row[
"ID"];
319 $LastItemType = $Row[
"Type"];
320 array_push($ItemIdList, $Row);
324 $LastItemId = array_pop($ItemIdList);
325 $LastItemType = NULL;
326 array_push($ItemIdList, $LastItemId);
329 # link last item to source item 330 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
331 $this->SetPreviousAndNextItemIds(
332 $ItemId, $ItemType, $LastItemId, $LastItemType,
333 self::LISTEND_ID, self::LISTEND_ID);
337 # add item to list as only item 338 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
339 self::LISTEND_ID, self::LISTEND_ID,
340 self::LISTEND_ID, self::LISTEND_ID);
343 # add item to our local ID list 344 array_push($ItemIdList,
345 $this->ItemTypesInUse
346 ? array(
"ID" => $ItemId,
"Type" => $ItemType)
351 $this->DB->Query(
"UNLOCK TABLES");
363 # assume no items will be found in folder 366 # if item types are in use 367 if ($this->ItemTypesInUse)
369 # retrieve IDs and types of all items in list and links between items 370 $this->DB->Query(
"SELECT * FROM ".$this->ItemTableName
372 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
374 # build up lists of next and previous item pointers 375 $PreviousItemIds = array();
376 $NextItemIds = array();
377 while ($Record = $this->DB->FetchRow())
379 $Index = $Record[$this->ItemTypeFieldName]
380 .
":".$Record[$this->ItemIdFieldName];
381 $KnownItemTypes[$Index] = intval($Record[$this->ItemTypeFieldName]);
382 $KnownItemIds[$Index] = intval($Record[$this->ItemIdFieldName]);
383 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemTypeFieldName]
384 .
":".$Record[
"Previous".$this->ItemIdFieldName];
385 $NextItemIds[$Index] = $Record[
"Next".$this->ItemTypeFieldName]
386 .
":".$Record[
"Next".$this->ItemIdFieldName];
389 # find ID of first item in list 390 $ListEndIndex = self::LISTEND_ID.
":".self::LISTEND_ID;
391 $Index = array_search($ListEndIndex, $PreviousItemIds);
393 # if first item was found 394 if ($Index !== FALSE)
396 # traverse linked list to build list of item types and IDs 399 $ItemIds[$Index] = array(
400 "Type" => $KnownItemTypes[$Index],
401 "ID" => $KnownItemIds[$Index]);
402 $Index = $NextItemIds[$Index];
403 # (stop if we've reached the end of the list) 404 }
while (($Index != $ListEndIndex)
405 # (stop
if link points to item not in list)
406 && array_key_exists($Index, $NextItemIds)
407 # (stop
if link is circular)
408 && !array_key_exists($Index, $ItemIds));
413 # retrieve IDs of all items in list and links between items 414 $this->DB->Query(
"SELECT ".$this->ItemIdFieldName
415 .
", Previous".$this->ItemIdFieldName
416 .
", Next".$this->ItemIdFieldName
417 .
" FROM ".$this->ItemTableName
419 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
421 # build up lists of next item pointers 422 $PreviousItemIds = array();
423 $NextItemIds = array();
424 while ($Record = $this->DB->FetchRow())
426 $Index = intval($Record[$this->ItemIdFieldName]);
427 $PreviousItemIds[$Index] =
428 intval($Record[
"Previous".$this->ItemIdFieldName]);
429 $NextItemIds[$Index] =
430 intval($Record[
"Next".$this->ItemIdFieldName]);
433 # find ID of first item in list 434 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
436 # if first item was found 437 if ($ItemId !== FALSE)
439 # traverse linked list to build list of item IDs 442 $ItemIds[] = $ItemId;
443 $ItemId = $NextItemIds[$ItemId];
444 # (stop if we've reached the end of the list) 445 }
while (($ItemId != self::LISTEND_ID)
446 # (stop
if link points to item not in list)
447 && array_key_exists($ItemId, $NextItemIds)
448 # (stop
if link is circular)
449 && !in_array($ItemId, $ItemIds));
453 # return list of item IDs to caller 463 # retrieve count of items 464 return count($this->
GetIds());
474 public function Remove($ItemId, $ItemType = NULL)
476 # verify item types supplied or omitted as appropriate 477 $this->CheckItemTypeParameter($ItemType);
479 # retrieve item's "previous" pointer 480 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
482 # bail out if item was not found 483 if ($CurrentItemPreviousId === FALSE) {
return FALSE; }
485 # retrieve item's "next" pointer 486 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
487 if ($this->ItemTypesInUse)
489 $CurrentItemPreviousType = $CurrentItemPreviousId[
"Type"];
490 $CurrentItemPreviousId = $CurrentItemPreviousId[
"ID"];
491 $CurrentItemNextType = $CurrentItemNextId[
"Type"];
492 $CurrentItemNextId = $CurrentItemNextId[
"ID"];
496 $CurrentItemPreviousType = NULL;
497 $CurrentItemNextType = NULL;
500 # if item was not first in list 501 if ($CurrentItemPreviousId >= 0)
503 # link previous item to item's current next item 504 $this->SetNextItemId(
505 $CurrentItemPreviousId, $CurrentItemPreviousType,
506 $CurrentItemNextId, $CurrentItemNextType);
509 # if item was not last in list 510 if ($CurrentItemNextId >= 0)
512 # link next item to item's current previous item 513 $this->SetPreviousItemId(
514 $CurrentItemNextId, $CurrentItemNextType,
515 $CurrentItemPreviousId, $CurrentItemPreviousType);
518 # set items pointers to indicate it is not part of a list 519 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
520 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
521 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
523 # report that item was removed 528 # ---- PRIVATE INTERFACE ------------------------------------------------- 532 private $ItemTableName;
534 private $ItemIdFieldName;
536 private $ItemTypeFieldName;
538 private $ItemTypesInUse;
540 private $SqlCondition = NULL;
552 private function GetPreviousItemId($ItemId, $ItemType)
554 if ($this->ItemTypesInUse)
556 $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
557 .
", Previous".$this->ItemTypeFieldName
558 .
" FROM ".$this->ItemTableName
559 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
560 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
562 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
563 $Row = $this->DB->FetchRow();
564 if ($Row[
"Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
566 $ReturnValue[
"Type"] = $Row[
"Previous".$this->ItemTypeFieldName];
567 $ReturnValue[
"ID"] = $Row[
"Previous".$this->ItemIdFieldName];
572 $ReturnVal = $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
573 .
" FROM ".$this->ItemTableName
574 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
576 "Previous".$this->ItemIdFieldName);
577 return (($ReturnVal === NULL)
578 || ($ReturnVal == self::UNINITIALIZED_ID))
579 ? FALSE : $ReturnVal;
590 private function GetNextItemId($ItemId, $ItemType)
592 if ($this->ItemTypesInUse)
594 $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
595 .
", Next".$this->ItemTypeFieldName
596 .
" FROM ".$this->ItemTableName
597 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
598 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
600 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
601 $Row = $this->DB->FetchRow();
602 if ($Row[
"Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
604 $ReturnValue[
"Type"] = $Row[
"Next".$this->ItemTypeFieldName];
605 $ReturnValue[
"ID"] = $Row[
"Next".$this->ItemIdFieldName];
610 $ReturnVal = $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
611 .
" FROM ".$this->ItemTableName
612 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
614 "Next".$this->ItemIdFieldName);
615 return (($ReturnVal === NULL)
616 || ($ReturnVal == self::UNINITIALIZED_ID))
617 ? FALSE : $ReturnVal;
628 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
630 if ($this->ItemTypesInUse)
632 $this->DB->Query(
"UPDATE ".$this->ItemTableName
633 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
634 .
", Previous".$this->ItemTypeFieldName.
" = ".intval($NewType)
635 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
636 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
641 $this->DB->Query(
"UPDATE ".$this->ItemTableName
642 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
643 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
655 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
657 if ($this->ItemTypesInUse)
659 $this->DB->Query(
"UPDATE ".$this->ItemTableName
660 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
661 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewType)
662 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
663 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
668 $this->DB->Query(
"UPDATE ".$this->ItemTableName
669 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
670 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
684 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
685 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
687 if ($this->ItemTypesInUse)
689 $this->DB->Query(
"UPDATE ".$this->ItemTableName
690 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
691 .
", Previous".$this->ItemTypeFieldName.
" = " 692 .intval($NewPreviousType)
693 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
694 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewNextType)
695 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
696 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
697 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
701 $this->DB->Query(
"UPDATE ".$this->ItemTableName
702 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
703 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
704 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
713 private function CheckItemTypeParameter($ItemType)
715 if ($this->ItemTypesInUse)
717 if ($ItemType === NULL)
719 throw new Exception(
"Item type(s) not supplied.");
724 if ($ItemType !== NULL)
726 throw new Exception(
"Item type(s) supplied when not in use.");
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.