SparseBitmatrix.cpp

Go to the documentation of this file.

/*
 * SparseBitmatrix.cpp
 *
 * Time-stamp: <05/05/30 10:04:56 lars>
 *
 * history: 2004/04/01  1.0  LST created.
 */

#include "common/debug.hpp"
#include "SparseBitmatrix.hpp"
// #include "Sorting.h"

#include <iostream>
using namespace std;

SparseBitmatrix::SparseBitmatrix(int numRows) {
#if DEBUG_LEVEL>=20
  cerr << endl << "!SBc " << numRows << " x ?" << endl;
#endif

  this->numRows = numRows;
  rows = new (int*)[numRows];
  this->rowLengths = new int[numRows];
  this->rowLabels = new ROW_T[numRows];
  rowSizes = new int[numRows];
  this->m_maxRowLength = 0;
  sizeRows = numRows;
#if USE_DYNAMIC_MEMORY_NODE_EXIT
  rowshift = 0;
#endif
}


SparseBitmatrix::SparseBitmatrix(int numRows, int rowCapacity) {
#if DEBUG_LEVEL>=20
  cerr << endl << "!SBc " << numRows << " x " << rowCapacity << endl;
#endif

  this->numRows = numRows;
  rows = new (int*)[numRows];
  this->rowLengths = new int[numRows];
  this->rowLabels = new ROW_T[numRows];
  rowSizes = new int[numRows];
  for (int i = 0; i < numRows;  i++) {
    int len = rowCapacity;
    // this->rowLengths[i] = len;
    this->rowLengths[i] = 0;
    rowSizes[i] = len;
    this->rowLabels[i] = i; // -1; 
    rows[i] = new int[len];
  }
  // this->m_maxRowLength = rowLength;
  this->m_maxRowLength = 0;
  sizeRows = numRows;
#if USE_DYNAMIC_MEMORY_NODE_EXIT
  rowshift = 0;
#endif

}

SparseBitmatrix::SparseBitmatrix(int numRows, int* rowCapacities) {
#if DEBUG_LEVEL>=20
  cerr << endl << "!SBdyn " << numRows << " x ";
  int min = numRows > 0 ? rowCapacities[0] : 0,
    max = min, sum = min;
  for (int i = 1; i < numRows; i++) {
    sum += rowCapacities[i];
    if (rowCapacities[i] < min)
      min = rowCapacities[i];
    else if (rowCapacities[i] > max)
      max = rowCapacities[i];
  }
  double mean = numRows > 0 ? sum * 1.0 / numRows : 0;
  cerr << "(" << min << "-" << max << "; " << mean << ")" << endl;
#endif

  this->numRows = numRows;
  rows = new (int*)[numRows];
  this->rowLengths = new int[numRows];
  this->rowLabels = new ROW_T[numRows];
  rowSizes = new int[numRows];
  this->m_maxRowLength = 0;
  for (int i = 0; i < numRows;  i++) {
    int len = rowCapacities[i];
    // this->rowLengths[i] = len;
    this->rowLengths[i] = 0;
    rowSizes[i] = len;
    this->rowLabels[i] = i; // -1; 
    rows[i] = new int[len];
    // if (len > m_maxRowLength)
    //  this->m_maxRowLength = len;
  }
  sizeRows = numRows;
#if USE_DYNAMIC_MEMORY_NODE_EXIT
  rowshift = 0;
#endif
}

SparseBitmatrix::SparseBitmatrix(int numRows, int* rowCapacities, int* rowLabels) {
#if DEBUG_LEVEL>=20
  cerr << endl << "!SBdyn " << numRows << " x ";
  int min = numRows > 0 ? rowCapacities[0] : 0,
    max = min, sum = min;
  for (int i = 1; i < numRows; i++) {
    sum += rowCapacities[i];
    if (rowCapacities[i] < min)
      min = rowCapacities[i];
    else if (rowCapacities[i] > max)
      max = rowCapacities[i];
  }
  double mean = numRows > 0 ? sum * 1.0 / numRows : 0;
  cerr << "(" << min << "-" << max << "; " << mean << ")" << endl;
#endif

  this->numRows = numRows;
  rows = new (int*)[numRows];
  this->rowLengths = new int[numRows];
  this->rowLabels = new ROW_T[numRows];
  rowSizes = new int[numRows];
  this->m_maxRowLength = 0;
  for (int i = 0; i < numRows;  i++) {
    int len = rowCapacities[i];
    rows[i] = new int[len];
    rowSizes[i] = len;
    // this->rowLengths[i] = len;
    this->rowLengths[i] = 0;
    this->rowLabels[i] = rowLabels[i];
    // if (len > m_maxRowLength)
    //  this->m_maxRowLength = len;
  }
  sizeRows = numRows;
#if USE_DYNAMIC_MEMORY_NODE_EXIT
  rowshift = 0;
#endif
}

SparseBitmatrix::~SparseBitmatrix() {
#if DEBUG_LEVEL >= 20
  cerr << endl << "~SB ... "; cerr.flush();
  cerr << " rows[" << sizeRows << "] "; cerr.flush();
#endif
  for (int i = 0; i < sizeRows; i++) {
    assert(rows[i] != NULL);
#if DEBUG_LEVEL >= 20
    cerr << i << " "; cerr.flush();
#endif
    delete[] rows[i];
  }
#if USE_DYNAMIC_MEMORY_NODE_EXIT && false
#if DEBUG_LEVEL >= 20
  cerr << " rows "; cerr.flush();
#endif
  delete[] &(rows[-rowshift]);
#if DEBUG_LEVEL >= 20
  cerr << " rowLengths "; cerr.flush();
#endif
  delete[] &(rowLengths[-rowshift]);
#if DEBUG_LEVEL >= 20
  cerr << " rowLabels "; cerr.flush();
#endif
  delete[] &(rowLabels[-rowshift]);
#if DEBUG_LEVEL >= 20
  cerr << " rowSizes "; cerr.flush();
#endif
  delete[] &(rowSizes[-rowshift]);
#else
#if DEBUG_LEVEL >= 20
  cerr << " rows "; cerr.flush();
#endif
  assert(rows != NULL);
  delete[] rows;
#if DEBUG_LEVEL >= 20
  cerr << " rowLengths "; cerr.flush();
#endif
  assert(rowLengths != NULL);
  delete[] rowLengths;
#if DEBUG_LEVEL >= 20
  cerr << " rowLabels "; cerr.flush();
#endif
  delete[] rowLabels;
#if DEBUG_LEVEL >= 20
  cerr << " rowSizes "; cerr.flush();
#endif
  delete[] rowSizes;
#endif
#if DEBUG_LEVEL >= 20
  cerr << " - done" << endl;
#endif
}

/*
void SparseBitmatrix::sortRows() {
  for (int i = 0; i < numRows; i++)
    quickSort(rows[i], 0, rowLengths[i]);
}
*/


void SparseBitmatrix::dump() const {
  cout << endl << "dump " << numRows << " x ";
  int min = numRows > 0 ? rowLengths[0] : 0,
    max = min, sum = min;
  for (int i = 1; i < numRows; i++) {
    sum += rowLengths[i];
    if (rowLengths[i] < min)
      min = rowLengths[i];
    else if (rowLengths[i] > max)
      max = rowLengths[i];
  }
  double mean = numRows > 0 ? sum * 1.0 / numRows : 0;

  int smin = sizeRows > 0 ? rowSizes[0] : 0,
    smax = smin, ssum = smin;
  for (int i = 1; i < sizeRows; i++) {
    ssum += rowSizes[i];
    if (rowSizes[i] < smin)
      smin = rowSizes[i];
    else if (rowSizes[i] > smax)
      smax = rowSizes[i];
  }
  double smean = sizeRows > 0 ? ssum * 1.0 / sizeRows : 0;
  cout << "(" << min << "-" << max << "; " << mean << " : "
       << sizeRows << " x " << smin << "-" << smax << "; " << smean << ")" << endl;

  for (int i = 0; i < numRows; i++) {
    cout << i << " \"" << rowLabels[i] << "\":";
    int* row = rows[i];
    int len = rowLengths[i];
    for (int j = 0; j < len; j++)
      cout << " " << row[j];
    cout << "\tlen= " << rowLengths[i] << ", size= " << rowSizes[i] << endl;
  }

  if (numRows == 0) {
    cout << "  sizes: ";
    for (int i = 0; i < sizeRows; i++)
      cout << rowSizes[i] << " ";
    cout << endl;
  }
}


void SparseBitmatrix::dumpStructure() const {
  cout << endl << "dump " << numRows << " x ";
  int min = numRows > 0 ? rowLengths[0] : 0,
    max = min, sum = min;
  for (int i = 1; i < numRows; i++) {
    sum += rowLengths[i];
    if (rowLengths[i] < min)
      min = rowLengths[i];
    else if (rowLengths[i] > max)
      max = rowLengths[i];
  }
  double mean = numRows > 0 ? sum * 1.0 / numRows : 0;

  int smin = sizeRows > 0 ? rowSizes[0] : 0,
    smax = smin, ssum = smin;
  for (int i = 1; i < sizeRows; i++) {
    ssum += rowSizes[i];
    if (rowSizes[i] < smin)
      smin = rowSizes[i];
    else if (rowSizes[i] > smax)
      smax = rowSizes[i];
  }
  double smean = sizeRows > 0 ? ssum * 1.0 / sizeRows : 0;
  cout << "(" << min << "-" << max << "; " << mean << " : "
       << sizeRows << " x " << smin << "-" << smax << "; " << smean << ")" << endl;
}



void SparseBitmatrix::computeEmpiricalDensity(long& numCells, long& numUsedCells) const {
  // 0. search for non-empty row:
  int i = 0; 
  while (i < numRows && rowLengths[i] == 0)
    ++i;
  if (i == numRows) {
    numCells = 0;
    numUsedCells = 0;
    return;
  }

  // 1. compute #used cells and range of values stored.
  numUsedCells += rowLengths[i];
  int min = rows[i][0], max = rows[i][rowLengths[i]-1]; // assume rows are sorted in ascending order.
  i++;
  for ( ; i < numRows; i++) {
    numUsedCells += rowLengths[i];
    if (rows[i][0] < min)
      min = rows[i][0];
    if (rows[i][rowLengths[i]-1] > max)
      max = rows[i][rowLengths[i]-1];
  }

  numCells += numRows * (max - min + 1);
}



int SparseBitmatrix::filterMinimalRowLength(int minRowLength) {
  int toi = 0;
  m_maxRowLength = 0;
  for (int i = 0; i < numRows; i++) {
    int rowlen = rowLengths[i];
    if (rowlen >= minRowLength) {
      assert(rowSizes[toi] >= rowlen);
      rowLabels[toi] = rowLabels[i];
      rowLengths[toi] = rowlen;
      int* rowFrom = rows[i];
      int* rowTo = rows[toi];
      for (int j = 0; j < rowlen; j++)
        rowTo[j] = rowFrom[j];
      toi++;
      if (rowlen > m_maxRowLength)
        m_maxRowLength = rowlen; 
    }
  }
  numRows = toi;
  return toi;
}


int SparseBitmatrix::filterMinimalRowLength_destroyStructure(int minRowLength) {
  int toi = 0;
  m_maxRowLength = 0;
  for (int i = 0; i < numRows; i++) {
    int rowlen = rowLengths[i];
    if (rowlen >= minRowLength) {
      rows[toi] = rows[i];
      rowLengths[toi] = rowLengths[i];
      rowSizes[toi] = rowSizes[i];
      rowLabels[toi] = rowLabels[i];
      toi++;
      if (rowlen > m_maxRowLength)
        m_maxRowLength = rowlen; 
    } else {
      delete[] rows[i];
    }
  }
  for (int i = toi; i < numRows; i++) 
    rows[i] = NULL; // added 31.8.2004
  numRows = toi;
  // sizeRows = toi; // added 31.8.2004
  return toi;
}

/*
void SparseBitmatrix::shiftRowStorage(int firstRow) {
  assert(firstRow == 1);
#if USE_DYNAMIC_MEMORY_NODE_EXIT
  cout << "shift [" << rowshift << " + " << firstRow << "] ... "; cout.flush();

  // a. delete all rows[]:
  for (int i = 0; i < sizeRows; i++) {
    assert(rows[i] != NULL);
    delete[] rows[i];
  }

  // b. reallocate all rows[]:
  for (int i = 0; i < sizeRows-1; i++) {
    rowSizes[i] = rowSizes[i+1];
    rows[i] = new int[rowSizes[i]];
    rowLengths[i] = 0;
  }
  rows[sizeRows-1] = new int[0];
  rowSizes[sizeRows-1] = 0;
  rowLengths[sizeRows-1] = 0;
  numRows = 0;

  cout << "ok" << endl;
#endif
}
*/

---