timeline.h
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba *
4  * *
5  * This library is free software; you can redistribute it and/or modify it *
6  * under the terms of the GNU Affero General Public License as published *
7  * by the Free Software Foundation; either version 3 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This library is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU Affero General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU Affero General Public *
16  * License along with this program. *
17  * If not, see <http://www.gnu.org/licenses/>. *
18  * *
19  ***************************************************************************/
20 
21 #ifndef TIMELINE
22 #define TIMELINE
23 
24 #ifndef DOXYGEN
25 #include <cmath>
26 #endif
27 
28 namespace frepple
29 {
30 namespace utils
31 {
32 
33 /** @brief This class implements a "sorted list" data structure, sorting
34  * "events" based on a date.
35  *
36  * The data structure has slow insert scalability: O(n)<br>
37  * Moving data around in the structure is efficient though: O(1)<br>
38  * The class leverages the STL library and also follows its api.<br>
39  * The class used to instantiate a timeline must support the
40  * "bool operator < (TYPE)".
41  *
42  * Note that the events store the quantity but NOT the date. We pick up
43  * the date from the template type. The reasoning for this choice is that
44  * the quantity requires more computation than the date and is worthwhile
45  * caching. The date field can be read efficiently from the parent type.
46  */
47 template <class type> class TimeLine
48 {
49  friend class Event;
50  public:
51  class iterator;
52  class const_iterator;
53  /** @brief Base class for nodes in the timeline. */
54  class Event : public NonCopyable
55  {
56  friend class TimeLine<type>;
57  friend class const_iterator;
58  friend class iterator;
59  protected:
61  double oh;
62  double cum_prod;
65  Event() : oh(0), cum_prod(0), next(NULL), prev(NULL) {};
66 
67  public:
68  virtual ~Event() {};
69  virtual double getQuantity() const {return 0.0;}
70 
71  /** Return the current onhand value. */
72  double getOnhand() const {return oh;}
73 
74  /** Return the total produced quantity till the current date. */
75  double getCumulativeProduced() const {return cum_prod;}
76 
77  /** Return the total consumed quantity till the current date. */
78  double getCumulativeConsumed() const {return cum_prod - oh;}
79 
80  /** Return the date of the event. */
81  const Date& getDate() const {return dt;}
82 
83  /** Return a pointer to the owning timeline. */
84  virtual TimeLine<type>* getTimeLine() const {return NULL;}
85 
86  /** This functions returns the mimimum boundary valid at the time of
87  * this event. */
88  virtual double getMin(bool inclusive = true) const
89  {
90  assert(this->getTimeLine());
91  EventMinQuantity *m = this->getTimeLine()->lastMin;
92  if (inclusive)
93  while(m && getDate() < m->getDate()) m = m->prevMin;
94  else
95  while(m && getDate() <= m->getDate()) m = m->prevMin;
96  return m ? m->newMin : 0.0;
97  }
98 
99  /** This functions returns the maximum boundary valid at the time of
100  * this event. */
101  virtual double getMax(bool inclusive = true) const
102  {
103  assert(this->getTimeLine());
104  EventMaxQuantity *m = this->getTimeLine()->lastMax;
105  if (inclusive)
106  while(m && getDate() < m->getDate()) m = m->prevMax;
107  else
108  while(m && getDate() <= m->getDate()) m = m->prevMax;
109  return m ? m->newMax : 0.0;
110  }
111 
112  virtual unsigned short getType() const = 0;
113 
114  /** First criterion is date: earlier dates come first.<br>
115  * Second criterion is the size: big events come first.<br>
116  * As a third tie-breaking criterion, we use a pointer comparison.<br>
117  * This garantuees us a fixed and unambiguous ordering.<br>
118  * As a side effect, this makes sure that producers come before
119  * consumers. This feature is required to avoid zero-time
120  * material shortages.
121  */
122  bool operator < (const Event& fl2) const
123  {
124  assert (&fl2);
125  if (getDate() != fl2.getDate())
126  return getDate() < fl2.getDate();
127  else if (fabs(getQuantity() - fl2.getQuantity()) > ROUNDING_ERROR)
128  return getQuantity() > fl2.getQuantity();
129  else
130  return this < &fl2;
131  }
132  };
133 
134  /** @brief A timeline event representing a change of the current value. */
135  class EventChangeOnhand : public Event
136  {
137  friend class TimeLine<type>;
138  private:
139  double quantity;
140  public:
141  double getQuantity() const {return quantity;}
142  EventChangeOnhand(double qty = 0.0) : quantity(qty) {}
143  virtual unsigned short getType() const {return 1;}
144  };
145 
146  /** @brief A timeline event representing a change of the minimum target. */
147  class EventMinQuantity : public Event
148  {
149  friend class TimeLine<type>;
150  friend class Event;
151  private:
152  double newMin;
153  protected:
155  public:
156  EventMinQuantity(Date d, double f=0.0) : newMin(f), prevMin(NULL)
157  {this->dt = d;}
158  void setMin(double f) {newMin = f;}
159  virtual double getMin(bool inclusive = true) const
160  {
161  if (inclusive) return newMin;
162  else return prevMin ? prevMin->newMin : 0.0;
163  }
164  virtual unsigned short getType() const {return 3;}
165  };
166 
167  /** @brief A timeline event representing a change of the maximum target. */
168  class EventMaxQuantity : public Event
169  {
170  friend class Event;
171  friend class TimeLine<type>;
172  private:
173  double newMax;
174  protected:
176  public:
177  EventMaxQuantity(Date d, double f=0.0) : newMax(f), prevMax(NULL)
178  {this->dt = d;}
179  void setMax(double f) {newMax = f;}
180  virtual double getMax(bool inclusive = true) const
181  {
182  if (inclusive) return newMax;
183  else return prevMax ? prevMax->newMax : 0.0;
184  }
185  virtual unsigned short getType() const {return 4;}
186  };
187 
188  /** @brief This is bi-directional iterator through the timeline. */
190  {
191  protected:
192  const Event* cur;
193  public:
194  const_iterator() : cur(NULL) {}
195  const_iterator(const Event* e) : cur(e) {};
196  const_iterator(const iterator& c) : cur(c.cur) {}
197  const Event& operator*() const {return *cur;}
198  const Event* operator->() const {return cur;}
199  const_iterator& operator++() {if (cur) cur = cur->next; return *this;}
201  {const_iterator tmp = *this; ++*this; return tmp;}
202  const_iterator& operator--() {if (cur) cur = cur->prev; return *this;}
204  {const_iterator tmp = *this; --*this; return tmp;}
205  bool operator==(const const_iterator& x) const {return cur == x.cur;}
206  bool operator!=(const const_iterator& x) const {return cur != x.cur;}
207  };
208 
209  /** @brief This is bi-directional iterator through the timeline. */
210  class iterator : public const_iterator
211  {
212  public:
213  iterator() {}
215  Event& operator*() const {return *const_cast<Event*>(this->cur);}
216  Event* operator->() const {return const_cast<Event*>(this->cur);}
217  iterator& operator++() {if (this->cur) this->cur = this->cur->next; return *this;}
218  iterator operator++(int) {iterator tmp = *this; ++*this; return tmp;}
219  iterator& operator--() {if (this->cur) this->cur = this->cur->prev; return *this;}
220  iterator operator--(int) {iterator tmp = *this; --*this; return tmp;}
221  bool operator==(const iterator& x) const {return this->cur == x.cur;}
222  bool operator!=(const iterator& x) const {return this->cur != x.cur;}
223  };
224 
225  TimeLine() : first(NULL), last(NULL), lastMax(NULL), lastMin(NULL) {}
226  int size() const
227  {
228  int cnt(0);
229  for (Event* p=first; p; p=p->next) ++cnt;
230  return cnt;
231  }
232  iterator begin() {return iterator(first);}
233  iterator begin(Event* e) {return iterator(e);}
234  iterator rbegin() {return iterator(last);}
235  iterator end() {return iterator(NULL);}
236  const_iterator begin() const {return const_iterator(first);}
237  const_iterator begin(const Event* e) const {return const_iterator(e);}
238  const_iterator rbegin() const {return const_iterator(last);}
239  const_iterator end() const {return const_iterator(NULL);}
240  bool empty() const {return first==NULL;}
241  void insert(Event*);
242  void insert(EventChangeOnhand* e, double qty, const Date& d)
243  {
244  e->quantity = qty;
245  e->dt = d;
246  insert(static_cast<Event*>(e));
247  };
248  void erase(Event*);
249  void update(EventChangeOnhand*, double, const Date&);
250 
251  /** This function is used for debugging purposes.<br>
252  * It prints a header line, followed by the date, quantity and on_hand
253  * of all events in the timeline.
254  */
255  void inspect(const string& name) const
256  {
257  logger << "Inspecting " << this << ": \"" << name << "\":" << endl;
258  for (const_iterator oo=begin(); oo!=end(); ++oo)
259  logger << " " << oo->getDate() << " "
260  << oo->getQuantity() << " " << oo->getOnhand()
261  << " " << oo->getCumulativeProduced() << &*oo << endl;
262  }
263 
264  /** This functions returns the mimimum valid at a certain date. */
265  virtual double getMin(Date d, bool inclusive = true) const
266  {
267  EventMinQuantity *m = this->lastMin;
268  if (inclusive)
269  while(m && d < m->getDate()) m = m->prevMin;
270  else
271  while(m && d <= m->getDate()) m = m->prevMin;
272  return m ? m->getMin() : 0.0;
273  }
274 
275  /** This functions returns the mimimum valid at a certain event. */
276  virtual double getMin(const Event *e, bool inclusive = true) const
277  {
278  if (!e) return 0.0;
279  EventMinQuantity *m = this->lastMin;
280  if (inclusive)
281  while(m && e->getDate() < m->getDate()) m = m->prevMin;
282  else
283  while(m && e->getDate() <= m->getDate()) m = m->prevMin;
284  return m ? m->getMin() : 0.0;
285  }
286 
287  /** This functions returns the maximum valid at a certain date. */
288  virtual double getMax(Date d, bool inclusive = true) const
289  {
290  EventMaxQuantity *m = this->lastMax;
291  if (inclusive)
292  while(m && d < m->getDate()) m = m->prevMax;
293  else
294  while(m && d <= m->getDate()) m = m->prevMax;
295  return m ? m->getMax() : 0.0;
296  }
297 
298  /** This functions returns the mimimum valid at a certain eveny. */
299  virtual double getMax(const Event *e, bool inclusive = true) const
300  {
301  if (!e) return 0.0;
302  EventMaxQuantity *m = this->lastMax;
303  if (inclusive)
304  while(m && e->getDate() < m->getDate()) m = m->prevMax;
305  else
306  while(m && e->getDate() <= m->getDate()) m = m->prevMax;
307  return m ? m->getMax() : 0.0;
308  }
309 
310  /** This functions returns the mimimum event valid at a certain date. */
311  virtual EventMinQuantity* getMinEvent(Date d, bool inclusive = true) const
312  {
313  EventMinQuantity *m = this->lastMin;
314  if (inclusive)
315  while(m && d < m->getDate()) m = m->prevMin;
316  else
317  while(m && d <= m->getDate()) m = m->prevMin;
318  return m ? m : NULL;
319  }
320 
321  /** This functions returns the maximum event valid at a certain date. */
322  virtual EventMaxQuantity* getMaxEvent(Date d, bool inclusive = true) const
323  {
324  EventMaxQuantity *m = this->lastMax;
325  if (inclusive)
326  while(m && d < m->getDate()) m = m->prevMax;
327  else
328  while(m && d <= m->getDate()) m = m->prevMax;
329  return m ? m : NULL;
330  }
331 
332  /** This function is used to trace the consistency of the data structure. */
333  bool check() const;
334 
335  private:
336  /** A pointer to the first event in the timeline. */
337  Event* first;
338 
339  /** A pointer to the last event in the timeline. */
340  Event* last;
341 
342  /** A pointer to the last maximum change. */
343  EventMaxQuantity *lastMax;
344 
345  /** A pointer to the last minimum change. */
346  EventMinQuantity *lastMin;
347 };
348 
349 
350 template <class type> void TimeLine<type>::insert (Event* e)
351 {
352  // Loop through all entities till we find the insertion point
353  // While searching from the end, update the onhand and cumulative produced
354  // quantity of all nodes passed
355  iterator i = rbegin();
356  double qty = e->getQuantity();
357  if (qty > 0)
358  for (; i!=end() && *e<*i; --i)
359  {
360  i->oh += qty;
361  i->cum_prod += qty;
362  }
363  else
364  for (; i!=end() && *e<*i; --i)
365  i->oh += qty;
366 
367  // Insert
368  if (i == end())
369  {
370  // Insert at the head
371  if (first)
372  first->prev = e;
373  else
374  // First element
375  last = e;
376  e->next = first;
377  e->prev = NULL;
378  first = e;
379  e->oh = qty;
380  if (qty>0) e->cum_prod = qty;
381  else e->cum_prod = 0;
382  }
383  else
384  {
385  // Insert in the middle
386  e->prev = &*i;
387  e->next = i->next;
388  if (i->next)
389  i->next->prev = e;
390  else
391  // New last element
392  last = e;
393  i->next = e;
394  e->oh = i->oh + qty;
395  if (qty>0) e->cum_prod = i->cum_prod + qty;
396  else e->cum_prod = i->cum_prod;
397  }
398 
399  if (e->getType() == 3)
400  {
401  // Insert in the list of minima
402  EventMinQuantity *m = static_cast<EventMinQuantity*>(e);
403  if (!lastMin || m->getDate() >= lastMin->getDate())
404  {
405  // New last minimum
406  m->prevMin = lastMin;
407  lastMin = m;
408  }
409  else
410  {
411  EventMinQuantity * o = lastMin;
412  while (o->prevMin && m->getDate() >= o->prevMin->getDate())
413  o = o->prevMin;
414  m->prevMin = o->prevMin;
415  o->prevMin = m;
416  }
417  }
418  else if (e->getType() == 4)
419  {
420  // Insert in the list of maxima
421  EventMaxQuantity* m = static_cast<EventMaxQuantity*>(e);
422  if (!lastMax || m->getDate() >= lastMax->getDate())
423  {
424  // New last maximum
425  m->prevMax = lastMax;
426  lastMax = m;
427  }
428  else
429  {
430  EventMaxQuantity *o = lastMax;
431  while (o->prevMax && m->getDate() >= o->prevMax->getDate())
432  o = o->prevMax;
433  m->prevMax = o->prevMax;
434  o->prevMax = m;
435  }
436  }
437 
438  // Final debugging check
439  assert(check());
440 }
441 
442 
443 template <class type> void TimeLine<type>::erase(Event* e)
444 {
445  // Update later entries
446  double qty = e->getQuantity();
447  if (qty>0)
448  for (iterator i = begin(e); i!=end(); ++i)
449  {
450  i->oh -= qty;
451  i->cum_prod -= qty;
452  }
453  else
454  for (iterator i = begin(e); i!=end(); ++i)
455  i->oh -= qty;
456 
457  if (e->prev)
458  e->prev->next = e->next;
459  else
460  // Erasing the head
461  first = e->next;
462 
463  if (e->next)
464  e->next->prev = e->prev;
465  else
466  // Erasing the tail
467  last = e->prev;
468 
469  // Clear prev and next pointers
470  e->prev = NULL;
471  e->next = NULL;
472 
473  // Remove the list of minima
474  if (e->getType() == 3)
475  {
476  EventMinQuantity *m = static_cast<EventMinQuantity*>(e);
477  if (lastMin == e)
478  // New last minimum
479  lastMin = m->prevMin;
480  else
481  {
482  EventMinQuantity *o = lastMin;
483  while (o->prevMin != e && o) o = o->prevMin;
484  if (o) o->prevMin = m->prevMin;
485  }
486  }
487 
488  // Remove the list of maxima
489  else if (e->getType() == 4)
490  {
491  EventMaxQuantity *m = static_cast<EventMaxQuantity*>(e);
492  if (lastMax == e)
493  // New last maximum
494  lastMax = m->prevMax;
495  else
496  {
497  EventMaxQuantity * o = lastMax;
498  while (o->prevMax != e && o) o = o->prevMax;
499  if (o) o->prevMax = m->prevMax;
500  }
501  }
502 
503  // Final debugging check
504  assert(check());
505 }
506 
507 
508 template <class type> void TimeLine<type>::update(EventChangeOnhand* e, double newqty, const Date& d)
509 {
510  // Compute the delta quantity
511  double delta = e->quantity - newqty;
512  double oldqty = e->quantity;
513 
514  // Set the new date and quantity. The algorithm below swaps the element with
515  // its predecessor or successor till the timeline is properly sorted again.
516  e->dt = d;
517  e->quantity = newqty;
518 
519  // Update the position in the timeline.
520  // Remember that the quantity is also used by the '<' operator! Changing the
521  // quantity thus can affect the order of elements.
522  while ( e->next && !(*e<*e->next) )
523  {
524  // Move to a later date
525  Event *theNext = e->next;
526  Event *theNextNext = theNext->next;
527  if (e->prev) e->prev->next = theNext;
528  theNext->prev = e->prev;
529  theNext->next = e;
530  e->prev = theNext;
531  e->next = theNextNext;
532  if (theNextNext)
533  theNextNext->prev = e;
534  else
535  last = e;
536  if (first == e) first = theNext;
537  e->oh = theNext->oh;
538  e->cum_prod = theNext->cum_prod;
539  theNext->oh -= oldqty;
540  if (oldqty > 0) theNext->cum_prod -= oldqty;
541  }
542  while ( e->prev && !(*e->prev<*e) )
543  {
544  // Move to an earlier date
545  Event *thePrev = e->prev;
546  Event *thePrevPrev = thePrev->prev;
547  if (e->next) e->next->prev = thePrev;
548  thePrev->next = e->next;
549  thePrev->prev = e;
550  e->next = thePrev;
551  e->prev = thePrevPrev;
552  if (thePrevPrev)
553  thePrevPrev->next = e;
554  else
555  first = e;
556  if (last == e) last = thePrev;
557  thePrev->oh = e->oh;
558  thePrev->cum_prod = e->cum_prod;
559  e->oh -= thePrev->getQuantity();
560  if (thePrev->getQuantity() > 0) e->cum_prod -= thePrev->getQuantity();
561  }
562 
563  // Update the onhand for all later events
564  if (fabs(delta) > ROUNDING_ERROR)
565  {
566  double cumdelta = (oldqty>0? oldqty : 0) - (newqty>0 ? newqty : 0);
567  if (fabs(cumdelta) > 0)
568  for (iterator i=begin(e); i!=end(); ++i)
569  {
570  i->oh -= delta;
571  i->cum_prod -= cumdelta;
572  }
573  else
574  for (iterator i=begin(e); i!=end(); ++i)
575  i->oh -= delta;
576  }
577 
578  // Final debugging check commented out, since loadplans change in pairs.
579  // After changing the first one the second is affected too but not
580  // repositioned yet...
581  //assert(check());
582 }
583 
584 
585 template <class type> bool TimeLine<type>::check() const
586 {
587  double expectedOH = 0.0;
588  double expectedCumProd = 0.0;
589  const Event *prev = NULL;
590  for (const_iterator i = begin(); i!=end(); ++i)
591  {
592  // Problem 1: The onhands don't add up properly
593  expectedOH += i->getQuantity();
594  if (i->getQuantity() > 0) expectedCumProd += i->getQuantity();
595  if (fabs(expectedOH - i->oh) > ROUNDING_ERROR)
596  {
597  inspect("Error: timeline onhand value corrupted on "
598  + string(i->getDate()));
599  return false;
600  }
601  // Problem 2: The cumulative produced quantity isn't correct
602  if (fabs(expectedCumProd - i->cum_prod) > ROUNDING_ERROR)
603  {
604  inspect("Error: timeline cumulative produced value corrupted on "
605  + string(i->getDate()));
606  return false;
607  }
608  // Problem 3: Timeline is not sorted correctly
609  if (prev && !(*prev<*i)
610  && fabs(prev->getQuantity() - i->getQuantity())>ROUNDING_ERROR)
611  {
612  inspect("Error: timeline sort corrupted on " + string(i->getDate()));
613  return false;
614  }
615  prev = &*i;
616  }
617  return true;
618 }
619 
620 } // end namespace
621 } // end namespace
622 #endif
623