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