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 
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 
69  function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
70  $TargetItemType = NULL, $NewItemType = NULL)
71  {
72  # retrieve item IDs
73  $NewItemId = is_object($NewItemOrItemId)
74  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
75  $TargetItemId = is_object($TargetItemOrItemId)
76  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
77 
78  # remove source item from current position if necessary
79  $this->Remove($NewItemId);
80 
81  # retrieve current previous item pointer for target item
82  $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
83  $TargetItemId, $TargetItemType);
84 
85  # if target item not found
86  if ($TargetItemCurrentPreviousId === FALSE)
87  {
88  # add new item to beginning of list
89  $this->Prepend($NewItemId, $NewItemType);
90  }
91  else
92  {
93  # retrieve target item type if available
94  if (is_array($TargetItemCurrentPreviousId))
95  {
96  $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
97  $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
98  }
99  else
100  {
101  $TargetItemCurrentPreviousType = NULL;
102  }
103 
104  # update IDs to link in new item
105  $this->SetPreviousItemId(
106  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
107  if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
108  {
109  $this->SetNextItemId($TargetItemCurrentPreviousId,
110  $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
111  }
112  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
113  $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
114  $TargetItemId, $TargetItemType);
115  }
116  }
117 
127  function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
128  $TargetItemType = NULL, $NewItemType = NULL)
129  {
130  # retrieve item IDs
131  $NewItemId = is_object($NewItemOrItemId)
132  ? $NewItemOrItemId->Id() : $NewItemOrItemId;
133  $TargetItemId = is_object($TargetItemOrItemId)
134  ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;
135 
136  # remove new item from existing position (if necessary)
137  $this->Remove($NewItemId, $NewItemType);
138 
139  # retrieve current next item pointer for target item
140  $TargetItemCurrentNextId = $this->GetNextItemId(
141  $TargetItemId, $TargetItemType);
142 
143  # if target item not found
144  if ($TargetItemCurrentNextId === FALSE)
145  {
146  # add new item to end of list
147  $this->Append($NewItemId, $NewItemType);
148  }
149  else
150  {
151  # retrieve target item type if available
152  if (is_array($TargetItemCurrentNextId))
153  {
154  $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
155  $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
156  }
157  else
158  {
159  $TargetItemCurrentNextType = NULL;
160  }
161 
162  # update IDs to link in new item
163  $this->SetNextItemId(
164  $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
165  if ($TargetItemCurrentNextId != self::LISTEND_ID)
166  {
167  $this->SetPreviousItemId(
168  $TargetItemCurrentNextId, $TargetItemCurrentNextType,
169  $NewItemId, $NewItemType);
170  }
171  $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
172  $TargetItemId, $TargetItemType,
173  $TargetItemCurrentNextId, $TargetItemCurrentNextType);
174  }
175  }
176 
183  function Prepend($ItemOrItemId, $ItemType = NULL)
184  {
185  # get item ID
186  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
187 
188  # remove new item from current position if necessary
189  $this->Remove($ItemId, $ItemType);
190 
191  # if there are items currently in list
192  $ItemIds = $this->GetIds(FALSE);
193  if (count($ItemIds))
194  {
195  # link first item to source item
196  if ($this->ItemTypeFieldName)
197  {
198  $Row = array_shift($ItemIds);
199  $FirstItemId = $Row["ID"];
200  $FirstItemType = $Row["Type"];
201  }
202  else
203  {
204  $FirstItemId = array_shift($ItemIds);
205  $FirstItemType = NULL;
206  }
207 
208  $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
209  $this->SetPreviousAndNextItemIds(
210  $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
211  $FirstItemId, $FirstItemType);
212  }
213  else
214  {
215  # add item to list as only item
216  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
217  self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID);
218  }
219  }
220 
227  function Append($ItemOrItemId, $ItemType = NULL)
228  {
229  # get item ID
230  $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;
231 
232  # remove item from current position if necessary
233  $this->Remove($ItemId, $ItemType);
234 
235  # if there are items currently in list
236  $ItemIds = $this->GetIds();
237  if (count($ItemIds))
238  {
239  # link last item to source item
240  if ($this->ItemTypeFieldName)
241  {
242  $Row = array_pop($ItemIds);
243  $LastItemId = $Row["ID"];
244  $LastItemType = $Row["Type"];
245  }
246  else
247  {
248  $LastItemId = array_pop($ItemIds);
249  $LastItemType = NULL;
250  }
251  $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
252  $this->SetPreviousAndNextItemIds(
253  $ItemId, $ItemType, $LastItemId, $LastItemType,
254  self::LISTEND_ID, self::LISTEND_ID);
255  }
256  else
257  {
258  # add item to list as only item
259  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
260  self::LISTEND_ID, self::LISTEND_ID,
261  self::LISTEND_ID, self::LISTEND_ID);
262  }
263  }
264 
272  function GetIds()
273  {
274  # assume no items will be found in folder
275  $ItemIds = array();
276 
277  # if item types are in use
278  if ($this->ItemTypeFieldName)
279  {
280  # retrieve IDs and types of all items in list and links between items
281  $this->DB->Query("SELECT * FROM ".$this->ItemTableName
282  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
283  ." ORDER BY ".$this->ItemIdFieldName." ASC");
284 
285  # build up lists of next and previous item pointers
286  $PreviousItemIds = array();
287  $NextItemIds = array();
288  while ($Record = $this->DB->FetchRow())
289  {
290  $Index = $Record[$this->ItemTypeFieldName]
291  .":".$Record[$this->ItemIdFieldName];
292  $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
293  $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
294  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemTypeFieldName]
295  .":".$Record["Previous".$this->ItemIdFieldName];
296  $NextItemIds[$Index] = $Record["Next".$this->ItemTypeFieldName]
297  .":".$Record["Next".$this->ItemIdFieldName];
298  }
299 
300  # find ID of first item in list
301  $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
302  $Index = array_search($ListEndIndex, $PreviousItemIds);
303 
304  # if first item was found
305  if ($Index !== FALSE)
306  {
307  # traverse linked list to build list of item types and IDs
308  do
309  {
310  $ItemIds[$Index] = array(
311  "Type" => $KnownItemTypes[$Index],
312  "ID" => $KnownItemIds[$Index]);
313  $Index = $NextItemIds[$Index];
314  }
315  # (stop if we've reached the end of the list)
316  while (($Index != $ListEndIndex)
317  # (stop if link points to item not in list)
318  && array_key_exists($Index, $NextItemIds)
319  # (stop if link is circular)
320  && !array_key_exists($Index, $ItemIds));
321  }
322  }
323  else
324  {
325  # retrieve IDs of all items in list and links between items
326  $this->DB->Query("SELECT ".$this->ItemIdFieldName
327  .", Previous".$this->ItemIdFieldName
328  .", Next".$this->ItemIdFieldName
329  ." FROM ".$this->ItemTableName
330  .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
331  ." ORDER BY ".$this->ItemIdFieldName." ASC");
332 
333  # build up lists of next item pointers
334  $PreviousItemIds = array();
335  $NextItemIds = array();
336  while ($Record = $this->DB->FetchRow())
337  {
338  $Index = $Record[$this->ItemIdFieldName];
339  $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
340  $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
341  }
342 
343  # find ID of first item in list
344  $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);
345 
346  # if first item was found
347  if ($ItemId !== FALSE)
348  {
349  # traverse linked list to build list of item IDs
350  do
351  {
352  $ItemIds[] = $ItemId;
353  $ItemId = $NextItemIds[$ItemId];
354  }
355  # (stop if we've reached the end of the list)
356  while (($ItemId != self::LISTEND_ID)
357  # (stop if link points to item not in list)
358  && array_key_exists($ItemId, $NextItemIds)
359  # (stop if link is circular)
360  && !in_array($ItemId, $ItemIds));
361  }
362  }
363 
364  # return list of item IDs to caller
365  return $ItemIds;
366  }
367 
374  function Remove($ItemId, $ItemType = NULL)
375  {
376  # retrieve item's "previous" pointer
377  $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);
378 
379  # bail out if item was not found
380  if ($CurrentItemPreviousId === FALSE) { return; }
381 
382  # retrieve item's "next" pointer
383  $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
384  if ($this->ItemTypeFieldName)
385  {
386  $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
387  $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
388  $CurrentItemNextType = $CurrentItemNextId["Type"];
389  $CurrentItemNextId = $CurrentItemNextId["ID"];
390  }
391  else
392  {
393  $CurrentItemPreviousType = NULL;
394  $CurrentItemNextType = NULL;
395  }
396 
397  # if item was not first in list
398  if ($CurrentItemPreviousId >= 0)
399  {
400  # link previous item to item's current next item
401  $this->SetNextItemId(
402  $CurrentItemPreviousId, $CurrentItemPreviousType,
403  $CurrentItemNextId, $CurrentItemNextType);
404  }
405 
406  # if item was not last in list
407  if ($CurrentItemNextId >= 0)
408  {
409  # link next item to item's current previous item
410  $this->SetPreviousItemId(
411  $CurrentItemNextId, $CurrentItemNextType,
412  $CurrentItemPreviousId, $CurrentItemPreviousType);
413  }
414 
415  # set items pointers to indicate it is not part of a list
416  $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
417  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
418  self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
419  }
420 
421 
422  # ---- PRIVATE INTERFACE -------------------------------------------------
423 
424  private $DB;
425  private $ItemTableName;
426  private $ItemIdFieldName;
427  private $ItemTypeFieldName;
428  private $SqlCondition;
429 
430  const UNINITIALIZED_ID = -1;
431  const LISTEND_ID = -2;
432 
433  # get ordering values (return FALSE if specified item not found)
434  private function GetPreviousItemId($ItemId, $ItemType)
435  {
436  if ($this->ItemTypeFieldName)
437  {
438  $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
439  .", Previous".$this->ItemTypeFieldName
440  ." FROM ".$this->ItemTableName
441  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
442  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
443  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
444  if (!$this->DB->NumRowsSelected()) { return FALSE; }
445  $Row = $this->DB->FetchRow();
446  if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
447  { return FALSE; }
448  $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
449  $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
450  return $ReturnValue;
451  }
452  else
453  {
454  $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
455  ." FROM ".$this->ItemTableName
456  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
457  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
458  "Previous".$this->ItemIdFieldName);
459  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
460  }
461  }
462  private function GetNextItemId($ItemId, $ItemType)
463  {
464  if ($this->ItemTypeFieldName)
465  {
466  $this->DB->Query("SELECT Next".$this->ItemIdFieldName
467  .", Next".$this->ItemTypeFieldName
468  ." FROM ".$this->ItemTableName
469  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
470  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
471  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
472  if (!$this->DB->NumRowsSelected()) { return FALSE; }
473  $Row = $this->DB->FetchRow();
474  if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
475  { return FALSE; }
476  $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
477  $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
478  return $ReturnValue;
479  }
480  else
481  {
482  $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
483  ." FROM ".$this->ItemTableName
484  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
485  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
486  "Next".$this->ItemIdFieldName);
487  return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
488  }
489  }
490 
491  # set ordering values
492  private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
493  {
494  if ($this->ItemTypeFieldName)
495  {
496  $this->DB->Query("UPDATE ".$this->ItemTableName
497  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
498  .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
499  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
500  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
501  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
502  }
503  else
504  {
505  $this->DB->Query("UPDATE ".$this->ItemTableName
506  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
507  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
508  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
509  }
510  }
511  private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
512  {
513  if ($this->ItemTypeFieldName)
514  {
515  $this->DB->Query("UPDATE ".$this->ItemTableName
516  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
517  .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
518  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
519  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
520  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
521  }
522  else
523  {
524  $this->DB->Query("UPDATE ".$this->ItemTableName
525  ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
526  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
527  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
528  }
529  }
530  private function SetPreviousAndNextItemIds($ItemId, $ItemType,
531  $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
532  {
533  if ($this->ItemTypeFieldName)
534  {
535  $this->DB->Query("UPDATE ".$this->ItemTableName
536  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
537  .", Previous".$this->ItemTypeFieldName." = "
538  .intval($NewPreviousType)
539  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
540  .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
541  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
542  ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
543  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
544  }
545  else
546  {
547  $this->DB->Query("UPDATE ".$this->ItemTableName
548  ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
549  .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
550  ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
551  .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
552  }
553  }
554 }
555 
556 
557 ?>