CWIS Developer Documentation
PersistentDoublyLinkedList.php
Go to the documentation of this file.
1 <?PHP
2 #
3 # FILE: PersistentDoublyLinkedList.php
4 #
5 # Part of the ScoutLib application support library
6 # Copyright 2012-2015 Edward Almasy and Internet Scout Research Group
7 # http://scout.wisc.edu
8 #
9 
22 {
23 
24  # ---- PUBLIC INTERFACE --------------------------------------------------
25 
48  public function __construct($ItemTableName, $ItemIdFieldName,
49  $SqlCondition = NULL, $ItemTypeFieldName = NULL)
50  {
51  # grab our own database handle
52  $this->DB = new Database();
53 
54  # save configuration
55  $this->ItemTableName = $ItemTableName;
56  $this->ItemIdFieldName = $ItemIdFieldName;
57  $this->ItemTypeFieldName = $ItemTypeFieldName;
58  $this->ItemTypesInUse = ($ItemTypeFieldName === NULL) ? FALSE : TRUE;
59  $this->SqlCondition($SqlCondition);
60  }
61 
73  public function SqlCondition($Condition = NULL)
74  {
75  if ($Condition) { $this->SqlCondition = $Condition; }
76  return $this->SqlCondition;
77  }
78 
88  public function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
89  $TargetItemType = NULL, $NewItemType = NULL)
90  {
91  # verify item types supplied or omitted as appropriate
92  $this->CheckItemTypeParameter($TargetItemType);
93  $this->CheckItemTypeParameter($NewItemType);
94 
95  # retrieve item IDs
96  $NewItemId = is_object($NewItemOrItemId)
97  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
98  $TargetItemId = is_object($TargetItemOrItemId)
99  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
100 
101  # remove source item from current position if necessary
102  $this->Remove($NewItemId, $NewItemType);
103 
104  # retrieve current previous item pointer for target item
105  $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
106  $TargetItemId, $TargetItemType);
107 
108  # if target item not found
109  if ($TargetItemCurrentPreviousId === FALSE)
110  {
111  # add new item to beginning of list
112  $this->Prepend($NewItemId, $NewItemType);
113  }
114  else
115  {
116  # retrieve target item type if available
117  if (is_array($TargetItemCurrentPreviousId))
118  {
119  $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
120  $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
121  }
122  else
123  {
124  $TargetItemCurrentPreviousType = NULL;
125  }
126 
127  # update IDs to link in new item
128  $this->SetPreviousItemId(
129  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
130  if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
131  {
132  $this->SetNextItemId($TargetItemCurrentPreviousId,
133  $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
134  }
135  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
136  $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
137  $TargetItemId, $TargetItemType);
138  }
139  }
140 
150  public function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
151  $TargetItemType = NULL, $NewItemType = NULL)
152  {
153  # verify item types supplied or omitted as appropriate
154  $this->CheckItemTypeParameter($TargetItemType);
155  $this->CheckItemTypeParameter($NewItemType);
156 
157  # retrieve item IDs
158  $NewItemId = is_object($NewItemOrItemId)
159  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
160  $TargetItemId = is_object($TargetItemOrItemId)
161  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
162 
163  # remove new item from existing position (if necessary)
164  $this->Remove($NewItemId, $NewItemType);
165 
166  # retrieve current next item pointer for target item
167  $TargetItemCurrentNextId = $this->GetNextItemId(
168  $TargetItemId, $TargetItemType);
169 
170  # if target item not found
171  if ($TargetItemCurrentNextId === FALSE)
172  {
173  # add new item to end of list
174  $this->Append($NewItemId, $NewItemType);
175  }
176  else
177  {
178  # retrieve target item type if available
179  if (is_array($TargetItemCurrentNextId))
180  {
181  $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
182  $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
183  }
184  else
185  {
186  $TargetItemCurrentNextType = NULL;
187  }
188 
189  # update IDs to link in new item
190  $this->SetNextItemId(
191  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
192  if ($TargetItemCurrentNextId != self::LISTEND_ID)
193  {
194  $this->SetPreviousItemId(
195  $TargetItemCurrentNextId, $TargetItemCurrentNextType,
196  $NewItemId, $NewItemType);
197  }
198  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
199  $TargetItemId, $TargetItemType,
200  $TargetItemCurrentNextId, $TargetItemCurrentNextType);
201  }
202  }
203 
210  public function Prepend($ItemOrItemId, $ItemType = NULL)
211  {
212  # verify item types supplied or omitted as appropriate
213  $this->CheckItemTypeParameter($ItemType);
214 
215  # get item ID
216  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
217 
218  # remove new item from current position if necessary
219  $this->Remove($ItemId, $ItemType);
220 
221  # if there are items currently in list
222  $ItemIds = $this->GetIds(FALSE);
223  if (count($ItemIds))
224  {
225  # link first item to source item
226  if ($this->ItemTypesInUse)
227  {
228  $Row = array_shift($ItemIds);
229  $FirstItemId = $Row["ID"];
230  $FirstItemType = $Row["Type"];
231  }
232  else
233  {
234  $FirstItemId = array_shift($ItemIds);
235  $FirstItemType = NULL;
236  }
237 
238  $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
239  $this->SetPreviousAndNextItemIds(
240  $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
241  $FirstItemId, $FirstItemType);
242  }
243  else
244  {
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);
249  }
250  }
251 
261  public function Append($ItemsOrItemIds, $ItemTypes = NULL)
262  {
263  # verify item types supplied or omitted as appropriate
264  $this->CheckItemTypeParameter($ItemTypes);
265 
266  # make incoming values into arrays if they aren't already
267  if (!is_array($ItemsOrItemIds))
268  {
269  $ItemsOrItemIds = array($ItemsOrItemIds);
270  }
271  if (!is_array($ItemTypes))
272  {
273  $NewItemTypes = array();
274  foreach ($ItemsOrItemIds as $Id)
275  {
276  $NewItemTypes[] = $ItemTypes;
277  }
278  $ItemTypes = $NewItemTypes;
279  }
280 
281  # get item IDs
282  $ItemIds = array();
283  foreach ($ItemsOrItemIds as $ItemOrId)
284  {
285  $ItemIds[] = is_object($ItemOrId) ? $ItemOrId->Id() : $ItemOrId;
286  }
287 
288  # lock database to prevent anyone from mucking up our changes
289  $this->DB->Query("LOCK TABLES `".$this->ItemTableName."` WRITE");
290 
291  # for each item
292  $ItemIdList = $this->GetIds();
293  foreach ($ItemIds as $Index => $ItemId)
294  {
295  # retrieve item type
296  $ItemType = $ItemTypes[$Index];
297 
298  # if there are items currently in list
299  if (count($ItemIdList))
300  {
301  # remove item from current position if necessary
302  $ItemWasRemoved = $this->Remove($ItemId, $ItemType);
303 
304  # reload item ID list if necessary
305  if ($ItemWasRemoved)
306  {
307  $ItemIdList = $this->GetIds();
308  }
309  }
310 
311  # if there are still items currently in list
312  if (count($ItemIdList))
313  {
314  # find ID and type of last item in list
315  if ($this->ItemTypesInUse)
316  {
317  $Row = array_pop($ItemIdList);
318  $LastItemId = $Row["ID"];
319  $LastItemType = $Row["Type"];
320  array_push($ItemIdList, $Row);
321  }
322  else
323  {
324  $LastItemId = array_pop($ItemIdList);
325  $LastItemType = NULL;
326  array_push($ItemIdList, $LastItemId);
327  }
328 
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);
334  }
335  else
336  {
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);
341  }
342 
343  # add item to our local ID list
344  array_push($ItemIdList,
345  $this->ItemTypesInUse
346  ? array("ID" => $ItemId, "Type" => $ItemType)
347  : $ItemId);
348  }
349 
350  # unlock database
351  $this->DB->Query("UNLOCK TABLES");
352  }
353 
361  public function GetIds()
362  {
363  # assume no items will be found in folder
364  $ItemIds = array();
365 
366  # if item types are in use
367  if ($this->ItemTypesInUse)
368  {
369  # retrieve IDs and types of all items in list and links between items
370  $this->DB->Query("SELECT * FROM ".$this->ItemTableName
371  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
372  ." ORDER BY ".$this->ItemIdFieldName." ASC");
373 
374  # build up lists of next and previous item pointers
375  $PreviousItemIds = array();
376  $NextItemIds = array();
377  while ($Record = $this->DB->FetchRow())
378  {
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];
387  }
388 
389  # find ID of first item in list
390  $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
391  $Index = array_search($ListEndIndex, $PreviousItemIds);
392 
393  # if first item was found
394  if ($Index !== FALSE)
395  {
396  # traverse linked list to build list of item types and IDs
397  do
398  {
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));
409  }
410  }
411  else
412  {
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
418  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
419  ." ORDER BY ".$this->ItemIdFieldName." ASC");
420 
421  # build up lists of next item pointers
422  $PreviousItemIds = array();
423  $NextItemIds = array();
424  while ($Record = $this->DB->FetchRow())
425  {
426  $Index = intval($Record[$this->ItemIdFieldName]);
427  $PreviousItemIds[$Index] =
428  intval($Record["Previous".$this->ItemIdFieldName]);
429  $NextItemIds[$Index] =
430  intval($Record["Next".$this->ItemIdFieldName]);
431  }
432 
433  # find ID of first item in list
434  $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
435 
436  # if first item was found
437  if ($ItemId !== FALSE)
438  {
439  # traverse linked list to build list of item IDs
440  do
441  {
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));
450  }
451  }
452 
453  # return list of item IDs to caller
454  return $ItemIds;
455  }
456 
461  public function GetCount()
462  {
463  # retrieve count of items
464  return count($this->GetIds());
465  }
466 
474  public function Remove($ItemId, $ItemType = NULL)
475  {
476  # verify item types supplied or omitted as appropriate
477  $this->CheckItemTypeParameter($ItemType);
478 
479  # retrieve item's "previous" pointer
480  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
481 
482  # bail out if item was not found
483  if ($CurrentItemPreviousId === FALSE) { return FALSE; }
484 
485  # retrieve item's "next" pointer
486  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
487  if ($this->ItemTypesInUse)
488  {
489  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
490  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
491  $CurrentItemNextType = $CurrentItemNextId["Type"];
492  $CurrentItemNextId = $CurrentItemNextId["ID"];
493  }
494  else
495  {
496  $CurrentItemPreviousType = NULL;
497  $CurrentItemNextType = NULL;
498  }
499 
500  # if item was not first in list
501  if ($CurrentItemPreviousId >= 0)
502  {
503  # link previous item to item's current next item
504  $this->SetNextItemId(
505  $CurrentItemPreviousId, $CurrentItemPreviousType,
506  $CurrentItemNextId, $CurrentItemNextType);
507  }
508 
509  # if item was not last in list
510  if ($CurrentItemNextId >= 0)
511  {
512  # link next item to item's current previous item
513  $this->SetPreviousItemId(
514  $CurrentItemNextId, $CurrentItemNextType,
515  $CurrentItemPreviousId, $CurrentItemPreviousType);
516  }
517 
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);
522 
523  # report that item was removed
524  return TRUE;
525  }
526 
527 
528  # ---- PRIVATE INTERFACE -------------------------------------------------
529 
530  private $DB;
532  private $ItemTableName;
534  private $ItemIdFieldName;
536  private $ItemTypeFieldName;
538  private $ItemTypesInUse;
540  private $SqlCondition = NULL;
541 
542  const UNINITIALIZED_ID = -1;
543  const LISTEND_ID = -2;
544 
552  private function GetPreviousItemId($ItemId, $ItemType)
553  {
554  if ($this->ItemTypesInUse)
555  {
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)
561  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
562  if (!$this->DB->NumRowsSelected()) { return FALSE; }
563  $Row = $this->DB->FetchRow();
564  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
565  { return FALSE; }
566  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
567  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
568  return $ReturnValue;
569  }
570  else
571  {
572  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
573  ." FROM ".$this->ItemTableName
574  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
575  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
576  "Previous".$this->ItemIdFieldName);
577  return (($ReturnVal === NULL)
578  || ($ReturnVal == self::UNINITIALIZED_ID))
579  ? FALSE : $ReturnVal;
580  }
581  }
582 
590  private function GetNextItemId($ItemId, $ItemType)
591  {
592  if ($this->ItemTypesInUse)
593  {
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)
599  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
600  if (!$this->DB->NumRowsSelected()) { return FALSE; }
601  $Row = $this->DB->FetchRow();
602  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
603  { return FALSE; }
604  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
605  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
606  return $ReturnValue;
607  }
608  else
609  {
610  $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
611  ." FROM ".$this->ItemTableName
612  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
613  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
614  "Next".$this->ItemIdFieldName);
615  return (($ReturnVal === NULL)
616  || ($ReturnVal == self::UNINITIALIZED_ID))
617  ? FALSE : $ReturnVal;
618  }
619  }
620 
628  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
629  {
630  if ($this->ItemTypesInUse)
631  {
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)
637  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
638  }
639  else
640  {
641  $this->DB->Query("UPDATE ".$this->ItemTableName
642  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
643  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
644  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
645  }
646  }
647 
655  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
656  {
657  if ($this->ItemTypesInUse)
658  {
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)
664  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
665  }
666  else
667  {
668  $this->DB->Query("UPDATE ".$this->ItemTableName
669  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
670  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
671  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
672  }
673  }
674 
684  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
685  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
686  {
687  if ($this->ItemTypesInUse)
688  {
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 : ""));
698  }
699  else
700  {
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)
705  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
706  }
707  }
708 
713  private function CheckItemTypeParameter($ItemType)
714  {
715  if ($this->ItemTypesInUse)
716  {
717  if ($ItemType === NULL)
718  {
719  throw new Exception("Item type(s) not supplied.");
720  }
721  }
722  else
723  {
724  if ($ItemType !== NULL)
725  {
726  throw new Exception("Item type(s) supplied when not in use.");
727  }
728  }
729  }
730 }
SQL database abstraction object with smart query caching.
Definition: Database.php:22
__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.