QpSparseArray.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Special container for certain coefficients describing multi-class SVMs
6  *
7  *
8  *
9  *
10  * \author T. Glasmachers
11  * \date 2011
12  *
13  *
14  * \par Copyright 1995-2015 Shark Development Team
15  *
16  * <BR><HR>
17  * This file is part of Shark.
18  * <http://image.diku.dk/shark/>
19  *
20  * Shark is free software: you can redistribute it and/or modify
21  * it under the terms of the GNU Lesser General Public License as published
22  * by the Free Software Foundation, either version 3 of the License, or
23  * (at your option) any later version.
24  *
25  * Shark is distributed in the hope that it will be useful,
26  * but WITHOUT ANY WARRANTY; without even the implied warranty of
27  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28  * GNU Lesser General Public License for more details.
29  *
30  * You should have received a copy of the GNU Lesser General Public License
31  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
32  *
33  */
34 //===========================================================================
35 
36 
37 #ifndef SHARK_ALGORITHMS_QP_QPSPARSEARRAY_H
38 #define SHARK_ALGORITHMS_QP_QPSPARSEARRAY_H
39 
40 
42 #include <shark/Data/Dataset.h>
43 
44 
45 namespace shark {
46 
47 
48 /// \brief specialized container class for multi-class SVM problems
49 ///
50 /// \par
51 /// This sparse matrix container allows to explicitly store only those
52 /// entries of a matrix row that deviate from a row wise default value.
53 /// This allows for efficient storage of the "kernel modifiers"
54 /// used to encode dual multi-class support vector machine problems.
55 template<class QpFloatType>
57 {
58 public:
59  /// \brief Non-default (non-zero) array entry.
60  ///
61  /// \par
62  /// Data structure describing a non-default
63  /// (typically non-zero) entry of a row.
64  struct Entry
65  {
66  std::size_t index;
67  QpFloatType value;
68  };
69 
70  /// \brief Data structure describing a row of the sparse array.
71  struct Row
72  {
74  std::size_t size;
75  QpFloatType defaultvalue;
76  };
77 
78  /// Constructor. The space parameter is an upper limit
79  /// on the number of non-default (aka non-zero) entries
80  /// of the array.
82  std::size_t height,
83  std::size_t width,
84  std::size_t space)
85  : m_width(width)
86  , m_height(height)
87  , m_used(0)
88  , m_data(space)
89  , m_row(height)
90  {
91  memset(&m_row[0], 0, height * sizeof(Row));
92  }
93 
94  /// number of columns
95  inline std::size_t width() const
96  { return m_width; }
97 
98  /// number of rows
99  inline std::size_t height() const
100  { return m_height; }
101 
102  /// obtain an element of the matrix
103  QpFloatType operator () (std::size_t row, std::size_t col) const
104  {
105  Row const& r = m_row[row];
106  for (std::size_t i=0; i<r.size; i++)
107  {
108  Entry const& e = r.entry[i];
109  if (e.index == col) return e.value;
110  }
111  return r.defaultvalue;
112  }
113 
114  /// obtain a row of the matrix
115  inline Row const& row(std::size_t row) const
116  { return m_row[row]; }
117 
118  /// set the default value, that is, the value
119  /// of all implicitly defined elements of a row
120  inline void setDefaultValue(std::size_t row, QpFloatType defaultvalue)
121  { m_row[row].defaultvalue = defaultvalue; }
122 
123  /// Set a specific value. Note that entries can not
124  /// be changed once they are added, and that adding
125  /// elements must be done row-wise, and in order
126  /// within each row. However, the order of rows does
127  /// not matter.
128  void add(std::size_t row, std::size_t col, QpFloatType value)
129  {
130  SHARK_CHECK(m_used < m_data.size(), "[QpSparseArray::add] insufficient storage space");
131 
132  Row& r = m_row[row];
133  if (r.entry == NULL) r.entry = &m_data[m_used];
134  else SHARK_CHECK(r.entry + r.size == &m_data[m_used], "[QpSparseArray::add] data must be added row-wise");
135 
136  m_data[m_used].index = col;
137  m_data[m_used].value = value;
138  m_used++;
139  r.size++;
140  }
141 
142 protected:
143  /// number of columns
144  std::size_t m_width;
145 
146  /// number of rows
147  std::size_t m_height;
148 
149  /// current total number of non-default components
150  std::size_t m_used;
151 
152  /// storage for Entry structures
153  std::vector<Entry> m_data;
154 
155  /// storage for Row structures
156  std::vector<Row> m_row;
157 };
158 
159 
160 } // namespace shark
161 #endif