CODEWITHSUNDEEP
c++algorithm
Fredrik
Fredrik

Reputation: 355

c++ order range with values that doesn't fulfill strict weak ordering

I need to order values in a range so the range represent a chain.

struct Link
{
   int id;
   int next;
};

The values of Link::id and Link::next are arbitrary, and do not provide any semantic meaning by them selves (not for the ordering algorithm any way).

The relationship between two links (after ordering) is: lhs.next is exactly rhs.id.

preconditions

Example:

std::vector< Link> range{ { 4, 1}, { 1, 5}, { 3, 4}, { 2, 3}};
auto chain = some_algorithm( range);
// expect the ordering to be: { { 2, 3}, { 3, 4}, { 4, 1}, { 1, 5}};

I can think of at least two approaches, but I suspect this has been solved in an idiomatic way. So, my question is: how to solve this in an idiomatic way?

Upvotes: 1

Views: 147

Answers (2)

Fredrik
Fredrik

Reputation: 355

This is what I came up with:

The "concept" R is some type that that behaves range-like, could be a container, could be something else.

If there are gaps (link-wise) in the range, new chains will be ordered. I didn't want to have some "assert-output", or throwing. I still maintain my goals, since in my use-case I know all values can form exactly one chain.

  template< typename R, typename ISP>
  R chain( R range, ISP is_link_predicate)
  {
     auto first = std::begin( range);
     auto current = first;
     const auto last = std::end( range);

     while( current != last)
     {
        const auto next = current + 1;

        // try to find a value in [next, last) that can be linked with *current.
        auto link = std::find_if( next, last, [current,is_link_predicate]( auto& value){
           return is_link_predicate( *current, value);
        });

        if( link != last)
        {
           using std::swap;
           swap( *next, *link);
           current = next;
        }
        else
        {
           // we need to check if some value in [next, last) can be "inserted" in the
           // beginning of the chain. That is, can form a link with *first.
           auto new_first = std::find_if( next, last, [first,is_link_predicate]( auto& value){
              return is_link_predicate( value, *first);
           });

           if( new_first != last)
           {
              // we got a new_first, we need to rotate it first
              //
              // C = current
              // N = next (not ordered).
              // - = ordered values
              // = = not ordered values
              // X = value to be "inserted" first, new_first
              //
              // -----CN====X===  we start with
              // X-----C========  we end up with
              //
              std::rotate( first, new_first, new_first + 1);
              current = next;
           }
           else
           {
              // no values in [next, last) is part of the current chain.
              // we start building the next chain.
              current = next;
              first = current;
           }
        }
     }

     return range;
  }

Comments?

Upvotes: 0

stefaanv
stefaanv

Reputation: 14392

I doubt that there is a idiomatic way because this isn't a common case.

Chaining is mostly done by pointers/iterators (e.g. std::list) and the actual chaining is mostly done while inserting.

The interesting thing would be to find the first link and what to do with circular chaining and with error cases.

Upvotes: 4

Related Questions