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-2013 Edward Almasy and Internet Scout Research Group
7 # http://scout.wisc.edu
8 #
9 
22 
23  # ---- PUBLIC INTERFACE --------------------------------------------------
24 
47  function __construct($ItemTableName, $ItemIdFieldName,
48  $SqlCondition = NULL, $ItemTypeFieldName = NULL)
49  {
50  # grab our own database handle
51  $this->DB = new Database();
52 
53  # save configuration
54  $this->ItemTableName = $ItemTableName;
55  $this->ItemIdFieldName = $ItemIdFieldName;
56  $this->ItemTypeFieldName = $ItemTypeFieldName;
57  $this->ItemTypesInUse = ($ItemTypeFieldName === NULL) ? FALSE : TRUE;
58  $this->SqlCondition($SqlCondition);
59  }
60 
72  function SqlCondition($Condition = NULL)
73  {
74  if ($Condition) { $this->SqlCondition = $Condition; }
75  return $this->SqlCondition;
76  }
77 
87  function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
88  $TargetItemType = NULL, $NewItemType = NULL)
89  {
90  # retrieve item IDs
91  $NewItemId = is_object($NewItemOrItemId)
92  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
93  $TargetItemId = is_object($TargetItemOrItemId)
94  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
95 
96  # remove source item from current position if necessary
97  $this->Remove($NewItemId);
98 
99  # retrieve current previous item pointer for target item
100  $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
101  $TargetItemId, $TargetItemType);
102 
103  # if target item not found
104  if ($TargetItemCurrentPreviousId === FALSE)
105  {
106  # add new item to beginning of list
107  $this->Prepend($NewItemId, $NewItemType);
108  }
109  else
110  {
111  # retrieve target item type if available
112  if (is_array($TargetItemCurrentPreviousId))
113  {
114  $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
115  $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
116  }
117  else
118  {
119  $TargetItemCurrentPreviousType = NULL;
120  }
121 
122  # update IDs to link in new item
123  $this->SetPreviousItemId(
124  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
125  if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
126  {
127  $this->SetNextItemId($TargetItemCurrentPreviousId,
128  $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
129  }
130  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
131  $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
132  $TargetItemId, $TargetItemType);
133  }
134  }
135 
145  function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
146  $TargetItemType = NULL, $NewItemType = NULL)
147  {
148  # retrieve item IDs
149  $NewItemId = is_object($NewItemOrItemId)
150  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
151  $TargetItemId = is_object($TargetItemOrItemId)
152  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
153 
154  # remove new item from existing position (if necessary)
155  $this->Remove($NewItemId, $NewItemType);
156 
157  # retrieve current next item pointer for target item
158  $TargetItemCurrentNextId = $this->GetNextItemId(
159  $TargetItemId, $TargetItemType);
160 
161  # if target item not found
162  if ($TargetItemCurrentNextId === FALSE)
163  {
164  # add new item to end of list
165  $this->Append($NewItemId, $NewItemType);
166  }
167  else
168  {
169  # retrieve target item type if available
170  if (is_array($TargetItemCurrentNextId))
171  {
172  $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
173  $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
174  }
175  else
176  {
177  $TargetItemCurrentNextType = NULL;
178  }
179 
180  # update IDs to link in new item
181  $this->SetNextItemId(
182  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
183  if ($TargetItemCurrentNextId != self::LISTEND_ID)
184  {
185  $this->SetPreviousItemId(
186  $TargetItemCurrentNextId, $TargetItemCurrentNextType,
187  $NewItemId, $NewItemType);
188  }
189  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
190  $TargetItemId, $TargetItemType,
191  $TargetItemCurrentNextId, $TargetItemCurrentNextType);
192  }
193  }
194 
201  function Prepend($ItemOrItemId, $ItemType = NULL)
202  {
203  # get item ID
204  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
205 
206  # remove new item from current position if necessary
207  $this->Remove($ItemId, $ItemType);
208 
209  # if there are items currently in list
210  $ItemIds = $this->GetIds(FALSE);
211  if (count($ItemIds))
212  {
213  # link first item to source item
214  if ($this->ItemTypesInUse)
215  {
216  $Row = array_shift($ItemIds);
217  $FirstItemId = $Row["ID"];
218  $FirstItemType = $Row["Type"];
219  }
220  else
221  {
222  $FirstItemId = array_shift($ItemIds);
223  $FirstItemType = NULL;
224  }
225 
226  $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
227  $this->SetPreviousAndNextItemIds(
228  $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
229  $FirstItemId, $FirstItemType);
230  }
231  else
232  {
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);
236  }
237  }
238 
248  function Append($ItemsOrItemIds, $ItemTypes = NULL)
249  {
250  # check that item types were supplied if needed
251  if ($this->ItemTypesInUse && ($ItemTypes === NULL))
252  {
253  throw new Exception("Item type(s) not supplied.");
254  }
255 
256  # make incoming values into arrays if they aren't already
257  if (!is_array($ItemsOrItemIds))
258  {
259  $ItemsOrItemIds = array($ItemsOrItemIds);
260  }
261  if (!is_array($ItemTypes))
262  {
263  $NewItemTypes = array();
264  foreach ($ItemsOrItemIds as $Id)
265  {
266  $NewItemTypes[] = $ItemTypes;
267  }
268  $ItemTypes = $NewItemTypes;
269  }
270 
271  # get item IDs
272  $ItemIds = array();
273  foreach ($ItemsOrItemIds as $ItemOrId)
274  {
275  $ItemIds[] = is_object($ItemOrId) ? $ItemOrId->Id() : $ItemOrId;
276  }
277 
278  # lock database to prevent anyone from mucking up our changes
279  $this->DB->Query("LOCK TABLES `".$this->ItemTableName."` WRITE");
280 
281  # for each item
282  $ItemIdList = $this->GetIds();
283  foreach ($ItemIds as $Index => $ItemId)
284  {
285  # retrieve item type
286  $ItemType = $ItemTypes[$Index];
287 
288  # if there are items currently in list
289  if (count($ItemIdList))
290  {
291  # remove item from current position if necessary
292  $ItemWasRemoved = $this->Remove($ItemId, $ItemType);
293 
294  # reload item ID list if necessary
295  if ($ItemWasRemoved)
296  {
297  $ItemIdList = $this->GetIds();
298  }
299  }
300 
301  # if there are still items currently in list
302  if (count($ItemIdList))
303  {
304  # find ID and type of last item in list
305  if ($this->ItemTypesInUse)
306  {
307  $Row = array_pop($ItemIdList);
308  $LastItemId = $Row["ID"];
309  $LastItemType = $Row["Type"];
310  array_push($ItemIdList, $Row);
311  }
312  else
313  {
314  $LastItemId = array_pop($ItemIdList);
315  $LastItemType = NULL;
316  array_push($ItemIdList, $LastItemId);
317  }
318 
319  # link last item to source item
320  $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
321  $this->SetPreviousAndNextItemIds(
322  $ItemId, $ItemType, $LastItemId, $LastItemType,
323  self::LISTEND_ID, self::LISTEND_ID);
324  }
325  else
326  {
327  # add item to list as only item
328  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
329  self::LISTEND_ID, self::LISTEND_ID,
330  self::LISTEND_ID, self::LISTEND_ID);
331  }
332 
333  # add item to our local ID list
334  array_push($ItemIdList,
335  $this->ItemTypesInUse
336  ? array("ID" => $ItemId, "Type" => $ItemType)
337  : $ItemId);
338  }
339 
340  # unlock database
341  $this->DB->Query("UNLOCK TABLES");
342  }
343 
351  function GetIds()
352  {
353  # assume no items will be found in folder
354  $ItemIds = array();
355 
356  # if item types are in use
357  if ($this->ItemTypesInUse)
358  {
359  # retrieve IDs and types of all items in list and links between items
360  $this->DB->Query("SELECT * FROM ".$this->ItemTableName
361  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
362  ." ORDER BY ".$this->ItemIdFieldName." ASC");
363 
364  # build up lists of next and previous item pointers
365  $PreviousItemIds = array();
366  $NextItemIds = array();
367  while ($Record = $this->DB->FetchRow())
368  {
369  $Index = $Record[$this->ItemTypeFieldName]
370  .":".$Record[$this->ItemIdFieldName];
371  $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
372  $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
373  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemTypeFieldName]
374  .":".$Record["Previous".$this->ItemIdFieldName];
375  $NextItemIds[$Index] = $Record["Next".$this->ItemTypeFieldName]
376  .":".$Record["Next".$this->ItemIdFieldName];
377  }
378 
379  # find ID of first item in list
380  $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
381  $Index = array_search($ListEndIndex, $PreviousItemIds);
382 
383  # if first item was found
384  if ($Index !== FALSE)
385  {
386  # traverse linked list to build list of item types and IDs
387  do
388  {
389  $ItemIds[$Index] = array(
390  "Type" => $KnownItemTypes[$Index],
391  "ID" => $KnownItemIds[$Index]);
392  $Index = $NextItemIds[$Index];
393  }
394  # (stop if we've reached the end of the list)
395  while (($Index != $ListEndIndex)
396  # (stop if link points to item not in list)
397  && array_key_exists($Index, $NextItemIds)
398  # (stop if link is circular)
399  && !array_key_exists($Index, $ItemIds));
400  }
401  }
402  else
403  {
404  # retrieve IDs of all items in list and links between items
405  $this->DB->Query("SELECT ".$this->ItemIdFieldName
406  .", Previous".$this->ItemIdFieldName
407  .", Next".$this->ItemIdFieldName
408  ." FROM ".$this->ItemTableName
409  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
410  ." ORDER BY ".$this->ItemIdFieldName." ASC");
411 
412  # build up lists of next item pointers
413  $PreviousItemIds = array();
414  $NextItemIds = array();
415  while ($Record = $this->DB->FetchRow())
416  {
417  $Index = $Record[$this->ItemIdFieldName];
418  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
419  $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
420  }
421 
422  # find ID of first item in list
423  $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
424 
425  # if first item was found
426  if ($ItemId !== FALSE)
427  {
428  # traverse linked list to build list of item IDs
429  do
430  {
431  $ItemIds[] = $ItemId;
432  $ItemId = $NextItemIds[$ItemId];
433  }
434  # (stop if we've reached the end of the list)
435  while (($ItemId != self::LISTEND_ID)
436  # (stop if link points to item not in list)
437  && array_key_exists($ItemId, $NextItemIds)
438  # (stop if link is circular)
439  && !in_array($ItemId, $ItemIds));
440  }
441  }
442 
443  # return list of item IDs to caller
444  return $ItemIds;
445  }
446 
451  function GetCount()
452  {
453  # retrieve count of items
454  return $this->DB->Query("SELECT COUNT(DISTINCT `".$this->ItemIdFieldName
455  ."`) AS ItemCount FROM ".$this->ItemTableName
456  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : ""),
457  "ItemCount");
458  }
459 
467  function Remove($ItemId, $ItemType = NULL)
468  {
469  # retrieve item's "previous" pointer
470  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
471 
472  # bail out if item was not found
473  if ($CurrentItemPreviousId === FALSE) { return FALSE; }
474 
475  # retrieve item's "next" pointer
476  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
477  if ($this->ItemTypesInUse)
478  {
479  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
480  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
481  $CurrentItemNextType = $CurrentItemNextId["Type"];
482  $CurrentItemNextId = $CurrentItemNextId["ID"];
483  }
484  else
485  {
486  $CurrentItemPreviousType = NULL;
487  $CurrentItemNextType = NULL;
488  }
489 
490  # if item was not first in list
491  if ($CurrentItemPreviousId >= 0)
492  {
493  # link previous item to item's current next item
494  $this->SetNextItemId(
495  $CurrentItemPreviousId, $CurrentItemPreviousType,
496  $CurrentItemNextId, $CurrentItemNextType);
497  }
498 
499  # if item was not last in list
500  if ($CurrentItemNextId >= 0)
501  {
502  # link next item to item's current previous item
503  $this->SetPreviousItemId(
504  $CurrentItemNextId, $CurrentItemNextType,
505  $CurrentItemPreviousId, $CurrentItemPreviousType);
506  }
507 
508  # set items pointers to indicate it is not part of a list
509  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
510  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
511  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
512 
513  # report that item was removed
514  return TRUE;
515  }
516 
517 
518  # ---- PRIVATE INTERFACE -------------------------------------------------
519 
520  private $DB;
522  private $ItemTableName;
524  private $ItemIdFieldName;
526  private $ItemTypeFieldName;
528  private $ItemTypesInUse;
530  private $SqlCondition = NULL;
531 
532  const UNINITIALIZED_ID = -1;
533  const LISTEND_ID = -2;
534 
542  private function GetPreviousItemId($ItemId, $ItemType)
543  {
544  if ($this->ItemTypesInUse)
545  {
546  $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
547  .", Previous".$this->ItemTypeFieldName
548  ." FROM ".$this->ItemTableName
549  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
550  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
551  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
552  if (!$this->DB->NumRowsSelected()) { return FALSE; }
553  $Row = $this->DB->FetchRow();
554  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
555  { return FALSE; }
556  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
557  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
558  return $ReturnValue;
559  }
560  else
561  {
562  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
563  ." FROM ".$this->ItemTableName
564  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
565  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
566  "Previous".$this->ItemIdFieldName);
567  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
568  }
569  }
570 
578  private function GetNextItemId($ItemId, $ItemType)
579  {
580  if ($this->ItemTypesInUse)
581  {
582  $this->DB->Query("SELECT Next".$this->ItemIdFieldName
583  .", Next".$this->ItemTypeFieldName
584  ." FROM ".$this->ItemTableName
585  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
586  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
587  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
588  if (!$this->DB->NumRowsSelected()) { return FALSE; }
589  $Row = $this->DB->FetchRow();
590  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
591  { return FALSE; }
592  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
593  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
594  return $ReturnValue;
595  }
596  else
597  {
598  $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
599  ." FROM ".$this->ItemTableName
600  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
601  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
602  "Next".$this->ItemIdFieldName);
603  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
604  }
605  }
606 
614  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
615  {
616  if ($this->ItemTypesInUse)
617  {
618  $this->DB->Query("UPDATE ".$this->ItemTableName
619  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
620  .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
621  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
622  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
623  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
624  }
625  else
626  {
627  $this->DB->Query("UPDATE ".$this->ItemTableName
628  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
629  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
630  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
631  }
632  }
633 
641  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
642  {
643  if ($this->ItemTypesInUse)
644  {
645  $this->DB->Query("UPDATE ".$this->ItemTableName
646  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
647  .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
648  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
649  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
650  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
651  }
652  else
653  {
654  $this->DB->Query("UPDATE ".$this->ItemTableName
655  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
656  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
657  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
658  }
659  }
660 
670  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
671  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
672  {
673  if ($this->ItemTypesInUse)
674  {
675  $this->DB->Query("UPDATE ".$this->ItemTableName
676  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
677  .", Previous".$this->ItemTypeFieldName." = "
678  .intval($NewPreviousType)
679  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
680  .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
681  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
682  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
683  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
684  }
685  else
686  {
687  $this->DB->Query("UPDATE ".$this->ItemTableName
688  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
689  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
690  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
691  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
692  }
693  }
694 }
695 
696 
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.