1// Ceres Solver - A fast non-linear least squares minimizer
2// Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
3// http://code.google.com/p/ceres-solver/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are met:
7//
8// * Redistributions of source code must retain the above copyright notice,
9//   this list of conditions and the following disclaimer.
10// * Redistributions in binary form must reproduce the above copyright notice,
11//   this list of conditions and the following disclaimer in the documentation
12//   and/or other materials provided with the distribution.
13// * Neither the name of Google Inc. nor the names of its contributors may be
14//   used to endorse or promote products derived from this software without
15//   specific prior written permission.
16//
17// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27// POSSIBILITY OF SUCH DAMAGE.
28//
29// Author: sameeragarwal@google.com (Sameer Agarwal)
30//
31// Interface for matrices that allow block based random access.
32
33#ifndef CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_
34#define CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_
35
36#include "ceres/mutex.h"
37
38namespace ceres {
39namespace internal {
40
41// A matrix implementing the BlockRandomAccessMatrix interface is a
42// matrix whose rows and columns are divided into blocks. For example
43// the matrix A:
44//
45//            3     4      5
46//  A =  5 [c_11  c_12  c_13]
47//       4 [c_21  c_22  c_23]
48//
49// has row blocks of size 5 and 4, and column blocks of size 3, 4 and
50// 5. It has six cells corresponding to the six row-column block
51// combinations.
52//
53// BlockRandomAccessMatrix objects provide access to cells c_ij using
54// the GetCell method. when a cell is present, GetCell will return a
55// CellInfo object containing a pointer to an array which contains the
56// cell as a submatrix and a mutex that guards this submatrix. If the
57// user is accessing the matrix concurrently, it is his responsibility
58// to use the mutex to exclude other writers from writing to the cell
59// concurrently.
60//
61// There is no requirement that all cells be present, i.e. the matrix
62// itself can be block sparse. When a cell is not present, the GetCell
63// method will return a NULL pointer.
64//
65// There is no requirement about how the cells are stored beyond that
66// form a dense submatrix of a larger dense matrix. Like everywhere
67// else in Ceres, RowMajor storage assumed.
68//
69// Example usage:
70//
71//  BlockRandomAccessMatrix* A = new BlockRandomAccessMatrixSubClass(...)
72//
73//  int row, col, row_stride, col_stride;
74//  CellInfo* cell = A->GetCell(row_block_id, col_block_id,
75//                              &row, &col,
76//                              &row_stride, &col_stride);
77//
78//  if (cell != NULL) {
79//     MatrixRef m(cell->values, row_stride, col_stride);
80//     CeresMutexLock l(&cell->m);
81//     m.block(row, col, row_block_size, col_block_size) = ...
82//  }
83
84// Structure to carry a pointer to the array containing a cell and the
85// Mutex guarding it.
86struct CellInfo {
87  CellInfo()
88      : values(NULL) {
89  }
90
91  explicit CellInfo(double* ptr)
92      : values(ptr) {
93  }
94
95  double* values;
96  Mutex m;
97};
98
99class BlockRandomAccessMatrix {
100 public:
101  virtual ~BlockRandomAccessMatrix();
102
103  // If the cell (row_block_id, col_block_id) is present, then return
104  // a CellInfo with a pointer to the dense matrix containing it,
105  // otherwise return NULL. The dense matrix containing this cell has
106  // size row_stride, col_stride and the cell is located at position
107  // (row, col) within this matrix.
108  //
109  // The size of the cell is row_block_size x col_block_size is
110  // assumed known to the caller. row_block_size less than or equal to
111  // row_stride and col_block_size is upper bounded by col_stride.
112  virtual CellInfo* GetCell(int row_block_id,
113                            int col_block_id,
114                            int* row,
115                            int* col,
116                            int* row_stride,
117                            int* col_stride) = 0;
118
119  // Zero out the values of the array. The structure of the matrix
120  // (size and sparsity) is preserved.
121  virtual void SetZero() = 0;
122
123  // Number of scalar rows and columns in the matrix, i.e the sum of
124  // all row blocks and column block sizes respectively.
125  virtual int num_rows() const = 0;
126  virtual int num_cols() const = 0;
127};
128
129}  // namespace internal
130}  // namespace ceres
131
132#endif  // CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_
133