10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: sameeragarwal@google.com (Sameer Agarwal) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_INTERNAL_BLOCK_RANDOM_ACCESS_SPARSE_MATRIX_H_ 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#define CERES_INTERNAL_BLOCK_RANDOM_ACCESS_SPARSE_MATRIX_H_ 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <set> 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <vector> 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <utility> 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/mutex.h" 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/block_random_access_matrix.h" 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/collections_port.h" 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/triplet_sparse_matrix.h" 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/integral_types.h" 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/macros.h" 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h" 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/scoped_ptr.h" 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/types.h" 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 5079397c21138f54fcff6ec067b44b847f1f7e0e98Carlos Hernandez// A thread safe square block sparse implementation of 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// BlockRandomAccessMatrix. Internally a TripletSparseMatrix is used 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// for doing the actual storage. This class augments this matrix with 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// an unordered_map that allows random read/write access. 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass BlockRandomAccessSparseMatrix : public BlockRandomAccessMatrix { 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // blocks is an array of block sizes. block_pairs is a set of 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // <row_block_id, col_block_id> pairs to identify the non-zero cells 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // of this matrix. 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong BlockRandomAccessSparseMatrix(const vector<int>& blocks, 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const set<pair<int, int> >& block_pairs); 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The destructor is not thread safe. It assumes that no one is 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // modifying any cells when the matrix is being destroyed. 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual ~BlockRandomAccessSparseMatrix(); 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // BlockRandomAccessMatrix Interface. 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual CellInfo* GetCell(int row_block_id, 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int col_block_id, 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* row, 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* col, 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* row_stride, 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* col_stride); 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // This is not a thread safe method, it assumes that no cell is 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // locked. 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual void SetZero(); 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Since the matrix is square, num_rows() == num_cols(). 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int num_rows() const { return tsm_->num_rows(); } 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int num_cols() const { return tsm_->num_cols(); } 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Access to the underlying matrix object. 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const TripletSparseMatrix* matrix() const { return tsm_.get(); } 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong TripletSparseMatrix* mutable_matrix() { return tsm_.get(); } 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong private: 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int64 IntPairToLong(int a, int b) { 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong return a * kMaxRowBlocks + b; 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const int64 kMaxRowBlocks; 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // row/column block sizes. 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const vector<int> blocks_; 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // A mapping from <row_block_id, col_block_id> to the position in 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // the values array of tsm_ where the block is stored. 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong typedef HashMap<long int, CellInfo* > LayoutType; 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong LayoutType layout_; 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The underlying matrix object which actually stores the cells. 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<TripletSparseMatrix> tsm_; 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong friend class BlockRandomAccessSparseMatrixTest; 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CERES_DISALLOW_COPY_AND_ASSIGN(BlockRandomAccessSparseMatrix); 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_INTERNAL_BLOCK_RANDOM_ACCESS_SPARSE_MATRIX_H_ 111