Sorting coordinates by 'enveloping' or 'dominance' criterion

Question

I'm trying to sort coordinates in a vector based on whether they are enveloped or dominated by other coordinates. For example the coordinate [1 , 2 , 1 , 1] is enveloped or dominated by [4, 2 , 1 , 2] even though the 2nd and 3rd values of both coordinates are equal.

Highlight of program. (Complete program online at rextester.com)

int input[18][4] = { { 4 , 3 , 3 , 3 } , { 1 , 5 , 4 , 1 } , { 2 , 4 , 5 , 4 } ,
                     { 3 , 1 , 2 , 5 } , { 4 , 2 , 1 , 2 } , { 1 , 3 , 3 , 1 } ,
                     { 2 , 3 , 3 , 3 } , { 3 , 1 , 2 , 3 } , { 5 , 2 , 1 , 2 } ,
                     { 1 , 4 , 4 , 1 } , { 1 , 1 , 2 , 1 } , { 1 , 2 , 1 , 1 } ,
                     { 2 , 1 , 2 , 4 } , { 2 , 2 , 1 , 2 } , { 3 , 1 , 1 , 2 } ,
                     { 2 , 1 , 2 , 3 } , { 1 , 1 , 1 , 1 } , { 2 , 1 , 1 , 2 } };   

struct Coordinate
{
    Coordinate(){}
    Coordinate( int (&val)[4] );
    bool operator<( const Coordinate& otherCoord ) const;
    void print() const;

    int value[4];
};      

void print( const std::vector<Coordinate>& coord );

int main()
{
    std::vector<Coordinate> coord;
    coord.assign( input  , input + 18 );
    print( coord );

    std::sort( coord.begin() , coord.end() );
    print( coord );
}

Program output is however not what I expected,

[ 1 , 1 , 1 , 1 ]
[ 1 , 4 , 4 , 1 ]
[ 2 , 1 , 1 , 2 ]
[ 2 , 1 , 2 , 3 ]
[ 3 , 1 , 1 , 2 ]
[ 1 , 3 , 3 , 1 ]
[ 2 , 2 , 1 , 2 ]
[ 2 , 1 , 2 , 4 ]
[ 1 , 2 , 1 , 1 ]
[ 1 , 1 , 2 , 1 ]
[ 4 , 3 , 3 , 3 ]
[ 5 , 2 , 1 , 2 ]  // <-- ???
[ 3 , 1 , 2 , 3 ]
[ 2 , 3 , 3 , 3 ]
[ 4 , 2 , 1 , 2 ]  // <-- ???
[ 3 , 1 , 2 , 5 ]
[ 2 , 4 , 5 , 4 ]
[ 1 , 5 , 4 , 1 ]

For example [ 5 , 2 , 1 , 2 ] envelopes or dominates [ 4 , 2 , 1 , 2 ] yet appears before it as shown in the program output.

Answer 1

What you are asking for is lexicographical ordering that basically amounts to saying the comparison (x1, y1) < (x2, y2) is equivalent to saying if (x1 < x2 || (x1 == x2 && y1 < y2))

The body of your Coordinate::operator< can be modified as follows:

for( int i = 0; i < 4; ++i ) {
   if( value[i] > otherCoord.value[i] ) 
     return false; 
   if (value[i] < otherCoord.value[i] ) 
     return true; 
} 
return false;

We return false at the end because we are performing strict less-than comparison. When we've reached that line we know that all the elements of both coordinates are identical, so if we return true then we've satisfied <= instead.

However, I would propose that you update this code to use more modern C++. Namely vectors and arrays. This is nice especially because the default operator< for a std::array will perform lexicographical ordering for you. (Additionally you don't have to worry about pointer math because you get to use iterators).

Here is your new class:

template<size_t N>
struct Coordinate
{
    Coordinate(){}
    Coordinate( std::array<int, N> _val);
    bool operator<( const Coordinate& otherCoord ) const;
    void print() const;
    
    std::array<int, N> value;
};  

And here's how you'd implement operator<:

template<size_t N>
bool Coordinate<N>::operator<( const Coordinate<N>& otherCoord ) const
{
    return value < otherCoord.value;
}

And finally main:

int main()
{
    std::vector<Coordinate<4>> coords;
    coords.assign( input.begin(), input.end() );
    print(coords);
    std::sort(coords.begin(), coords.end());
    print( coords );
}

Prefer the templates for Coordinate so that you can make coordinates of arbitrary dimensionality at compile-time. Right now there is a lot of magic numbering going on to make it all work.

Here's a live demo

Answer 2

I've found the answer and I'm posting here for posterity's sake.

The sorting criterion must define strict weak ordering, which is defined by the following four properties

Accordingly I've re-implemented operator< as follows.

Note: implementation intentionally suboptimal for sake of clarity. (Comparisons should ideally be done once and cached.)

bool Coordinate::operator<( const Coordinate& otherCoord ) const
{
    int ltCount = 0;
    int gtCount = 0;

    for( int i = 0; i < 4; ++i )
    {
        if( value[i] < otherCoord.value[i] ) ++ltCount;
        if( value[i] > otherCoord.value[i] ) ++gtCount;
    }

    if( ltCount == 4 ) return true;     // Strictly less
    if( gtCount == 4 ) return false;    // Strictly greater

    // Neither stritcly greater or less. Create ordering (based on magnitute of first coordinate)
    for( int i = 0; i < 4; ++i )
    {
        if( value[i] == otherCoord.value[i] ) continue;
        return( value[i] < otherCoord.value[i] );
    }

    return false;   // this should NEVER happen if coords are NOT equal.
}