NCBI C++ ToolKit
time_line.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef UTIL_TIME_LINE__HPP
2 #define UTIL_TIME_LINE__HPP
3 
4 /* $Id: time_line.hpp 39985 2008-11-05 16:25:07Z ivanovp $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Anatoliy Kuznetsov, Victor Joukov
30  *
31  * File Description: Timeline object for approximate tracking of time events
32  *
33  */
34 
35 #include <corelib/ncbitime.hpp>
36 #include <util/bitset/bmconst.h>
37 #include <deque>
38 
39 
41 
42 /// Timeline class for fast approximate time tracking.
43 ///
44 /// This class discretizes time with specified precision using bit-vectors.
45 /// Time vector is divided so each slot represents N seconds(N-discr.factor)
46 /// Each slot points on bit-vector of ids (object id)
47 ///
48 /// Typical application is when we need to setup a wake-up calls for millons
49 /// of int enumerated objects.
50 ///
51 /// Example:
52 /// <pre>
53 /// 123
54 /// 28
55 /// 10
56 /// 4
57 /// 3
58 /// 2
59 /// ^ ^
60 /// | |
61 /// ----+----+----+----+----+----+----+----+----+----+----+----+---->
62 /// slot 0 1 2 3 4 5 ..... Time
63 ///
64 /// When reaching moment 5 (slot 5) we can get the list of expired
65 /// objects (all vectors from 0 to 5 OR-ed) : { 2,3,4,10,28,123 }
66 ///
67 /// </pre>
68 ///
69 template <class BV>
70 class CTimeLine
71 {
72 public:
73  typedef BV TBitVector;
74  typedef deque<TBitVector*> TTimeLine;
75 
76 public:
77  /// @param discr_factor
78  /// Time discretization factor (seconds), discretization defines
79  /// time line precision.
80  /// @param tm
81  /// Initial time. (if 0 current time is taken)
82  CTimeLine(unsigned discr_factor, time_t tm);
83 
84  void ReInit(time_t tm = 0);
85 
86  ~CTimeLine();
87 
88  /// Add object to the timeline
89  /// @param tm
90  /// Moment in time associated with the object
91  /// @param object_id
92  /// Objects id
93  void AddObject(time_t tm, unsigned object_id);
94 
95  void AddObjects(time_t tm, const TBitVector& objects);
96 
97  /// Remove object from the time line, object_time defines time slot
98  /// @return true if object has been removed, false if object is not
99  /// in the specified timeline
100  bool RemoveObject(time_t object_time, unsigned object_id);
101 
102  /// Find and remove object
103  void RemoveObject(unsigned object_id);
104 
105  /// Move object from one time slot to another
106  void MoveObject(time_t old_time, time_t new_time, unsigned object_id);
107 
108  /// Extracts all objects up to 'tm' and puts them into 'objects' vector.
109  /// Objects inserted into 'tm' are not extracted to provide histeresis.
110  void ExtractObjects(time_t tm, TBitVector* objects);
111 
112  /// Enumerate all objects registered in the timeline
113  void EnumerateObjects(TBitVector* objects) const;
114 
115  /// Return head of the timeline
116  time_t GetHead() const { return m_TimeLineHead; }
117 
118  /// Time discretization factor
119  unsigned GetDiscrFactor() const { return m_DiscrFactor; }
120 
121 private:
124  /// Add object to the timeline using time slot
125  void x_AddObjectToSlot(unsigned time_slot, unsigned object_id);
126  /// Compute slot position in the timeline
127  unsigned x_TimeLineSlot(time_t tm) const;
128 
129 private:
130  unsigned m_DiscrFactor; //< Discretization factor
131  time_t m_TimeLineHead; //< Timeline head time
132  TTimeLine m_TimeLine; //< timeline vector
133 };
134 
135 
136 
137 #define TIMELINE_ITERATE(Var, Cont) \
138  for ( typename TTimeLine::iterator Var = (Cont).begin(); Var != (Cont).end(); ++Var )
139 
140 #define TIMELINE_CONST_ITERATE(Var, Cont) \
141  for ( typename TTimeLine::const_iterator Var = (Cont).begin(); Var != (Cont).end(); ++Var )
142 
143 template<class BV>
144 CTimeLine<BV>::CTimeLine(unsigned discr_factor, time_t tm)
145 : m_DiscrFactor(discr_factor)
146 {
147  ReInit(tm);
148 }
149 
150 
151 template<class BV>
153 {
154  TIMELINE_ITERATE(it, m_TimeLine) {
155  TBitVector* bv = *it;
156  delete bv;
157  }
158 }
159 
160 
161 template<class BV>
162 void CTimeLine<BV>::ReInit(time_t tm)
163 {
164  TIMELINE_ITERATE(it, m_TimeLine) {
165  TBitVector* bv = *it;
166  delete bv;
167  }
168  if (tm == 0) {
169  tm = time(0);
170  }
171  m_TimeLine.resize(0);
172  m_TimeLineHead = (tm / m_DiscrFactor) * m_DiscrFactor;
173  m_TimeLine.push_back(0);
174 }
175 
176 
177 template<class BV>
178 void CTimeLine<BV>::AddObject(time_t object_time, unsigned object_id)
179 {
180  if (object_time < m_TimeLineHead) {
181  object_time = m_TimeLineHead;
182  }
183 
184  unsigned slot = x_TimeLineSlot(object_time);
185  x_AddObjectToSlot(slot, object_id);
186 }
187 
188 
189 template<class BV>
191 {
192 }
193 
194 
195 template<class BV>
196 void CTimeLine<BV>::x_AddObjectToSlot(unsigned slot, unsigned object_id)
197 {
198  while (slot >= m_TimeLine.size()) {
199  m_TimeLine.push_back(0);
200  }
201  TBitVector* bv = m_TimeLine[slot];
202  if (bv == 0) {
203  // TODO: Add class factory class to create TBitVector
204  // meanwhile use hardcoded bm::BM_GAP (faster and economical)
205  // (bm::BM_GAP is NOT defined for template bv)
206  bv = new TBitVector(bm::BM_GAP);
207  m_TimeLine[slot] = bv;
208  }
209  bv->set(object_id);
210 }
211 
212 
213 template<class BV>
214 bool CTimeLine<BV>::RemoveObject(time_t object_time, unsigned object_id)
215 {
216  if (object_time < m_TimeLineHead) {
217  return false;
218  }
219  unsigned slot = x_TimeLineSlot(object_time);
220  if (slot < m_TimeLine.size()) {
221  TBitVector* bv = m_TimeLine[slot];
222  if (!bv) {
223  return false;
224  }
225  bool changed = bv->set_bit(object_id, false);
226  if (changed) {
227  return true;
228  }
229  }
230  return false;
231 }
232 
233 
234 template<class BV>
235 void CTimeLine<BV>::RemoveObject(unsigned object_id)
236 {
237  TIMELINE_ITERATE(it, m_TimeLine) {
238  TBitVector* bv = *it;
239  if (bv) {
240  bool changed = bv->set_bit(object_id, false);
241  if (changed) {
242  return;
243  }
244  }
245  } // NON_CONST_ITERATE
246 }
247 
248 template<class BV>
250 {
251  TIMELINE_CONST_ITERATE(it, m_TimeLine) {
252  TBitVector* bv = *it;
253  if (bv) {
254  *objects |= *bv;
255  }
256  } // CONST_ITERATE
257 }
258 
259 template<class BV>
260 void CTimeLine<BV>::MoveObject(time_t old_time,
261  time_t new_time,
262  unsigned object_id)
263 {
264  bool removed = RemoveObject(old_time, object_id);
265  if (!removed) {
266  RemoveObject(object_id);
267  }
268  AddObject(new_time, object_id);
269 }
270 
271 
272 template<class BV>
273 unsigned CTimeLine<BV>::x_TimeLineSlot(time_t tm) const
274 {
275  //_ASSERT(tm >= m_TimeLineHead);
276 
277  if (tm <= m_TimeLineHead)
278  return 0;
279 
280  unsigned interval_head = (unsigned)((tm / m_DiscrFactor) * m_DiscrFactor);
281  unsigned diff = (unsigned)(interval_head - m_TimeLineHead);
282  return diff / m_DiscrFactor;
283 }
284 
285 
286 template<class BV>
288 {
289  _ASSERT(objects);
290 
291  unsigned slot = x_TimeLineSlot(tm);
292  for (unsigned i = 0; i < slot; ++i) {
293  if (m_TimeLine.size() == 0) {
294  ReInit(tm);
295  return;
296  }
297  const TBitVector* bv = m_TimeLine[0];
298  if (bv) {
299  *objects |= *bv;
300  delete bv;
301  }
302  m_TimeLine.pop_front();
303  }
304  m_TimeLineHead = m_TimeLineHead + slot * m_DiscrFactor;
305 }
306 
307 
308 
310 
311 #endif // UTIL_TIME_LINE__HPP
Constants, lookup tables and typedefs.
Timeline class for fast approximate time tracking.
Definition: time_line.hpp:71
void MoveObject(time_t old_time, time_t new_time, unsigned object_id)
Move object from one time slot to another.
Definition: time_line.hpp:260
void AddObject(time_t tm, unsigned object_id)
Add object to the timeline.
Definition: time_line.hpp:178
BV TBitVector
Definition: time_line.hpp:73
CTimeLine(unsigned discr_factor, time_t tm)
Definition: time_line.hpp:144
void AddObjects(time_t tm, const TBitVector &objects)
Definition: time_line.hpp:190
deque< TBitVector * > TTimeLine
Definition: time_line.hpp:74
bool RemoveObject(time_t object_time, unsigned object_id)
Remove object from the time line, object_time defines time slot.
Definition: time_line.hpp:214
void EnumerateObjects(TBitVector *objects) const
Enumerate all objects registered in the timeline.
Definition: time_line.hpp:249
void ExtractObjects(time_t tm, TBitVector *objects)
Extracts all objects up to 'tm' and puts them into 'objects' vector.
Definition: time_line.hpp:287
CTimeLine(const CTimeLine &)
unsigned m_DiscrFactor
Definition: time_line.hpp:130
time_t GetHead() const
Return head of the timeline.
Definition: time_line.hpp:116
unsigned x_TimeLineSlot(time_t tm) const
Compute slot position in the timeline.
Definition: time_line.hpp:273
void x_AddObjectToSlot(unsigned time_slot, unsigned object_id)
Add object to the timeline using time slot.
Definition: time_line.hpp:196
CTimeLine & operator=(const CTimeLine &)
TTimeLine m_TimeLine
Definition: time_line.hpp:132
void ReInit(time_t tm=0)
Definition: time_line.hpp:162
unsigned GetDiscrFactor() const
Time discretization factor.
Definition: time_line.hpp:119
time_t m_TimeLineHead
Definition: time_line.hpp:131
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:148
int i
Defines: CTimeFormat - storage class for time format.
#define _ASSERT
#define TIMELINE_CONST_ITERATE(Var, Cont)
Definition: time_line.hpp:140
#define TIMELINE_ITERATE(Var, Cont)
Definition: time_line.hpp:137
Modified on Sun Jul 14 04:58:36 2024 by modify_doxy.py rev. 669887