(C++) std::vector stretch

A function that stretches a std::vector. In other words, it resize a std::vector but keeps the sum of its values equal.

+-------+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |
+-------+-----+-----+-----+-----+-----+
| v #1  | 1.0 | 2.0 | 3.0 |  .  |  .  | 
| v #2  | 0.6 | 0.8 | 1.2 | 1.6 | 1.8 |
+-------+-----+-----+-----+-----+-----+
v #1: original vector, size 3
v #2: resulting vector, size 5

If you know a more elegant implementation (I am sure there is), I hope you will E-mail me (or that you put it here as well).

include <vector>

include <cmath>

include <cassert>

include <numeric>


std::vector<double> stretch(const std::vector<double>& vOrig, const int& newSize)
{
  //Already at right size?
  const int oldSize = vOrig.size();
  if (oldSize == newSize) return vOrig;
  if (newSize < oldSize)
  {
    //Return vector needs to be schrunken
    std::vector<double> vNew(newSize,0.0);
    const double delta = static_cast<double>(newSize) / static_cast<double>(oldSize);
    assert(delta < 1.0);
    for (int i=0; i<oldSize; ++i)
    {
      const double iD = static_cast<double>(i);
      const int indexLeft  = std::floor(iD * delta);
      const int indexRight = std::floor((iD+1.0) * delta);
      assert(indexLeft  >= 0 && indexLeft  < static_cast<int>(vNew.size()) );
      if (indexLeft==indexRight || indexRight >= newSize)
      {
        const double value = vOrig[i];
        vNew[indexLeft]  += value;
      }
      else
      {
        const double propLeft  = (std::ceil(iD*delta) - (iD * delta)) / delta;
        assert(propLeft  >= -0.00001 && propLeft  <= 1.00001);
        const double propRight = (((iD + 1.0) * delta) - std::floor((iD+1.0)*delta)) / delta;
        assert(propRight >= -0.00001 && propRight <= 1.00001);
        assert( (propLeft+propRight) > 0.999 && (propLeft+propRight) < 1.0001 );
        const double valueLeft = vOrig[i] * propLeft;
        const double valueRight = vOrig[i] * propRight;
        vNew[indexLeft]  += valueLeft;
        vNew[indexRight] += valueRight;
      }
    }
    return vNew;
  }
  else
  {
    //Return vector needs to be stretched
    std::vector<double> vNew(newSize,0.0);
    const double delta = static_cast<double>(oldSize) / static_cast<double>(newSize);
    assert(delta < 1.0);
    for (int i=0; i<newSize; ++i)
    {
      const double iD = static_cast<double>(i);
      //We are going to write at vNew[i]
      //We need to read from vOrig, from the range [iD*delta, (iD+1.0)*delta >
      //This range might be divided over two indices
      const int indexLeft  = std::floor(iD * delta);
      const int indexRight = std::floor((iD+1.0) * delta);
      if (indexLeft==indexRight || indexRight >= static_cast<int>(vOrig.size()))
      {
        assert(indexLeft < static_cast<int>(vOrig.size()));
        vNew[i] = vOrig[indexLeft] * delta;
      }
      else
      {
        const double propLeft  = std::ceil(iD*delta) - (iD * delta);
        const double propRight = ((iD + 1.0) * delta) - std::floor((iD+1.0)*delta);
        assert( (propLeft+propRight) > (0.999 * delta) && (propLeft+propRight) < (1.0001 * delta) );
        assert(indexLeft < static_cast<int>(vOrig.size()));
        const double valueLeft = vOrig[indexLeft] * propLeft;
        assert(indexRight < static_cast<int>(vOrig.size()));
        const double valueRight = vOrig[indexRight] * propRight;
        const double valueTotal = (indexLeft == indexRight ? valueRight : valueLeft + valueRight);
        vNew[i] = valueTotal;
      }
    }
    return vNew;
  }
}
int main()
{
  const int size = 1 + (std::rand() % 100);
  std::vector<double> vOrig(size);
  for(int i=0; i!=size; ++i) vOrig[i] = static_cast<double>(std::rand() % 100);
  std::vector<double> vNew = stretch(vOrig,1 + (std::rand()%100));
  const double sumOrig = std::accumulate(vOrig.begin(),vOrig.end(),0.0);
  const double sumNew  = std::accumulate(vNew.begin() ,vNew.end() ,0.0);
  //A loose equivalent as floating point calculations do not have infinite precision
  assert( sumOrig > sumNew - 0.0001 && sumOrig < sumNew + 0.0001 );
}

Code links

last edited (November 18, 2006) by bilderbikkel, Number of views: 1401, Current Rev: 4 (Diff)

[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]