dali/internal/update/touch/history.h

   1 #ifndef __DALI_INTERNAL_HISTORY_H__
   2 #define __DALI_INTERNAL_HISTORY_H__
   3
   4 //
   5 // Copyright (c) 2014 Samsung Electronics Co., Ltd.
   6 //
   7 // Licensed under the Flora License, Version 1.0 (the License);
   8 // you may not use this file except in compliance with the License.
   9 // You may obtain a copy of the License at
  10 //
  11 //     http://floralicense.org/license/
  12 //
  13 // Unless required by applicable law or agreed to in writing, software
  14 // distributed under the License is distributed on an AS IS BASIS,
  15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 // See the License for the specific language governing permissions and
  17 // limitations under the License.
  18 //
  19
  20 // EXTERNAL INCLUDES
  21 #include <set>
  22 #include <limits>
  23
  24 // INTERNAL INCLUDES
  25 #include <dali/public-api/common/dali-common.h>
  26 #include <dali/public-api/math/vector2.h>
  27
  28 namespace Dali
  29 {
  30
  31 namespace Internal
  32 {
  33
  34 /**
  35  * HistoryPair
  36  * represents a key-value element in the HistoryContainer
  37  */
  38 template<class T>
  39 struct HistoryPairType
  40 {
  41 public:
  42
  43   HistoryPairType(float firstValue)
  44   : first(firstValue)
  45   {
  46   }
  47
  48   HistoryPairType(float firstValue, T secondValue)
  49   : first(firstValue),
  50     second(secondValue)
  51   {
  52   }
  53
  54   bool operator<(const HistoryPairType& rhs) const
  55   {
  56     return first < rhs.first;
  57   }
  58
  59   float first;
  60   T second;
  61 };
  62
  63 /**
  64  * History container.
  65  * This container is used for keeping a list of element pairs while providing an API that can
  66  * generate interpolated values of requested elements that lie between two stored elements.
  67  *
  68  * e.g. stored values:
  69  *
  70  * 1.0 - 10
  71  * 2.0 - 30
  72  * 3.0 - 50
  73  *
  74  * Requesting value at key 1.5 will use the adjacent stored keys (1.0 and 2.0) to return an
  75  * interpolated value of 20.0 (i.e. 0.5 of the way between 10 and 30).
  76  *
  77  * Requesting value at key 2.9 will use the adjacent stored keys (2.0 and 3.0) to return an
  78  * interpolated value of 48.0 (i.e. 0.9 of the way between 30 and 50)
  79  */
  80 class History
  81 {
  82   typedef HistoryPairType<Vector2> HistoryPair;
  83   typedef std::set<HistoryPair> HistoryContainer;
  84   typedef HistoryContainer::iterator HistoryContainerIter;
  85
  86 public:
  87
  88   /**
  89    * History constructor
  90    */
  91   History()
  92   : mMaxSize(std::numeric_limits<size_t>::max())
  93   {
  94   }
  95
  96   /**
  97    * History destructor
  98    */
  99   ~History()
 100   {
 101   }
 102
 103   /**
 104    * Sets the maximum size of the history container in terms of elements stored, default is no limit
 105    * @param[in] maxSize The maximum number of elements stored in container
 106    */
 107   void SetMaxSize(size_t maxSize)
 108   {
 109     mMaxSize = maxSize;
 110
 111     if(mHistory.size() > mMaxSize)
 112     {
 113       // determine reduction in history size, and remove these elements
 114       size_t reduction = mHistory.size() - mMaxSize;
 115
 116       while(reduction--)
 117       {
 118         mHistory.erase(mHistory.begin() );
 119       }
 120     }
 121   }
 122
 123   void Clear()
 124   {
 125     mHistory.clear();
 126   }
 127
 128   /**
 129    * Adds an element (y) to the container at position (x)
 130    *
 131    * @param[in] x Key position value to add
 132    * @param[in] y Value to add at Key.
 133    */
 134   void Add(float x, const Vector2& y)
 135   {
 136     if(mHistory.size() >= mMaxSize)
 137     {
 138       RemoveTail();
 139     }
 140
 141     mHistory.insert(HistoryPair(x,y));
 142   }
 143
 144   /**
 145    * Removes first element in the container
 146    */
 147   void RemoveTail()
 148   {
 149     mHistory.erase(mHistory.begin());
 150   }
 151
 152   /**
 153    * Retrieves value from the history using key (x).
 154    * If the requested key (x) lies between two points, a linearly interpolated value between the two
 155    * points is returned.
 156    *
 157    * @param[in] x Key position to retrieve
 158    *
 159    * @return The interpolated Value is returned for this position.
 160    */
 161   Vector2 Get(float x) const
 162   {
 163     HistoryContainerIter i = mHistory.lower_bound(x);
 164
 165     if(i == mHistory.end())
 166     {
 167       --i;
 168     }
 169
 170     // For samples based on first point, just return position.
 171     if(i == mHistory.begin())
 172     {
 173       return i->second;
 174     }
 175
 176     // within begin() ... end() range
 177     float x2 = i->first;
 178     Vector2 y2 = i->second;
 179
 180     --i;
 181     float x1 = i->first;
 182     Vector2 y1 = i->second;
 183
 184     // For samples based on first 2 points, just use linear interpolation
 185     // TODO: Should really perform quadratic interpolation whenever there are 3+
 186     // points.
 187     if(i == mHistory.begin())
 188     {
 189       return y1 + (y2 - y1) * (x - x1) / (x2 - x1);
 190     }
 191
 192     // For samples based elsewhere, always use quadratic interpolation.
 193     --i;
 194     float x0 = i->first;
 195     Vector2 y0 = i->second;
 196
 197     if(i != mHistory.begin())
 198     {
 199       --i;
 200       float xn = i->first;
 201       Vector2 yn = i->second;
 202
 203       x2 = (x2 + x1) * 0.5f;
 204       x1 = (x1 + x0) * 0.5f;
 205       x0 = (xn + x0) * 0.5f;
 206
 207       y2 = (y2 + y1) * 0.5f;
 208       y1 = (y1 + y0) * 0.5f;
 209       y0 = (yn + y0) * 0.5f;
 210     }
 211     // Quadratic equation:
 212
 213     // y = ax^2 + bx + c
 214     // by making touches relative to x0, y0 (i.e. x0 = 0, y0 = 0)
 215     // we get c = 0, and equation becomes:
 216     // y = ax^2 + bx
 217     // 1) Y1 = a . X1^2 + b X1
 218     // 2) Y2 = a . X2^2 + b X2
 219     // solving simulatenous equations gets:
 220
 221     // make time (x) & position (y) relative to x0, y0
 222     y1 -= y0;
 223     y2 -= y0;
 224     x1 -= x0;
 225     x2 -= x0;
 226
 227     x -= x0;
 228
 229     Vector2 a = ( y1 - (y2 * x1) / x2 ) / (x1 * (x1 - x2) );
 230     Vector2 b = ( y1 / x1 ) - (a * x1);
 231
 232     return a * x * x + b * x + y0;
 233   }
 234
 235   /**
 236    * Retrieves a value from the history relative to the head.
 237    *
 238    * @note If the Keys (x) in the history decrease in value the further back you go. Then a
 239    * negative deltaX value should be supplied to refer to these keys relative to the head key.
 240    *
 241    * @param[in] deltaX Key position to retrieve relative to head key
 242    *
 243    * @return The interpolated Value is returned for this relative position.
 244    */
 245   Vector2 GetRelativeToHead(float deltaX) const
 246   {
 247     HistoryContainerIter i = mHistory.end();
 248     --i;
 249     return Get(i->first + deltaX);
 250   }
 251
 252   /**
 253    * Retrieves the head time value.
 254    *
 255    * @retrun The head time value.
 256    */
 257   float GetHeadTime() const
 258   {
 259     HistoryContainerIter i = mHistory.end();
 260     if(i==mHistory.begin())
 261     {
 262       return 0.0f;
 263     }
 264     --i;
 265     return i->first;
 266   }
 267
 268   /**
 269    * Retrieves the head value.
 270    *
 271    * @return The head value.
 272    */
 273   Vector2 GetHead() const
 274   {
 275     HistoryContainerIter i = mHistory.end();
 276     if(i==mHistory.begin())
 277     {
 278       return Vector2();
 279     }
 280     --i;
 281     return i->second;
 282   }
 283
 284 private:
 285
 286   HistoryContainer mHistory;                ///< History container
 287   size_t mMaxSize;                          ///< Current maximum size of container
 288
 289 };
 290
 291 } // namespace Internal
 292
 293 } // namespace Dali
 294
 295 #endif // __DALI_INTERNAL_HISTORY_H__