title: Functions to compress and uncompress array of integers
body: <p>I was recently asked to complete a task for a c++ role, however as the application was decided not to be progressed any further I thought that I would post here for some feedback / advice / improvements / reminder of concepts I've forgotten.</p>
  
  <p>The task was:</p>
  
  <p>The following data is a time series of integer values</p>
  
  <pre><code>int timeseries[32] = {67497, 67376, 67173, 67235, 67057, 67031, 66951,
  66974, 67042, 67025, 66897, 67077, 67082, 67033, 67019, 67149, 67044,
  67012, 67220, 67239, 66893, 66984, 66866, 66693, 66770, 66722, 66620,
  66579, 66596, 66713, 66852, 66715};
  </code></pre>
  
  <p>The series might be, for example, the closing price of a stock each day
  over a 32 day period.</p>
  
  <p>As stored above, the data will occupy <code>32 x sizeof(int) bytes = 128 bytes</code>
  assuming 4 byte ints.</p>
  
  <p>Using delta encoding , write a function to compress, and a function to
  uncompress data like the above.</p>
  
  <p>Ok, so before this point I had never looked at compression so my solution is far from perfect. The manner in which I approached the problem is by compressing the array of integers into a array of bytes. When representing the integer as a byte I keep the calculate most
  significant byte (msb) and keep everything up to this point, whilst throwing the rest away. This is then added to the byte array. For negative values I increment the msb by 1 so that we can
  differentiate between positive and negative bytes when decoding by keeping the leading
  1 bit values.</p>
  
  <p>When decoding I parse this jagged byte array and simply reverse my
  previous actions performed when compressing. As mentioned I have never looked at compression prior to this task so I did come up with my own method to compress the data. I was looking at C++/Cli recently, had not really used it previously so just decided to write it in this language, no particular reason. Below is the class, and a unit test at the very bottom. Any advice / improvements / enhancements will be much appreciated. </p>
  
  <p>Thanks.</p>
  
  <pre><code>array&lt;array&lt;Byte&gt;^&gt;^ CDeltaEncoding::CompressArray(array&lt;int&gt;^ data)
  {
      int temp = 0;
      int original;
      int size = 0;
  
      array&lt;int&gt;^ tempData = gcnew array&lt;int&gt;(data-&gt;Length);
      data-&gt;CopyTo(tempData, 0);
  
      array&lt;array&lt;Byte&gt;^&gt;^ byteArray = gcnew array&lt;array&lt;Byte&gt;^&gt;(tempData-&gt;Length);
  
      for (int i = 0; i &lt; tempData-&gt;Length; ++i)
      {
              original = tempData[i];
              tempData[i] -= temp;
              temp = original;
  
              int msb = GetMostSignificantByte(tempData[i]);
  
              byteArray[i] = gcnew array&lt;Byte&gt;(msb);
              System::Buffer::BlockCopy(BitConverter::GetBytes(tempData[i]), 0, byteArray[i], 0, msb );
  
              size += byteArray[i]-&gt;Length;
      }
  
      return byteArray;
  }
  
  array&lt;int&gt;^ CDeltaEncoding::DecompressArray(array&lt;array&lt;Byte&gt;^&gt;^ buffer)
  {
      System::Collections::Generic::List&lt;int&gt;^ decodedArray = gcnew System::Collections::Generic::List&lt;int&gt;();
  
      int temp = 0;
  
      for (int i = 0; i &lt; buffer-&gt;Length; ++i) 
      {
              int retrievedVal = GetValueAsInteger(buffer[i]);
              decodedArray-&gt;Add(retrievedVal);
  
              decodedArray[i] += temp;
              temp = decodedArray[i];
      }
  
      return decodedArray-&gt;ToArray();
  }
  
  int CDeltaEncoding::GetMostSignificantByte(int value)
  {
      array&lt;Byte&gt;^ tempBuf = BitConverter::GetBytes(Math::Abs(value));
  
      int msb = tempBuf-&gt;Length;
  
      for (int i = tempBuf-&gt;Length -1; i &gt;= 0; --i)
      {
              if (tempBuf[i] != 0)
              {
                      msb = i + 1;
                      break;
              }
      }
  
      if (!IsPositiveInteger(value))
      {
              //We need an extra byte to differentiate the negative integers
              msb++;
      }
  
      return msb;
  }
  
  bool CDeltaEncoding::IsPositiveInteger(int value)
  {
      return value / Math::Abs(value) == 1;
  }
  
  int CDeltaEncoding::GetValueAsInteger(array&lt;Byte&gt;^ buffer)
  {
      array&lt;Byte&gt;^ tempBuf;
  
      if(buffer-&gt;Length % 2 == 0)
      {
              //With even integers there is no need to allocate a new byte array
              tempBuf = buffer;
      }
      else
      {
              tempBuf = gcnew array&lt;Byte&gt;(4);
              System::Buffer::BlockCopy(buffer, 0, tempBuf, 0, buffer-&gt;Length );
  
              unsigned int val = buffer[buffer-&gt;Length-1] &amp;= 0xFF;
  
              if ( val == 0xFF )
              {
                      //We have negative integer compressed into 3 bytes
                      //Copy over the this last byte as well so we keep the negative pattern
                      System::Buffer::BlockCopy(buffer, buffer-&gt;Length-1, tempBuf, buffer-&gt;Length, 1 );
              }
      }
  
      switch(tempBuf-&gt;Length)
      {
      case sizeof(short):
              return BitConverter::ToInt16(tempBuf,0);
      case sizeof(int):
      default:
              return BitConverter::ToInt32(tempBuf,0);
      }
  }
  </code></pre>
  
  <p>And then in a test class I had:</p>
  
  <pre><code>void CTestDeltaEncoding::TestCompression()
  {
      array&lt;array&lt;Byte&gt;^&gt;^ byteArray = CDeltaEncoding::CompressArray(m_testdata);
  
      array&lt;int&gt;^ decompressedArray = CDeltaEncoding::DecompressArray(byteArray);
  
      int totalBytes = 0;
      for (int i = 0; i&lt;byteArray-&gt;Length; i++)
      {
              totalBytes += byteArray[i]-&gt;Length;
      }
  
      Assert::IsTrue(m_testdata-&gt;Length * sizeof(m_testdata) &gt; totalBytes, "Expected the total bytes to be less than the original array!!");
  
      //Expected totalBytes = 53
  }
  </code></pre>