gmSparseVector.h

Go to the documentation of this file.

/************************************************************************
**
** Copyright (C) 2014 by Carlos Augusto Teixera Mendes
** All rights reserved.
**
** This file is part of the "GeMA" software. It's use should respect
** the terms in the license agreement that can be found together 
** with this source code.
** It is provided AS IS, with NO WARRANTY OF ANY KIND, 
** INCLUDING THE WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR 
** A PARTICULAR PURPOSE.
**
************************************************************************/

#ifndef _GEMA_SPARSE_VECTOR_H_
#define _GEMA_SPARSE_VECTOR_H_

#include "gmCoreConfig.h"

#include <QVarLengthArray>
#include <QHash>
#include <QLinkedList>
#include <QtAlgorithms>
#include <assert.h>


// IMPORTANT: None of the codes below is fit for multi-threaded access and can not be used 
//            in a value set data without locking!


template <class T> class GmHashSparseVector
{
public:
  const T at(int index, const T& defValue) const { return _data.value(index, defValue); }

  void insert(int index, const T& val) { _data.insert(index, val); }

  void remove(int index, const T& defValue) { Q_UNUSED(defValue); _data.remove(index); }

  void clear(int n, const T& defVal) { Q_UNUSED(n); Q_UNUSED(defVal); _data.clear(); }


private:
  QHash<int, T> _data;  
};

template <class T> class GmLinkedSparseVector
{
public:
  const T at(int index, const T& defValue) const 
  { 
    QLinkedList<QPair<int, T> >::const_iterator it = _data.constBegin();
    for(; it != _data.constEnd(); it++)
    {
      if(it->first == index)
        return it->second;
      else if(it->first > index)
        return defValue;
    }
    return defValue; 
  }

  void insert(int index, const T& val) 
  {  
    QLinkedList<QPair<int, T> >::iterator it = _data.begin();
    for(; it != _data.end(); it++)
    {
      if(it->first == index)
      {
        it->second = val;
        return;
      }
      else if(it->first > index)
      {
        _data.insert(it, qMakePair<int, T>(index, val));
        return;
      }
    }
    _data.insert(_data.end(), qMakePair<int, T>(index, val));
  }

  void remove(int index, const T& defValue) 
  { 
    Q_UNUSED(defValue); 
    QLinkedList<QPair<int, T> >::iterator it = _data.begin();
    for(; it != _data.end(); it++)
    {
      if(it->first == index)
      {
        _data.erase(it);
        return;
      }
      else if(it->first > index)
        return;
    }
  }

  void clear(int n, const T& defVal) { Q_UNUSED(n); Q_UNUSED(defVal); _data.clear(); }

private:
  QLinkedList<QPair<int, T> > _data;  
};


template <class T> class GmRleSparseVector
{
public:
  GmRleSparseVector()
  {
    _index.append(0);
  }

  const T at(int index, const T& defValue) const 
  { 
    Q_UNUSED(defValue);
    assert(index >= 0 && index < *(_index.end()-1));
    assert(_index.size() == _data.size() + 1);

    // Make it point to the smaller value in _index that is >= index
    // There is a sentinel at the end of _index with the highest valid index so 
    // a match will always be found
    QVarLengthArray<int, 16>::const_iterator it = qLowerBound(_index.constBegin(), _index.constEnd(), index);
    assert(it != _index.constEnd());  

    int itPos = it - _index.constBegin();

    if(*it == index)
      return _data.at(itPos);

    assert(*it > index);
    assert(itPos > 0);

    return _data.at(itPos - 1);
  }

  void insert(int index, const T& val) 
  { 
    assert(index >= 0 && index <= *(_index.end()-1));
    assert(_index.size() == _data.size() + 1);

    QVarLengthArray<int, 16>::iterator it;

    // Are we appending a new value to the vector?
    it = _index.end()-1; // it points to the sentinel with the array size
    if(index == *it)
    {
      if(!_data.isEmpty() && val == _data.last())
        *it = index + 1;
      else
      {
        _data.append(val);
        _index.append(index+1);
      }
#if defined ENABLE_TESTS || defined ENABLE_SPARSE_TESTS
      validateInternalStructure();
#endif
      return;
    }

    // No. We are CHANGING the value at an EXISTING index
    // Make 'it' point to the smaller value in _index that is >= index
    it = qLowerBound(_index.begin(), _index.end(), index);
    assert(it != _index.end());

    int itPos = it - _index.begin();

    if(*it == index)
    {
      if(_data[itPos] == val)
        return;

      assert(it+1 != _index.end()); // Since the queried index must be less than the sentinel

      if(*(it+1) == index + 1)
      {
        // No other index is sharing this value.  If it is equal to one (or both) of its 
        // neighbors, merge, else we can just store the new value.  We just have to be 
        // carefull to check if the next neighbor is not the sentinel...
        if(itPos+1 < _data.size() && _data[itPos+1] == val)
        {
          if(itPos > 0 && _data[itPos - 1] == val)
          {
            // New data is equal to both the next and previous index values.
            // Removes this value and the next one
            _index.erase(it, it+2);
            _data.remove(itPos, 2);
          }
          else
          {
            // New data is equal to the next value.  Removes this value and updates
            // the index for the next one
            *(it+1) = index;
            _index.erase(it);
            _data.remove(itPos);
          }
        }
        else if(itPos > 0 && _data[itPos - 1] == val)
        {
          // New data is the same as the data for the previous index. Just remove this value,
          // merging it with the previous one
          _index.erase(it);
          _data.remove(itPos);
        }
        else
          _data[itPos] = val;  // Value is different from both neighbors
      }
      else
      {
        // The current value is shared, so we must split it (unless the new value is 
        // equal to the value of the previous index in which case we just need to increase 
        // the current index)
        (*it)++;
        if(itPos == 0 || _data[itPos-1] != val)
        {
          _data.insert(itPos, val);
          _index.insert(it, index);
        }
      }
    }
    else
    {
      assert(*it > index);
      assert(itPos > 0);

      if(_data[itPos-1] == val)
        return;

      if(*it == index + 1)  
      {
        // The index is just one less than the next stored index, so we just have to insert
        // a single value pair (unless the value is equal to the next index, in which case 
        // suffices to update the stored index -- just be carefull that the next index might 
        // be the sentinel)
        if(itPos < _data.size() && _data[itPos] == val)
          *it = index;
        else
        {
          _data.insert(itPos, val);
          _index.insert(it, index);
        }
      }
      else
      {
        // Two values must be inserted... One to store (index, val) and the other for 
        // the previous value for the rest of the sequence
        _data.insert(itPos, _data[itPos-1]);
        it = _index.insert(it, index+1);
        _data.insert(itPos, val);
        _index.insert(it, index);
      }
    }
#if defined ENABLE_TESTS || defined ENABLE_SPARSE_TESTS
    validateInternalStructure();
#endif
  }

  void remove(int index, const T& defValue) { insert(index, defValue); }

  void clear(int n, const T& defVal) 
  { 
    _index.clear(); 
    _index.append(0); 
    _index.append(n);
    _data.clear();
    _data.append(defVal);
#if defined ENABLE_TESTS || defined ENABLE_SPARSE_TESTS
    validateInternalStructure();
#endif
  }

#if defined ENABLE_TESTS || defined ENABLE_SPARSE_TESTS
  void validateInternalStructure()
  {
    assert(_index.size() == _data.size() + 1);
    
    assert(_index[0] == 0);
    for(int i = 1, n = _index.size(); i<n; i++)
      assert(_index[i] > _index[i-1]);

    for(int i = 1, n = _data.size(); i<n; i++)
      assert(_data[i] != _data[i-1]);
  }
#endif

private:
  QVarLengthArray<int, 1> _index;  
  QVarLengthArray<T, 1>   _data;   
};




#endif