CWIS Developer Documentation
PersistentDoublyLinkedList.php
Go to the documentation of this file.
1 <?PHP
2 
3 #
4 # FILE: PersistentDoublyLinkedList.php
5 #
6 # Part of the ScoutLib application support library
7 # Copyright 2012 Edward Almasy and Internet Scout
8 # http://scout.wisc.edu
9 #
10 
23 
24  # ---- PUBLIC INTERFACE --------------------------------------------------
25 
48  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->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->ItemTypeFieldName)
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 
245  function Append($ItemOrItemId, $ItemType = NULL)
246  {
247  # get item ID
248  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
249 
250  # remove item from current position if necessary
251  $this->Remove($ItemId, $ItemType);
252 
253  # if there are items currently in list
254  $ItemIds = $this->GetIds();
255  if (count($ItemIds))
256  {
257  # link last item to source item
258  if ($this->ItemTypeFieldName)
259  {
260  $Row = array_pop($ItemIds);
261  $LastItemId = $Row["ID"];
262  $LastItemType = $Row["Type"];
263  }
264  else
265  {
266  $LastItemId = array_pop($ItemIds);
267  $LastItemType = NULL;
268  }
269  $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
270  $this->SetPreviousAndNextItemIds(
271  $ItemId, $ItemType, $LastItemId, $LastItemType,
272  self::LISTEND_ID, self::LISTEND_ID);
273  }
274  else
275  {
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);
280  }
281  }
282 
290  function GetIds()
291  {
292  # assume no items will be found in folder
293  $ItemIds = array();
294 
295  # if item types are in use
296  if ($this->ItemTypeFieldName)
297  {
298  # retrieve IDs and types of all items in list and links between items
299  $this->DB->Query("SELECT * FROM ".$this->ItemTableName
300  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
301  ." ORDER BY ".$this->ItemIdFieldName." ASC");
302 
303  # build up lists of next and previous item pointers
304  $PreviousItemIds = array();
305  $NextItemIds = array();
306  while ($Record = $this->DB->FetchRow())
307  {
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];
316  }
317 
318  # find ID of first item in list
319  $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
320  $Index = array_search($ListEndIndex, $PreviousItemIds);
321 
322  # if first item was found
323  if ($Index !== FALSE)
324  {
325  # traverse linked list to build list of item types and IDs
326  do
327  {
328  $ItemIds[$Index] = array(
329  "Type" => $KnownItemTypes[$Index],
330  "ID" => $KnownItemIds[$Index]);
331  $Index = $NextItemIds[$Index];
332  }
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));
339  }
340  }
341  else
342  {
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
348  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
349  ." ORDER BY ".$this->ItemIdFieldName." ASC");
350 
351  # build up lists of next item pointers
352  $PreviousItemIds = array();
353  $NextItemIds = array();
354  while ($Record = $this->DB->FetchRow())
355  {
356  $Index = $Record[$this->ItemIdFieldName];
357  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
358  $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
359  }
360 
361  # find ID of first item in list
362  $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
363 
364  # if first item was found
365  if ($ItemId !== FALSE)
366  {
367  # traverse linked list to build list of item IDs
368  do
369  {
370  $ItemIds[] = $ItemId;
371  $ItemId = $NextItemIds[$ItemId];
372  }
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));
379  }
380  }
381 
382  # return list of item IDs to caller
383  return $ItemIds;
384  }
385 
392  function Remove($ItemId, $ItemType = NULL)
393  {
394  # retrieve item's "previous" pointer
395  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
396 
397  # bail out if item was not found
398  if ($CurrentItemPreviousId === FALSE) { return; }
399 
400  # retrieve item's "next" pointer
401  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
402  if ($this->ItemTypeFieldName)
403  {
404  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
405  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
406  $CurrentItemNextType = $CurrentItemNextId["Type"];
407  $CurrentItemNextId = $CurrentItemNextId["ID"];
408  }
409  else
410  {
411  $CurrentItemPreviousType = NULL;
412  $CurrentItemNextType = NULL;
413  }
414 
415  # if item was not first in list
416  if ($CurrentItemPreviousId >= 0)
417  {
418  # link previous item to item's current next item
419  $this->SetNextItemId(
420  $CurrentItemPreviousId, $CurrentItemPreviousType,
421  $CurrentItemNextId, $CurrentItemNextType);
422  }
423 
424  # if item was not last in list
425  if ($CurrentItemNextId >= 0)
426  {
427  # link next item to item's current previous item
428  $this->SetPreviousItemId(
429  $CurrentItemNextId, $CurrentItemNextType,
430  $CurrentItemPreviousId, $CurrentItemPreviousType);
431  }
432 
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);
437  }
438 
439 
440  # ---- PRIVATE INTERFACE -------------------------------------------------
441 
442  private $DB;
443  private $ItemTableName;
444  private $ItemIdFieldName;
445  private $ItemTypeFieldName;
446  private $SqlCondition = NULL;
447 
448  const UNINITIALIZED_ID = -1;
449  const LISTEND_ID = -2;
450 
451  # get ordering values (return FALSE if specified item not found)
452  private function GetPreviousItemId($ItemId, $ItemType)
453  {
454  if ($this->ItemTypeFieldName)
455  {
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)
461  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
462  if (!$this->DB->NumRowsSelected()) { return FALSE; }
463  $Row = $this->DB->FetchRow();
464  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
465  { return FALSE; }
466  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
467  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
468  return $ReturnValue;
469  }
470  else
471  {
472  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
473  ." FROM ".$this->ItemTableName
474  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
475  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
476  "Previous".$this->ItemIdFieldName);
477  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
478  }
479  }
480  private function GetNextItemId($ItemId, $ItemType)
481  {
482  if ($this->ItemTypeFieldName)
483  {
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)
489  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
490  if (!$this->DB->NumRowsSelected()) { return FALSE; }
491  $Row = $this->DB->FetchRow();
492  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
493  { return FALSE; }
494  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
495  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
496  return $ReturnValue;
497  }
498  else
499  {
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;
506  }
507  }
508 
509  # set ordering values
510  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
511  {
512  if ($this->ItemTypeFieldName)
513  {
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 : ""));
520  }
521  else
522  {
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 : ""));
527  }
528  }
529  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
530  {
531  if ($this->ItemTypeFieldName)
532  {
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 : ""));
539  }
540  else
541  {
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 : ""));
546  }
547  }
548  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
549  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
550  {
551  if ($this->ItemTypeFieldName)
552  {
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 : ""));
562  }
563  else
564  {
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 : ""));
570  }
571  }
572 }
573 
574 
575 ?>