Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members

SparseBitmatrix.hpp

Go to the documentation of this file.
00001 /*
00002  * SparseBitmatrix.h
00003  *
00004  * Time-stamp: <05/06/01 12:40:26 lars>
00005  *
00006  * history: 2004/04/01  1.0  LST created.
00007  */
00008 
00009 #ifndef __SPARSE_BITMATRIX__
00010 #define __SPARSE_BITMATRIX__ t
00011 
00012 #include <iostream>
00013 using namespace std;
00014 
00015 #include "common/debug.hpp"
00016 // #include "LabeledSparseBitvector.hpp"
00017 #include "SparseBitvector.hpp"
00018 
00019 // FIXME should become template parameters
00020 typedef unsigned int ROW_T;
00021 
00030 class SparseBitmatrix {
00031  public:
00032   SparseBitmatrix(int numRows);
00033   SparseBitmatrix(int numRows, int rowCapacity);
00034   SparseBitmatrix(int numRows, int* rowCapacities);
00035   SparseBitmatrix(int numRows, int* rowCapacities, int* rowLabels);
00036   ~SparseBitmatrix();
00037 
00038   int nRows() const { return numRows; }
00039   void setNRows(int nRows) { 
00040     assert(nRows <= sizeRows);
00041     numRows = nRows; 
00042   }
00043   // int& rowLength(int row) { return rowLengths[row]; }
00044   int& rowLength(int row) const { 
00045     assert(row >= 0);
00046     assert(row < sizeRows);
00047     return rowLengths[row]; 
00048   }
00049   int* rowValues(int row) const { 
00050     assert(row >= 0);
00051     assert(row < sizeRows);
00052     return rows[row]; 
00053   }
00054   void setRowLength(int row, int length) { 
00055     assert(row >= 0);
00056     assert(row < sizeRows);
00057     assert(length >= 0);
00058     assert(length <= rowSizes[row]);
00059     rowLengths[row] = length; 
00060   }
00061   /*
00062   int& operator[] (int row, int position) { 
00063     assert(row >= 0);
00064     assert(row < numRows);
00065     assert(position >= 0);
00066     assert(position < rowSizes[row]);
00067     return rows[row][position]; 
00068   }
00069   */
00070   /*
00071   int element(int row, int position) {
00072     assert(row >= 0);
00073     assert(row < numRows);
00074     assert(position >= 0);
00075     assert(position < rowSizes[row]);
00076     return rows[row][position]; 
00077   }
00078   void setElement(int row, int position, int column) {
00079     assert(row >= 0);
00080     assert(row < numRows);
00081     assert(position >= 0);
00082     assert(position < rowSizes[row]);
00083     rows[row][position] = column; 
00084   }
00085   */
00086   void push_back(int row, int column) {
00087     assert(row >= 0);
00088     assert(row < numRows);
00089     assert(rowLengths[row] < rowSizes[row]);
00090     assert(rowLengths[row] == 0 || column > rows[row][rowLengths[row]-1]); // assert each row to be sorted in ascending order
00091     rows[row][rowLengths[row]++] = column;
00092   }
00093 
00094   int maxRowLength() const { return m_maxRowLength; }
00095   void setMaxRowLength(int maxRowLength) { this->m_maxRowLength = maxRowLength; }
00096   int computeMaxRowLength() { 
00097     m_maxRowLength = 0;
00098     for (int i = 0; i < numRows; i++)
00099       if (rowLengths[i] > m_maxRowLength)
00100         m_maxRowLength = rowLengths[i];
00101     return m_maxRowLength; 
00102   }
00103 
00104   ROW_T rowLabel(int row) const { 
00105     assert(row >= 0);
00106     assert(row < numRows);
00107     return rowLabels[row]; 
00108   }
00109   void setRowLabel(int row, ROW_T label) { 
00110     assert(row >= 0);
00111     assert(row < numRows);
00112     rowLabels[row] = label; 
00113   }
00114   ROW_T* getRowLabels() const { 
00115     return rowLabels; 
00116   }
00117 
00121   int capacity() const { return sizeRows; }
00122 
00126   int capacity(int row) const { 
00127     assert(row >= 0);
00128     assert(row < sizeRows);
00129     return rowSizes[row]; 
00130   }
00131 
00135   int* capacities() const { 
00136     return rowSizes;
00137   }
00138 
00145   SparseBitvector& getRow(int row) const {
00146     assert(row >= 0);
00147     assert(row < numRows);
00148 #if DEBUG_LEVEL > 0
00149     return *(new SparseBitvector(rows[row], rowLengths[row], rowSizes[row]));
00150 #else
00151     return *(new SparseBitvector(rows[row], rowLengths[row]));
00152 #endif
00153   }
00154 
00155   /*
00156   void getRow(int row, SparseBitvector& vector) const {
00157     assert(row >= 0);
00158     assert(row < numRows);
00159 #if DEBUG_LEVEL > 0
00160     vector.set(rows[row], rowLengths[row], rowSizes[row]);
00161 #else
00162     vector.set(rows[row], rowLengths[row]);
00163 #endif
00164   }
00165   */
00166 
00170   void computeEmpiricalDensity(long& numCells, long& numUsedCells) const;
00171 
00172   void dump() const;
00173   void dumpStructure() const;
00174   void sortRows();
00175 
00181   int SparseBitmatrix::filterMinimalRowLength(int minRowLength);
00182 
00183   int SparseBitmatrix::filterMinimalRowLength_destroyStructure(int minRowLength);
00184 
00189   void SparseBitmatrix::shiftRowStorage(int firstRow);  
00190 
00191   //#if USE_DYNAMIC_MEMORY_NODE_EXIT
00192   //private:
00193   //int rowshift;
00194   //#endif
00195 
00196 private:
00197   int numRows;
00198   int** rows;
00199   int m_maxRowLength;
00200   int* rowLengths;
00201   ROW_T* rowLabels;
00202 
00203   // size (i.e., allocated memory):
00204   int sizeRows;
00205   int* rowSizes;
00206 
00207   
00208 
00209 };
00210 
00211 #endif

Generated on Sun Sep 17 17:50:40 2006 for FIM environment by  doxygen 1.4.4