Array function

[SwqGNwbp]

I need to write a function that would get a copy of an array and go through it to see which of the below conditions is satisfied by that array. function prototype is this :

unsigned g( const unsigned a[], unsigned elements );

No I/O. g returns a code in the range [0, 8) according to the data in a:
0: elements < 2, so no element has a predecessor.
e.g. {}
e.g. {1234}
1: elements >= 2, and every element is < its predecessor.
e.g. {10, 9, 2}
2: elements >= 2, and all the elements are equal.
e.g. {8, 8, 8, 8}
3: at least one element is < its predecessor, at least one element is == its predecessor, but no element is > its predecessor.
e.g. {10, 10, 8, 8, 5, 5, 5, 5, 3}
4: elements >= 2, and every element is > its predecessor.
e.g. {2, 4, 8, 16}
5: at least one element is < its predecessor, at least one element is > its predecessor, but no element is == its predecessor.
e.g. {3, 2, 3, 4}
6: at least one element is == its predecessor, at least one element is > its predecessor, but no elements is < its predecessor.
e.g. {5, 5, 10, 20}
7: at least one element is < its predecessor, at least one element is == its predecessor, and at least one element is > its predecessor.
e.g. {5, 4, 5, 5}
If I haven’t made a mistake, you should be able to convince yourself that every array will fall into exactly one of these 8 categories. g’s job is to return the number of that category.
For instance, g( {5, 4, 5, 5} should return 7

unsigned g( const unsigned a[], unsigned elements )
{
    if ( elements < 2 ) return ( 0 );

    enum { LT, EQ, GT };
    unsigned int count[3] = {};
    
    std::inner_product ( a, a + elements - 1, a + 1, count,
                        []( unsigned int *p, unsigned int i ) { return ( ++p[i], p ); },
                        []( int x, int y ) { return ( x < y ? LT : ( x == y ? EQ : GT ) ); } );

   if ( count[LT] == elements - 1 ) return ( 1 );
   else if ( count[EQ] == elements - 1 ) return ( 2 );
   else if ( count[LT] && count[EQ] && !count[GT] ) return ( 3 );
   else if ( count[LT] && count[EQ] && count[GT] ) return ( 7 );
   else throw ( die( "Unpredictable result." ) );

I'm getting compiler error in std::inner_product part. Any solution or substitution?

[abhishekm71]

One thing that comes to my notice is that in the function inner_product, the parameter "accumulator" should be an int rather than an array (count).

EDIT: Also,
1. Your 2nd paramter should be a + elements - 2, otherwise 'a + 1' shall go beyond bounds.
2. I'm not sure if inner_product is the correct function to use for such an application. As per the reference on this website, the function accumulates to a single value rather than accumulating to an array's elements.
http://www.cplusplus.com/reference/numeric/inner_product/?kw=inner_product

[SwqGNwbp]

Thanks for points. Could you fix this function or any other method to write it?

[abhishekm71]

Well for one, if you are not too much worried about time complexity, you can call the function thrice for each of LT, EQ and GT cases.

Something like,

std::inner_product ( a, a + elements - 2, a + 1, count[LT],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x < y ); } );
std::inner_product ( a, a + elements - 2, a + 1, count[EQ],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x == y ); } );
std::inner_product ( a, a + elements - 2, a + 1, count[GT],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x > y ); } );

Or you can manually iterate through the array and increment the count fields using a sequence of nested if else statements.

[SwqGNwbp]

unsigned g( const unsigned a[], unsigned elements )
{
    if ( elements < 2 ) return ( 0 );

    enum { LT, EQ, GT };
    unsigned int count[3] = {};
    
std::inner_product ( a, a + elements - 2, a + 1, count[LT],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x < y ); } );
std::inner_product ( a, a + elements - 2, a + 1, count[EQ],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x == y ); } );
std::inner_product ( a, a + elements - 2, a + 1, count[GT],
                        []( unsigned int x, unsigned int y ) { return ( x + y ); },
                        []( int x, int y ) { return ( x > y ); } );

   if ( count[LT] == elements - 1 ) return ( 1 );
   else if ( count[EQ] == elements - 1 ) return ( 2 );
   else if ( count[LT] && count[EQ] && !count[GT] ) return ( 3 );
   else if ( count[LT] && count[EQ] && count[GT] ) return ( 7 );
   else throw ( die( "Unpredictable result." ) );
}

This is compiler error:

c:\program files (x86)\microsoft visual studio 11.0\vc\include\numeric(204): error C4996: 'std::_Inner_product2': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'
1>          c:\program files (x86)\microsoft visual studio 11.0\vc\include\numeric(180) : see declaration of 'std::_Inner_product2'
1>          c:\users\behzad\documents\visual studio 2012\projects\hwex1\hwex1.cpp(167) : see reference to function template instantiation '_Ty std::inner_product<const unsigned int[],const unsigned int[],unsigned int,g::<lambda_496d58af4467a09d741271a93b561caa>,g::<lambda_f9f41d7fb7b9beb4d12bce88cc9a708c>>(_InIt1,_InIt1,_InIt2,_Ty,_Fn21,_Fn22)' being compiled
1>          with
1>          [
1>              _Ty=unsigned int,
1>              _InIt1=const unsigned int [],
1>              _InIt2=const unsigned int [],
1>              _Fn21=g::<lambda_496d58af4467a09d741271a93b561caa>,
1>              _Fn22=g::<lambda_f9f41d7fb7b9beb4d12bce88cc9a708c>
1>          ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

[abhishekm71]

Seems to be a type conversion error:

#include <iostream>     // std::cout
#include <functional>   // std::minus, std::divides
#include <numeric>      // std::inner_product

unsigned myaccumulator (unsigned x, unsigned y) {return x+y;}
unsigned myLessThan (unsigned x, unsigned y) {return x<y;}

int main () {
  unsigned init = 0;
  unsigned series1[] = {10,20,30};
  unsigned series2[] = {1,2,3};

  std::cout << "using default inner_product: ";
  std::cout << std::inner_product(series1,series1+3,series2,init);
  std::cout << '\n';


  std::cout << "using custom functions: ";
  std::cout << std::inner_product(series1,series1+2,series1 + 1,init,
                                  myaccumulator,myLessThan);
  std::cout << '\n';

  return 0;
}

Success	time: 0 memory: 3340 signal:0
using default inner_product: 140
using custom functions: 2

http://ideone.com/grH4rE

[abhishekm71]

Also, please note that the function does not modify the value of init. It just gives the output of the accumulator as the return value.

[SwqGNwbp]

Any idea how to write it without inner_product

[abhishekm71]

Why don't you simply iterate over your array and update the LT, EQ and GT fields using a sequence of if else statements?

for ( int i = 0; i < a.size() - 1; ++i ) {

  if ( a[i] > a[i+1] )
    count[GT]++;
  else   if ( a[i] == a[i+1] )
    count[EQ]++;
  else   if ( a[i] < a[i+1] )
    count[LT]++;

}

[keskiverto]

ben756 wrote:

Any idea how to write it without inner_product?

The reference documentation of std::inner_product, to which a link has already provided in an earlier comment, has a line:

The behavior of this function template is equivalent to

[D80DSL3A]

If I may, it matters only if each condition occurs once, so no need to keep count.
I think this would do:

bool LT=false, EQ=false, GT=false;
for ( int i = 0; i < a.size() - 1; ++i ) {
  if ( a[i+1] > a[i] ) // greater than predecessor    
    GT = true;  
  else if ( a[i+1] < a[i] )
    LT = true;
  else // only other possibility
    EQ = true;
}

Then, note how the return value depends on the values of LT, EQ and GT:

unsigned retVal = 0;
if( LT ) retVal = 1;
if( EQ ) retVal += 2;
if( GT ) retVal += 4;

EDIT: swapped lines 1 and 2.

[SwqGNwbp]

Why for every numbers it returns to 6?

unsigned g( const unsigned a[], unsigned elements )
{
	    if ( elements < 2 ) return ( 0 );

    enum { LT, EQ, GT };
    unsigned int count[3] = {};
	for ( int i = 0; i < elements - 1; ++i ) {
		bool LT=false, EQ=false, GT=false;
		if ( a[i+1] > a[i] ) GT = true;    
		else if ( a[i+1] < a[i] ) LT = true;
		else EQ = true;
}

unsigned retVal = 0;
if( LT ) retVal = 1;
if( EQ ) retVal += 2;
if( GT ) retVal += 4;
}

[D80DSL3A]

Oops! bool LT=false, EQ=false, GT=false; belongs outside (before) the for loop. My bad. I have corrected it above.

You're getting 6 with your code because the LT, EQ and GT in scope at line 15 on are those declared on line 5, which have the values 0,1 and 2 respectively. Lines 16 and 17 give a total of 6 for retVal.

[SwqGNwbp]

in a.size() there is a compiler error"Expression must have class type"

[keskiverto]

You did copy a code snipped, where 'a' is of container type that has member size(), and used it in context, where 'a' is a plain array. In your system, you have "elements" instead.

[SwqGNwbp]

This is my function:

unsigned g( const unsigned a[], unsigned elements )
{
bool LT=false, EQ=false, GT=false;
for ( unsigned i = 0; i < elements - 1; ++i ) {
  if ( a[i+1] > a[i] )   
    GT = true;  
  else if ( a[i+1] < a[i] )
    LT = true;
  else
    EQ = true;
}

unsigned retVal = 0;
if( LT ) retVal = 1;
if( EQ ) retVal += 2;
if( GT ) retVal += 4;

return retVal;
}

and I called it in main by foe example:

    unsigned qa[] = {1,1,1,1} ;
	g (qa, 4); 

but output for this function is nothing??

[D80DSL3A]

Try std::cout << g(qa, 4);. You must be tired.

[SwqGNwbp]

Finally!! Thanks,