LCOV - code coverage report
Current view: top level - neighbors - covertree_point.hpp (source / functions) Hit Total Coverage
Test: clean.info Lines: 31 31 100.0 %
Date: 2013-05-24 Functions: 79 89 88.8 %
Branches: 48 68 70.6 %

           Branch data     Line data    Source code
       1                 :            : /* * This program is free software; you can redistribute it and/or modify
       2                 :            :  * it under the terms of the GNU General Public License as published by
       3                 :            :  * the Free Software Foundation; either version 3 of the License, or
       4                 :            :  * (at your option) any later version.
       5                 :            :  *
       6                 :            :  * Written (W) 2012 Fernando José Iglesias García
       7                 :            :  * Written (W) John Langford and Dinoj Surendran, v_array and its templatization
       8                 :            :  * Copyright (C) 2012 Fernando José Iglesias García
       9                 :            :  */
      10                 :            : 
      11                 :            : #ifndef _JL_COVERTREE_POINT_H_
      12                 :            : #define _JL_COVERTREE_POINT_H_
      13                 :            : 
      14                 :            : /* Tapkee includes */
      15                 :            : #include <tapkee/defines.hpp>
      16                 :            : /* End of Tapkee includes */
      17                 :            : 
      18                 :            : #include <iostream>
      19                 :            : #include <cmath>
      20                 :            : 
      21                 :            : namespace tapkee
      22                 :            : {
      23                 :            : namespace tapkee_internal
      24                 :            : {
      25                 :            : 
      26                 :            : /** @brief Class v_array taken directly from JL's implementation */
      27                 :            : template<class T> 
      28                 :            : class v_array{
      29                 :            : 
      30                 :            :         public:
      31                 :            :                 /** Getter for the the last element of the v_array
      32                 :            :                  *  @return the last element of the array */
      33                 :      27724 :                 T last() { return elements[index-1];}
      34                 :            : 
      35                 :            :                 /** Decrement the pointer to the last element */
      36                 :       1536 :                 void decr() { index--;}
      37                 :            : 
      38                 :            :                 /** Create an empty v_array */
      39                 :       8392 :                 v_array() : index(0), length(0), elements(NULL) {}
      40                 :            : 
      41                 :            :                 /** Element access operator
      42                 :            :                  *  @param i of the element to be read
      43                 :            :                  *  @return the corresponding element */
      44                 :     190864 :                 T& operator[](IndexType i) { return elements[i]; }
      45                 :            : 
      46                 :            :         public:
      47                 :            :                 /** Pointer to the last element of the v_array */
      48                 :            :                 int index;
      49                 :            : 
      50                 :            :                 /** Length of the v_array */
      51                 :            :                 int length;
      52                 :            : 
      53                 :            :                 /** Pointer to the beginning of the v_array elements */
      54                 :            :                 T* elements;
      55                 :            : };
      56                 :            : 
      57                 :            : /**
      58                 :            :  * Insert a new element at the end of the vector
      59                 :            :  *
      60                 :            :  * @param v vector
      61                 :            :  * @param new_ele element to insert
      62                 :            :  */
      63                 :            : template<class T> 
      64                 :      48301 : void push(v_array<T>& v, const T &new_ele)
      65                 :            : {
      66 [ +  + ][ +  + ]:      53612 :         while(v.index >= v.length)
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ +  + ][ +  + ]
         [ #  # ][ +  + ]
         [ +  + ][ #  # ]
         [ +  + ][ #  # ]
      67                 :            :         {
      68                 :       5311 :                 v.length = 2*v.length + 3;
      69                 :       5311 :                 v.elements = (T *)realloc(v.elements,sizeof(T) * v.length);
      70                 :            :         }
      71 [ #  # ][ -  + ]:      48301 :         v[v.index++] = new_ele;
                 [ -  + ]
      72                 :      48301 : }
      73                 :            : 
      74                 :            : /**
      75                 :            :  * Used to modify the capacity of the vector
      76                 :            :  *
      77                 :            :  * @param v vector
      78                 :            :  * @param length the new length of the vector
      79                 :            :  */
      80                 :            : template<class T> 
      81                 :        551 : void alloc(v_array<T>& v, int length)
      82                 :            : {
      83                 :        551 :         v.elements = (T *)realloc(v.elements, sizeof(T) * length);
      84                 :        551 :         v.length = length;
      85                 :        551 : }
      86                 :            : 
      87                 :            : /**
      88                 :            :  * Returns the vector previous to the pointed one in the stack of
      89                 :            :  * vectors and decrements the index of the stack. No memory is
      90                 :            :  * freed here. If there are no vectors stored in the stack, create
      91                 :            :  * and return a new empty vector
      92                 :            :  *
      93                 :            :  * @param stack of vectors
      94                 :            :  * @return the adequate vector according to the previous conditions
      95                 :            :  */
      96                 :            : template<class T> 
      97                 :       3528 : v_array<T> pop(v_array<v_array<T> > &stack)
      98                 :            : {
      99 [ +  + ][ +  + ]:       3528 :         if (stack.index > 0)
         [ +  + ][ #  # ]
         [ +  + ][ +  + ]
     100                 :       3159 :                 return stack[--stack.index];
     101                 :            :         else
     102                 :       3528 :                 return v_array<T>();
     103                 :            : }
     104                 :            : 
     105                 :            : /** @brief Class Point to use with John Langford's CoverTree. This
     106                 :            :  * class must have some associated functions defined (distance,
     107                 :            :  * and print, see below) so it can be used with the CoverTree
     108                 :            :  * implementation.
     109                 :            :  */
     110                 :            : template <class RandomAccessIterator>
     111                 :            : struct CoverTreePoint
     112                 :            : {
     113                 :       1209 :         CoverTreePoint() : iter_(), norm_(0.0)
     114                 :            :         {
     115                 :       1209 :         };
     116                 :        670 :         CoverTreePoint(const RandomAccessIterator& iter, ScalarType norm) :
     117                 :        670 :                 iter_(iter), norm_(norm)
     118                 :            :         {
     119                 :        670 :         };
     120                 :            : 
     121                 :            :         RandomAccessIterator iter_;
     122                 :            :         ScalarType norm_;
     123                 :            : }; /* struct JLCoverTreePoint */
     124                 :            : 
     125                 :            : template <class Type, class RandomAccessIterator, class Callback> 
     126                 :            : struct distance_impl;
     127                 :            : 
     128                 :            : /** Functions declared out of the class definition to respect CoverTree 
     129                 :            :  *  structure */
     130                 :            : template <class RandomAccessIterator, class Callback>
     131                 :      19126 : inline ScalarType distance(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
     132                 :            :                 const CoverTreePoint<RandomAccessIterator>& r, ScalarType upper_bound)
     133                 :            : {
     134                 :            :         //assert(upper_bound>=0);
     135                 :            : 
     136 [ +  + ][ +  + ]:      19126 :         if (l.iter_==r.iter_)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     137                 :        670 :                 return 0.0;
     138                 :            : 
     139                 :      19126 :         return distance_impl<typename Callback::type,RandomAccessIterator,Callback>()(cb,l,r,upper_bound);
     140                 :            : }
     141                 :            : 
     142                 :            : struct KernelType;
     143                 :            : 
     144                 :            : template <class RandomAccessIterator, class Callback>
     145                 :            : struct distance_impl<KernelType,RandomAccessIterator,Callback>
     146                 :            : {
     147                 :       9807 :         inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
     148                 :            :                                  const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
     149                 :            :         {
     150                 :       9807 :                 return std::sqrt(l.norm_ + r.norm_ - 2*cb(r.iter_,l.iter_));
     151                 :            :         }
     152                 :            : };
     153                 :            : 
     154                 :            : struct DistanceType;
     155                 :            : 
     156                 :            : template <class RandomAccessIterator, class Callback>
     157                 :            : struct distance_impl<DistanceType,RandomAccessIterator,Callback>
     158                 :            : {
     159                 :       8649 :         inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
     160                 :            :                                  const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
     161                 :            :         {
     162                 :       8649 :                 return cb(l.iter_,r.iter_);
     163                 :            :         }
     164                 :            : };
     165                 :            : 
     166                 :            : /** Print the information of the CoverTree point */
     167                 :            : template <class RandomAccessIterator>
     168                 :            : void print(const CoverTreePoint<RandomAccessIterator>&)
     169                 :            : {
     170                 :            : }
     171                 :            : 
     172                 :            : }
     173                 :            : }
     174                 :            : #endif /* _JL_COVERTREE_POINT_H_*/

Generated by: LCOV version 1.9