1  // [License]


2  // The AribaUnderlay Copyright


3  //


4  // Copyright (c) 20082009, Institute of Telematics, UniversitÃ€t Karlsruhe (TH)


5  //


6  // Institute of Telematics


7  // UniversitÃ€t Karlsruhe (TH)


8  // Zirkel 2, 76128 Karlsruhe


9  // Germany


10  //


11  // Redistribution and use in source and binary forms, with or without


12  // modification, are permitted provided that the following conditions are


13  // met:


14  //


15  // 1. Redistributions of source code must retain the above copyright


16  // notice, this list of conditions and the following disclaimer.


17  // 2. Redistributions in binary form must reproduce the above copyright


18  // notice, this list of conditions and the following disclaimer in the


19  // documentation and/or other materials provided with the distribution.


20  //


21  // THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND


22  // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE


23  // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR


24  // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OF TELEMATICS OR


25  // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,


26  // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,


27  // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR


28  // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF


29  // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING


30  // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS


31  // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


32  //


33  // The views and conclusions contained in the software and documentation


34  // are those of the authors and should not be interpreted as representing


35  // official policies, either expressed or implied, of the Institute of


36  // Telematics.


37  // [License]


38  #ifndef DISTANCES_HPP_


39  #define DISTANCES_HPP_


40 


41  /**


42  * TODO: Doc


43  *


44  * @author Sebastian Mies <mies@tm.uka.de>


45  */


46  namespace distances {


47 


48  /// returns the maximum value of a type


49  template<class T>


50  T max_value() {


51  return ~(T)0;


52  }


53 


54  /// returns the maximum value of a type


55  template<class T>


56  T min_value() {


57  return 0;


58  }


59 


60  /// euclidean distance between two points (metric)


61  struct default_distance {


62  template<typename T>


63  T operator ()(const T& x, const T& y) {


64  return abs(x  y);


65  }


66  };


67 


68  /// xor distance (metric)


69  struct xor_distance {


70  template<typename T>


71  T operator()(const T& x, const T& y) {


72  return x ^ y;


73  }


74  };


75 


76  /// distance between two points on a ring (metric)


77  struct ring_distance {


78  template<typename T>


79  T operator()(const T& x, const T& y) {


80  const T m = max_value<T>();


81  T d_nor = (x >= y) ? (xy) : (yx);


82  T d_inv = m  d_nor;


83  return d_nor < d_inv ? d_nor : d_inv;


84  }


85  };


86 


87  /// distance from x to a predecessor y on a ring (not a metric!)


88  struct ring_pred_distance {


89  template<typename T>


90  T operator ()(const T& x, const T& y) {


91  const T m = max_value<T>();


92  if (x >= y) return x  y;


93  else return m  y + x;


94  }


95  };


96 


97  /// distance from x to a successor y on a ring (not a metric!)


98  struct ring_succ_distance {


99  template<typename T>


100  T operator ()(const T& y, const T& x) {


101  const T m = max_value<T>();


102  if (x >= y) return x  y;


103  else return m  y + x;


104  }


105  };


106 


107  }


108 


109  #endif /* DISTANCES_HPP_ */

