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 
389  function GetCount()
390  {
391  # retrieve count of items
392  return $this->DB->Query("SELECT COUNT(DISTINCT `".$this->ItemIdFieldName
393  ."`) AS ItemCount FROM ".$this->ItemTableName
394  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : ""),
395  "ItemCount");
396  }
397 
404  function Remove($ItemId, $ItemType = NULL)
405  {
406  # retrieve item's "previous" pointer
407  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
408 
409  # bail out if item was not found
410  if ($CurrentItemPreviousId === FALSE) { return; }
411 
412  # retrieve item's "next" pointer
413  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
414  if ($this->ItemTypeFieldName)
415  {
416  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
417  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
418  $CurrentItemNextType = $CurrentItemNextId["Type"];
419  $CurrentItemNextId = $CurrentItemNextId["ID"];
420  }
421  else
422  {
423  $CurrentItemPreviousType = NULL;
424  $CurrentItemNextType = NULL;
425  }
426 
427  # if item was not first in list
428  if ($CurrentItemPreviousId >= 0)
429  {
430  # link previous item to item's current next item
431  $this->SetNextItemId(
432  $CurrentItemPreviousId, $CurrentItemPreviousType,
433  $CurrentItemNextId, $CurrentItemNextType);
434  }
435 
436  # if item was not last in list
437  if ($CurrentItemNextId >= 0)
438  {
439  # link next item to item's current previous item
440  $this->SetPreviousItemId(
441  $CurrentItemNextId, $CurrentItemNextType,
442  $CurrentItemPreviousId, $CurrentItemPreviousType);
443  }
444 
445  # set items pointers to indicate it is not part of a list
446  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
447  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
448  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
449  }
450 
451 
452  # ---- PRIVATE INTERFACE -------------------------------------------------
453 
454  private $DB;
456  private $ItemTableName;
458  private $ItemIdFieldName;
460  private $ItemTypeFieldName;
462  private $SqlCondition = NULL;
463 
464  const UNINITIALIZED_ID = -1;
465  const LISTEND_ID = -2;
466 
474  private function GetPreviousItemId($ItemId, $ItemType)
475  {
476  if ($this->ItemTypeFieldName)
477  {
478  $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
479  .", Previous".$this->ItemTypeFieldName
480  ." FROM ".$this->ItemTableName
481  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
482  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
483  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
484  if (!$this->DB->NumRowsSelected()) { return FALSE; }
485  $Row = $this->DB->FetchRow();
486  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
487  { return FALSE; }
488  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
489  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
490  return $ReturnValue;
491  }
492  else
493  {
494  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
495  ." FROM ".$this->ItemTableName
496  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
497  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
498  "Previous".$this->ItemIdFieldName);
499  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
500  }
501  }
502 
510  private function GetNextItemId($ItemId, $ItemType)
511  {
512  if ($this->ItemTypeFieldName)
513  {
514  $this->DB->Query("SELECT Next".$this->ItemIdFieldName
515  .", Next".$this->ItemTypeFieldName
516  ." FROM ".$this->ItemTableName
517  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
518  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
519  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
520  if (!$this->DB->NumRowsSelected()) { return FALSE; }
521  $Row = $this->DB->FetchRow();
522  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
523  { return FALSE; }
524  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
525  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
526  return $ReturnValue;
527  }
528  else
529  {
530  $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
531  ." FROM ".$this->ItemTableName
532  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
533  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
534  "Next".$this->ItemIdFieldName);
535  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
536  }
537  }
538 
546  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
547  {
548  if ($this->ItemTypeFieldName)
549  {
550  $this->DB->Query("UPDATE ".$this->ItemTableName
551  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
552  .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
553  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
554  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
555  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
556  }
557  else
558  {
559  $this->DB->Query("UPDATE ".$this->ItemTableName
560  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
561  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
562  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
563  }
564  }
565 
573  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
574  {
575  if ($this->ItemTypeFieldName)
576  {
577  $this->DB->Query("UPDATE ".$this->ItemTableName
578  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
579  .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
580  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
581  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
582  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
583  }
584  else
585  {
586  $this->DB->Query("UPDATE ".$this->ItemTableName
587  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
588  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
589  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
590  }
591  }
592 
602  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
603  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
604  {
605  if ($this->ItemTypeFieldName)
606  {
607  $this->DB->Query("UPDATE ".$this->ItemTableName
608  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
609  .", Previous".$this->ItemTypeFieldName." = "
610  .intval($NewPreviousType)
611  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
612  .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
613  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
614  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
615  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
616  }
617  else
618  {
619  $this->DB->Query("UPDATE ".$this->ItemTableName
620  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
621  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
622  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
623  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
624  }
625  }
626 }
627 
628 
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.
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($ItemOrItemId, $ItemType=NULL)
Add item to end of list.