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 --------------------------------------------------
49 $SqlCondition = NULL, $ItemTypeFieldName = NULL)
51 # grab our own database handle
55 $this->ItemTableName = $ItemTableName;
56 $this->ItemIdFieldName = $ItemIdFieldName;
57 $this->ItemTypeFieldName = $ItemTypeFieldName;
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->ItemTypeFieldName)
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);
245 function Append($ItemOrItemId, $ItemType = NULL)
248 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
250 # remove item from current position if necessary
251 $this->
Remove($ItemId, $ItemType);
253 # if there are items currently in list
254 $ItemIds = $this->
GetIds();
257 # link last item to source item
258 if ($this->ItemTypeFieldName)
260 $Row = array_pop($ItemIds);
261 $LastItemId = $Row[
"ID"];
262 $LastItemType = $Row[
"Type"];
266 $LastItemId = array_pop($ItemIds);
267 $LastItemType = NULL;
269 $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
270 $this->SetPreviousAndNextItemIds(
271 $ItemId, $ItemType, $LastItemId, $LastItemType,
272 self::LISTEND_ID, self::LISTEND_ID);
276 # add item to list as only item
277 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
278 self::LISTEND_ID, self::LISTEND_ID,
279 self::LISTEND_ID, self::LISTEND_ID);
292 # assume no items will be found in folder
295 # if item types are in use
296 if ($this->ItemTypeFieldName)
298 # retrieve IDs and types of all items in list and links between items
299 $this->DB->Query(
"SELECT * FROM ".$this->ItemTableName
301 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
303 # build up lists of next and previous item pointers
304 $PreviousItemIds = array();
305 $NextItemIds = array();
306 while ($Record = $this->DB->FetchRow())
308 $Index = $Record[$this->ItemTypeFieldName]
309 .
":".$Record[$this->ItemIdFieldName];
310 $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
311 $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
312 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemTypeFieldName]
313 .
":".$Record[
"Previous".$this->ItemIdFieldName];
314 $NextItemIds[$Index] = $Record[
"Next".$this->ItemTypeFieldName]
315 .
":".$Record[
"Next".$this->ItemIdFieldName];
318 # find ID of first item in list
319 $ListEndIndex = self::LISTEND_ID.
":".self::LISTEND_ID;
320 $Index = array_search($ListEndIndex, $PreviousItemIds);
322 # if first item was found
323 if ($Index !== FALSE)
325 # traverse linked list to build list of item types and IDs
328 $ItemIds[$Index] = array(
329 "Type" => $KnownItemTypes[$Index],
330 "ID" => $KnownItemIds[$Index]);
331 $Index = $NextItemIds[$Index];
333 # (stop if we've reached the end of the list)
334 while (($Index != $ListEndIndex)
335 # (stop
if link points to item not in list)
336 && array_key_exists($Index, $NextItemIds)
337 # (stop
if link is circular)
338 && !array_key_exists($Index, $ItemIds));
343 # retrieve IDs of all items in list and links between items
344 $this->DB->Query(
"SELECT ".$this->ItemIdFieldName
345 .
", Previous".$this->ItemIdFieldName
346 .
", Next".$this->ItemIdFieldName
347 .
" FROM ".$this->ItemTableName
349 .
" ORDER BY ".$this->ItemIdFieldName.
" ASC");
351 # build up lists of next item pointers
352 $PreviousItemIds = array();
353 $NextItemIds = array();
354 while ($Record = $this->DB->FetchRow())
356 $Index = $Record[$this->ItemIdFieldName];
357 $PreviousItemIds[$Index] = $Record[
"Previous".$this->ItemIdFieldName];
358 $NextItemIds[$Index] = $Record[
"Next".$this->ItemIdFieldName];
361 # find ID of first item in list
362 $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
364 # if first item was found
365 if ($ItemId !== FALSE)
367 # traverse linked list to build list of item IDs
370 $ItemIds[] = $ItemId;
371 $ItemId = $NextItemIds[$ItemId];
373 # (stop if we've reached the end of the list)
374 while (($ItemId != self::LISTEND_ID)
375 # (stop
if link points to item not in list)
376 && array_key_exists($ItemId, $NextItemIds)
377 # (stop
if link is circular)
378 && !in_array($ItemId, $ItemIds));
382 # return list of item IDs to caller
392 function Remove($ItemId, $ItemType = NULL)
394 # retrieve item's "previous" pointer
395 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
397 # bail out if item was not found
398 if ($CurrentItemPreviousId === FALSE) {
return; }
400 # retrieve item's "next" pointer
401 $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
402 if ($this->ItemTypeFieldName)
404 $CurrentItemPreviousType = $CurrentItemPreviousId[
"Type"];
405 $CurrentItemPreviousId = $CurrentItemPreviousId[
"ID"];
406 $CurrentItemNextType = $CurrentItemNextId[
"Type"];
407 $CurrentItemNextId = $CurrentItemNextId[
"ID"];
411 $CurrentItemPreviousType = NULL;
412 $CurrentItemNextType = NULL;
415 # if item was not first in list
416 if ($CurrentItemPreviousId >= 0)
418 # link previous item to item's current next item
419 $this->SetNextItemId(
420 $CurrentItemPreviousId, $CurrentItemPreviousType,
421 $CurrentItemNextId, $CurrentItemNextType);
424 # if item was not last in list
425 if ($CurrentItemNextId >= 0)
427 # link next item to item's current previous item
428 $this->SetPreviousItemId(
429 $CurrentItemNextId, $CurrentItemNextType,
430 $CurrentItemPreviousId, $CurrentItemPreviousType);
433 # set items pointers to indicate it is not part of a list
434 $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
435 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
436 self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
440 # ---- PRIVATE INTERFACE -------------------------------------------------
443 private $ItemTableName;
444 private $ItemIdFieldName;
445 private $ItemTypeFieldName;
446 private $SqlCondition = NULL;
451 # get ordering values (return FALSE if specified item not found)
452 private function GetPreviousItemId($ItemId, $ItemType)
454 if ($this->ItemTypeFieldName)
456 $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
457 .
", Previous".$this->ItemTypeFieldName
458 .
" FROM ".$this->ItemTableName
459 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
460 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
462 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
463 $Row = $this->DB->FetchRow();
464 if ($Row[
"Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
466 $ReturnValue[
"Type"] = $Row[
"Previous".$this->ItemTypeFieldName];
467 $ReturnValue[
"ID"] = $Row[
"Previous".$this->ItemIdFieldName];
472 $ReturnVal = $this->DB->Query(
"SELECT Previous".$this->ItemIdFieldName
473 .
" FROM ".$this->ItemTableName
474 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
476 "Previous".$this->ItemIdFieldName);
477 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
480 private function GetNextItemId($ItemId, $ItemType)
482 if ($this->ItemTypeFieldName)
484 $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
485 .
", Next".$this->ItemTypeFieldName
486 .
" FROM ".$this->ItemTableName
487 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
488 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
490 if (!$this->DB->NumRowsSelected()) {
return FALSE; }
491 $Row = $this->DB->FetchRow();
492 if ($Row[
"Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
494 $ReturnValue[
"Type"] = $Row[
"Next".$this->ItemTypeFieldName];
495 $ReturnValue[
"ID"] = $Row[
"Next".$this->ItemIdFieldName];
500 $ReturnVal = $this->DB->Query(
"SELECT Next".$this->ItemIdFieldName
501 .
" FROM ".$this->ItemTableName
502 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
503 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""),
504 "Next".$this->ItemIdFieldName);
505 return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
509 # set ordering values
510 private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
512 if ($this->ItemTypeFieldName)
514 $this->DB->Query(
"UPDATE ".$this->ItemTableName
515 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
516 .
", Previous".$this->ItemTypeFieldName.
" = ".intval($NewType)
517 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
518 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
519 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
523 $this->DB->Query(
"UPDATE ".$this->ItemTableName
524 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewId)
525 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
526 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
529 private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
531 if ($this->ItemTypeFieldName)
533 $this->DB->Query(
"UPDATE ".$this->ItemTableName
534 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
535 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewType)
536 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
537 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
538 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
542 $this->DB->Query(
"UPDATE ".$this->ItemTableName
543 .
" SET Next".$this->ItemIdFieldName.
" = ".intval($NewId)
544 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
545 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
548 private function SetPreviousAndNextItemIds($ItemId, $ItemType,
549 $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
551 if ($this->ItemTypeFieldName)
553 $this->DB->Query(
"UPDATE ".$this->ItemTableName
554 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
555 .
", Previous".$this->ItemTypeFieldName.
" = "
556 .intval($NewPreviousType)
557 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
558 .
", Next".$this->ItemTypeFieldName.
" = ".intval($NewNextType)
559 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
560 .
" AND ".$this->ItemTypeFieldName.
" = ".intval($ItemType)
561 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));
565 $this->DB->Query(
"UPDATE ".$this->ItemTableName
566 .
" SET Previous".$this->ItemIdFieldName.
" = ".intval($NewPreviousId)
567 .
", Next".$this->ItemIdFieldName.
" = ".intval($NewNextId)
568 .
" WHERE ".$this->ItemIdFieldName.
" = ".intval($ItemId)
569 .($this->SqlCondition ?
" AND ".$this->SqlCondition :
""));