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 }