DoublyLinkedItemList.php
Go to the documentation of this file.
00001 <?PHP 00002 00003 # 00004 # FILE: SPT--DoublyLinkedList.php 00005 # 00006 # METHODS PROVIDED: 00007 # DoublyLinkedList() 00008 # - constructor 00009 # SomeMethod($SomeParameter, $AnotherParameter) 00010 # - short description of method 00011 # 00012 # AUTHOR: 00013 # 00014 # Part of the Scout Portal Toolkit 00015 # Copyright 2007 Internet Scout 00016 # http://scout.wisc.edu 00017 # 00018 00019 class DoublyLinkedItemList { 00020 00021 # ---- PUBLIC INTERFACE -------------------------------------------------- 00022 00023 # object constructor 00024 function DoublyLinkedItemList( 00025 $ItemTableName, $ItemIdFieldName, $SqlCondition = NULL) 00026 { 00027 # grab our own database handle 00028 $this->DB = new SPTDatabase(); 00029 00030 # save configuration 00031 $this->ItemIdFieldName = $ItemIdFieldName; 00032 $this->ItemTableName = $ItemTableName; 00033 $this->SqlCondition($SqlCondition); 00034 } 00035 00036 # insert/move item to before specified item 00037 function InsertBefore($SourceItemOrItemId, $TargetItemOrItemId) 00038 { 00039 # retrieve item IDs 00040 $SourceItemId = is_object($SourceItemOrItemId) 00041 ? $SourceItemOrItemId->Id() : $SourceItemOrItemId; 00042 $TargetItemId = is_object($TargetItemOrItemId) 00043 ? $TargetItemOrItemId->Id() : $TargetItemOrItemId; 00044 00045 # remove source item from current position if necessary 00046 $this->Remove($SourceItemId); 00047 00048 # update IDs to link in new item 00049 $CurrentTargetItemPreviousId = $this->GetPreviousItemId($TargetItemId); 00050 $this->SetPreviousItemId($TargetItemId, $SourceItemId); 00051 if ($CurrentTargetItemPreviousId != -1) 00052 { 00053 $this->SetNextItemId($CurrentTargetItemPreviousId, $SourceItemId); 00054 } 00055 $this->SetPreviousAndNextItemIds($SourceItemId, 00056 $CurrentTargetItemPreviousId, $TargetItemId); 00057 } 00058 00059 # insert/move item to after specified item 00060 function InsertAfter($SourceItemOrItemId, $TargetItemOrItemId) 00061 { 00062 # retrieve item IDs 00063 $SourceItemId = is_object($SourceItemOrItemId) 00064 ? $SourceItemOrItemId->Id() : $SourceItemOrItemId; 00065 $TargetItemId = is_object($TargetItemOrTargetItemId) 00066 ? $TargetItemOrTargetItemId->Id() : $TargetItemOrTargetItemId; 00067 00068 # remove source item from current position if necessary 00069 $this->Remove($SourceItemId); 00070 00071 # update IDs to link in new item 00072 $CurrentTargetItemNextId = $this->GetNextItemIdInOrder($TargetItemId); 00073 $this->SetNextItemId($TargetItemId, $SourceItemId); 00074 if ($CurrentTargetItemNextId != -1) 00075 { 00076 $this->SetPreviousItemId($CurrentTargetItemNextId, $SourceItemId); 00077 } 00078 $this->SetPreviousAndNextItemIds($SourceItemId, 00079 $TargetItemId, $CurrentTargetItemNextId); 00080 } 00081 00082 # add/move item to beginning of list 00083 function Prepend($ItemOrItemId) 00084 { 00085 # get item ID 00086 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId; 00087 00088 # remove new item from current position if necessary 00089 $this->Remove($ItemId); 00090 00091 # if there are items currently in list 00092 $ItemIds = $this->GetIds(FALSE); 00093 if (count($ItemIds)) 00094 { 00095 # link last item to source item 00096 $FirstItemId = array_shift($ItemIds); 00097 $this->SetPreviousItemId($FirstItemId, $ItemId); 00098 $this->SetPreviousAndNextItemIds($ItemId, -1, $FirstItemId); 00099 } 00100 else 00101 { 00102 # add item to list as only item 00103 $this->SetPreviousAndNextItemIds($ItemId, -1, -1); 00104 } 00105 } 00106 00107 # add/move item to end of list 00108 function Append($ItemOrItemId) 00109 { 00110 # get item ID 00111 $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId; 00112 00113 # remove item from current position if necessary 00114 $this->Remove($ItemId); 00115 00116 # if there are items currently in list 00117 $ItemIds = $this->GetIds(FALSE); 00118 if (count($ItemIds)) 00119 { 00120 # link last item to source item 00121 $LastItemId = array_pop($ItemIds); 00122 $this->SetNextItemId($LastItemId, $ItemId); 00123 $this->SetPreviousAndNextItemIds($ItemId, $LastItemId, -1); 00124 } 00125 else 00126 { 00127 # add item to list as only item 00128 $this->SetPreviousAndNextItemIds($ItemId, -1, -1); 00129 } 00130 } 00131 00132 # retrieve list of item IDs in order 00133 function GetIds($AddStrayItemsToOrder = TRUE) 00134 { 00135 # retrieve ordering IDs 00136 $this->DB->Query("SELECT ".$this->ItemIdFieldName 00137 .", Previous".$this->ItemIdFieldName 00138 .", Next".$this->ItemIdFieldName 00139 ." FROM ".$this->ItemTableName 00140 .$this->GetCondition(TRUE) 00141 ." ORDER BY ".$this->ItemIdFieldName." ASC"); 00142 $PreviousItemIds = array(); 00143 $NextItemIds = array(); 00144 while ($Record = $this->DB->FetchRow()) 00145 { 00146 $ItemId = intval($Record[$this->ItemIdFieldName]); 00147 $PreviousItemIds[$ItemId] = 00148 intval($Record["Previous".$this->ItemIdFieldName]); 00149 $NextItemIds[$ItemId] = intval($Record["Next".$this->ItemIdFieldName]); 00150 } 00151 00152 # pull unordered items out of list 00153 $StrayItemIds = array_keys($PreviousItemIds, -2); 00154 foreach ($StrayItemIds as $StrayItemId) 00155 { 00156 unset($PreviousItemIds[$StrayItemId]); 00157 unset($NextItemIds[$StrayItemId]); 00158 } 00159 00160 # find first item 00161 $ItemId = array_search(-1, $PreviousItemIds); 00162 00163 # if first item was found 00164 $ItemIds = array(); 00165 if ($ItemId !== FALSE) 00166 { 00167 # traverse linked list to build list of item IDs 00168 do 00169 { 00170 $ItemIds[] = $ItemId; 00171 unset($PreviousItemIds[$ItemId]); 00172 if (isset($NextItemIds[$ItemId])) { $ItemId = $NextItemIds[$ItemId]; } 00173 } 00174 while (isset($NextItemIds[$ItemId]) && ($ItemId != -1) 00175 && !in_array($ItemId, $ItemIds)); 00176 00177 # add any items left over to stray items list 00178 $StrayItemIds = array_unique($StrayItemIds + array_keys($PreviousItemIds)); 00179 } 00180 00181 # add any stray items to end of list (if so configured) 00182 if ($AddStrayItemsToOrder) 00183 { 00184 foreach ($StrayItemIds as $StrayItemId) 00185 { 00186 $this->Append($StrayItemId); 00187 $ItemIds[] = $StrayItemId; 00188 } 00189 } 00190 00191 # return list of item IDs to caller 00192 return $ItemIds; 00193 } 00194 00195 # remove item from existing order 00196 function Remove($ItemId) 00197 { 00198 $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId); 00199 $CurrentItemNextId = $this->GetNextItemIdInOrder($ItemId); 00200 if ($CurrentItemPreviousId >= 0) 00201 { 00202 $this->SetNextItemId( 00203 $CurrentItemPreviousId, $CurrentItemNextId); 00204 } 00205 if ($CurrentItemNextId >= 0) 00206 { 00207 $this->SetPreviousItemId( 00208 $CurrentItemNextId, $CurrentItemPreviousId); 00209 } 00210 } 00211 00212 # set SQL condition for ordering operations 00213 # (use NULL to clear condition) 00214 function SqlCondition($NewCondition) 00215 { 00216 $this->Condition = $NewCondition; 00217 } 00218 00219 00220 # ---- PRIVATE INTERFACE ------------------------------------------------- 00221 00222 var $DB; 00223 var $ItemIdFieldName; 00224 var $ItemTableName; 00225 var $Condition; 00226 00227 # get/set ordering values 00228 function GetPreviousItemId($ItemId) 00229 { 00230 return $this->DB->Query("SELECT Previous".$this->ItemIdFieldName 00231 ." FROM ".$this->ItemTableName 00232 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId) 00233 .$this->GetCondition(), 00234 "Previous".$this->ItemIdFieldName); 00235 } 00236 function GetNextItemIdInOrder($ItemId) 00237 { 00238 return $this->DB->Query("SELECT Next".$this->ItemIdFieldName 00239 ." FROM ".$this->ItemTableName 00240 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId) 00241 .$this->GetCondition(), 00242 "Next".$this->ItemIdFieldName); 00243 } 00244 function SetPreviousItemId($ItemId, $NewValue) 00245 { 00246 $this->DB->Query("UPDATE ".$this->ItemTableName 00247 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewValue) 00248 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId) 00249 .$this->GetCondition()); 00250 } 00251 function SetNextItemId($ItemId, $NewValue) 00252 { 00253 $this->DB->Query("UPDATE ".$this->ItemTableName 00254 ." SET Next".$this->ItemIdFieldName." = ".intval($NewValue) 00255 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId) 00256 .$this->GetCondition()); 00257 } 00258 function SetPreviousAndNextItemIds($ItemId, $NewPreviousId, $NewNextId) 00259 { 00260 $this->DB->Query("UPDATE ".$this->ItemTableName 00261 ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId) 00262 .", Next".$this->ItemIdFieldName." = ".intval($NewNextId) 00263 ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId) 00264 .$this->GetCondition()); 00265 } 00266 00267 # return DB query condition (if any) with proper additional syntax 00268 function GetCondition($ThisIsOnlyCondition = FALSE) 00269 { 00270 return $this->Condition ? 00271 ($ThisIsOnlyCondition ? " WHERE " : " AND ").$this->Condition 00272 : ""; 00273 } 00274 } 00275 00276 00277 ?>