Tapkee
covertree_point.hpp
Go to the documentation of this file.
00001 /* * This program is free software; you can redistribute it and/or modify
00002  * it under the terms of the GNU General Public License as published by
00003  * the Free Software Foundation; either version 3 of the License, or
00004  * (at your option) any later version.
00005  *
00006  * Written (W) 2012 Fernando José Iglesias García
00007  * Written (W) John Langford and Dinoj Surendran, v_array and its templatization
00008  * Copyright (C) 2012 Fernando José Iglesias García
00009  */
00010 
00011 #ifndef _JL_COVERTREE_POINT_H_
00012 #define _JL_COVERTREE_POINT_H_
00013 
00014 /* Tapkee includes */
00015 #include <tapkee/defines.hpp>
00016 /* End of Tapkee includes */
00017 
00018 #include <iostream>
00019 #include <cmath>
00020 
00021 namespace tapkee
00022 {
00023 namespace tapkee_internal
00024 {
00025 
00027 template<class T> 
00028 class v_array{
00029 
00030     public:
00033         T last() { return elements[index-1];}
00034 
00036         void decr() { index--;}
00037 
00039         v_array() : index(0), length(0), elements(NULL) {}
00040 
00044         T& operator[](IndexType i) { return elements[i]; }
00045 
00046     public:
00048         int index;
00049 
00051         int length;
00052 
00054         T* elements;
00055 };
00056 
00063 template<class T> 
00064 void push(v_array<T>& v, const T &new_ele)
00065 {
00066     while(v.index >= v.length)
00067     {
00068         v.length = 2*v.length + 3;
00069         v.elements = (T *)realloc(v.elements,sizeof(T) * v.length);
00070     }
00071     v[v.index++] = new_ele;
00072 }
00073 
00080 template<class T> 
00081 void alloc(v_array<T>& v, int length)
00082 {
00083     v.elements = (T *)realloc(v.elements, sizeof(T) * length);
00084     v.length = length;
00085 }
00086 
00096 template<class T> 
00097 v_array<T> pop(v_array<v_array<T> > &stack)
00098 {
00099     if (stack.index > 0)
00100         return stack[--stack.index];
00101     else
00102         return v_array<T>();
00103 }
00104 
00110 template <class RandomAccessIterator>
00111 struct CoverTreePoint
00112 {
00113     CoverTreePoint() : iter_(), norm_(0.0)
00114     {
00115     };
00116     CoverTreePoint(const RandomAccessIterator& iter, ScalarType norm) :
00117         iter_(iter), norm_(norm)
00118     {
00119     };
00120 
00121     RandomAccessIterator iter_;
00122     ScalarType norm_;
00123 }; /* struct JLCoverTreePoint */
00124 
00125 template <class Type, class RandomAccessIterator, class Callback> 
00126 struct distance_impl;
00127 
00130 template <class RandomAccessIterator, class Callback>
00131 inline ScalarType distance(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
00132         const CoverTreePoint<RandomAccessIterator>& r, ScalarType upper_bound)
00133 {
00134     //assert(upper_bound>=0);
00135 
00136     if (l.iter_==r.iter_)
00137         return 0.0;
00138 
00139     return distance_impl<typename Callback::type,RandomAccessIterator,Callback>()(cb,l,r,upper_bound);
00140 }
00141 
00142 struct KernelType;
00143 
00144 template <class RandomAccessIterator, class Callback>
00145 struct distance_impl<KernelType,RandomAccessIterator,Callback>
00146 {
00147     inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
00148                                  const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
00149     {
00150         return std::sqrt(l.norm_ + r.norm_ - 2*cb(r.iter_,l.iter_));
00151     }
00152 };
00153 
00154 struct DistanceType;
00155 
00156 template <class RandomAccessIterator, class Callback>
00157 struct distance_impl<DistanceType,RandomAccessIterator,Callback>
00158 {
00159     inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
00160                                  const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
00161     {
00162         return cb(l.iter_,r.iter_);
00163     }
00164 };
00165 
00167 template <class RandomAccessIterator>
00168 void print(const CoverTreePoint<RandomAccessIterator>&)
00169 {
00170 }
00171 
00172 }
00173 }
00174 #endif /* _JL_COVERTREE_POINT_H_*/
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines