core/vnl/vnl_crs_index.cxx
Go to the documentation of this file.
00001 // This is core/vnl/vnl_crs_index.cxx
00002 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00003 #pragma implementation
00004 #endif
00005 //:
00006 // \file
00007 // \author Matt Leotta (Brown)
00008 // \date   April 13, 2005
00009 
00010 #include "vnl_crs_index.h"
00011 
00012 //: Constructor - from a binary mask
00013 vnl_crs_index::vnl_crs_index(const vcl_vector<vcl_vector<bool> >& mask)
00014  : num_cols_(mask[0].size()), col_idx_(), row_ptr_(mask.size()+1,0)
00015 {
00016   int k=0;
00017   for (unsigned int i=0; i<mask.size(); ++i){
00018     const vcl_vector<bool>& col = mask[i];
00019     row_ptr_[i] = k;
00020     for (unsigned int j=0; j<num_cols_; ++j){
00021       if (col[j]){
00022         col_idx_.push_back(j);
00023         ++k;
00024       }
00025     }
00026   }
00027   row_ptr_[mask.size()] = k;
00028 }
00029 
00030 
00031 //: return the index at location (i,j)
00032 //  returns -1 if the entry is 0
00033 int
00034 vnl_crs_index::operator() (int i, int j) const
00035 {
00036   int low = row_ptr_[i];
00037   int high = row_ptr_[i+1]-1;
00038 
00039   // binary search for finding the element at column j
00040   while (low<=high){
00041     if (j<col_idx_[low] || j>col_idx_[high])
00042       return -1; // element is zero (no index)
00043 
00044     int mid = (low+high)>>1; //(low+high)/2;
00045     if (j<(int)col_idx_[mid])
00046         high = mid-1;
00047     else if (j>(int)col_idx_[mid])
00048         low=mid+1;
00049     else
00050       return mid;
00051   }
00052 
00053   return -1; // element is zero (no index)
00054 }
00055 
00056 
00057 //: returns row \p i as a vector of index-column pairs
00058 vnl_crs_index::sparse_vector
00059 vnl_crs_index::sparse_row(int i) const
00060 {
00061   sparse_vector row;
00062   for (int j=row_ptr_[i]; j<row_ptr_[i+1]; ++j){
00063     row.push_back(idx_pair(j,col_idx_[j]));
00064   }
00065   return row;
00066 }
00067 
00068 
00069 //: returns column \p j as a vector of index-row pairs
00070 // \note because of CRS this method is a bit less efficient than sparse_row
00071 vnl_crs_index::sparse_vector
00072 vnl_crs_index::sparse_col(int j) const
00073 {
00074   sparse_vector col;
00075   for (int i=0; i<num_rows(); ++i){
00076     int idx = (*this)(i,j);
00077     if (idx >= 0)
00078       col.push_back(idx_pair(idx,i));
00079   }
00080 
00081   return col;
00082 }