/* My attempt to implement a unit test similar to Google's test. https://github.com/google/googletest Using similar lightly because mine doesn't even compare to theirs, lel. Either way, it was interesting to implement something that at least works. I didn't copy anything from them except for their floating point class. Ironically I found and fixed a load of bugs in this very program just because of the unit tests testing itself. */ #include #include #include #include #include #include namespace testing { namespace internal { // Base class class TestUnit { public: // Virtual destructor to allow proper destruction of Derived classes virtual ~TestUnit(){} // Calls the actual test case virtual void testCase() = 0; virtual const char* suitName() const = 0; virtual const char* testName() const = 0; // Returns true if the test has failed, false if not. // Returns false by default bool isFailure() const { return m_failure.failure.value_or( false ); } void failure( bool f, const char* file, const char* line ) { // Only set the flag to true once and don't allow it to be set to false after if( !m_failure.failure.has_value() || m_failure.failure.value() == false ) { m_failure.failure = std::optional( f ); m_failure.file = file; m_failure.line = line; } } // Returns the File name and Line number as a string std::string getErrorString() const { return std::string( "File: " ) + std::string( m_failure.file ) + std::string( "\n\t" ) + std::string( "Line: " ) + std::string( m_failure.line ); } private: struct FailureDetails { // optional because it has a handy has_value function, // so I don't have to keep track of whether failure gets written to or not with another flag std::optional failure; const char* file; const char* line; } m_failure; }; using Grouping = const char*; using TestCases = std::vector; // This only works because the compiler uses the same memory location for strings that are the same at compile time // Wouldn't work if you tried to input a string at run time and then use that to search for the key, you wouldn't find anything even if they are equal. std::map g_UnitMap; // Runs test for a grouping and returns the number of failures for that group int runTestCases( const TestCases& testCases ) { int failureCount = 0; for( const auto& i : testCases ) { // Test case i->testCase(); bool failure = i->isFailure(); std::cout << "\t" << i->testName() << ": " << (failure ? "Failure" : "Success"); if( failure ) { ++failureCount; std::cout << "\n\t" << i->getErrorString() << '\n'; } std::cout << std::endl; } return failureCount; } } void InitTest( int* argc, char** argv ) { // Not really used yet } // Returns total amount of failures int runTests() { int totalFailureCount = 0; // Binds i.first to the variable grouping and i.second to the variable testCases for( const auto& [grouping, testCases] : internal::g_UnitMap ) { // Grouping std::cout << grouping << ":\n"; int failureCount = internal::runTestCases( testCases ); std::cout << "\n\tFailures: " << failureCount << '\n' << std::endl; totalFailureCount += failureCount; } std::cout << "\nTotal failure count: " << totalFailureCount << std::endl; return totalFailureCount; } } // Macros need double indirection because pre processors are weird // Macros are evaluated left to right instead of the usual depth first you expect from a usual function call // STRINGIFY(__LINE__) would result in "__LINE__" instead of __LINE__ getting evaluated to a number and then stringified // With the added layer of indirection STRINGIFY_IMPL __LINE__ does get properly evaluated before getting stringified // Similar thing would happen if you tried to do CONCAT( a, __LINE__ ), // you'd get a__LINE__ instead of a5 ( assuming __LINE__ would evaluate to 5 as an example ) // So thats why you usually see double indirections for macros // Also don't need to worry about `prototypes` - or using a macro before its declaration #define STRINGIFY( s ) STRINGIFY_IMPL( s ) #define STRINGIFY_IMPL( s ) #s // __FILE__ already is a string #define __FAILURE( _Expression ) \ failure( _Expression, __FILE__, STRINGIFY( __LINE__ ) ) #define EXPECT_EQ( lhs, rhs ) \ __FAILURE( !(lhs == rhs) ) #define EXPECT_EQ_FAIL( lhs, rhs ) \ __FAILURE( (lhs == rhs) ) #define EXPECT_NE( lhs, rhs ) \ __FAILURE( (lhs == rhs) ) #define EXPECT_NE_FAIL( lhs, rhs ) \ __FAILURE( !(lhs == rhs) ) #define EXPECT_LE( lhs, rhs ) \ __FAILURE( !(lhs <= rhs) ) #define EXPECT_LE_FAIL( lhs, rhs ) \ __FAILURE( (lhs <= rhs) ) #define EXPECT_LT( lhs, rhs ) \ __FAILURE( !(lhs < rhs) ) #define EXPECT_LT_FAIL( lhs, rhs ) \ __FAILURE( (lhs < rhs) ) #define EXPECT_GE( lhs, rhs ) \ __FAILURE( (lhs < rhs) ) #define EXPECT_GE_FAIL( lhs, rhs ) \ __FAILURE( !(lhs < rhs) ) #define EXPECT_GT( lhs, rhs ) \ __FAILURE( (lhs <= rhs) ) #define EXPECT_GT_FAIL( lhs, rhs ) \ __FAILURE( !(lhs <= rhs) ) #define EXPECT_TRUE( value ) \ EXPECT_EQ( value, 1 ) #define EXPECT_FALSE( value ) \ EXPECT_EQ( value, 0 ) #define EXPECT_FLOAT_EQ( lhs, rhs ) \ __FAILURE( !(compareFloat( lhs, rhs ) == 0) ) #define EXPECT_FLOAT_EQ_FAIL( lhs, rhs ) \ __FAILURE( (compareFloat( lhs, rhs ) == 0) ) #define EXPECT_DOUBLE_EQ( lhs, rhs ) \ __FAILURE( !(compareFloat( lhs, rhs ) == 0) ) #define EXPECT_DOUBLE_EQ_FAIL( lhs, rhs ) \ __FAILURE( (compareFloat( lhs, rhs ) == 0) ) #define ASSERT_FLOAT_EQ( lhs, rhs ) \ assert( (compareFloat( lhs, rhs ) == 0) ) #define ASSERT_FLOAT_EQ_FAIL( lhs, rhs ) \ assert( !(compareFloat( lhs, rhs ) == 0) ) #define ASSERT_DOUBLE_EQ( lhs, rhs ) \ assert( (compareFloat( lhs, rhs ) == 0) ) #define ASSERT_DOUBLE_EQ_FAIL( lhs, rhs ) \ assert( !(compareFloat( lhs, rhs ) == 0) ) #define EXPECT_FLOAT_NE( lhs, rhs ) \ __FAILURE( (compareFloat( lhs, rhs ) == 0) ) #define EXPECT_FLOAT_NE_FAIL( lhs, rhs ) \ __FAILURE( !(compareFloat( lhs, rhs ) == 0) ) #define EXPECT_DOUBLE_NE( lhs, rhs ) \ __FAILURE( (compareFloat( lhs, rhs ) == 0) ) #define EXPECT_DOUBLE_NE_FAIL( lhs, rhs ) \ __FAILURE( !(compareFloat( lhs, rhs ) == 0) ) #define ASSERT_FLOAT_NE( lhs, rhs ) \ assert( !(compareFloat( lhs, rhs ) == 0) ) #define ASSERT_FLOAT_NE_FAIL( lhs, rhs ) \ assert( (compareFloat( lhs, rhs ) == 0) ) #define ASSERT_DOUBLE_NE( lhs, rhs ) \ assert( !(compareFloat( lhs, rhs ) == 0) ) #define ASSERT_DOUBLE_NE_FAIL( lhs, rhs ) \ assert( (compareFloat( lhs, rhs ) == 0) ) #define ASSERT_EQ( lhs, rhs ) \ assert( (lhs == rhs) ) #define ASSERT_EQ_FAIL( lhs, rhs ) \ assert( !(lhs == rhs) ) #define ASSERT_NE( lhs, rhs ) \ assert( !(lhs == rhs) ) #define ASSERT_NE_FAIL( lhs, rhs ) \ assert( (lhs == rhs) ) #define ASSERT_LE( lhs, rhs ) \ assert( (lhs <= rhs) ) #define ASSERT_LE_FAIL( lhs, rhs ) \ assert( !(lhs <= rhs) ) #define ASSERT_LT( lhs, rhs ) \ assert( (lhs < rhs) ) #define ASSERT_LT_FAIL( lhs, rhs ) \ assert( !(lhs < rhs) ) #define ASSERT_GE( lhs, rhs ) \ assert( !(lhs < rhs) ) #define ASSERT_GE_FAIL( lhs, rhs ) \ assert( (lhs < rhs) ) #define ASSERT_GT( lhs, rhs ) \ assert( !(lhs <= rhs) ) #define ASSERT_GT_FAIL( lhs, rhs ) \ assert( (lhs <= rhs) ) #define ASSERT_TRUE( value ) \ ASSERT_EQ( value, 1 ) #define ASSERT_FALSE( value ) \ ASSERT_EQ( value, 0 ) #define RUN_ALL_TESTS() \ testing::runTests() #define TEST_CLASS_NAME( test_case_name, test_name ) \ _CLASS_##test_case_name##test_name /* Macro that generates a class UNITTEST( FooGroup, BarName ) Would generate the class _CLASS_FooGroupBarName and an instance of it with the name FooGroupBarName_INIT_ which in turn calls the constructor which inserts the unit test into the global UnitMap I don't think this is quite how Google did it but meh, it works. */ #define UNITTEST( test_suit_name, test_name ) \ class TEST_CLASS_NAME( test_suit_name, test_name ) \ : public testing::internal::TestUnit \ { \ public: \ TEST_CLASS_NAME( test_suit_name, test_name )() \ { \ testing::internal::g_UnitMap[STRINGIFY( test_suit_name )] \ .push_back( this ); \ } \ \ private: \ virtual void testCase() override; \ virtual const char* suitName() const override \ { return STRINGIFY(test_suit_name); } \ virtual const char* testName() const override \ { return STRINGIFY(test_name); } \ } test_suit_name##test_name##_INIT_; \ \ void TEST_CLASS_NAME( test_suit_name, test_name )::testCase() /// ===================================================================== #if defined( WIN32 ) || defined( WIN64 ) #define WINDOWS 1 #else #define WINDOWS 0 #endif // Borrowed from Google :), because comparing floats with an epsilon is a bust for big values namespace Google { #define GTEST_OS_WINDOWS WINDOWS template class TypeWithSize { public: // This prevents the user from using TypeWithSize with incorrect // values of N. typedef void UInt; }; // The specialization for size 4. template <> class TypeWithSize<4> { public: // unsigned int has size 4 in both gcc and MSVC. // // As base/basictypes.h doesn't compile on Windows, we cannot use // uint32, uint64, and etc here. typedef int Int; typedef unsigned int UInt; }; // The specialization for size 8. template <> class TypeWithSize<8> { public: #if GTEST_OS_WINDOWS typedef __int64 Int; typedef unsigned __int64 UInt; #else typedef long long Int; // NOLINT typedef unsigned long long UInt; // NOLINT #endif // GTEST_OS_WINDOWS }; // Template parameter: // // RawType: the raw floating-point type (either float or double) template class FloatingPoint { public: // Defines the unsigned integer type that has the same size as the // floating point number. typedef typename TypeWithSize::UInt Bits; // Constants. // # of bits in a number. static const size_t kBitCount = 8*sizeof(RawType); // # of fraction bits in a number. static const size_t kFractionBitCount = std::numeric_limits::digits - 1; // # of exponent bits in a number. static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount; // The mask for the sign bit. static const Bits kSignBitMask = static_cast(1) << (kBitCount - 1); // The mask for the fraction bits. static const Bits kFractionBitMask = ~static_cast(0) >> (kExponentBitCount + 1); // The mask for the exponent bits. static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask); // How many ULP's (Units in the Last Place) we want to tolerate when // comparing two numbers. The larger the value, the more error we // allow. A 0 value means that two numbers must be exactly the same // to be considered equal. // // The maximum error of a single floating-point operation is 0.5 // units in the last place. On Intel CPU's, all floating-point // calculations are done with 80-bit precision, while double has 64 // bits. Therefore, 4 should be enough for ordinary use. // // See the following article for more details on ULP: // http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm. static const size_t kMaxUlps = 4; // Constructs a FloatingPoint from a raw floating-point number. // // On an Intel CPU, passing a non-normalized NAN (Not a Number) // around may change its bits, although the new value is guaranteed // to be also a NAN. Therefore, don't expect this constructor to // preserve the bits in x when x is a NAN. explicit FloatingPoint(const RawType& x) { u_.value_ = x; } // Static methods // Reinterprets a bit pattern as a floating-point number. // // This function is needed to test the AlmostEquals() method. static RawType ReinterpretBits(const Bits bits) { FloatingPoint fp(0); fp.u_.bits_ = bits; return fp.u_.value_; } // Returns the floating-point number that represent positive infinity. static RawType Infinity() { return ReinterpretBits(kExponentBitMask); } // Non-static methods // Returns the bits that represents this number. const Bits &bits() const { return u_.bits_; } // Returns the exponent bits of this number. Bits exponent_bits() const { return kExponentBitMask & u_.bits_; } // Returns the fraction bits of this number. Bits fraction_bits() const { return kFractionBitMask & u_.bits_; } // Returns the sign bit of this number. Bits sign_bit() const { return kSignBitMask & u_.bits_; } // Returns true iff this is NAN (not a number). bool is_nan() const { // It's a NAN if the exponent bits are all ones and the fraction // bits are not entirely zeros. return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0); } // Returns true iff this number is at most kMaxUlps ULP's away from // rhs. In particular, this function: // // - returns false if either number is (or both are) NAN. // - treats really large numbers as almost equal to infinity. // - thinks +0.0 and -0.0 are 0 DLP's apart. bool AlmostEquals(const FloatingPoint& rhs) const { // The IEEE standard says that any comparison operation involving // a NAN must return false. if (is_nan() || rhs.is_nan()) return false; return DistanceBetweenSignAndMagnitudeNumbers(u_.bits_, rhs.u_.bits_) <= kMaxUlps; } private: // The data type used to store the actual floating-point number. union FloatingPointUnion { RawType value_; // The raw floating-point number. Bits bits_; // The bits that represent the number. }; // Converts an integer from the sign-and-magnitude representation to // the biased representation. More precisely, let N be 2 to the // power of (kBitCount - 1), an integer x is represented by the // unsigned number x + N. // // For instance, // // -N + 1 (the most negative number representable using // sign-and-magnitude) is represented by 1; // 0 is represented by N; and // N - 1 (the biggest number representable using // sign-and-magnitude) is represented by 2N - 1. // // Read http://en.wikipedia.org/wiki/Signed_number_representations // for more details on signed number representations. static Bits SignAndMagnitudeToBiased(const Bits &sam) { if (kSignBitMask & sam) { // sam represents a negative number. return ~sam + 1; } else { // sam represents a positive number. return kSignBitMask | sam; } } // Given two numbers in the sign-and-magnitude representation, // returns the distance between them as an unsigned number. static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1, const Bits &sam2) { const Bits biased1 = SignAndMagnitudeToBiased(sam1); const Bits biased2 = SignAndMagnitudeToBiased(sam2); return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1); } FloatingPointUnion u_; }; } // End of borrow // Only allow floats and double types to call this function // Returns 1 if lhs > rhs // Returns 0 if lhs == rhs ( or at least almost equal ) // Returns -1 if lhs < rhs template>* = nullptr> int compareFloat( T lhs, T rhs ) { const Google::FloatingPoint lhsF( lhs ), rhsF( rhs ); if( lhsF.AlmostEquals( rhsF ) ) return 0; else if( lhs < rhs ) return -1; else return 1; } // UnitTest tests UNITTEST( UnitTest, EQ_int ) { int v = 5; EXPECT_EQ( 5, v ); } UNITTEST( UnitTest, EQ_float ) { float v = 5.3f; EXPECT_FLOAT_EQ( 5.3f, v ); } UNITTEST( UnitTest, EQ_double ) { double v = 5.3; EXPECT_DOUBLE_EQ( 5.3, v ); } UNITTEST( UnitTest, NE_int ) { int v = 91; EXPECT_NE( 92, v ); } UNITTEST( UnitTest, NE_float ) { float v = 9.1f; EXPECT_FLOAT_NE( 9.10001f, v ); } UNITTEST( UnitTest, NE_double ) { double v = 9.1; EXPECT_DOUBLE_NE( 9.1000000001, v ); } UNITTEST( UnitTest, Less_Than ) { float v = 8414.2f; EXPECT_LT( 3434.f, v ); } UNITTEST( UnitTest, Bigger_Than ) { float v = 2414.2f; EXPECT_GT( 3434.f, v ); } UNITTEST( UnitTest, Less_Or_Equal ) { int v = 5000; EXPECT_LE( 5000, v ); } UNITTEST( UnitTest, Bigger_Or_Equal ) { int v = 5000; EXPECT_GE( 5000, v ); } UNITTEST( UnitTest, Overflow ) { // signed overflow is undefined behaviour, but not for unsigned integers unsigned v = 4294967295; EXPECT_EQ( 0, v + 1 ); } UNITTEST( UnitTest, Expect_to_fail ) { unsigned v = 4294967295; EXPECT_EQ_FAIL( 4294967296ull, v + 1 ); } UNITTEST( UnitTest, Failing_on_Purpose ) { unsigned v = 45; EXPECT_NE( 45, v ); } UNITTEST( UnitTest, Double_Expect ) { unsigned v = 500; EXPECT_EQ( 250 * 2, v ); EXPECT_EQ( 1001 / 2, v ); } UNITTEST( UnitTest, Double_Expect_Fail_First ) { unsigned v = 500; EXPECT_EQ_FAIL( 251 * 2, v ); EXPECT_EQ( 1001 / 2, v ); } UNITTEST( UnitTest, Double_Expect_Fail_Second ) { unsigned v = 500; EXPECT_EQ( 250 * 2, v ); EXPECT_EQ_FAIL( 1002 / 2, v ); } UNITTEST( UnitTest, Fail_All_Except_Last ) { unsigned v = 5; EXPECT_GT_FAIL( 5, v ); EXPECT_LT_FAIL( 5, v ); EXPECT_EQ_FAIL( 5, v * v ); EXPECT_NE_FAIL( 5, v ); //ASSERT_EQ_FAIL( 5, !!v ); EXPECT_EQ( 5, v ); } class BankAccount { public: BankAccount() : BankAccount( 0.0 ) {} BankAccount( double balance ) : m_balance( balance ) {} // Amount has to be a value >= 0, you can't deposit a negative amount bool deposit( double amount ) { if( compareFloat( amount, 0 ) >= 0 ) { m_balance += amount; return true; } return false; } // This one can go negative void pay( double amount ) { m_balance -= amount; } // Can't withdraw more than we have // Returns true on success, false if we don't have enough funds bool withdraw( double amount ) { if( m_balance < amount ) { return false; } pay( amount ); return true; } double getBalance() const { return m_balance; } bool isZero() const { return !compareFloat( 0, m_balance ); } private: double m_balance; }; // BankAccount class tests UNITTEST( BankAccount, is_empty ) { BankAccount account; EXPECT_DOUBLE_EQ( 0.0, account.getBalance() ); } UNITTEST( BankAccount, deposit_positive_amount ) { BankAccount account( 5.3 ); account.deposit( 12345 ); EXPECT_DOUBLE_EQ( 12350.3, account.getBalance() ); } UNITTEST( BankAccount, deposit_negative_amount ) { BankAccount account( 5.3 ); bool success = account.deposit( -6 ); EXPECT_FALSE( success ); EXPECT_DOUBLE_EQ( 5.3, account.getBalance() ); } UNITTEST( BankAccount, pay ) { BankAccount account( 10 ); account.pay( 4 ); EXPECT_DOUBLE_EQ( 6, account.getBalance() ); } UNITTEST( BankAccount, pay_into_red ) { BankAccount account( 10 ); account.pay( 25 ); EXPECT_DOUBLE_EQ( -15, account.getBalance() ); } UNITTEST( BankAccount, attempt_to_withdraw_when_in_red ) { BankAccount account( -50 ); bool success = account.withdraw( 0.01 ); EXPECT_FALSE( success ); EXPECT_DOUBLE_EQ( -50, account.getBalance() ); } UNITTEST( BankAccount, withdraw_half ) { BankAccount account( 1000.0 ); bool success = account.withdraw( account.getBalance() / 2 ); EXPECT_TRUE( success ); EXPECT_DOUBLE_EQ( 500.0, account.getBalance() ); } UNITTEST( BankAccount, withdraw_too_much ) { BankAccount account( 1000.0 ); bool success = account.withdraw( 1000.1 ); EXPECT_FALSE( success ); EXPECT_DOUBLE_EQ( 1000.0, account.getBalance() ); } UNITTEST( BankAccount, zero ) { BankAccount account( 1000 ); account.pay( 1000 ); EXPECT_TRUE( account.isZero() ); } template IterLhs cmp( IterLhs lhsBegin, IterLhs lhsEnd, IterRhs rhsBegin, IterRhs rhsEnd ) { using LhsValue = typename std::iterator_traits::value_type; using RhsValue = typename std::iterator_traits::value_type; using Common_Type = typename std::common_type::type; for( ; lhsBegin != lhsEnd && rhsBegin != rhsEnd; lhsBegin++, rhsBegin++ ) { if constexpr( std::is_floating_point::value || std::is_floating_point::value ) { if( compareFloat( *lhsBegin, *rhsBegin ) ) { return lhsBegin; } } else if ( !(*lhsBegin == *rhsBegin) ) { return lhsBegin; } } return lhsBegin; } template IterLhs cmp( IterLhs lhsBegin, IterLhs lhsEnd, IterRhs rhsBegin, IterRhs rhsEnd, BinaryFunction binaryFunction ) { for( ; lhsBegin != lhsEnd && rhsBegin != rhsEnd; lhsBegin++, rhsBegin++ ) { if( !binaryFunction( *lhsBegin, *rhsBegin ) ) return lhsBegin; } return lhsBegin; } // Iterator compare function tests UNITTEST( Iterator_Cmp, vector_int_same ) { std::vector v1{ 1, 2, 3, 4, 5, 6 }; std::vector v2{ 1, 2, 3, 4, 5, 6 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end() ), v1.end() ); } UNITTEST( Iterator_Cmp, vector_double_same ) { std::vector v1{ 0.5, 0.6, 0.4, 0.2, 0.7 }; std::vector v2{ 0.5, 0.6, 0.4, 0.2, 0.7 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end() ), v1.end() ); } #include UNITTEST( Iterator_Cmp, different_containers ) { std::vector v1{ 5, 8, 19, 20, 1, 44 }; std::list v2{ 5, 8, 19, 20, 1, 44 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end() ), v1.end() ); } class CustomType { public: CustomType( int value ):m_value( value ){} int getValue() const { return m_value; } friend bool operator==( const CustomType& lhs, const CustomType& rhs ) { return lhs.getValue() == rhs.getValue(); } private: int m_value; }; class CustomTypeNoCompare { public: CustomTypeNoCompare( int value ):m_value( value ){} int getValue() const { return m_value; } private: int m_value; }; UNITTEST( Iterator_Cmp, custom_type ) { std::vector v1{ 4, 20, 13, 17, -5, -199 }; std::vector v2{ 4, 20, 13, 17, -5, -199 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end() ), v1.end() ); } UNITTEST( Iterator_Cmp, custom_type_lambda ) { std::vector v1{ 4, 20, 13, 17, -5, -199 }; std::vector v2{ 4, 20, 13, 17, -5, -199 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end(), []( const CustomTypeNoCompare& lhs, const CustomTypeNoCompare& rhs ) { return lhs.getValue() == rhs.getValue(); } ), v1.end() ); } UNITTEST( Iterator_Cmp, less_than_all ) { std::vector v1{ 3, 5, 8, 10, 11 }; std::vector v2{ -6, 3, -3, 5, 9 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end(), []( int lhs, int rhs ) { return lhs >= rhs; } ), v1.end() ); } UNITTEST( Iterator_Cmp, less_until_index_2 ) { std::vector v1{ 3, 5, 8, 10, 11 }; std::vector v2{ -6, 3, 9, 5, 9 }; EXPECT_EQ( cmp( v1.begin(), v1.end(), v2.begin(), v2.end(), []( int lhs, int rhs ) { return lhs >= rhs; } ), v1.begin() + 2 ); } template // O(n) auto maxSubArray( Iter begin, Iter end ) -> typename std::iterator_traits::value_type { Iter ptr = begin; auto current = *ptr; auto max = current; while( ++ptr != end ) { current = std::max( *ptr + current, *ptr ); max = std::max( max, current ); } return max; } // MaxSubArray algorithm tests UNITTEST( MaxSubArray, addition ) { std::vector v1{ 4, 9, 3 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 16 ); } UNITTEST( MaxSubArray, one_is_bigger_than_the_other ) { std::vector v1{ 5, 1, -8, 7 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 7 ); } UNITTEST( MaxSubArray, simple ) { std::vector v1{ 5, -1, 4, -9, 4, 5, 2 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 11 ); } UNITTEST( MaxSubArray, sum_all ) { std::vector v1{ 5, -1, 4, -2, 4, 5, 2 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 17 ); } UNITTEST( MaxSubArray, zero ) { std::vector v1{ 0 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 0 ); } UNITTEST( MaxSubArray, negative ) { std::vector v1{ -5, -8, -3, -9, -14, -7, -4 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), -3 ); } UNITTEST( MaxSubArray, bigger ) { std::vector v1{ 5, 8, -11, 8, -12, 6, 10, 5, -2, 5, -1, 7, -2, -10, -15, -8, 9, -4, 14, 3, 4, -6, 1, -6 }; EXPECT_EQ( maxSubArray( v1.begin(), v1.end() ), 30 ); } int main( int argc, char** argv ) { testing::InitTest( &argc, argv ); std::cout << "[Grouping]: [Test name]\n"; return RUN_ALL_TESTS(); }

Unit Tests