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 ?>