Generalized sort function using lambda functions

[prestokeys]

Please help me improve my customSort function. It is to accept a lambda function as parameter which customizes your sort in any special way you want.

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <functional>

enum personType {teacher, student, baby};

struct Person {
	std::string name;
	int age;
	personType type;
};

bool nTrue (const std::deque<bool>& orderingCriteria1, const std::deque<bool>& orderingCriteria2, int n) {
	if (!orderingCriteria1[n])
		return false;
	for (int i = 0; i < n; i++)
		if (orderingCriteria2[i])
			return false;
	return true;
};
		
template <typename RandomAccessIterator, typename T>
void customSort (RandomAccessIterator first, RandomAccessIterator last, std::function<std::deque<bool> (T)>& orderingCriteria) {
	std::sort (first, last, [=](const T& x, const T& y)->bool {
		const int N = orderingCriteria(x).size();
		for (int i = 0; i < N; i++)
			if (nTrue (orderingCriteria(x), orderingCriteria(y), i))
				return true;
		return false;
		}
	);
}

int main () {
	Person Mark {"Mark ", 18, student}, MrMac {"Mr. Mac", 35, teacher}, Lola {"Lola (baby)", 2, baby}, MsWhite {"Ms. White", 29, teacher}, 
		Cindy {"Cindy", 8, student}, Zainab {"Zainab (baby)", 1, baby}, Mikey {"Mikey (baby)", 1, baby}, Fred {"Fred", 17, student}, Zolal {"Zolal", 19, student};
	std::vector<Person> people = {Mark, MrMac, Lola, MsWhite, Cindy, Zainab, Mikey, Fred, Zolal};
	std::function<std::deque<bool> (Person)> orderingCriteria = [](Person person)->std::deque<bool> {
		std::deque<bool> result = {
			person.name.at(0) == 'Z',
			person.age == 8, 
			person.type == teacher, 
			person.type == student, 
			person.type == baby}; 
		// result.emplace_back (whatever using loops)
		//
		return result;
	};   // must use std::function<std::deque<bool> (Person)> instead of auto, else template deduction for T will fail
	
	customSort (people.begin(), people.end(), orderingCriteria);
	for (auto it = people.cbegin(); it != people.cend(); ++it)
		std::cout << it->name << std::endl;
		
	std::cin.get();
	return 0;
}

For example, std::vector<Person> people = {Mark, MrMac, Lola, MsWhite, Cindy, Zainab, Mikey, Fred, Zolal} is to be sorted so that teachers will be placed first, then students, and then babies, but with the exception that people with names starting with Z be placed before anyone else, followed by people with age equal to 8. All this is set up by the ordered list:

person.name.at(0) == 'Z',
person.age == 8, 
person.type == teacher, 
person.type == student, 
person.type == baby

So the output gives

Zolal
Zainab (baby)
Cindy 
Ms. White
Mr. Mac
Fred
Mark
Mikey (baby)
Lola (baby)

Teachers are supposed to be placed before students, which in turn placed before babies, but Cindy's age is 8, and so is placed before the teachers, and Zolal and Zainab start with Z, so is placed before her. So far so good, but now I want the further sorting result that all people within their subcategories be sorted in their own way, e.g. Zainab should come before Zolal alphabetically, Ms. White should precede Mr. Mac because she is younger, etc... How do I further generalize my customSort function so it carries out those further criteria as well?

[LB]

I don't understand why you want to go through all this trouble when you could just write the lambda to pass to std::sort yourself as needed?

[prestokeys]

Because the lambda function itself needs to be passed into another function, which I called nTrue, to make it work. In order for criterion n to rank n in the ordering, we have to make sure that criteria 1 to n-1 are false for the second argument of the binary function. It is the function nTrue that actually needs to be generalized in order to generalize cumstomSort. Something along the lines of "if equality holds", then use another criteria to sort within this subcategory, and so forth. So perhaps each component of the std::deque<bool> forming the lambda function needs to be a std::pair<bool, something> where the second component will make the secondary comparisons in the event of equality of a category.

[LB]

I think you misunderstood my question. Why do you even need nTrue or customSort?

[prestokeys]

Because I've done what you said several times in my program already, and it is getting repetitive and messy. Writing the all purpose function customSort makes my code tidier. Plus it is an interesting challenge to write customSort, which I think would be a cool function if it can be generalized more. Once done, then you need only define the boolean statements that give the ordering to pass into customSort.

Here is a snippet of my program that uses (my current version of) customSort:

std::function<std::deque<bool> (Menu::Option*)> orderingCriteria = [](const Menu::Option* o)->std::deque<bool> {
	std::deque<bool> result = {o->optionType == OrderingEverythingInSubmenu, o->optionType == NotOrdering, 
                o->optionType == UndoPreviousOrder, o->name == "Wine"};
	for (int age = MIN_AGE; age <= MAX_AGE; age++)
		result.emplace_back (o->name.find (toString (age) + " year-old") != std::string::npos);						
	return result;
};	
customSort (specialOptions.begin(), specialOptions.end(), orderingCriteria);

Things are much tidier and readible now. But customSort needs more work, as described in my opening post.

[LB]

If you are re-writing the same binary predicate, just make it a real function and just refer to it over and over. If there are slight variations, make a functor class out of it that you can construct with the variances specified on-the-fly.

In other words, pretend you are using C++03 ;)

[JLBorges]

> Writing the all purpose function customSort makes my code tidier.
> Once done, then you need only define the boolean statements
> that give the ordering to pass into customSort.
> But customSort needs more work, as described in my opening post

Instead of a custom sort, can't we use a predicate builder which builds a complex strict-weak-ordering predicate from an ordered set of simple boolean expressions?

Something like:

template < typename T, typename... PREDICATE > struct predicate_builder ;

template < typename T, typename PREDICATE > struct predicate_builder<T,PREDICATE>
{
    predicate_builder( PREDICATE fn ) : cmp(fn) {}

    bool operator() ( T a, T b ) const { return cmp(a,b) ; }

    const PREDICATE cmp ;
};

template < typename T, typename FIRST, typename... REST >
struct predicate_builder<T,FIRST,REST...> : predicate_builder<T,REST...>
{
    using base = predicate_builder<T,REST...> ;

    predicate_builder( FIRST first, REST... rest ) : base(rest...), cmp(first) {}

    bool operator() ( T a, T b ) const
    {
        if( cmp(a,b) ) return true ;
        else if( cmp(b,a) ) return false ;
        else return base::operator() (a,b) ;
    }

    const FIRST cmp ;
};

template< typename T, typename... PREDICATE >
predicate_builder<T,PREDICATE...> compose( PREDICATE... fn )
{ return predicate_builder<T,PREDICATE...>(fn...) ; }

#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
     // 58 to be placed before anything else,
     // 11 to be placed after everything else,
     // order on ascending last digit,
     // except that last digit 7 appears before other last digits,
     // if last digits are equal, order by decreasing value
     const auto cmp = compose<int>
     (
         [] ( int a, int b ) { return a == 58 && b != 58 ; },
         [] ( int a, int b ) { return a != 11 && b == 11 ; },
         [] ( int a, int b ) { return a%10 == 7 && b%10 != 7 ; },
         [] ( int a, int b ) { return a%10 < b%10 ; },
         [] ( int a, int b ) { return a > b ; }
     ) ;

     int a[] = { 19, 22, 11, 25, 11, 58, 77, 32, 58, 45, 16, 77, 39, 83, 95, 98, 17 } ;

     std::sort( std::begin(a), std::end(a), cmp ) ;
     for( int v : a ) std::cout << v << ' ' ;
     std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/34302f808dd54977

[prestokeys]

Ah! Thank you soooo much. Of course, your name was on my mind this whole time, JLBorges. I knew variadic templates will come to the rescue again. I'll take a good look at this.

[prestokeys]

	auto isPrime = [](int x)->bool {return x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19 ||
		x == 23 || x == 29 || x == 31 || x == 37 || x == 41 || x == 43 || x == 47;};
	// 25 placed first before anything else
    // 16 to be placed after everything else,
    // even numbers placed after all 25's, if any, have been placed (and the even numbers sorted in increasing value among themselves)
    // prime numbers then placed in groups in the order 1-9, 10-19, 20-29, 30-39, 40-49 (and in decreasing value within each group)
	// after these order on ascending last digit,
    // except that last digit 7 appears before other last digits,
    // if last digits are equal, order by increasing value
    const auto comp = compose<int>
    (
     	[] (int a, int b) {return a == 25 && b != 25;},
        [] (int a, int b) {return a != 16 && b == 16;},
        [] (int a, int b) {return a%2 == 0 && b%2 != 0;},
        [] (int a, int b) {return a%2 == 0 && b%2 == 0 && a < b;},
        [=] (int a, int b) {return isPrime (a) && !isPrime (b);},
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a < 10 && b >= 10;},  // need to define a method to add new predicates using loops
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a < 20 && b >= 20;},
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a < 30 && b >= 30;},
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a < 40 && b >= 40;},
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a < 50 && b >= 50;},
        [=] (int a, int b) {return isPrime (a) && isPrime (b) && a > b;},  // the primes in decreasing value within their groups
        [] (int a, int b) {return a%10 == 7 && b%10 != 7;},
        [] (int a, int b) {return a%10 < b%10;},
        [] (int a, int b) {return a < b;}
    );

    int a[] = {19, 22, 11, 23, 25, 31, 40, 37, 32, 35, 45, 21, 33, 21, 38, 25, 47, 27, 16, 47, 39, 16, 25, 5, 7, 35, 48, 17, 27, 57, 31, 29, 23, 43, 17, 41, 3, 7, 13};
    
    std::sort (std::begin (a), std::end (a), comp) ;
    for (int v : a) 
		std::cout << v << ' ' ;
    std::cout << '\n' ;

How to define a function to allow the part that needs a loop, where we have (arbitrarily many) groups of 10? I tried something along the lines of

template <typename T, typename...BINARY_PREDICATE, typename...ADDED>
predicate_builder<T, BINARY_PREDICATE..., ADDED...> add (predicate_builder<T, BINARY_PREDICATE...>& comp, ADDED...added) {
	predicate_builder<T, BINARY_PREDICATE..., ADDED...> newComp; 
	// ???
	return newComp;
}

but cannot find what to put inside, because augmenting at the end means creating a new base class for all the previous.

[JLBorges]

How is the predicate_builder<> getting involved in this? predicate_builder<> just composes a binary predicate out of a set of binary predicates; keep separate concerns separate.

There is no requirement that every predicate must be a lambda expression. For complex predicates, write a function object; lambda expressions are good when they are short and sweet.

// prime numbers then placed in groups in the order 1-9, 10-19, 20-29, 30-39, 40-49 
// (and in decreasing value within each group)
struct primes_in_groups
{
    bool operator() ( int a, int b ) const
    {
        const bool is_prime_a = is_prime(a) ;
        const bool is_prime_b = is_prime(b) ;

        switch( is_prime_a + is_prime_b )
        {
            case 0 : return false ;
            case 1 : return is_prime_a ;
            default : // both are prime numbers
                if( a/10 == b/10 ) return a > b ;
                else return a/10 < b/10 ;
        }
    }

    static bool is_prime( int n )
    {
        if( n < 2 ) return false ;
        if( n == 2 ) return true ;
        if( n%2 == 0 ) return false ;
        int ubsqrt = std::sqrt(n) + 2 ;
        for( int i = 3 ; i < ubsqrt ; i += 2 ) if( n%i == 0 ) return false ;
        return true ;
    }
};

int main()
{
    // 25 placed first before anything else
    // 16 to be placed after everything else,
    // even numbers placed after all 25's, if any, have been placed
    // (and the even numbers sorted in increasing value among themselves)
    // prime numbers then placed in groups in the order 1-9, 10-19, 20-29, 30-39, 40-49 
    // (and in decreasing value within each group)
	// after these order on ascending last digit,
    // except that last digit 7 appears before other last digits,
    // if last digits are equal, order by increasing value

    const auto even_numbers = [] ( int a, int b )
    {
        if( a%2 == 0 && b%2 == 0 ) return a<b ;
        else return a%2 == 0 && b%2 != 0 ;
    };

    const auto comp = compose<int>
    (
     	[] (int a, int b) {return a == 25 && b != 25;},
        [] (int a, int b) {return a != 16 && b == 16;},
        even_numbers,
        primes_in_groups(),
        [] (int a, int b) {return a%10 == 7 && b%10 != 7;},
        [] (int a, int b) {return a%10 < b%10;},
        [] (int a, int b) {return a < b;}
    );

    int a[] = { 19, 22, 11, 23, 25, 31, 40, 37, 32, 35, 45, 21, 33, 21, 38, 25, 47, 27, 16,
                47, 39, 16, 25, 5, 7, 35, 48, 17, 27, 57, 31, 29, 23, 43, 17, 41, 3, 7, 13 };

    std::sort (std::begin (a), std::end (a), comp ) ;
    for( int v : a ) std::cout << v << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/9ac80dd728a2f103