CWIS Developer Documentation

- Home
- Main Page
- Classes
- Files

- File List
- File Members

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
21 class PersistentDoublyLinkedList {
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
Database
SQL database abstraction object with smart query caching.
Definition: Axis--Database.php:22
PersistentDoublyLinkedList\__construct
__construct($ItemTableName, $ItemIdFieldName, $SqlCondition=NULL, $ItemTypeFieldName=NULL)
Object constructor.
Definition: PersistentDoublyLinkedList.php:47
PersistentDoublyLinkedList\SqlCondition
SqlCondition($Condition=NULL)
Get or set/update SQL condition for referencing items in database.
Definition: PersistentDoublyLinkedList.php:71
PersistentDoublyLinkedList\UNINITIALIZED_ID
const UNINITIALIZED_ID
Definition: PersistentDoublyLinkedList.php:464
PersistentDoublyLinkedList\LISTEND_ID
const LISTEND_ID
Definition: PersistentDoublyLinkedList.php:465
PersistentDoublyLinkedList\Prepend
Prepend($ItemOrItemId, $ItemType=NULL)
Add item to beginning of list.
Definition: PersistentDoublyLinkedList.php:200
PersistentDoublyLinkedList\GetIds
GetIds()
Retrieve array of IDs of items in list, in the order that they appear in the list.
Definition: PersistentDoublyLinkedList.php:289
PersistentDoublyLinkedList\Remove
Remove($ItemId, $ItemType=NULL)
Remove item from list.
Definition: PersistentDoublyLinkedList.php:404
PHP
PHP
Definition: OAIClient.php:39
PersistentDoublyLinkedList\InsertBefore
InsertBefore($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list before specified item.
Definition: PersistentDoublyLinkedList.php:86
PersistentDoublyLinkedList\GetCount
GetCount()
Get number of items in list.
Definition: PersistentDoublyLinkedList.php:389
PersistentDoublyLinkedList\InsertAfter
InsertAfter($TargetItemOrItemId, $NewItemOrItemId, $TargetItemType=NULL, $NewItemType=NULL)
Insert item into list after specified item.
Definition: PersistentDoublyLinkedList.php:144
PersistentDoublyLinkedList
Persistent doubly-linked-list data structure, with its data stored in a specified database table...
Definition: PersistentDoublyLinkedList.php:21
PersistentDoublyLinkedList\Append
Append($ItemOrItemId, $ItemType=NULL)
Add item to end of list.
Definition: PersistentDoublyLinkedList.php:244