4 # FILE: PersistentDoublyLinkedList.php
6 # Part of the ScoutLib application support library
7 # Copyright 2012 Edward Almasy and Internet Scout
8 # http://scout.wisc.edu
24 # ---- 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->SqlCondition = $SqlCondition;
70 $TargetItemType = NULL, $NewItemType = NULL)
73 $NewItemId = is_object($NewItemOrItemId)
74 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
75 $TargetItemId = is_object($TargetItemOrItemId)
76 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
78 # remove source item from current position if necessary
81 # retrieve current previous item pointer for target item
82 $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
83 $TargetItemId, $TargetItemType);
85 # if target item not found
86 if ($TargetItemCurrentPreviousId === FALSE)
88 # add new item to beginning of list
89 $this->
Prepend($NewItemId, $NewItemType);
93 # retrieve target item type if available
94 if (is_array($TargetItemCurrentPreviousId))
96 $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId[
"Type"];
97 $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId[
"ID"];
101 $TargetItemCurrentPreviousType = NULL;
104 # update IDs to link in new item
105 $this->SetPreviousItemId(
106 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
107 if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
109 $this->SetNextItemId($TargetItemCurrentPreviousId,
110 $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
112 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
113 $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
114 $TargetItemId, $TargetItemType);
128 $TargetItemType = NULL, $NewItemType = NULL)
131 $NewItemId = is_object($NewItemOrItemId)
132 ? $NewItemOrItemId->Id() : $NewItemOrItemId;
133 $TargetItemId = is_object($TargetItemOrItemId)
134 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
136 # remove new item from existing position (if necessary)
137 $this->
Remove($NewItemId, $NewItemType);
139 # retrieve current next item pointer for target item
140 $TargetItemCurrentNextId = $this->GetNextItemId(
141 $TargetItemId, $TargetItemType);
143 # if target item not found
144 if ($TargetItemCurrentNextId === FALSE)
146 # add new item to end of list
147 $this->
Append($NewItemId, $NewItemType);
151 # retrieve target item type if available
152 if (is_array($TargetItemCurrentNextId))
154 $TargetItemCurrentNextType = $TargetItemCurrentNextId[
"Type"];
155 $TargetItemCurrentNextId = $TargetItemCurrentNextId[
"ID"];
159 $TargetItemCurrentNextType = NULL;
162 # update IDs to link in new item
163 $this->SetNextItemId(
164 $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
165 if ($TargetItemCurrentNextId != self::LISTEND_ID)
167 $this->SetPreviousItemId(
168 $TargetItemCurrentNextId, $TargetItemCurrentNextType,
169 $NewItemId, $NewItemType);
171 $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
172 $TargetItemId, $TargetItemType,
173 $TargetItemCurrentNextId, $TargetItemCurrentNextType);
183 function Prepend($ItemOrItemId, $ItemType = NULL)
186 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
188 # remove new item from current position if necessary
189 $this->
Remove($ItemId, $ItemType);
191 # if there are items currently in list
192 $ItemIds = $this->
GetIds(FALSE);
195 # link first item to source item
196 if ($this->ItemTypeFieldName)
198 $Row = array_shift($ItemIds);
199 $FirstItemId = $Row[
"ID"];
200 $FirstItemType = $Row[
"Type"];
204 $FirstItemId = array_shift($ItemIds);
205 $FirstItemType = NULL;
208 $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
209 $this->SetPreviousAndNextItemIds(
210 $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
211 $FirstItemId, $FirstItemType);
215 # add item to list as only item
216 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
217 self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID);
227 function Append($ItemOrItemId, $ItemType = NULL)
230 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
232 # remove item from current position if necessary
233 $this->
Remove($ItemId, $ItemType);
235 # if there are items currently in list
236 $ItemIds = $this->
GetIds();
239 # link last item to source item
240 if ($this->ItemTypeFieldName)
242 $Row = array_pop($ItemIds);
243 $LastItemId = $Row[
"ID"];
244 $LastItemType = $Row[
"Type"];
248 $LastItemId = array_pop($ItemIds);
249 $LastItemType = NULL;
251 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
252 $this->SetPreviousAndNextItemIds(
253 $ItemId, $ItemType, $LastItemId, $LastItemType,
254 self::LISTEND_ID, self::LISTEND_ID);
258 # add item to list as only item
259 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
260 self::LISTEND_ID, self::LISTEND_ID,
261 self::LISTEND_ID, self::LISTEND_ID);
274 # assume no items will be found in folder
277 # if item types are in use
278 if ($this->ItemTypeFieldName)
280 # retrieve IDs and types of all items in list and links between items
281 $this->DB->Query(
"SELECT * FROM ".$this->ItemTableName
282 .($this->SqlCondition ?
" WHERE ".$this->SqlCondition :
"")
283 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
285 # build up lists of next and previous item pointers
286 $PreviousItemIds = array();
287 $NextItemIds = array();
288 while ($Record = $this->DB->FetchRow())
290 $Index = $Record[$this->ItemTypeFieldName]
291 .
":".$Record[$this->ItemIdFieldName];
292 $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
293 $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
294 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemTypeFieldName]
295 .
":".$Record[
"Previous".$this->ItemIdFieldName];
296 $NextItemIds[$Index] = $Record[
"Next".$this->ItemTypeFieldName]
297 .
":".$Record[
"Next".$this->ItemIdFieldName];
300 # find ID of first item in list
301 $ListEndIndex = self::LISTEND_ID.
":".self::LISTEND_ID;
302 $Index = array_search($ListEndIndex, $PreviousItemIds);
304 # if first item was found
305 if ($Index !== FALSE)
307 # traverse linked list to build list of item types and IDs
310 $ItemIds[$Index] = array(
311 "Type" => $KnownItemTypes[$Index],
312 "ID" => $KnownItemIds[$Index]);
313 $Index = $NextItemIds[$Index];
315 # (stop if we've reached the end of the list)
316 while (($Index != $ListEndIndex)
317 # (stop
if link points to item not in list)
318 && array_key_exists($Index, $NextItemIds)
319 # (stop
if link is circular)
320 && !array_key_exists($Index, $ItemIds));
325 # retrieve IDs of all items in list and links between items
326 $this->DB->Query(
"SELECT ".$this->ItemIdFieldName
327 .
", Previous".$this->ItemIdFieldName
328 .
", Next".$this->ItemIdFieldName
329 .
" FROM ".$this->ItemTableName
330 .($this->SqlCondition ?
" WHERE ".$this->SqlCondition :
"")
331 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
333 # build up lists of next item pointers
334 $PreviousItemIds = array();
335 $NextItemIds = array();
336 while ($Record = $this->DB->FetchRow())
338 $Index = $Record[$this->ItemIdFieldName];
339 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemIdFieldName];
340 $NextItemIds[$Index] = $Record[
"Next".$this->ItemIdFieldName];
343 # find ID of first item in list
344 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
346 # if first item was found
347 if ($ItemId !== FALSE)
349 # traverse linked list to build list of item IDs
352 $ItemIds[] = $ItemId;
353 $ItemId = $NextItemIds[$ItemId];
355 # (stop if we've reached the end of the list)
356 while (($ItemId != self::LISTEND_ID)
357 # (stop
if link points to item not in list)
358 && array_key_exists($ItemId, $NextItemIds)
359 # (stop
if link is circular)
360 && !in_array($ItemId, $ItemIds));
364 # return list of item IDs to caller
374 function Remove($ItemId, $ItemType = NULL)
376 # retrieve item's "previous" pointer
377 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
379 # bail out if item was not found
380 if ($CurrentItemPreviousId === FALSE) {
return; }
382 # retrieve item's "next" pointer
383 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
384 if ($this->ItemTypeFieldName)
386 $CurrentItemPreviousType = $CurrentItemPreviousId[
"Type"];
387 $CurrentItemPreviousId = $CurrentItemPreviousId[
"ID"];
388 $CurrentItemNextType = $CurrentItemNextId[
"Type"];
389 $CurrentItemNextId = $CurrentItemNextId[
"ID"];
393 $CurrentItemPreviousType = NULL;
394 $CurrentItemNextType = NULL;
397 # if item was not first in list
398 if ($CurrentItemPreviousId >= 0)
400 # link previous item to item's current next item
401 $this->SetNextItemId(
402 $CurrentItemPreviousId, $CurrentItemPreviousType,
403 $CurrentItemNextId, $CurrentItemNextType);
406 # if item was not last in list
407 if ($CurrentItemNextId >= 0)
409 # link next item to item's current previous item
410 $this->SetPreviousItemId(
411 $CurrentItemNextId, $CurrentItemNextType,
412 $CurrentItemPreviousId, $CurrentItemPreviousType);
415 # set items pointers to indicate it is not part of a list
416 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
417 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
418 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
422 # ---- PRIVATE INTERFACE -------------------------------------------------
425 private $ItemTableName;
426 private $ItemIdFieldName;
427 private $ItemTypeFieldName;
428 private $SqlCondition;
433 # get ordering values (return FALSE if specified item not found)
434 private function GetPreviousItemId($ItemId, $ItemType)
436 if ($this->ItemTypeFieldName)
438 $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
439 .
", Previous".$this->ItemTypeFieldName
440 .
" FROM ".$this->ItemTableName
441 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
442 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
443 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
444 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
445 $Row = $this->DB->FetchRow();
446 if ($Row[
"Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
448 $ReturnValue[
"Type"] = $Row[
"Previous".$this->ItemTypeFieldName];
449 $ReturnValue[
"ID"] = $Row[
"Previous".$this->ItemIdFieldName];
454 $ReturnVal = $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
455 .
" FROM ".$this->ItemTableName
456 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
457 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""),
458 "Previous".$this->ItemIdFieldName);
459 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
462 private function GetNextItemId($ItemId, $ItemType)
464 if ($this->ItemTypeFieldName)
466 $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
467 .
", Next".$this->ItemTypeFieldName
468 .
" FROM ".$this->ItemTableName
469 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
470 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
471 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
472 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
473 $Row = $this->DB->FetchRow();
474 if ($Row[
"Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
476 $ReturnValue[
"Type"] = $Row[
"Next".$this->ItemTypeFieldName];
477 $ReturnValue[
"ID"] = $Row[
"Next".$this->ItemIdFieldName];
482 $ReturnVal = $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
483 .
" FROM ".$this->ItemTableName
484 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
485 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""),
486 "Next".$this->ItemIdFieldName);
487 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
491 # set ordering values
492 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
494 if ($this->ItemTypeFieldName)
496 $this->DB->Query(
"UPDATE ".$this->ItemTableName
497 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
498 .
", Previous".$this->ItemTypeFieldName.
" = ".intval($NewType)
499 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
500 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
501 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
505 $this->DB->Query(
"UPDATE ".$this->ItemTableName
506 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
507 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
508 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
511 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
513 if ($this->ItemTypeFieldName)
515 $this->DB->Query(
"UPDATE ".$this->ItemTableName
516 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
517 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewType)
518 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
519 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
520 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
524 $this->DB->Query(
"UPDATE ".$this->ItemTableName
525 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
526 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
527 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
530 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
531 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
533 if ($this->ItemTypeFieldName)
535 $this->DB->Query(
"UPDATE ".$this->ItemTableName
536 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
537 .
", Previous".$this->ItemTypeFieldName.
" = "
538 .intval($NewPreviousType)
539 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
540 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewNextType)
541 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
542 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
543 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
547 $this->DB->Query(
"UPDATE ".$this->ItemTableName
548 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
549 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
550 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
551 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));