summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/svm/sparse_vector.h
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/svm/sparse_vector.h')
-rw-r--r--ml/dlib/dlib/svm/sparse_vector.h1170
1 files changed, 1170 insertions, 0 deletions
diff --git a/ml/dlib/dlib/svm/sparse_vector.h b/ml/dlib/dlib/svm/sparse_vector.h
new file mode 100644
index 000000000..c42723f89
--- /dev/null
+++ b/ml/dlib/dlib/svm/sparse_vector.h
@@ -0,0 +1,1170 @@
+// Copyright (C) 2009 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_SVm_SPARSE_VECTOR
+#define DLIB_SVm_SPARSE_VECTOR
+
+#include "sparse_vector_abstract.h"
+#include <cmath>
+#include <limits>
+#include "../algs.h"
+#include <vector>
+#include <map>
+#include "../graph_utils/edge_list_graphs.h"
+#include "../matrix.h"
+
+
+namespace dlib
+{
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename T, typename U>
+ typename T::value_type::second_type distance_squared (
+ const T& a,
+ const U& b
+ )
+ {
+ typedef typename T::value_type::second_type scalar_type;
+ typedef typename U::value_type::second_type scalar_typeU;
+ // Both T and U must contain the same kinds of elements
+ COMPILE_TIME_ASSERT((is_same_type<scalar_type, scalar_typeU>::value));
+
+ typename T::const_iterator ai = a.begin();
+ typename U::const_iterator bi = b.begin();
+
+ scalar_type sum = 0, temp = 0;
+ while (ai != a.end() && bi != b.end())
+ {
+ if (ai->first == bi->first)
+ {
+ temp = ai->second - bi->second;
+ ++ai;
+ ++bi;
+ }
+ else if (ai->first < bi->first)
+ {
+ temp = ai->second;
+ ++ai;
+ }
+ else
+ {
+ temp = bi->second;
+ ++bi;
+ }
+
+ sum += temp*temp;
+ }
+
+ while (ai != a.end())
+ {
+ sum += ai->second*ai->second;
+ ++ai;
+ }
+ while (bi != b.end())
+ {
+ sum += bi->second*bi->second;
+ ++bi;
+ }
+
+ return sum;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename U, typename V, typename W>
+ typename T::value_type::second_type distance_squared (
+ const V& a_scale,
+ const T& a,
+ const W& b_scale,
+ const U& b
+ )
+ {
+ typedef typename T::value_type::second_type scalar_type;
+ typedef typename U::value_type::second_type scalar_typeU;
+ // Both T and U must contain the same kinds of elements
+ COMPILE_TIME_ASSERT((is_same_type<scalar_type, scalar_typeU>::value));
+
+ typename T::const_iterator ai = a.begin();
+ typename U::const_iterator bi = b.begin();
+
+ scalar_type sum = 0, temp = 0;
+ while (ai != a.end() && bi != b.end())
+ {
+ if (ai->first == bi->first)
+ {
+ temp = a_scale*ai->second - b_scale*bi->second;
+ ++ai;
+ ++bi;
+ }
+ else if (ai->first < bi->first)
+ {
+ temp = a_scale*ai->second;
+ ++ai;
+ }
+ else
+ {
+ temp = b_scale*bi->second;
+ ++bi;
+ }
+
+ sum += temp*temp;
+ }
+
+ while (ai != a.end())
+ {
+ sum += a_scale*a_scale*ai->second*ai->second;
+ ++ai;
+ }
+ while (bi != b.end())
+ {
+ sum += b_scale*b_scale*bi->second*bi->second;
+ ++bi;
+ }
+
+ return sum;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename U>
+ typename T::value_type::second_type distance (
+ const T& a,
+ const U& b
+ )
+ {
+ return std::sqrt(distance_squared(a,b));
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename U, typename V, typename W>
+ typename T::value_type::second_type distance (
+ const V& a_scale,
+ const T& a,
+ const W& b_scale,
+ const U& b
+ )
+ {
+ return std::sqrt(distance_squared(a_scale,a,b_scale,b));
+ }
+
+// ------------------------------------------------------------------------------------
+ // ------------------------------------------------------------------------------------
+
+ template <typename T, typename EXP>
+ typename enable_if<is_matrix<T> >::type assign (
+ T& dest,
+ const matrix_exp<EXP>& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(src),
+ "\t void assign(dest,src)"
+ << "\n\t the src matrix must be a row or column vector"
+ );
+
+ dest = src;
+ }
+
+ template <typename T, typename EXP>
+ typename disable_if<is_matrix<T> >::type assign (
+ T& dest,
+ const matrix_exp<EXP>& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(src),
+ "\t void assign(dest,src)"
+ << "\n\t the src matrix must be a row or column vector"
+ );
+
+ dest.clear();
+ typedef typename T::value_type item_type;
+ for (long i = 0; i < src.size(); ++i)
+ {
+ dest.insert(dest.end(),item_type(i, src(i)));
+ }
+ }
+
+ template <typename T, typename U>
+ typename disable_if_c<is_matrix<T>::value || is_matrix<U>::value>::type assign (
+ T& dest, // sparse
+ const U& src // sparse
+ )
+ {
+ dest.assign(src.begin(), src.end());
+ }
+
+ template <typename T, typename U, typename Comp, typename Alloc, typename S>
+ typename disable_if<is_matrix<S> >::type assign (
+ std::map<T,U,Comp,Alloc>& dest, // sparse
+ const S& src // sparse
+ )
+ {
+ dest.clear();
+ dest.insert(src.begin(), src.end());
+ }
+
+// ------------------------------------------------------------------------------------
+ // ------------------------------------------------------------------------------------
+
+ template <typename T>
+ struct has_unsigned_keys
+ {
+ static const bool value = is_unsigned_type<typename T::value_type::first_type>::value;
+ };
+
+// ------------------------------------------------------------------------------------
+
+ namespace impl
+ {
+ template <typename T, typename U>
+ typename T::value_type::second_type general_dot (
+ const T& a,
+ const U& b
+ )
+ {
+ typedef typename T::value_type::second_type scalar_type;
+
+ typename T::const_iterator ai = a.begin();
+ typename U::const_iterator bi = b.begin();
+
+ scalar_type sum = 0;
+ while (ai != a.end() && bi != b.end())
+ {
+ if (ai->first == bi->first)
+ {
+ sum += ai->second * bi->second;
+ ++ai;
+ ++bi;
+ }
+ else if (ai->first < bi->first)
+ {
+ ++ai;
+ }
+ else
+ {
+ ++bi;
+ }
+ }
+
+ return sum;
+ }
+
+ template <typename T, typename U>
+ inline typename T::value_type::second_type dot (
+ const T& a,
+ const U& b
+ )
+ {
+ return general_dot(a,b);
+ }
+
+ template <typename T, typename U, typename alloc>
+ U dot (
+ const std::vector<std::pair<T,U>,alloc>& a,
+ const std::vector<std::pair<T,U>,alloc>& b
+ )
+ {
+ // You are getting this error because you are attempting to use sparse sample vectors
+ // but you aren't using an unsigned integer as your key type in the sparse vectors.
+ COMPILE_TIME_ASSERT(is_unsigned_type<T>::value);
+
+ if (a.size() == 0 || b.size() == 0)
+ return 0;
+
+ // if a is really a dense vector but just represented in a sparse container
+ if (a.back().first == a.size()-1)
+ {
+ double sum = 0;
+ for (unsigned long i = 0; i < b.size(); ++i)
+ {
+ if (b[i].first >= a.size())
+ break;
+ sum += a[b[i].first].second * b[i].second;
+ }
+ return sum;
+ }
+ // if b is really a dense vector but just represented in a sparse container
+ else if (b.back().first == b.size()-1)
+ {
+ double sum = 0;
+ for (unsigned long i = 0; i < a.size(); ++i)
+ {
+ if (a[i].first >= b.size())
+ break;
+ sum += b[a[i].first].second * a[i].second;
+ }
+ return sum;
+ }
+ else
+ {
+ return general_dot(a,b);
+ }
+ }
+ }
+
+ template <typename T>
+ inline typename T::value_type::second_type dot (
+ const T& a,
+ const T& b
+ )
+ {
+ return impl::dot(a,b);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5, typename T6>
+ inline T4 dot (
+ const std::vector<T1,T2>& a,
+ const std::map<T3,T4,T5,T6>& b
+ )
+ {
+ return impl::dot(a,b);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5, typename T6>
+ inline T4 dot (
+ const std::map<T3,T4,T5,T6>& a,
+ const std::vector<T1,T2>& b
+ )
+ {
+ return impl::dot(a,b);
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename EXP>
+ typename T::value_type::second_type dot (
+ const T& a,
+ const matrix_exp<EXP>& b
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(b),
+ "\t scalar_type dot(sparse_vector a, dense_vector b)"
+ << "\n\t 'b' must be a vector to be used in a dot product."
+ );
+
+ typedef typename T::value_type::second_type scalar_type;
+ typedef typename T::value_type::first_type first_type;
+
+ scalar_type sum = 0;
+ for (typename T::const_iterator ai = a.begin();
+ (ai != a.end()) && (ai->first < static_cast<first_type>(b.size()));
+ ++ai)
+ {
+ sum += ai->second * b(ai->first);
+ }
+
+ return sum;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename EXP>
+ typename T::value_type::second_type dot (
+ const matrix_exp<EXP>& b,
+ const T& a
+ )
+ {
+ return dot(a,b);
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename T::value_type::second_type length_squared (
+ const T& a
+ )
+ {
+ typedef typename T::value_type::second_type scalar_type;
+
+ typename T::const_iterator i;
+
+ scalar_type sum = 0;
+
+ for (i = a.begin(); i != a.end(); ++i)
+ {
+ sum += i->second * i->second;
+ }
+
+ return sum;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename T::value_type::second_type length (
+ const T& a
+ )
+ {
+ return std::sqrt(length_squared(a));
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, typename U>
+ typename disable_if<is_matrix<T>,void>::type scale_by (
+ T& a,
+ const U& value
+ )
+ {
+ for (typename T::iterator i = a.begin(); i != a.end(); ++i)
+ {
+ i->second *= value;
+ }
+ }
+
+ template <typename T, typename U>
+ typename enable_if<is_matrix<T>,void>::type scale_by (
+ T& a,
+ const U& value
+ )
+ {
+ a *= value;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename disable_if<is_matrix<T>,T>::type add (
+ const T& a,
+ const T& b
+ )
+ {
+ T temp;
+
+ typename T::const_iterator i = a.begin();
+ typename T::const_iterator j = b.begin();
+ while (i != a.end() && j != b.end())
+ {
+ if (i->first == j->first)
+ {
+ temp.insert(temp.end(), std::make_pair(i->first, i->second + j->second));
+ ++i;
+ ++j;
+ }
+ else if (i->first < j->first)
+ {
+ temp.insert(temp.end(), *i);
+ ++i;
+ }
+ else
+ {
+ temp.insert(temp.end(), *j);
+ ++j;
+ }
+ }
+
+ while (i != a.end())
+ {
+ temp.insert(temp.end(), *i);
+ ++i;
+ }
+ while (j != b.end())
+ {
+ temp.insert(temp.end(), *j);
+ ++j;
+ }
+
+ return temp;
+ }
+
+ template <typename T, typename U>
+ typename enable_if_c<is_matrix<T>::value && is_matrix<U>::value, matrix_add_exp<T,U> >::type add (
+ const T& a,
+ const U& b
+ )
+ {
+ return matrix_add_exp<T,U>(a.ref(),b.ref());
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename disable_if<is_matrix<T>,T>::type subtract (
+ const T& a,
+ const T& b
+ )
+ {
+ T temp;
+
+ typename T::const_iterator i = a.begin();
+ typename T::const_iterator j = b.begin();
+ while (i != a.end() && j != b.end())
+ {
+ if (i->first == j->first)
+ {
+ temp.insert(temp.end(), std::make_pair(i->first, i->second - j->second));
+ ++i;
+ ++j;
+ }
+ else if (i->first < j->first)
+ {
+ temp.insert(temp.end(), *i);
+ ++i;
+ }
+ else
+ {
+ temp.insert(temp.end(), std::make_pair(j->first, -j->second));
+ ++j;
+ }
+ }
+
+ while (i != a.end())
+ {
+ temp.insert(temp.end(), *i);
+ ++i;
+ }
+ while (j != b.end())
+ {
+ temp.insert(temp.end(), std::make_pair(j->first, -j->second));
+ ++j;
+ }
+
+ return temp;
+ }
+
+ template <typename T, typename U>
+ typename enable_if_c<is_matrix<T>::value && is_matrix<U>::value, matrix_subtract_exp<T,U> >::type subtract (
+ const T& a,
+ const U& b
+ )
+ {
+ return matrix_subtract_exp<T,U>(a.ref(),b.ref());
+ }
+
+// ------------------------------------------------------------------------------------
+// ------------------------------------------------------------------------------------
+
+ namespace impl
+ {
+ template <typename T>
+ typename enable_if<is_matrix<typename T::type>,unsigned long>::type max_index_plus_one (
+ const T& samples
+ )
+ {
+ if (samples.size() > 0)
+ return samples(0).size();
+ else
+ return 0;
+ }
+
+ template <typename T>
+ typename enable_if<is_built_in_scalar_type<typename T::type>,unsigned long>::type max_index_plus_one (
+ const T& sample
+ )
+ {
+ return sample.size();
+ }
+
+ // This !is_built_in_scalar_type<typename T::type>::value is here to avoid an inexplicable bug in Vistual Studio 2005
+ template <typename T>
+ typename enable_if_c<(!is_built_in_scalar_type<typename T::type>::value) && (is_pair<typename T::type::value_type>::value) ,unsigned long>::type
+ max_index_plus_one (
+ const T& samples
+ )
+ {
+ typedef typename T::type sample_type;
+ // You are getting this error because you are attempting to use sparse sample vectors
+ // but you aren't using an unsigned integer as your key type in the sparse vectors.
+ COMPILE_TIME_ASSERT(has_unsigned_keys<sample_type>::value);
+
+
+ // these should be sparse samples so look over all them to find the max index.
+ unsigned long max_dim = 0;
+ for (long i = 0; i < samples.size(); ++i)
+ {
+ if (samples(i).size() > 0)
+ max_dim = std::max<unsigned long>(max_dim, (--samples(i).end())->first + 1);
+ }
+
+ return max_dim;
+ }
+ }
+
+ template <typename T>
+ typename enable_if<is_pair<typename T::value_type>,unsigned long>::type max_index_plus_one (
+ const T& sample
+ )
+ {
+ if (sample.size() > 0)
+ return (--sample.end())->first + 1;
+ return 0;
+ }
+
+ template <typename T>
+ typename disable_if_c<is_pair<typename T::value_type>::value ||
+ is_same_type<typename T::value_type,sample_pair>::value ||
+ is_same_type<typename T::value_type,ordered_sample_pair>::value , unsigned long>::type
+ max_index_plus_one (
+ const T& samples
+ )
+ {
+ return impl::max_index_plus_one(mat(samples));
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP>
+ inline void add_to (
+ matrix<T,NR,NC,MM,L>& dest,
+ const matrix_exp<EXP>& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void add_to(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (long r = 0; r < src.size(); ++r)
+ dest(r) += src(r);
+ }
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP>
+ inline typename disable_if<is_matrix<EXP> >::type add_to (
+ matrix<T,NR,NC,MM,L>& dest,
+ const EXP& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void add_to(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (typename EXP::const_iterator i = src.begin(); i != src.end(); ++i)
+ dest(i->first) += i->second;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP, typename U>
+ inline void add_to (
+ matrix<T,NR,NC,MM,L>& dest,
+ const matrix_exp<EXP>& src,
+ const U& C
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void add_to(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (long r = 0; r < src.size(); ++r)
+ dest(r) += C*src(r);
+ }
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP, typename U>
+ inline typename disable_if<is_matrix<EXP> >::type add_to (
+ matrix<T,NR,NC,MM,L>& dest,
+ const EXP& src,
+ const U& C
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void add_to(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (typename EXP::const_iterator i = src.begin(); i != src.end(); ++i)
+ dest(i->first) += C*i->second;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP>
+ inline void subtract_from (
+ matrix<T,NR,NC,MM,L>& dest,
+ const matrix_exp<EXP>& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void subtract_from(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (long r = 0; r < src.size(); ++r)
+ dest(r) -= src(r);
+ }
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP>
+ inline typename disable_if<is_matrix<EXP> >::type subtract_from (
+ matrix<T,NR,NC,MM,L>& dest,
+ const EXP& src
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void subtract_from(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (typename EXP::const_iterator i = src.begin(); i != src.end(); ++i)
+ dest(i->first) -= i->second;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP, typename U>
+ inline void subtract_from (
+ matrix<T,NR,NC,MM,L>& dest,
+ const matrix_exp<EXP>& src,
+ const U& C
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void subtract_from(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (long r = 0; r < src.size(); ++r)
+ dest(r) -= C*src(r);
+ }
+
+ template <typename T, long NR, long NC, typename MM, typename L, typename EXP, typename U>
+ inline typename disable_if<is_matrix<EXP> >::type subtract_from (
+ matrix<T,NR,NC,MM,L>& dest,
+ const EXP& src,
+ const U& C
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(is_vector(dest) && max_index_plus_one(src) <= static_cast<unsigned long>(dest.size()),
+ "\t void subtract_from(dest,src)"
+ << "\n\t dest must be a vector large enough to hold the src vector."
+ << "\n\t is_vector(dest): " << is_vector(dest)
+ << "\n\t max_index_plus_one(src): " << max_index_plus_one(src)
+ << "\n\t dest.size(): " << dest.size()
+ );
+
+ for (typename EXP::const_iterator i = src.begin(); i != src.end(); ++i)
+ dest(i->first) -= C*i->second;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename T::value_type::second_type min (
+ const T& a
+ )
+ {
+ typedef typename T::value_type::second_type type;
+
+ type temp = 0;
+ for (typename T::const_iterator i = a.begin(); i != a.end(); ++i)
+ {
+ if (temp > i->second)
+ temp = i->second;
+ }
+ return temp;
+ }
+
+// ------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename T::value_type::second_type max (
+ const T& a
+ )
+ {
+ typedef typename T::value_type::second_type type;
+
+ type temp = 0;
+ for (typename T::const_iterator i = a.begin(); i != a.end(); ++i)
+ {
+ if (temp < i->second)
+ temp = i->second;
+ }
+ return temp;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ namespace impl
+ {
+ template <typename sparse_vector_type>
+ inline matrix<typename sparse_vector_type::value_type::second_type,0,1> sparse_to_dense (
+ const sparse_vector_type& vect,
+ unsigned long num_dimensions
+ )
+ {
+ // You must use unsigned integral key types in your sparse vectors
+ typedef typename sparse_vector_type::value_type::first_type idx_type;
+ typedef typename sparse_vector_type::value_type::second_type value_type;
+ COMPILE_TIME_ASSERT(is_unsigned_type<idx_type>::value);
+
+ matrix<value_type,0,1> result;
+
+ if (vect.size() == 0)
+ return result;
+
+ result.set_size(num_dimensions);
+ result = 0;
+
+ for (typename sparse_vector_type::const_iterator j = vect.begin(); j != vect.end(); ++j)
+ {
+ if ((long)(j->first) < result.size())
+ {
+ result(j->first) += j->second;
+ }
+ }
+
+ return result;
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename idx_type, typename value_type, typename alloc>
+ matrix<value_type,0,1> sparse_to_dense (
+ const std::vector<std::pair<idx_type,value_type>,alloc>& vect,
+ unsigned long num_dimensions
+ )
+ {
+ return impl::sparse_to_dense(vect,num_dimensions);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename idx_type, typename value_type, typename alloc>
+ matrix<value_type,0,1> sparse_to_dense (
+ const std::vector<std::pair<idx_type,value_type>,alloc>& vect
+ )
+ {
+ return impl::sparse_to_dense(vect, max_index_plus_one(vect));
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename T1, typename T2, typename T3, typename T4>
+ matrix<T2,0,1> sparse_to_dense (
+ const std::map<T1,T2,T3,T4>& vect,
+ unsigned long num_dimensions
+ )
+ {
+ return impl::sparse_to_dense(vect,num_dimensions);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename T1, typename T2, typename T3, typename T4>
+ matrix<T2,0,1> sparse_to_dense (
+ const std::map<T1,T2,T3,T4>& vect
+ )
+ {
+ return impl::sparse_to_dense(vect, max_index_plus_one(vect));
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename T>
+ typename enable_if<is_matrix<T>,T&>::type sparse_to_dense(
+ T& item
+ ) { return item; }
+
+ template <typename EXP>
+ matrix<typename EXP::type,0,1> sparse_to_dense(
+ const matrix_exp<EXP>& item,
+ unsigned long num
+ )
+ {
+ typedef typename EXP::type type;
+ if (item.size() == (long)num)
+ return item;
+ else if (item.size() < (long)num)
+ return join_cols(item, zeros_matrix<type>((long)num-item.size(),1));
+ else
+ return colm(item,0,(long)num);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename sample_type, typename alloc>
+ std::vector<matrix<typename sample_type::value_type::second_type,0,1> > sparse_to_dense (
+ const std::vector<sample_type, alloc>& samples,
+ unsigned long num_dimensions
+ )
+ {
+ typedef typename sample_type::value_type pair_type;
+ typedef typename pair_type::second_type value_type;
+
+ std::vector< matrix<value_type,0,1> > result;
+
+ // now turn all the samples into dense samples
+ result.resize(samples.size());
+
+ for (unsigned long i = 0; i < samples.size(); ++i)
+ {
+ result[i] = sparse_to_dense(samples[i],num_dimensions);
+ }
+
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename sample_type, typename alloc>
+ std::vector<matrix<typename sample_type::value_type::second_type,0,1> > sparse_to_dense (
+ const std::vector<sample_type, alloc>& samples
+ )
+ {
+ return sparse_to_dense(samples, max_index_plus_one(samples));
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T
+ >
+ T make_sparse_vector (
+ const T& v
+ )
+ {
+ // You must use unsigned integral key types in your sparse vectors
+ typedef typename T::value_type::first_type idx_type;
+ typedef typename T::value_type::second_type value_type;
+ COMPILE_TIME_ASSERT(is_unsigned_type<idx_type>::value);
+ std::map<idx_type,value_type> temp;
+ for (typename T::const_iterator i = v.begin(); i != v.end(); ++i)
+ {
+ temp[i->first] += i->second;
+ }
+
+ return T(temp.begin(), temp.end());
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T
+ >
+ void make_sparse_vector_inplace(
+ T& vect
+ )
+ {
+ vect = make_sparse_vector(vect);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename U,
+ typename alloc
+ >
+ void make_sparse_vector_inplace (
+ std::vector<std::pair<T,U>,alloc>& vect
+ )
+ {
+ if (vect.size() > 0)
+ {
+ std::sort(vect.begin(), vect.end());
+
+ // merge duplicates
+ for (unsigned long i = 1; i < vect.size(); ++i)
+ {
+ // if we found a duplicate
+ if (vect[i-1].first == vect[i].first)
+ {
+ // now start collapsing and merging the vector
+ unsigned long j = i-1;
+ for (unsigned long k = i; k < vect.size(); ++k)
+ {
+ if (vect[j].first == vect[k].first)
+ {
+ vect[j].second += vect[k].second;
+ }
+ else
+ {
+ ++j;
+ vect[j] = vect[k];
+ }
+ }
+
+
+ // we removed elements when we merged so we need to adjust the size.
+ vect.resize(j+1);
+ return;
+ }
+ }
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename EXP, typename T, long NR, long NC, typename MM, typename L>
+ void sparse_matrix_vector_multiply (
+ const std::vector<sample_pair>& edges,
+ const matrix_exp<EXP>& v,
+ matrix<T,NR,NC,MM,L>& result
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(max_index_plus_one(edges) <= (unsigned long)v.size() &&
+ is_col_vector(v),
+ "\t void sparse_matrix_vector_multiply()"
+ << "\n\t Invalid inputs were given to this function"
+ << "\n\t max_index_plus_one(edges): " << max_index_plus_one(edges)
+ << "\n\t v.size(): " << v.size()
+ << "\n\t is_col_vector(v): " << is_col_vector(v)
+ );
+
+ result.set_size(v.nr(),v.nc());
+ result = 0;
+
+ for (unsigned long k = 0; k < edges.size(); ++k)
+ {
+ const long i = edges[k].index1();
+ const long j = edges[k].index2();
+ const double d = edges[k].distance();
+
+ result(i) += v(j)*d;
+ if (i != j)
+ result(j) += v(i)*d;
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename EXP>
+ matrix<typename EXP::type,0,1> sparse_matrix_vector_multiply (
+ const std::vector<sample_pair>& edges,
+ const matrix_exp<EXP>& v
+ )
+ {
+ matrix<typename EXP::type,0,1> result;
+ sparse_matrix_vector_multiply(edges,v,result);
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename EXP, typename T, long NR, long NC, typename MM, typename L>
+ void sparse_matrix_vector_multiply (
+ const std::vector<ordered_sample_pair>& edges,
+ const matrix_exp<EXP>& v,
+ matrix<T,NR,NC,MM,L>& result
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(max_index_plus_one(edges) <= (unsigned long)v.size() &&
+ is_col_vector(v),
+ "\t void sparse_matrix_vector_multiply()"
+ << "\n\t Invalid inputs were given to this function"
+ << "\n\t max_index_plus_one(edges): " << max_index_plus_one(edges)
+ << "\n\t v.size(): " << v.size()
+ << "\n\t is_col_vector(v): " << is_col_vector(v)
+ );
+
+
+ result.set_size(v.nr(),v.nc());
+ result = 0;
+
+ for (unsigned long k = 0; k < edges.size(); ++k)
+ {
+ const long i = edges[k].index1();
+ const long j = edges[k].index2();
+ const double d = edges[k].distance();
+
+ result(i) += v(j)*d;
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <typename EXP>
+ matrix<typename EXP::type,0,1> sparse_matrix_vector_multiply (
+ const std::vector<ordered_sample_pair>& edges,
+ const matrix_exp<EXP>& v
+ )
+ {
+ matrix<typename EXP::type,0,1> result;
+ sparse_matrix_vector_multiply(edges,v,result);
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename EXP,
+ typename sparse_vector_type,
+ typename T,
+ long NR,
+ long NC,
+ typename MM,
+ typename L
+ >
+ void sparse_matrix_vector_multiply (
+ const matrix_exp<EXP>& m,
+ const sparse_vector_type& v,
+ matrix<T,NR,NC,MM,L>& result
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_ASSERT(max_index_plus_one(v) <= (unsigned long)m.nc(),
+ "\t void sparse_matrix_vector_multiply()"
+ << "\n\t Invalid inputs were given to this function"
+ << "\n\t max_index_plus_one(v): " << max_index_plus_one(v)
+ << "\n\t m.size(): " << m.size()
+ );
+
+ result.set_size(m.nr(),1);
+ result = 0;
+
+ for (typename sparse_vector_type::const_iterator i = v.begin(); i != v.end(); ++i)
+ {
+ for (long r = 0; r < result.nr(); ++r)
+ {
+ result(r) += m(r, i->first)*i->second;
+ }
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename EXP,
+ typename sparse_vector_type
+ >
+ matrix<typename EXP::type,0,1> sparse_matrix_vector_multiply (
+ const matrix_exp<EXP>& m,
+ const sparse_vector_type& v
+ )
+ {
+ matrix<typename EXP::type,0,1> result;
+ sparse_matrix_vector_multiply(m,v,result);
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_SVm_SPARSE_VECTOR
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-28 07:51:09 +0000