00001
00002
00003
00004
00005
00006
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
00017 #include "SparseBitvector.hpp"
00018
00019
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
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
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
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]);
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
00157
00158
00159
00160
00161
00162
00163
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
00192
00193
00194
00195
00196 private:
00197 int numRows;
00198 int** rows;
00199 int m_maxRowLength;
00200 int* rowLengths;
00201 ROW_T* rowLabels;
00202
00203
00204 int sizeRows;
00205 int* rowSizes;
00206
00207
00208
00209 };
00210
00211 #endif