timeline.h

Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.8.0/include/frepple/timeline.h $
00003   version : $LastChangedRevision: 1141 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2010-01-01 15:36:10 +0100 (Fri, 01 Jan 2010) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007 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           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           EventMaxQuantity *m = this->getTimeLine()->lastMax;
00110           if (inclusive)
00111             while(m && getDate() < m->getDate()) m = m->prevMax;
00112           else
00113             while(m && getDate() <= m->getDate()) m = m->prevMax;
00114           return m ? m->newMax : 0.0;
00115         }
00116 
00117         virtual unsigned short getType() const = 0;
00118 
00119         /** First criterion is date: earlier dates come first.<br>
00120           * Second criterion is the size: big events come first.<br>
00121           * As a third tie-breaking criterion, we use a pointer comparison.<br>
00122           * This garantuees us a fixed and unambiguous ordering.<br>
00123           * As a side effect, this makes sure that producers come before
00124           * consumers. This feature is required to avoid zero-time
00125           * material shortages.
00126           */
00127         bool operator < (const Event& fl2) const
00128         {
00129           assert (&fl2);
00130           if (getDate() != fl2.getDate())
00131             return getDate() < fl2.getDate();
00132           else if (fabs(getQuantity() - fl2.getQuantity()) > ROUNDING_ERROR)
00133             return getQuantity() > fl2.getQuantity();
00134           else
00135             return this < &fl2;
00136         }
00137     };
00138 
00139     /** @brief A timeline event representing a change of the current value. */
00140     class EventChangeOnhand : public Event
00141     {
00142       friend class TimeLine<type>;
00143       private:
00144         double quantity;
00145       public:
00146         double getQuantity() const {return quantity;}
00147         EventChangeOnhand(double qty = 0.0) : quantity(qty) {}
00148         virtual unsigned short getType() const {return 1;}
00149     };
00150 
00151     /** @brief A timeline event representing a change of the minimum target. */
00152     class EventMinQuantity : public Event
00153     {
00154       friend class TimeLine<type>;
00155       friend class Event;
00156       private:
00157         double newMin;
00158       protected:
00159         EventMinQuantity *prevMin;
00160       public:
00161         EventMinQuantity(Date d, double f=0.0) : newMin(f), prevMin(NULL)
00162           {this->dt = d;}
00163         void setMin(double f) {newMin = f;}
00164         virtual double getMin(bool inclusive = true) const 
00165         {
00166           if (inclusive) return newMin;
00167           else return prevMin ? prevMin->newMin : 0.0;
00168         }
00169         virtual unsigned short getType() const {return 3;}
00170     };
00171 
00172     /** @brief A timeline event representing a change of the maximum target. */
00173     class EventMaxQuantity : public Event
00174     {
00175       friend class Event;
00176       friend class TimeLine<type>;
00177       private:
00178         double newMax;
00179       protected:
00180         EventMaxQuantity *prevMax;
00181       public:
00182         EventMaxQuantity(Date d, double f=0.0) : newMax(f), prevMax(NULL)
00183           {this->dt = d;}
00184         void setMax(double f) {newMax = f;}
00185         virtual double getMax(bool inclusive = true) const
00186         {
00187           if (inclusive) return newMax;
00188           else return prevMax ? prevMax->newMax : 0.0;
00189         }      
00190         virtual unsigned short getType() const {return 4;}
00191     };
00192 
00193     /** @brief This is bi-directional iterator through the timeline.
00194       *
00195       * It looks a bit STL-compliant, but this is only superficially. The
00196       * class doesn't meet all requirements for a full STL-compliant
00197       * iterator.
00198       * @todo Make the timeline iterators fully STL compliant.
00199       */
00200     class const_iterator
00201     {
00202       protected:
00203         const Event* cur;
00204       public:
00205         const_iterator() {}
00206         const_iterator(const Event* e) : cur(e) {};
00207         const_iterator(const iterator& c) : cur(c.cur) {}
00208         const Event& operator*() const {return *cur;}
00209         const Event* operator->() const {return cur;}
00210         const_iterator& operator++() {cur = cur->next; return *this;}
00211         const_iterator operator++(int)
00212           {const_iterator tmp = *this; ++*this; return tmp;}
00213         const_iterator& operator--() {cur = cur->prev; return *this;}
00214         const_iterator operator--(int)
00215           {const_iterator tmp = *this; --*this; return tmp;}
00216         bool operator==(const const_iterator& x) const {return cur == x.cur;}
00217         bool operator!=(const const_iterator& x) const {return cur != x.cur;}
00218     };
00219 
00220     /** @brief This is bi-directional iterator through the timeline. */
00221     class iterator : public const_iterator
00222     {
00223       public:
00224         iterator() {}
00225         iterator(Event* e) : const_iterator(e) {};
00226         Event& operator*() const {return *const_cast<Event*>(this->cur);}
00227         Event* operator->() const {return const_cast<Event*>(this->cur);}
00228         iterator& operator++() {this->cur = this->cur->next; return *this;}
00229         iterator operator++(int) {iterator tmp = *this; ++*this; return tmp;}
00230         iterator& operator--() {this->cur = this->cur->prev; return *this;}
00231         iterator operator--(int) {iterator tmp = *this; --*this; return tmp;}
00232         bool operator==(const iterator& x) const {return this->cur == x.cur;}
00233         bool operator!=(const iterator& x) const {return this->cur != x.cur;}
00234     };
00235 
00236     TimeLine() : first(NULL), last(NULL), lastMax(NULL), lastMin(NULL) {}
00237     int size() const
00238     {
00239       int cnt(0);
00240       for (Event* p=first; p; p=p->next) ++cnt;
00241       return cnt;
00242     }
00243     iterator begin() {return iterator(first);}
00244     iterator begin(Event* e) {return iterator(e);}
00245     iterator rbegin() {return iterator(last);}
00246     iterator end() {return iterator(NULL);}
00247     const_iterator begin() const {return const_iterator(first);}
00248     const_iterator begin(const Event* e) const {return const_iterator(e);}
00249     const_iterator rbegin() const {return const_iterator(last);}
00250     const_iterator end() const {return const_iterator(NULL);}
00251     bool empty() const {return first==NULL;}
00252     void insert(Event*);
00253     void insert(EventChangeOnhand* e, double qty, const Date& d)
00254     {
00255       e->quantity = qty;
00256       e->dt = d;
00257       insert(static_cast<Event*>(e));
00258     };
00259     void erase(Event*);
00260     void update(EventChangeOnhand*, double, const Date&);
00261 
00262     /** This function is used for debugging purposes.<br>
00263       * It prints a header line, followed by the date, quantity and on_hand
00264       * of all events in the timeline.
00265       */
00266     void inspect(const string& name) const
00267     {
00268       logger << "Inspecting  " << this << ": \"" << name << "\":" << endl;
00269       for (const_iterator oo=begin(); oo!=end(); ++oo)
00270         logger << "  " << oo->getDate() << "   "
00271         << oo->getQuantity() << "    " << oo->getOnhand()
00272         << "    " << oo->getCumulativeProduced() <<  &*oo << endl;
00273     }
00274 
00275     /** This function is used to trace the consistency of the data structure. */
00276     bool check() const;
00277 
00278   private:
00279     /** A pointer to the first event in the timeline. */
00280     Event* first;
00281 
00282     /** A pointer to the last event in the timeline. */
00283     Event* last;
00284 
00285     /** A pointer to the last maximum change. */
00286     EventMaxQuantity *lastMax;
00287 
00288     /** A pointer to the last minimum change. */
00289     EventMinQuantity *lastMin;
00290 };
00291 
00292 
00293 template <class type> void TimeLine<type>::insert (Event* e)
00294 {
00295   // Loop through all entities till we find the insertion point
00296   // While searching from the end, update the onhand and cumulative produced
00297   // quantity of all nodes passed
00298   iterator i = rbegin();
00299   double qty = e->getQuantity();
00300   if (qty > 0)
00301     for (; i!=end() && *e<*i; --i)
00302     {
00303       i->oh += qty;
00304       i->cum_prod += qty;
00305     }
00306   else
00307     for (; i!=end() && *e<*i; --i)
00308       i->oh += qty;
00309 
00310   // Insert
00311   if (i == end())
00312   {
00313     // Insert at the head
00314     if (first)
00315       first->prev = e;
00316     else
00317       // First element
00318       last = e;
00319     e->next = first;
00320     e->prev = NULL;
00321     first = e;
00322     e->oh = qty;
00323     if (qty>0) e->cum_prod = qty;
00324     else e->cum_prod = 0;
00325   }
00326   else
00327   {
00328     // Insert in the middle
00329     e->prev = &*i;
00330     e->next = i->next;
00331     if (i->next)
00332       i->next->prev = e;
00333     else
00334       // New last element
00335       last = e;
00336     i->next = e;
00337     e->oh = i->oh + qty;
00338     if (qty>0) e->cum_prod = i->cum_prod + qty;
00339     else e->cum_prod = i->cum_prod;
00340   }
00341 
00342   if (e->getType() == 3)
00343   {
00344     // Insert in the list of minima
00345     EventMinQuantity *m = static_cast<EventMinQuantity*>(e);
00346     if (!lastMin || m->getDate() >= lastMin->getDate())
00347     {
00348       // New last minimum
00349       m->prevMin = lastMin;
00350       lastMin = m;
00351     }
00352     else
00353     {
00354       EventMinQuantity * o = lastMin;
00355       while (o->prevMin && m->getDate() >= o->prevMin->getDate())
00356         o = o->prevMin;
00357       m->prevMin = o->prevMin;
00358       o->prevMin = m;
00359     }
00360   }
00361   else if (e->getType() == 4)
00362   {
00363     // Insert in the list of maxima
00364     EventMaxQuantity* m = static_cast<EventMaxQuantity*>(e);
00365     if (!lastMax || m->getDate() >= lastMax->getDate())
00366     {
00367       // New last maximum
00368       m->prevMax = lastMax;
00369       lastMax = m;
00370     }
00371     else
00372     {
00373       EventMaxQuantity *o = lastMax;
00374       while (o->prevMax && o->getDate() <= o->prevMax->getDate())
00375         o = o->prevMax;
00376       m->prevMax = o->prevMax;
00377       o->prevMax = m;
00378     }
00379   }
00380 
00381   // Final debugging check
00382   assert(check());
00383 }
00384 
00385 
00386 template <class type> void TimeLine<type>::erase(Event* e)
00387 {
00388   // Update later entries
00389   double qty = e->getQuantity();
00390   if (qty>0)
00391     for (iterator i = begin(e); i!=end(); ++i)
00392     {
00393       i->oh -= qty;
00394       i->cum_prod -= qty;
00395     }
00396   else
00397     for (iterator i = begin(e); i!=end(); ++i)
00398       i->oh -= qty;
00399 
00400   if (e->prev)
00401     e->prev->next = e->next;
00402   else
00403     // Erasing the head
00404     first = e->next;
00405 
00406   if (e->next)
00407     e->next->prev = e->prev;
00408   else
00409     // Erasing the tail
00410     last = e->prev;
00411   
00412   // Clear prev and next pointers
00413   e->prev = NULL;
00414   e->next = NULL;
00415 
00416   // Final debugging check
00417   assert(check());
00418 }
00419 
00420 
00421 template <class type> void TimeLine<type>::update(EventChangeOnhand* e, double newqty, const Date& d)
00422 {
00423   // Compute the delta quantity
00424   double delta = e->quantity - newqty;
00425   double oldqty = e->quantity;
00426 
00427   // Set the new date and quantity. The algorithm below swaps the element with
00428   // its predecessor or successor till the timeline is properly sorted again.
00429   e->dt = d;
00430   e->quantity = newqty;
00431 
00432   // Update the position in the timeline.
00433   // Remember that the quantity is also used by the '<' operator! Changing the
00434   // quantity thus can affect the order of elements.
00435   while ( e->next && !(*e<*e->next) )
00436   {
00437     // Move to a later date
00438     Event *theNext = e->next, *theNextNext = theNext->next;
00439     if (e->prev) e->prev->next = theNext;
00440     theNext->prev = e->prev;
00441     theNext->next = e;
00442     e->prev = theNext;
00443     e->next = theNextNext;
00444     if (theNextNext)
00445       theNextNext->prev = e;
00446     else
00447       last = e;
00448     if (first == e) first = theNext;
00449     e->oh = theNext->oh;
00450     e->cum_prod = theNext->cum_prod;
00451     theNext->oh -= oldqty;
00452     if (oldqty > 0) theNext->cum_prod -= oldqty;
00453   }
00454   while ( e->prev && !(*e->prev<*e) )
00455   {
00456     // Move to an earlier date
00457     Event *thePrev = e->prev, *thePrevPrev = thePrev->prev;
00458     if (e->next) e->next->prev = thePrev;
00459     thePrev->next = e->next;
00460     thePrev->prev = e;
00461     e->next = thePrev;
00462     e->prev = thePrevPrev;
00463     if (thePrevPrev)
00464       thePrevPrev->next = e;
00465     else
00466       first = e;
00467     if (last == e) last = thePrev;
00468     thePrev->oh = e->oh;
00469     thePrev->cum_prod = e->cum_prod;
00470     e->oh -= thePrev->getQuantity();
00471     if (thePrev->getQuantity() > 0) e->cum_prod -= thePrev->getQuantity();
00472   }
00473 
00474   // Update the onhand for all later events
00475   if (fabs(delta) > ROUNDING_ERROR)
00476   {
00477     double cumdelta = (oldqty>0? oldqty : 0) - (newqty>0 ? newqty : 0);
00478     if (fabs(cumdelta) > 0)
00479       for (iterator i=begin(e); i!=end(); ++i)
00480       {
00481         i->oh -= delta;
00482         i->cum_prod -= cumdelta;
00483       }
00484     else
00485       for (iterator i=begin(e); i!=end(); ++i)
00486         i->oh -= delta;
00487   }
00488 
00489   // Final debugging check commented out, since loadplans change in pairs.
00490   // After changing the first one the second is affected too but not
00491   // repositioned yet...
00492   //assert(check());
00493 }
00494 
00495 
00496 template <class type> bool TimeLine<type>::check() const
00497 {
00498   double expectedOH = 0.0;
00499   double expectedCumProd = 0.0;
00500   const Event *prev = NULL;
00501   for (const_iterator i = begin(); i!=end(); ++i)
00502   {
00503     // Problem 1: The onhands don't add up properly
00504     expectedOH += i->getQuantity();
00505     if (i->getQuantity() > 0) expectedCumProd += i->getQuantity();
00506     if (fabs(expectedOH - i->oh) > ROUNDING_ERROR)
00507     {
00508       inspect("Error: timeline onhand value corrupted on "
00509           + string(i->getDate()));
00510       return false;
00511     }
00512     // Problem 2: The cumulative produced quantity isn't correct
00513     if (fabs(expectedCumProd - i->cum_prod) > ROUNDING_ERROR)
00514     {
00515       inspect("Error: timeline cumulative produced value corrupted on "
00516           + string(i->getDate()));
00517       return false;
00518     }
00519     // Problem 3: Timeline is not sorted correctly
00520     if (prev && !(*prev<*i)
00521         && fabs(prev->getQuantity() - i->getQuantity())>ROUNDING_ERROR)
00522     {
00523       inspect("Error: timeline sort corrupted on " + string(i->getDate()));
00524       return false;
00525     }
00526     prev = &*i;
00527   }
00528   return true;
00529 }
00530 
00531 } // end namespace
00532 } // end namespace
00533 #endif
00534 

Generated on 16 Apr 2010 for frePPLe by  doxygen 1.6.1