00001
00007 #include "SubsetDeltaGenerator.hpp"
00008 #include <cstddef>
00009 #include <cstring>
00010
00011 SubsetDeltaGenerator::SubsetDeltaGenerator( unsigned int n )
00012 {
00013 this->n = n;
00014 k = 0;
00015
00016 mCurrSubset = NULL;
00017 }
00018
00019 SubsetDeltaGenerator::~SubsetDeltaGenerator()
00020 {
00021 if( mCurrSubset != NULL )
00022 {
00023 delete [] mCurrSubset;
00024 }
00025 }
00026
00027 void SubsetDeltaGenerator::getDeltasForSubsetsOfFixedLength( unsigned int k, std::vector<SubsetDelta> & deltas )
00028 {
00029 this->k = k;
00030 mDeltas.clear();
00031
00032
00033 if( mCurrSubset != NULL )
00034 {
00035 delete [] mCurrSubset;
00036 mCurrSubset = NULL;
00037 }
00038
00039
00040
00041 mCurrSubset = new unsigned int[k];
00042 for( unsigned int i = 0; i < k; i++ )
00043 {
00044 mCurrSubset[i] = i;
00045 }
00046
00047
00048
00049 process( 1, 1 );
00050 forward( 1, 0 );
00051
00052
00053
00054 deltas = mDeltas;
00055 }
00056
00057
00058 void SubsetDeltaGenerator::forward( int pointer, int difference )
00059 {
00060 if( ( pointer < (int)k ) && ( difference - pointer < (int)n - (int)k - 1 ) )
00061 {
00062 forward( pointer + 2, difference + 2 );
00063 process( pointer + 1, n - k + pointer + 1 );
00064 reverse( pointer + 1, difference + 2 );
00065 process( pointer, difference + 2 );
00066 forward( pointer, difference + 1 );
00067 }
00068 else if( pointer == (int)k )
00069 {
00070 for( int i = difference + 2; i <= (int)n; i++ )
00071 {
00072 process( k, i );
00073 }
00074 }
00075 }
00076
00077
00078 void SubsetDeltaGenerator::reverse( int pointer, int difference )
00079 {
00080 if( ( pointer < (int)k ) && ( difference - pointer < (int)n - (int)k - 1 ) )
00081 {
00082 reverse( pointer, difference + 1 );
00083 process( pointer, difference + 1 );
00084 forward( pointer + 1, difference + 2 );
00085 process( pointer + 1, difference + 2 );
00086 reverse( pointer + 2, difference + 2 );
00087 }
00088 else if( pointer == (int)k )
00089 {
00090 for( int i = (int)n - 1; i >= difference + 1; i-- )
00091 {
00092 process( k, i );
00093 }
00094 }
00095 }
00096
00097
00098 void SubsetDeltaGenerator::process( int posChanged, int newValue )
00099 {
00100 SubsetDelta d;
00101 d.oldValue = mCurrSubset[posChanged - 1];
00102 d.newValue = newValue - 1;
00103 mDeltas.push_back( d );
00104
00105 mCurrSubset[posChanged - 1] = newValue - 1;
00106 }
00107