1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file idlist.h 26 * @brief Generic Real linked list. 27 */ 28 #ifndef _IDLIST_H_ 29 #define _IDLIST_H_ 30 31 #include <assert.h> 32 #include <stddef.h> 33 34 #include "soplex/spxdefines.h" 35 #include "soplex/islist.h" 36 37 namespace soplex 38 { 39 //--------------------------------------------------------------------- 40 // class IdElement<T> 41 //--------------------------------------------------------------------- 42 43 /**@brief Elements for \ref soplex::IdList "IdList"s. 44 @ingroup Elementary 45 46 #IdElement%s are derived from the template parameter class T and can hence 47 be used as such. The additional methods next() and prev() provide access 48 to the links for the list. They may freely be used by the programmer as long 49 as an IdElement is not member of a IdList. In this case, the IdList 50 controls members next() and prev(). However, IdList should provide 51 enough functionality for the user not to require any modification to these 52 members. 53 */ 54 /* The use of this->the_last and this->the_first instead of just the_last 55 * and the_first is bcause the HP aCC Compiler claims that according to the 56 * Standard these otherwise could not be seen. And since I was not able to 57 * even identify a hint on this in the Draft Standard we just do it, so 58 * the HP compiler is happy since it will not hurt the others. 59 */ 60 template < class T > 61 class IdElement : public T 62 { 63 //-------------------------- 64 /**@name Data */ 65 ///@{ 66 IdElement<T>* theprev; ///< pointer to previous element in the IdList 67 IdElement<T>* thenext; ///< pointer to next element in the IdList 68 ///@} 69 70 public: 71 72 //--------------------------------------- 73 /**@name Successors and predecessors */ 74 ///@{ 75 /// returns the next element in the IdList (writeable). 76 IdElement<T>*& next() 77 { 78 return thenext; 79 } 80 /// returns the next element in the IdList. 81 IdElement<T>* const& next() const 82 { 83 return thenext; 84 } 85 86 /// returns the previous element in the IdList (writeable). 87 IdElement<T>*& prev() 88 { 89 return theprev; 90 } 91 /// returns the previous element in the IdList. 92 IdElement<T>* const& prev() const 93 { 94 return theprev; 95 } 96 ///@} 97 98 //--------------------------------------- 99 /**@name Construction / destruction */ 100 ///@{ 101 /// default constructor. 102 IdElement() 103 : theprev(0) 104 , thenext(0) 105 {} 106 107 /// copy constructor. 108 /** Only the element itself is copied, while the links to the previous and 109 the next list element are set to zero pointers. 110 */ 111 IdElement(const T& old) 112 : T(old) 113 , theprev(0) 114 , thenext(0) 115 {} 116 }; 117 118 //--------------------------------------------------------------------- 119 // class IdList<T> 120 //--------------------------------------------------------------------- 121 122 123 /**@brief Generic Real linked list. 124 @ingroup Elementary 125 126 Class IdList implements an intrusive Real linked list as a template 127 class. As such, the list elements must provide the links themselfs. For 128 conveniance, we also provide class IdElement that adds both links to an 129 arbitrary class as template parameter. 130 */ 131 template < class T > 132 class IdList : public IsList<T> 133 { 134 public: 135 136 //--------------------------------------- 137 /**@name Access */ 138 ///@{ 139 /// returns first element in list. 140 T* first() const 141 { 142 return static_cast<T*>(this->the_first); 143 } 144 145 /// returns last element in list. 146 T* last() const 147 { 148 return static_cast<T*>(this->the_last); 149 } 150 151 /// returns successor of \p elem or 0, if \p elem is the last element. 152 T* next(const T* elem) const 153 { 154 return (elem == last()) ? 0 : elem->next(); 155 } 156 157 /// returns predecessor of \p elem or 0, if \p elem is the first element. 158 T* prev(const T* elem) const 159 { 160 return (elem == first()) ? 0 : elem->prev(); 161 } 162 ///@} 163 164 165 //--------------------------------------- 166 /**@name Extension */ 167 ///@{ 168 /// appends \p elem to end of list. 169 void append(T* elem) 170 { 171 if(last()) 172 { 173 last()->next() = elem; 174 elem->prev() = last(); 175 } 176 else 177 this->the_first = elem; 178 179 this->the_last = elem; 180 } 181 182 /// prepends \p elem at beginnig of list. 183 void prepend(T* elem) 184 { 185 if(first()) 186 { 187 elem->next() = first(); 188 first()->prev() = elem; 189 } 190 else 191 this->the_last = elem; 192 193 this->the_first = elem; 194 } 195 196 /// inserts \p elem after \p after. 197 void insert(T* elem, T* after) 198 { 199 assert(find(after)); 200 201 if(after == last()) 202 append(elem); 203 else 204 { 205 elem->next() = after->next(); 206 elem->prev() = after; 207 after->next() = elem->next()->prev() = elem; 208 } 209 } 210 211 /// appends \p list to end of list. 212 void append(IdList<T>& list) 213 { 214 if(list.first()) 215 { 216 append(list.first()); 217 this->the_last = list.last(); 218 } 219 } 220 221 /// prepends \p list at beginnig of list. 222 void prepend(IdList<T>& list) 223 { 224 if(list.first()) 225 { 226 prepend(list.last()); 227 this->the_first = list.the_first; 228 } 229 } 230 231 /// inserts \p list after \p after. 232 void insert(IdList<T>& list, T* after) 233 { 234 assert(find(after)); 235 236 if(list.first()) 237 { 238 list.last()->next() = after->next(); 239 list.first()->prev() = after; 240 after->next() = list.first(); 241 242 if(after == last()) 243 this->the_last = list.last(); 244 else 245 list.last()->next()->prev() = list.last(); 246 } 247 } 248 ///@} 249 250 //--------------------------------------- 251 /**@name Removal */ 252 ///@{ 253 /// removes element following \p after. 254 void remove_next(T* after) 255 { 256 remove(next(after)); 257 } 258 259 /// removes \p elem from list. 260 void remove(T* elem) 261 { 262 if(elem == first()) 263 { 264 this->the_first = next(elem); 265 266 if(first() == 0) 267 this->the_last = 0; 268 } 269 else if(elem == last()) 270 this->the_last = elem->prev(); 271 else 272 { 273 elem->next()->prev() = elem->prev(); 274 elem->prev()->next() = elem->next(); 275 } 276 } 277 278 /// removes sublist \p list. 279 void remove(IdList<T>& list) 280 { 281 if(first() != 0 && list.first() != 0) 282 { 283 assert(find(list.first())); 284 assert(find(list.last())); 285 286 if(first() == list.first()) 287 { 288 if(last() == list.last()) 289 this->the_first = this->the_last = 0; 290 else 291 this->the_first = list.last()->next(); 292 } 293 else if(last() == list.last()) 294 this->the_last = list.last()->prev(); 295 else 296 { 297 T* after = first(); 298 299 for(; after->next() != list.first(); after = after->next()) 300 ; 301 302 if(last() == list.last()) 303 this->the_last = after; 304 else 305 after->next() = list.last()->next(); 306 } 307 } 308 } 309 ///@} 310 311 //--------------------------------------- 312 /**@name Miscellaneous */ 313 ///@{ 314 /// adjusts list pointers to a new memory address. 315 /** When all elements have been moved in memory (e.g. because of 316 reallocation) with a fixed offset \p delta, the list will be reset 317 to the new adresses. 318 */ 319 void move(ptrdiff_t delta) 320 { 321 if(this->the_first) 322 { 323 T* elem; 324 IsList<T>::move(delta); 325 326 for(elem = last(); elem; elem = prev(elem)) 327 if(elem != first()) 328 elem->prev() = reinterpret_cast<T*>( 329 reinterpret_cast<char*>(elem->prev()) + delta); 330 } 331 } 332 333 /// consistency check. 334 bool isConsistent() const 335 { 336 #ifdef ENABLE_CONSISTENCY_CHECKS 337 const T* my_first = first(); 338 const T* my_last = last(); 339 340 for(const T* it = my_first; it; it = next(it)) 341 { 342 if(it != my_first && it->prev()->next() != it) 343 return SPX_MSG_INCONSISTENT("IdList"); 344 345 if(it != my_last && it->next()->prev() != it) 346 return SPX_MSG_INCONSISTENT("IdList"); 347 } 348 349 return IsList<T>::isConsistent(); 350 #else 351 return true; 352 #endif 353 } 354 ///@} 355 356 //--------------------------------------- 357 /**@name Constructors / Destructors */ 358 ///@{ 359 /// default constructor. 360 /** The default constructor may also be used to construct a sublist, by 361 providing a \p first and a \p last element. Element \p last must be a 362 successor of \p first. 363 */ 364 explicit 365 IdList(T* pfirst = 0, T* plast = 0, bool pDestroyElements = false) 366 : IsList<T>(pfirst, plast, pDestroyElements) 367 { 368 assert(isConsistent()); 369 } 370 ///@} 371 }; 372 373 } // namespace soplex 374 #endif // _IDLIST_H_ 375