timeline.h
Go to the documentation of this file.00001 /*************************************************************************** 00002 file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/include/frepple/timeline.h $ 00003 version : $LastChangedRevision: 1317 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2010-07-20 22:03:36 +0200 (Tue, 20 Jul 2010) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2010 by Johan De Taeye * 00010 * * 00011 * This library is free software; you can redistribute it and/or modify it * 00012 * under the terms of the GNU Lesser General Public License as published * 00013 * by the Free Software Foundation; either version 2.1 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser * 00019 * General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Lesser General Public * 00022 * License along with this library; if not, write to the Free Software * 00023 * Foundation Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,* 00024 * USA * 00025 * * 00026 ***************************************************************************/ 00027 00028 #ifndef TIMELINE 00029 #define TIMELINE 00030 00031 #ifndef DOXYGEN 00032 #include <cmath> 00033 #endif 00034 00035 namespace frepple 00036 { 00037 namespace utils 00038 { 00039 00040 /** @brief This class implements a "sorted list" data structure, sorting 00041 * "events" based on a date. 00042 * 00043 * The data structure has slow insert scalability: O(n)<br> 00044 * Moving data around in the structure is efficient though: O(1)<br> 00045 * The class leverages the STL library and also follows its api.<br> 00046 * The class used to instantiate a timeline must support the 00047 * "bool operator < (TYPE)". 00048 * 00049 * Note that the events store the quantity but NOT the date. We pick up 00050 * the date from the template type. The reasoning for this choice is that 00051 * the quantity requires more computation than the date and is worthwhile 00052 * caching. The date field can be read efficiently from the parent type. 00053 */ 00054 template <class type> class TimeLine 00055 { 00056 friend class Event; 00057 public: 00058 class iterator; 00059 class const_iterator; 00060 /** @brief Base class for nodes in the timeline. */ 00061 class Event : public NonCopyable 00062 { 00063 friend class TimeLine<type>; 00064 friend class const_iterator; 00065 friend class iterator; 00066 protected: 00067 Date dt; 00068 double oh; 00069 double cum_prod; 00070 Event* next; 00071 Event* prev; 00072 Event() : oh(0), cum_prod(0), next(NULL), prev(NULL) {}; 00073 00074 public: 00075 virtual ~Event() {}; 00076 virtual double getQuantity() const {return 0.0;} 00077 00078 /** Return the current onhand value. */ 00079 double getOnhand() const {return oh;} 00080 00081 /** Return the total produced quantity till the current date. */ 00082 double getCumulativeProduced() const {return cum_prod;} 00083 00084 /** Return the total consumed quantity till the current date. */ 00085 double getCumulativeConsumed() const {return cum_prod - oh;} 00086 00087 /** Return the date of the event. */ 00088 const Date& getDate() const {return dt;} 00089 00090 /** Return a pointer to the owning timeline. */ 00091 virtual TimeLine<type>* getTimeLine() const {return NULL;} 00092 00093 /** This functions returns the mimimum boundary valid at the time of 00094 * this event. */ 00095 virtual double getMin(bool inclusive = true) const 00096 { 00097 assert(this->getTimeLine()); 00098 EventMinQuantity *m = this->getTimeLine()->lastMin; 00099 if (inclusive) 00100 while(m && getDate() < m->getDate()) m = m->prevMin; 00101 else 00102 while(m && getDate() <= m->getDate()) m = m->prevMin; 00103 return m ? m->newMin : 0.0; 00104 } 00105 00106 /** This functions returns the maximum boundary valid at the time of 00107 * this event. */ 00108 virtual double getMax(bool inclusive = true) const 00109 { 00110 assert(this->getTimeLine()); 00111 EventMaxQuantity *m = this->getTimeLine()->lastMax; 00112 if (inclusive) 00113 while(m && getDate() < m->getDate()) m = m->prevMax; 00114 else 00115 while(m && getDate() <= m->getDate()) m = m->prevMax; 00116 return m ? m->newMax : 0.0; 00117 } 00118 00119 virtual unsigned short getType() const = 0; 00120 00121 /** First criterion is date: earlier dates come first.<br> 00122 * Second criterion is the size: big events come first.<br> 00123 * As a third tie-breaking criterion, we use a pointer comparison.<br> 00124 * This garantuees us a fixed and unambiguous ordering.<br> 00125 * As a side effect, this makes sure that producers come before 00126 * consumers. This feature is required to avoid zero-time 00127 * material shortages. 00128 */ 00129 bool operator < (const Event& fl2) const 00130 { 00131 assert (&fl2); 00132 if (getDate() != fl2.getDate()) 00133 return getDate() < fl2.getDate(); 00134 else if (fabs(getQuantity() - fl2.getQuantity()) > ROUNDING_ERROR) 00135 return getQuantity() > fl2.getQuantity(); 00136 else 00137 return this < &fl2; 00138 } 00139 }; 00140 00141 /** @brief A timeline event representing a change of the current value. */ 00142 class EventChangeOnhand : public Event 00143 { 00144 friend class TimeLine<type>; 00145 private: 00146 double quantity; 00147 public: 00148 double getQuantity() const {return quantity;} 00149 EventChangeOnhand(double qty = 0.0) : quantity(qty) {} 00150 virtual unsigned short getType() const {return 1;} 00151 }; 00152 00153 /** @brief A timeline event representing a change of the minimum target. */ 00154 class EventMinQuantity : public Event 00155 { 00156 friend class TimeLine<type>; 00157 friend class Event; 00158 private: 00159 double newMin; 00160 protected: 00161 EventMinQuantity *prevMin; 00162 public: 00163 EventMinQuantity(Date d, double f=0.0) : newMin(f), prevMin(NULL) 00164 {this->dt = d;} 00165 void setMin(double f) {newMin = f;} 00166 virtual double getMin(bool inclusive = true) const 00167 { 00168 if (inclusive) return newMin; 00169 else return prevMin ? prevMin->newMin : 0.0; 00170 } 00171 virtual unsigned short getType() const {return 3;} 00172 }; 00173 00174 /** @brief A timeline event representing a change of the maximum target. */ 00175 class EventMaxQuantity : public Event 00176 { 00177 friend class Event; 00178 friend class TimeLine<type>; 00179 private: 00180 double newMax; 00181 protected: 00182 EventMaxQuantity *prevMax; 00183 public: 00184 EventMaxQuantity(Date d, double f=0.0) : newMax(f), prevMax(NULL) 00185 {this->dt = d;} 00186 void setMax(double f) {newMax = f;} 00187 virtual double getMax(bool inclusive = true) const 00188 { 00189 if (inclusive) return newMax; 00190 else return prevMax ? prevMax->newMax : 0.0; 00191 } 00192 virtual unsigned short getType() const {return 4;} 00193 }; 00194 00195 /** @brief This is bi-directional iterator through the timeline. 00196 * 00197 * It looks a bit STL-compliant, but this is only superficially. The 00198 * class doesn't meet all requirements for a full STL-compliant 00199 * iterator. 00200 * @todo Make the timeline iterators fully STL compliant. 00201 */ 00202 class const_iterator 00203 { 00204 protected: 00205 const Event* cur; 00206 public: 00207 const_iterator() {} 00208 const_iterator(const Event* e) : cur(e) {}; 00209 const_iterator(const iterator& c) : cur(c.cur) {} 00210 const Event& operator*() const {return *cur;} 00211 const Event* operator->() const {return cur;} 00212 const_iterator& operator++() {cur = cur->next; return *this;} 00213 const_iterator operator++(int) 00214 {const_iterator tmp = *this; ++*this; return tmp;} 00215 const_iterator& operator--() {cur = cur->prev; return *this;} 00216 const_iterator operator--(int) 00217 {const_iterator tmp = *this; --*this; return tmp;} 00218 bool operator==(const const_iterator& x) const {return cur == x.cur;} 00219 bool operator!=(const const_iterator& x) const {return cur != x.cur;} 00220 }; 00221 00222 /** @brief This is bi-directional iterator through the timeline. */ 00223 class iterator : public const_iterator 00224 { 00225 public: 00226 iterator() {} 00227 iterator(Event* e) : const_iterator(e) {}; 00228 Event& operator*() const {return *const_cast<Event*>(this->cur);} 00229 Event* operator->() const {return const_cast<Event*>(this->cur);} 00230 iterator& operator++() {this->cur = this->cur->next; return *this;} 00231 iterator operator++(int) {iterator tmp = *this; ++*this; return tmp;} 00232 iterator& operator--() {this->cur = this->cur->prev; return *this;} 00233 iterator operator--(int) {iterator tmp = *this; --*this; return tmp;} 00234 bool operator==(const iterator& x) const {return this->cur == x.cur;} 00235 bool operator!=(const iterator& x) const {return this->cur != x.cur;} 00236 }; 00237 00238 TimeLine() : first(NULL), last(NULL), lastMax(NULL), lastMin(NULL) {} 00239 int size() const 00240 { 00241 int cnt(0); 00242 for (Event* p=first; p; p=p->next) ++cnt; 00243 return cnt; 00244 } 00245 iterator begin() {return iterator(first);} 00246 iterator begin(Event* e) {return iterator(e);} 00247 iterator rbegin() {return iterator(last);} 00248 iterator end() {return iterator(NULL);} 00249 const_iterator begin() const {return const_iterator(first);} 00250 const_iterator begin(const Event* e) const {return const_iterator(e);} 00251 const_iterator rbegin() const {return const_iterator(last);} 00252 const_iterator end() const {return const_iterator(NULL);} 00253 bool empty() const {return first==NULL;} 00254 void insert(Event*); 00255 void insert(EventChangeOnhand* e, double qty, const Date& d) 00256 { 00257 e->quantity = qty; 00258 e->dt = d; 00259 insert(static_cast<Event*>(e)); 00260 }; 00261 void erase(Event*); 00262 void update(EventChangeOnhand*, double, const Date&); 00263 00264 /** This function is used for debugging purposes.<br> 00265 * It prints a header line, followed by the date, quantity and on_hand 00266 * of all events in the timeline. 00267 */ 00268 void inspect(const string& name) const 00269 { 00270 logger << "Inspecting " << this << ": \"" << name << "\":" << endl; 00271 for (const_iterator oo=begin(); oo!=end(); ++oo) 00272 logger << " " << oo->getDate() << " " 00273 << oo->getQuantity() << " " << oo->getOnhand() 00274 << " " << oo->getCumulativeProduced() << &*oo << endl; 00275 } 00276 00277 /** This functions returns the mimimum valid at a certain date. */ 00278 virtual double getMin(Date d, bool inclusive = true) const 00279 { 00280 EventMinQuantity *m = this->lastMin; 00281 if (inclusive) 00282 while(m && d < m->getDate()) m = m->prevMin; 00283 else 00284 while(m && d <= m->getDate()) m = m->prevMin; 00285 return m ? m->getMin() : 0.0; 00286 } 00287 00288 /** This functions returns the mimimum valid at a certain event. */ 00289 virtual double getMin(const Event *e, bool inclusive = true) const 00290 { 00291 if (!e) return 0.0; 00292 EventMinQuantity *m = this->lastMin; 00293 if (inclusive) 00294 while(m && e->getDate() < m->getDate()) m = m->prevMin; 00295 else 00296 while(m && e->getDate() <= m->getDate()) m = m->prevMin; 00297 return m ? m->getMin() : 0.0; 00298 } 00299 00300 /** This functions returns the maximum valid at a certain date. */ 00301 virtual double getMax(Date d, bool inclusive = true) const 00302 { 00303 EventMaxQuantity *m = this->lastMax; 00304 if (inclusive) 00305 while(m && d < m->getDate()) m = m->prevMax; 00306 else 00307 while(m && d <= m->getDate()) m = m->prevMax; 00308 return m ? m->getMax() : 0.0; 00309 } 00310 00311 /** This functions returns the mimimum valid at a certain eveny. */ 00312 virtual double getMax(const Event *e, bool inclusive = true) const 00313 { 00314 if (!e) return 0.0; 00315 EventMaxQuantity *m = this->lastMax; 00316 if (inclusive) 00317 while(m && e->getDate() < m->getDate()) m = m->prevMax; 00318 else 00319 while(m && e->getDate() <= m->getDate()) m = m->prevMax; 00320 return m ? m->getMax() : 0.0; 00321 } 00322 00323 /** This functions returns the mimimum event valid at a certain date. */ 00324 virtual EventMinQuantity* getMinEvent(Date d, bool inclusive = true) const 00325 { 00326 EventMinQuantity *m = this->lastMin; 00327 if (inclusive) 00328 while(m && d < m->getDate()) m = m->prevMin; 00329 else 00330 while(m && d <= m->getDate()) m = m->prevMin; 00331 return m ? m : NULL; 00332 } 00333 00334 /** This functions returns the maximum event valid at a certain date. */ 00335 virtual EventMaxQuantity* getMaxEvent(Date d, bool inclusive = true) const 00336 { 00337 EventMaxQuantity *m = this->lastMax; 00338 if (inclusive) 00339 while(m && d < m->getDate()) m = m->prevMax; 00340 else 00341 while(m && d <= m->getDate()) m = m->prevMax; 00342 return m ? m : NULL; 00343 } 00344 00345 /** This function is used to trace the consistency of the data structure. */ 00346 bool check() const; 00347 00348 private: 00349 /** A pointer to the first event in the timeline. */ 00350 Event* first; 00351 00352 /** A pointer to the last event in the timeline. */ 00353 Event* last; 00354 00355 /** A pointer to the last maximum change. */ 00356 EventMaxQuantity *lastMax; 00357 00358 /** A pointer to the last minimum change. */ 00359 EventMinQuantity *lastMin; 00360 }; 00361 00362 00363 template <class type> void TimeLine<type>::insert (Event* e) 00364 { 00365 // Loop through all entities till we find the insertion point 00366 // While searching from the end, update the onhand and cumulative produced 00367 // quantity of all nodes passed 00368 iterator i = rbegin(); 00369 double qty = e->getQuantity(); 00370 if (qty > 0) 00371 for (; i!=end() && *e<*i; --i) 00372 { 00373 i->oh += qty; 00374 i->cum_prod += qty; 00375 } 00376 else 00377 for (; i!=end() && *e<*i; --i) 00378 i->oh += qty; 00379 00380 // Insert 00381 if (i == end()) 00382 { 00383 // Insert at the head 00384 if (first) 00385 first->prev = e; 00386 else 00387 // First element 00388 last = e; 00389 e->next = first; 00390 e->prev = NULL; 00391 first = e; 00392 e->oh = qty; 00393 if (qty>0) e->cum_prod = qty; 00394 else e->cum_prod = 0; 00395 } 00396 else 00397 { 00398 // Insert in the middle 00399 e->prev = &*i; 00400 e->next = i->next; 00401 if (i->next) 00402 i->next->prev = e; 00403 else 00404 // New last element 00405 last = e; 00406 i->next = e; 00407 e->oh = i->oh + qty; 00408 if (qty>0) e->cum_prod = i->cum_prod + qty; 00409 else e->cum_prod = i->cum_prod; 00410 } 00411 00412 if (e->getType() == 3) 00413 { 00414 // Insert in the list of minima 00415 EventMinQuantity *m = static_cast<EventMinQuantity*>(e); 00416 if (!lastMin || m->getDate() >= lastMin->getDate()) 00417 { 00418 // New last minimum 00419 m->prevMin = lastMin; 00420 lastMin = m; 00421 } 00422 else 00423 { 00424 EventMinQuantity * o = lastMin; 00425 while (o->prevMin && m->getDate() >= o->prevMin->getDate()) 00426 o = o->prevMin; 00427 m->prevMin = o->prevMin; 00428 o->prevMin = m; 00429 } 00430 } 00431 else if (e->getType() == 4) 00432 { 00433 // Insert in the list of maxima 00434 EventMaxQuantity* m = static_cast<EventMaxQuantity*>(e); 00435 if (!lastMax || m->getDate() >= lastMax->getDate()) 00436 { 00437 // New last maximum 00438 m->prevMax = lastMax; 00439 lastMax = m; 00440 } 00441 else 00442 { 00443 EventMaxQuantity *o = lastMax; 00444 while (o->prevMax && m->getDate() >= o->prevMax->getDate()) 00445 o = o->prevMax; 00446 m->prevMax = o->prevMax; 00447 o->prevMax = m; 00448 } 00449 } 00450 00451 // Final debugging check 00452 assert(check()); 00453 } 00454 00455 00456 template <class type> void TimeLine<type>::erase(Event* e) 00457 { 00458 // Update later entries 00459 double qty = e->getQuantity(); 00460 if (qty>0) 00461 for (iterator i = begin(e); i!=end(); ++i) 00462 { 00463 i->oh -= qty; 00464 i->cum_prod -= qty; 00465 } 00466 else 00467 for (iterator i = begin(e); i!=end(); ++i) 00468 i->oh -= qty; 00469 00470 if (e->prev) 00471 e->prev->next = e->next; 00472 else 00473 // Erasing the head 00474 first = e->next; 00475 00476 if (e->next) 00477 e->next->prev = e->prev; 00478 else 00479 // Erasing the tail 00480 last = e->prev; 00481 00482 // Clear prev and next pointers 00483 e->prev = NULL; 00484 e->next = NULL; 00485 00486 // Final debugging check 00487 assert(check()); 00488 } 00489 00490 00491 template <class type> void TimeLine<type>::update(EventChangeOnhand* e, double newqty, const Date& d) 00492 { 00493 // Compute the delta quantity 00494 double delta = e->quantity - newqty; 00495 double oldqty = e->quantity; 00496 00497 // Set the new date and quantity. The algorithm below swaps the element with 00498 // its predecessor or successor till the timeline is properly sorted again. 00499 e->dt = d; 00500 e->quantity = newqty; 00501 00502 // Update the position in the timeline. 00503 // Remember that the quantity is also used by the '<' operator! Changing the 00504 // quantity thus can affect the order of elements. 00505 while ( e->next && !(*e<*e->next) ) 00506 { 00507 // Move to a later date 00508 Event *theNext = e->next, *theNextNext = theNext->next; 00509 if (e->prev) e->prev->next = theNext; 00510 theNext->prev = e->prev; 00511 theNext->next = e; 00512 e->prev = theNext; 00513 e->next = theNextNext; 00514 if (theNextNext) 00515 theNextNext->prev = e; 00516 else 00517 last = e; 00518 if (first == e) first = theNext; 00519 e->oh = theNext->oh; 00520 e->cum_prod = theNext->cum_prod; 00521 theNext->oh -= oldqty; 00522 if (oldqty > 0) theNext->cum_prod -= oldqty; 00523 } 00524 while ( e->prev && !(*e->prev<*e) ) 00525 { 00526 // Move to an earlier date 00527 Event *thePrev = e->prev, *thePrevPrev = thePrev->prev; 00528 if (e->next) e->next->prev = thePrev; 00529 thePrev->next = e->next; 00530 thePrev->prev = e; 00531 e->next = thePrev; 00532 e->prev = thePrevPrev; 00533 if (thePrevPrev) 00534 thePrevPrev->next = e; 00535 else 00536 first = e; 00537 if (last == e) last = thePrev; 00538 thePrev->oh = e->oh; 00539 thePrev->cum_prod = e->cum_prod; 00540 e->oh -= thePrev->getQuantity(); 00541 if (thePrev->getQuantity() > 0) e->cum_prod -= thePrev->getQuantity(); 00542 } 00543 00544 // Update the onhand for all later events 00545 if (fabs(delta) > ROUNDING_ERROR) 00546 { 00547 double cumdelta = (oldqty>0? oldqty : 0) - (newqty>0 ? newqty : 0); 00548 if (fabs(cumdelta) > 0) 00549 for (iterator i=begin(e); i!=end(); ++i) 00550 { 00551 i->oh -= delta; 00552 i->cum_prod -= cumdelta; 00553 } 00554 else 00555 for (iterator i=begin(e); i!=end(); ++i) 00556 i->oh -= delta; 00557 } 00558 00559 // Final debugging check commented out, since loadplans change in pairs. 00560 // After changing the first one the second is affected too but not 00561 // repositioned yet... 00562 //assert(check()); 00563 } 00564 00565 00566 template <class type> bool TimeLine<type>::check() const 00567 { 00568 double expectedOH = 0.0; 00569 double expectedCumProd = 0.0; 00570 const Event *prev = NULL; 00571 for (const_iterator i = begin(); i!=end(); ++i) 00572 { 00573 // Problem 1: The onhands don't add up properly 00574 expectedOH += i->getQuantity(); 00575 if (i->getQuantity() > 0) expectedCumProd += i->getQuantity(); 00576 if (fabs(expectedOH - i->oh) > ROUNDING_ERROR) 00577 { 00578 inspect("Error: timeline onhand value corrupted on " 00579 + string(i->getDate())); 00580 return false; 00581 } 00582 // Problem 2: The cumulative produced quantity isn't correct 00583 if (fabs(expectedCumProd - i->cum_prod) > ROUNDING_ERROR) 00584 { 00585 inspect("Error: timeline cumulative produced value corrupted on " 00586 + string(i->getDate())); 00587 return false; 00588 } 00589 // Problem 3: Timeline is not sorted correctly 00590 if (prev && !(*prev<*i) 00591 && fabs(prev->getQuantity() - i->getQuantity())>ROUNDING_ERROR) 00592 { 00593 inspect("Error: timeline sort corrupted on " + string(i->getDate())); 00594 return false; 00595 } 00596 prev = &*i; 00597 } 00598 return true; 00599 } 00600 00601 } // end namespace 00602 } // end namespace 00603 #endif 00604
Documentation generated for frePPLe by
