timeline.h
Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.9.1/include/frepple/timeline.h $
00003   version : $LastChangedRevision: 1656 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2012-03-27 19:05:34 +0200 (Tue, 27 Mar 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 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   // Remove the list of minima
00487   if (e->getType() == 3)
00488   {
00489     EventMinQuantity *m = static_cast<EventMinQuantity*>(e);
00490     if (lastMin == e)
00491       // New last minimum
00492       lastMin = m->prevMin;
00493     else
00494     {
00495       EventMinQuantity *o = lastMin;
00496       while (o->prevMin != e && o) o = o->prevMin;
00497       if (o) o->prevMin = m->prevMin;
00498     }
00499   }
00500 
00501   // Remove the list of maxima
00502   else if (e->getType() == 4)
00503   {
00504     EventMaxQuantity *m = static_cast<EventMaxQuantity*>(e);
00505     if (lastMax == e)
00506       // New last maximum
00507       lastMax = m->prevMax;
00508     else
00509     {
00510       EventMaxQuantity * o = lastMax;
00511       while (o->prevMax != e && o) o = o->prevMax;
00512       if (o) o->prevMax = m->prevMax;
00513     }
00514   }
00515 
00516   // Final debugging check
00517   assert(check());
00518 }
00519 
00520 
00521 template <class type> void TimeLine<type>::update(EventChangeOnhand* e, double newqty, const Date& d)
00522 {
00523   // Compute the delta quantity
00524   double delta = e->quantity - newqty;
00525   double oldqty = e->quantity;
00526 
00527   // Set the new date and quantity. The algorithm below swaps the element with
00528   // its predecessor or successor till the timeline is properly sorted again.
00529   e->dt = d;
00530   e->quantity = newqty;
00531 
00532   // Update the position in the timeline.
00533   // Remember that the quantity is also used by the '<' operator! Changing the
00534   // quantity thus can affect the order of elements.
00535   while ( e->next && !(*e<*e->next) )
00536   {
00537     // Move to a later date
00538     Event *theNext = e->next, *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, *thePrevPrev = thePrev->prev;
00558     if (e->next) e->next->prev = thePrev;
00559     thePrev->next = e->next;
00560     thePrev->prev = e;
00561     e->next = thePrev;
00562     e->prev = thePrevPrev;
00563     if (thePrevPrev)
00564       thePrevPrev->next = e;
00565     else
00566       first = e;
00567     if (last == e) last = thePrev;
00568     thePrev->oh = e->oh;
00569     thePrev->cum_prod = e->cum_prod;
00570     e->oh -= thePrev->getQuantity();
00571     if (thePrev->getQuantity() > 0) e->cum_prod -= thePrev->getQuantity();
00572   }
00573 
00574   // Update the onhand for all later events
00575   if (fabs(delta) > ROUNDING_ERROR)
00576   {
00577     double cumdelta = (oldqty>0? oldqty : 0) - (newqty>0 ? newqty : 0);
00578     if (fabs(cumdelta) > 0)
00579       for (iterator i=begin(e); i!=end(); ++i)
00580       {
00581         i->oh -= delta;
00582         i->cum_prod -= cumdelta;
00583       }
00584     else
00585       for (iterator i=begin(e); i!=end(); ++i)
00586         i->oh -= delta;
00587   }
00588 
00589   // Final debugging check commented out, since loadplans change in pairs.
00590   // After changing the first one the second is affected too but not
00591   // repositioned yet...
00592   //assert(check());
00593 }
00594 
00595 
00596 template <class type> bool TimeLine<type>::check() const
00597 {
00598   double expectedOH = 0.0;
00599   double expectedCumProd = 0.0;
00600   const Event *prev = NULL;
00601   for (const_iterator i = begin(); i!=end(); ++i)
00602   {
00603     // Problem 1: The onhands don't add up properly
00604     expectedOH += i->getQuantity();
00605     if (i->getQuantity() > 0) expectedCumProd += i->getQuantity();
00606     if (fabs(expectedOH - i->oh) > ROUNDING_ERROR)
00607     {
00608       inspect("Error: timeline onhand value corrupted on "
00609           + string(i->getDate()));
00610       return false;
00611     }
00612     // Problem 2: The cumulative produced quantity isn't correct
00613     if (fabs(expectedCumProd - i->cum_prod) > ROUNDING_ERROR)
00614     {
00615       inspect("Error: timeline cumulative produced value corrupted on "
00616           + string(i->getDate()));
00617       return false;
00618     }
00619     // Problem 3: Timeline is not sorted correctly
00620     if (prev && !(*prev<*i)
00621         && fabs(prev->getQuantity() - i->getQuantity())>ROUNDING_ERROR)
00622     {
00623       inspect("Error: timeline sort corrupted on " + string(i->getDate()));
00624       return false;
00625     }
00626     prev = &*i;
00627   }
00628   return true;
00629 }
00630 
00631 } // end namespace
00632 } // end namespace
00633 #endif
00634 

Documentation generated for frePPLe by  doxygen