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-2017 Shark Development Team
15  *
16  * <BR><HR>
17  * This file is part of Shark.
18  * <http://shark-ml.org/>
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 
95 
96  /// number of columns
97  inline std::size_t width() const
98  { return m_width; }
99 
100  /// number of rows
101  inline std::size_t height() const
102  { return m_height; }
103 
104  /// obtain an element of the matrix
105  QpFloatType operator () (std::size_t row, std::size_t col) const
106  {
107  Row const& r = m_row[row];
108  for (std::size_t i=0; i<r.size; i++)
109  {
110  Entry const& e = r.entry[i];
111  if (e.index == col) return e.value;
112  }
113  return r.defaultvalue;
114  }
115 
116  /// obtain a row of the matrix
117  inline Row const& row(std::size_t row) const
118  { return m_row[row]; }
119 
120  /// set the default value, that is, the value
121  /// of all implicitly defined elements of a row
122  inline void setDefaultValue(std::size_t row, QpFloatType defaultvalue)
123  { m_row[row].defaultvalue = defaultvalue; }
124 
125  /// Set a specific value. Note that entries can not
126  /// be changed once they are added, and that adding
127  /// elements must be done row-wise, and in order
128  /// within each row. However, the order of rows does
129  /// not matter.
130  void add(std::size_t row, std::size_t col, QpFloatType value)
131  {
132  SIZE_CHECK(m_used < m_data.size());
133 
134  Row& r = m_row[row];
135  if (r.entry == NULL) r.entry = &m_data[m_used];
136  else SIZE_CHECK(r.entry + r.size == &m_data[m_used]);
137 
138  m_data[m_used].index = col;
139  m_data[m_used].value = value;
140  m_used++;
141  r.size++;
142  }
143 
144  void resize(std::size_t height,std::size_t width,std::size_t space){
145  m_width = width;
146  m_height = height;
147  m_used = 0;
148  m_data.resize(space);
149  m_row.resize(height);
150  memset(&m_row[0], 0, height * sizeof(Row));
151  }
152 
153 protected:
154  /// number of columns
155  std::size_t m_width;
156 
157  /// number of rows
158  std::size_t m_height;
159 
160  /// current total number of non-default components
161  std::size_t m_used;
162 
163  /// storage for Entry structures
164  std::vector<Entry> m_data;
165 
166  /// storage for Row structures
167  std::vector<Row> m_row;
168 };
169 
170 
171 } // namespace shark
172 #endif