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->SqlCondition($SqlCondition);
58  }
59 
71  function SqlCondition($Condition = NULL)
72  {
73  if ($Condition) { $this->SqlCondition = $Condition; }
74  return $this->SqlCondition;
75  }
76 
86  function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
87  $TargetItemType = NULL, $NewItemType = NULL)
88  {
89  # retrieve item IDs
90  $NewItemId = is_object($NewItemOrItemId)
91  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
92  $TargetItemId = is_object($TargetItemOrItemId)
93  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
94 
95  # remove source item from current position if necessary
96  $this->Remove($NewItemId);
97 
98  # retrieve current previous item pointer for target item
99  $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
100  $TargetItemId, $TargetItemType);
101 
102  # if target item not found
103  if ($TargetItemCurrentPreviousId === FALSE)
104  {
105  # add new item to beginning of list
106  $this->Prepend($NewItemId, $NewItemType);
107  }
108  else
109  {
110  # retrieve target item type if available
111  if (is_array($TargetItemCurrentPreviousId))
112  {
113  $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
114  $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
115  }
116  else
117  {
118  $TargetItemCurrentPreviousType = NULL;
119  }
120 
121  # update IDs to link in new item
122  $this->SetPreviousItemId(
123  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
124  if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
125  {
126  $this->SetNextItemId($TargetItemCurrentPreviousId,
127  $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
128  }
129  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
130  $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
131  $TargetItemId, $TargetItemType);
132  }
133  }
134 
144  function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
145  $TargetItemType = NULL, $NewItemType = NULL)
146  {
147  # retrieve item IDs
148  $NewItemId = is_object($NewItemOrItemId)
149  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
150  $TargetItemId = is_object($TargetItemOrItemId)
151  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
152 
153  # remove new item from existing position (if necessary)
154  $this->Remove($NewItemId, $NewItemType);
155 
156  # retrieve current next item pointer for target item
157  $TargetItemCurrentNextId = $this->GetNextItemId(
158  $TargetItemId, $TargetItemType);
159 
160  # if target item not found
161  if ($TargetItemCurrentNextId === FALSE)
162  {
163  # add new item to end of list
164  $this->Append($NewItemId, $NewItemType);
165  }
166  else
167  {
168  # retrieve target item type if available
169  if (is_array($TargetItemCurrentNextId))
170  {
171  $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
172  $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
173  }
174  else
175  {
176  $TargetItemCurrentNextType = NULL;
177  }
178 
179  # update IDs to link in new item
180  $this->SetNextItemId(
181  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
182  if ($TargetItemCurrentNextId != self::LISTEND_ID)
183  {
184  $this->SetPreviousItemId(
185  $TargetItemCurrentNextId, $TargetItemCurrentNextType,
186  $NewItemId, $NewItemType);
187  }
188  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
189  $TargetItemId, $TargetItemType,
190  $TargetItemCurrentNextId, $TargetItemCurrentNextType);
191  }
192  }
193 
200  function Prepend($ItemOrItemId, $ItemType = NULL)
201  {
202  # get item ID
203  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
204 
205  # remove new item from current position if necessary
206  $this->Remove($ItemId, $ItemType);
207 
208  # if there are items currently in list
209  $ItemIds = $this->GetIds(FALSE);
210  if (count($ItemIds))
211  {
212  # link first item to source item
213  if ($this->ItemTypeFieldName)
214  {
215  $Row = array_shift($ItemIds);
216  $FirstItemId = $Row["ID"];
217  $FirstItemType = $Row["Type"];
218  }
219  else
220  {
221  $FirstItemId = array_shift($ItemIds);
222  $FirstItemType = NULL;
223  }
224 
225  $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
226  $this->SetPreviousAndNextItemIds(
227  $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
228  $FirstItemId, $FirstItemType);
229  }
230  else
231  {
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);
235  }
236  }
237 
244  function Append($ItemOrItemId, $ItemType = NULL)
245  {
246  # get item ID
247  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
248 
249  # remove item from current position if necessary
250  $this->Remove($ItemId, $ItemType);
251 
252  # if there are items currently in list
253  $ItemIds = $this->GetIds();
254  if (count($ItemIds))
255  {
256  # link last item to source item
257  if ($this->ItemTypeFieldName)
258  {
259  $Row = array_pop($ItemIds);
260  $LastItemId = $Row["ID"];
261  $LastItemType = $Row["Type"];
262  }
263  else
264  {
265  $LastItemId = array_pop($ItemIds);
266  $LastItemType = NULL;
267  }
268  $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
269  $this->SetPreviousAndNextItemIds(
270  $ItemId, $ItemType, $LastItemId, $LastItemType,
271  self::LISTEND_ID, self::LISTEND_ID);
272  }
273  else
274  {
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);
279  }
280  }
281 
289  function GetIds()
290  {
291  # assume no items will be found in folder
292  $ItemIds = array();
293 
294  # if item types are in use
295  if ($this->ItemTypeFieldName)
296  {
297  # retrieve IDs and types of all items in list and links between items
298  $this->DB->Query("SELECT * FROM ".$this->ItemTableName
299  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
300  ." ORDER BY ".$this->ItemIdFieldName." ASC");
301 
302  # build up lists of next and previous item pointers
303  $PreviousItemIds = array();
304  $NextItemIds = array();
305  while ($Record = $this->DB->FetchRow())
306  {
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];
315  }
316 
317  # find ID of first item in list
318  $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
319  $Index = array_search($ListEndIndex, $PreviousItemIds);
320 
321  # if first item was found
322  if ($Index !== FALSE)
323  {
324  # traverse linked list to build list of item types and IDs
325  do
326  {
327  $ItemIds[$Index] = array(
328  "Type" => $KnownItemTypes[$Index],
329  "ID" => $KnownItemIds[$Index]);
330  $Index = $NextItemIds[$Index];
331  }
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));
338  }
339  }
340  else
341  {
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
347  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
348  ." ORDER BY ".$this->ItemIdFieldName." ASC");
349 
350  # build up lists of next item pointers
351  $PreviousItemIds = array();
352  $NextItemIds = array();
353  while ($Record = $this->DB->FetchRow())
354  {
355  $Index = $Record[$this->ItemIdFieldName];
356  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
357  $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
358  }
359 
360  # find ID of first item in list
361  $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
362 
363  # if first item was found
364  if ($ItemId !== FALSE)
365  {
366  # traverse linked list to build list of item IDs
367  do
368  {
369  $ItemIds[] = $ItemId;
370  $ItemId = $NextItemIds[$ItemId];
371  }
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));
378  }
379  }
380 
381  # return list of item IDs to caller
382  return $ItemIds;
383  }
384 
391  function Remove($ItemId, $ItemType = NULL)
392  {
393  # retrieve item's "previous" pointer
394  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
395 
396  # bail out if item was not found
397  if ($CurrentItemPreviousId === FALSE) { return; }
398 
399  # retrieve item's "next" pointer
400  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
401  if ($this->ItemTypeFieldName)
402  {
403  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
404  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
405  $CurrentItemNextType = $CurrentItemNextId["Type"];
406  $CurrentItemNextId = $CurrentItemNextId["ID"];
407  }
408  else
409  {
410  $CurrentItemPreviousType = NULL;
411  $CurrentItemNextType = NULL;
412  }
413 
414  # if item was not first in list
415  if ($CurrentItemPreviousId >= 0)
416  {
417  # link previous item to item's current next item
418  $this->SetNextItemId(
419  $CurrentItemPreviousId, $CurrentItemPreviousType,
420  $CurrentItemNextId, $CurrentItemNextType);
421  }
422 
423  # if item was not last in list
424  if ($CurrentItemNextId >= 0)
425  {
426  # link next item to item's current previous item
427  $this->SetPreviousItemId(
428  $CurrentItemNextId, $CurrentItemNextType,
429  $CurrentItemPreviousId, $CurrentItemPreviousType);
430  }
431 
432  # set items pointers to indicate it is not part of a list
433  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
434  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
435  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
436  }
437 
438 
439  # ---- PRIVATE INTERFACE -------------------------------------------------
440 
441  private $DB;
443  private $ItemTableName;
445  private $ItemIdFieldName;
447  private $ItemTypeFieldName;
449  private $SqlCondition = NULL;
450 
451  const UNINITIALIZED_ID = -1;
452  const LISTEND_ID = -2;
453 
461  private function GetPreviousItemId($ItemId, $ItemType)
462  {
463  if ($this->ItemTypeFieldName)
464  {
465  $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
466  .", Previous".$this->ItemTypeFieldName
467  ." FROM ".$this->ItemTableName
468  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
469  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
470  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
471  if (!$this->DB->NumRowsSelected()) { return FALSE; }
472  $Row = $this->DB->FetchRow();
473  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
474  { return FALSE; }
475  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
476  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
477  return $ReturnValue;
478  }
479  else
480  {
481  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
482  ." FROM ".$this->ItemTableName
483  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
484  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
485  "Previous".$this->ItemIdFieldName);
486  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
487  }
488  }
489 
497  private function GetNextItemId($ItemId, $ItemType)
498  {
499  if ($this->ItemTypeFieldName)
500  {
501  $this->DB->Query("SELECT Next".$this->ItemIdFieldName
502  .", Next".$this->ItemTypeFieldName
503  ." FROM ".$this->ItemTableName
504  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
505  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
506  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
507  if (!$this->DB->NumRowsSelected()) { return FALSE; }
508  $Row = $this->DB->FetchRow();
509  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
510  { return FALSE; }
511  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
512  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
513  return $ReturnValue;
514  }
515  else
516  {
517  $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
518  ." FROM ".$this->ItemTableName
519  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
520  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
521  "Next".$this->ItemIdFieldName);
522  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
523  }
524  }
525 
533  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
534  {
535  if ($this->ItemTypeFieldName)
536  {
537  $this->DB->Query("UPDATE ".$this->ItemTableName
538  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
539  .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
540  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
541  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
542  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
543  }
544  else
545  {
546  $this->DB->Query("UPDATE ".$this->ItemTableName
547  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
548  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
549  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
550  }
551  }
552 
560  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
561  {
562  if ($this->ItemTypeFieldName)
563  {
564  $this->DB->Query("UPDATE ".$this->ItemTableName
565  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
566  .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
567  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
568  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
569  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
570  }
571  else
572  {
573  $this->DB->Query("UPDATE ".$this->ItemTableName
574  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
575  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
576  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
577  }
578  }
579 
589  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
590  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
591  {
592  if ($this->ItemTypeFieldName)
593  {
594  $this->DB->Query("UPDATE ".$this->ItemTableName
595  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
596  .", Previous".$this->ItemTypeFieldName." = "
597  .intval($NewPreviousType)
598  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
599  .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
600  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
601  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
602  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
603  }
604  else
605  {
606  $this->DB->Query("UPDATE ".$this->ItemTableName
607  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
608  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
609  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
610  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
611  }
612  }
613 }
614 
615 
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.
PHP
Definition: OAIClient.php:39
InsertBefore($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list before specified item.
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.