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 

Documentation generated for frePPLe by  doxygen