Re: [boost] [review] Last day for formal review for Sort library

9 Dec 2014


      Dupuis,

On Fri Nov 21 2014 at 12:01:24 AM Steven Ross  wrote:
...
Thanks for your input Dupuis.
On Thu Nov 20 2014 at 10:32:46 AM DUPUIS Etienne 
wrote:
...
Another example, sorting by birth data and then by name :
// --------------- Start of code snippet ------------------------
struct Id {
     std::string name;
     time_t birth;
bool operator<(const Id& id) const {
         return (birth < id.birth) || ((birth == id.birth) && (name <
id.name));
     }
};
// --------------- End of code snippet ------------------------
...
Again, I understand that I must use string_sort and split the birth date
into 8-bit components. Am I right ?
That's a good idea!  I'll add such an example if the library is deemed
worthy of including in boost.
I've added such an example to the develop branch that handles signed ints,
signed floats, and multiple string keys all together:
https://github.com/spreadsort/sort/blob/develop/example/generalizedstruct.cp...
And will mention it in the docs.  Surprisingly, considering all the
complexity of its get_char function, it's about 50% faster than std::sort
on random data formatted like this.  Below are the comparison and get_char
functions for you to see.  Comparison sorting is definitely easier, but
hybrid-radix sorting is feasible and surprisingly efficient even for
harder-to-represent cases:

struct DATA_TYPE {
  time_t birth;
  float net_worth;
  string first_name;
  string last_name;
};

static const int birth_size = sizeof(time_t);
static const int first_name_offset = birth_size + sizeof(float);
static const boost::uint64_t base_mask = 0xff;

struct lessthan {
  inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    if (x.birth != y.birth) {
      return x.birth < y.birth;
    }
    if (x.net_worth != y.net_worth) {
      return x.net_worth < y.net_worth;
    }
    if (x.first_name != y.first_name) {
      return x.first_name < y.first_name;
    }
    return x.last_name < y.last_name;
  }
};

struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    // Sort date as a signed int, returning the appropriate byte.
    if (offset < birth_size) {
      const int bit_shift = 8 * (birth_size - offset - 1);
      unsigned char result = (x.birth & (base_mask << bit_shift)) >>
bit_shift;
      // Handling the sign bit.  Unnecessary if the data is always positive.
      if (offset == 0) {
        return result ^ 128;
      }

      return result;
    }

    // Sort a signed float.  This requires reversing the order of negatives
    // because of the way floats are represented in bits.
    if (offset < first_name_offset) {
      const int bit_shift = 8 * (first_name_offset - offset - 1);
      unsigned key = float_mem_cast(x.net_worth);
      unsigned char result = (key & (base_mask << bit_shift)) >> bit_shift;
      // Handling the sign.
      if (x.net_worth < 0) {
        return 255 - result;
      }
      // Increasing positives so they are higher than negatives.
      if (offset == birth_size) {
        return 128 + result;
      }

      return result;
    }

    // Sort a string that is before the end.  This approach supports
embedded
    // nulls.  If embedded nulls are not required, then just delete the "*
2"
    // and the inside of the following if just becomes:
    // return x.first_name[offset - first_name_offset];
    const unsigned first_name_end_offset =
      first_name_offset + x.first_name.size() * 2;
    if (offset < first_name_end_offset) {
      int char_offset = offset - first_name_offset;
      // This signals that the string continues.
      if (!(char_offset & 1)) {
        return 1;
      }
      return x.first_name[char_offset >> 1];
    }

    // This signals that the string has ended, so that shorter strings come
    // before longer ones.
    if (offset == first_name_end_offset) {
      return 0;
    }

    // The final string needs no special consideration.
    return x.last_name[offset - first_name_end_offset - 1];
  }
};

struct getsize {
  inline size_t operator()(const DATA_TYPE &x) const {
    return first_name_offset + x.first_name.size() * 2 + 1 +
      x.last_name.size();
  }
};