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;
74 return $this->SqlCondition;
87 $TargetItemType = NULL, $NewItemType = NULL)
90 $NewItemId = is_object($NewItemOrItemId)
91 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
92 $TargetItemId = is_object($TargetItemOrItemId)
93 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
95 # remove source item from current position if necessary
98 # retrieve current previous item pointer for target item
99 $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
100 $TargetItemId, $TargetItemType);
102 # if target item not found
103 if ($TargetItemCurrentPreviousId === FALSE)
105 # add new item to beginning of list
106 $this->
Prepend($NewItemId, $NewItemType);
110 # retrieve target item type if available
111 if (is_array($TargetItemCurrentPreviousId))
113 $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId[
"Type"];
114 $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId[
"ID"];
118 $TargetItemCurrentPreviousType = NULL;
121 # update IDs to link in new item
122 $this->SetPreviousItemId(
123 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
124 if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
126 $this->SetNextItemId($TargetItemCurrentPreviousId,
127 $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
129 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
130 $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
131 $TargetItemId, $TargetItemType);
145 $TargetItemType = NULL, $NewItemType = NULL)
148 $NewItemId = is_object($NewItemOrItemId)
149 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
150 $TargetItemId = is_object($TargetItemOrItemId)
151 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
153 # remove new item from existing position (if necessary)
154 $this->
Remove($NewItemId, $NewItemType);
156 # retrieve current next item pointer for target item
157 $TargetItemCurrentNextId = $this->GetNextItemId(
158 $TargetItemId, $TargetItemType);
160 # if target item not found
161 if ($TargetItemCurrentNextId === FALSE)
163 # add new item to end of list
164 $this->
Append($NewItemId, $NewItemType);
168 # retrieve target item type if available
169 if (is_array($TargetItemCurrentNextId))
171 $TargetItemCurrentNextType = $TargetItemCurrentNextId[
"Type"];
172 $TargetItemCurrentNextId = $TargetItemCurrentNextId[
"ID"];
176 $TargetItemCurrentNextType = NULL;
179 # update IDs to link in new item
180 $this->SetNextItemId(
181 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
182 if ($TargetItemCurrentNextId != self::LISTEND_ID)
184 $this->SetPreviousItemId(
185 $TargetItemCurrentNextId, $TargetItemCurrentNextType,
186 $NewItemId, $NewItemType);
188 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
189 $TargetItemId, $TargetItemType,
190 $TargetItemCurrentNextId, $TargetItemCurrentNextType);
200 function Prepend($ItemOrItemId, $ItemType = NULL)
203 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
205 # remove new item from current position if necessary
206 $this->
Remove($ItemId, $ItemType);
208 # if there are items currently in list
209 $ItemIds = $this->
GetIds(FALSE);
212 # link first item to source item
213 if ($this->ItemTypeFieldName)
215 $Row = array_shift($ItemIds);
216 $FirstItemId = $Row[
"ID"];
217 $FirstItemType = $Row[
"Type"];
221 $FirstItemId = array_shift($ItemIds);
222 $FirstItemType = NULL;
225 $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
226 $this->SetPreviousAndNextItemIds(
227 $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
228 $FirstItemId, $FirstItemType);
232 # add item to list as only item
233 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
234 self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID);
244 function Append($ItemOrItemId, $ItemType = NULL)
247 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
249 # remove item from current position if necessary
250 $this->
Remove($ItemId, $ItemType);
252 # if there are items currently in list
253 $ItemIds = $this->
GetIds();
256 # link last item to source item
257 if ($this->ItemTypeFieldName)
259 $Row = array_pop($ItemIds);
260 $LastItemId = $Row[
"ID"];
261 $LastItemType = $Row[
"Type"];
265 $LastItemId = array_pop($ItemIds);
266 $LastItemType = NULL;
268 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
269 $this->SetPreviousAndNextItemIds(
270 $ItemId, $ItemType, $LastItemId, $LastItemType,
271 self::LISTEND_ID, self::LISTEND_ID);
275 # add item to list as only item
276 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
277 self::LISTEND_ID, self::LISTEND_ID,
278 self::LISTEND_ID, self::LISTEND_ID);
291 # assume no items will be found in folder
294 # if item types are in use
295 if ($this->ItemTypeFieldName)
297 # retrieve IDs and types of all items in list and links between items
298 $this->DB->Query(
"SELECT * FROM ".$this->ItemTableName
300 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
302 # build up lists of next and previous item pointers
303 $PreviousItemIds = array();
304 $NextItemIds = array();
305 while ($Record = $this->DB->FetchRow())
307 $Index = $Record[$this->ItemTypeFieldName]
308 .
":".$Record[$this->ItemIdFieldName];
309 $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
310 $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
311 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemTypeFieldName]
312 .
":".$Record[
"Previous".$this->ItemIdFieldName];
313 $NextItemIds[$Index] = $Record[
"Next".$this->ItemTypeFieldName]
314 .
":".$Record[
"Next".$this->ItemIdFieldName];
317 # find ID of first item in list
318 $ListEndIndex = self::LISTEND_ID.
":".self::LISTEND_ID;
319 $Index = array_search($ListEndIndex, $PreviousItemIds);
321 # if first item was found
322 if ($Index !== FALSE)
324 # traverse linked list to build list of item types and IDs
327 $ItemIds[$Index] = array(
328 "Type" => $KnownItemTypes[$Index],
329 "ID" => $KnownItemIds[$Index]);
330 $Index = $NextItemIds[$Index];
332 # (stop if we've reached the end of the list)
333 while (($Index != $ListEndIndex)
334 # (stop
if link points to item not in list)
335 && array_key_exists($Index, $NextItemIds)
336 # (stop
if link is circular)
337 && !array_key_exists($Index, $ItemIds));
342 # retrieve IDs of all items in list and links between items
343 $this->DB->Query(
"SELECT ".$this->ItemIdFieldName
344 .
", Previous".$this->ItemIdFieldName
345 .
", Next".$this->ItemIdFieldName
346 .
" FROM ".$this->ItemTableName
348 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
350 # build up lists of next item pointers
351 $PreviousItemIds = array();
352 $NextItemIds = array();
353 while ($Record = $this->DB->FetchRow())
355 $Index = $Record[$this->ItemIdFieldName];
356 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemIdFieldName];
357 $NextItemIds[$Index] = $Record[
"Next".$this->ItemIdFieldName];
360 # find ID of first item in list
361 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
363 # if first item was found
364 if ($ItemId !== FALSE)
366 # traverse linked list to build list of item IDs
369 $ItemIds[] = $ItemId;
370 $ItemId = $NextItemIds[$ItemId];
372 # (stop if we've reached the end of the list)
373 while (($ItemId != self::LISTEND_ID)
374 # (stop
if link points to item not in list)
375 && array_key_exists($ItemId, $NextItemIds)
376 # (stop
if link is circular)
377 && !in_array($ItemId, $ItemIds));
381 # return list of item IDs to caller
391 # retrieve count of items
392 return $this->DB->Query(
"SELECT COUNT(DISTINCT `".$this->ItemIdFieldName
393 .
"`) AS ItemCount FROM ".$this->ItemTableName
404 function Remove($ItemId, $ItemType = NULL)
406 # retrieve item's "previous" pointer
407 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
409 # bail out if item was not found
410 if ($CurrentItemPreviousId === FALSE) {
return; }
412 # retrieve item's "next" pointer
413 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
414 if ($this->ItemTypeFieldName)
416 $CurrentItemPreviousType = $CurrentItemPreviousId[
"Type"];
417 $CurrentItemPreviousId = $CurrentItemPreviousId[
"ID"];
418 $CurrentItemNextType = $CurrentItemNextId[
"Type"];
419 $CurrentItemNextId = $CurrentItemNextId[
"ID"];
423 $CurrentItemPreviousType = NULL;
424 $CurrentItemNextType = NULL;
427 # if item was not first in list
428 if ($CurrentItemPreviousId >= 0)
430 # link previous item to item's current next item
431 $this->SetNextItemId(
432 $CurrentItemPreviousId, $CurrentItemPreviousType,
433 $CurrentItemNextId, $CurrentItemNextType);
436 # if item was not last in list
437 if ($CurrentItemNextId >= 0)
439 # link next item to item's current previous item
440 $this->SetPreviousItemId(
441 $CurrentItemNextId, $CurrentItemNextType,
442 $CurrentItemPreviousId, $CurrentItemPreviousType);
445 # set items pointers to indicate it is not part of a list
446 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
447 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
448 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
452 # ---- PRIVATE INTERFACE -------------------------------------------------
456 private $ItemTableName;
458 private $ItemIdFieldName;
460 private $ItemTypeFieldName;
462 private $SqlCondition = NULL;
474 private function GetPreviousItemId($ItemId, $ItemType)
476 if ($this->ItemTypeFieldName)
478 $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
479 .
", Previous".$this->ItemTypeFieldName
480 .
" FROM ".$this->ItemTableName
481 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
482 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
484 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
485 $Row = $this->DB->FetchRow();
486 if ($Row[
"Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
488 $ReturnValue[
"Type"] = $Row[
"Previous".$this->ItemTypeFieldName];
489 $ReturnValue[
"ID"] = $Row[
"Previous".$this->ItemIdFieldName];
494 $ReturnVal = $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
495 .
" FROM ".$this->ItemTableName
496 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
498 "Previous".$this->ItemIdFieldName);
499 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
510 private function GetNextItemId($ItemId, $ItemType)
512 if ($this->ItemTypeFieldName)
514 $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
515 .
", Next".$this->ItemTypeFieldName
516 .
" FROM ".$this->ItemTableName
517 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
518 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
520 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
521 $Row = $this->DB->FetchRow();
522 if ($Row[
"Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
524 $ReturnValue[
"Type"] = $Row[
"Next".$this->ItemTypeFieldName];
525 $ReturnValue[
"ID"] = $Row[
"Next".$this->ItemIdFieldName];
530 $ReturnVal = $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
531 .
" FROM ".$this->ItemTableName
532 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
533 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""),
534 "Next".$this->ItemIdFieldName);
535 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
546 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
548 if ($this->ItemTypeFieldName)
550 $this->DB->Query(
"UPDATE ".$this->ItemTableName
551 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
552 .
", Previous".$this->ItemTypeFieldName.
" = ".intval($NewType)
553 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
554 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
555 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
559 $this->DB->Query(
"UPDATE ".$this->ItemTableName
560 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
561 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
562 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
573 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
575 if ($this->ItemTypeFieldName)
577 $this->DB->Query(
"UPDATE ".$this->ItemTableName
578 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
579 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewType)
580 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
581 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
582 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
586 $this->DB->Query(
"UPDATE ".$this->ItemTableName
587 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
588 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
589 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
602 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
603 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
605 if ($this->ItemTypeFieldName)
607 $this->DB->Query(
"UPDATE ".$this->ItemTableName
608 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
609 .
", Previous".$this->ItemTypeFieldName.
" = "
610 .intval($NewPreviousType)
611 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
612 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewNextType)
613 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
614 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
615 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
619 $this->DB->Query(
"UPDATE ".$this->ItemTableName
620 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
621 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
622 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
623 .($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($ItemOrItemId, $ItemType=NULL)
Add item to end of list.