About

maxon::BaseSort is a class template that allows to sort data in arrays and to search in sorted arrays. For a default implementation handling simple data types see maxon::SimpleSort.

Note: See also SortedArray.

Create

A new sorting class is created by implementing a custom class based on maxon::BaseSort. This custom class may implement:

LessThan(): For sorting elements in an array.
IsEqual(): For finding elements in an array.

Further flags that can be set are:

maxon::BASESORTFLAGS::NONE: Always use constructor/destructor or move operator, never memcpy, memmove or realloc.
maxon::BASESORTFLAGS::MOVEANDCOPYOBJECTS: Elements are PODs and can be moved and copied using memcpy and moved using memmove.

Sorting

An instance of the custom sorting class can be used to sort the elements stored in a maxon::BaseArray.

maxon::BaseSort::Sort(): Sorts the elements of the given iterateable.

    // This example defines a BaseSort class for a simple data type
    // and applies it to a BaseArray.
 
    // custom BaseSort based class to sort integer values
    class IntegerSort : public maxon::BaseSort<IntegerSort, maxon::BASESORTFLAGS::MOVEANDCOPYOBJECTS>
    {
public:
      static inline Bool LessThan(maxon::Int a, maxon::Int b)
      {
        return a < b;
      }
    };
 
    // prepare array
    maxon::BaseArray<maxon::Int> numbers;
    numbers.Resize(count) iferr_return;
 
    // custom function to fill the array with random values
    FillWithRandomNumbers(numbers);
 
    // sort the elements stored in the array
    IntegerSort sort;
    sort.Sort(numbers);
 
    // check result
    for (const maxon::Int& number : numbers)
      DiagnosticOutput("Number: @", number);

Searching

To find elements in the given array, the array must be sorted. The custom sorting class must implement both LessThan() and IsEqual().

maxon::BaseSort::Find(): Returns the element with the given value in the array.
maxon::BaseSort::FindIndex(): Returns the index of the element with the given value.
maxon::BaseSort::FindInsertionIndex(): Returns the element of the given value or returns the insertion index if the element was not found.

    // This example defines a BaseSort class for a custom data type
    // and uses it to sort and search in a BaseArray.
 
    // custom BaseSort based class to sort CustomDate data.
    // it also allows to compare maxon::Int with CustomDate.
    class DateSort : public maxon::BaseSort<DateSort>
    {
public:
      // compare CustomDate with CustomDate
 
      static inline Bool LessThan(CustomDate key, CustomDate element)
      {
        if (key.year > element.year)
          return false;
        if (key.year < element.year)
          return true;
 
        if (key.month > element.month)
          return false;
        if (key.month < element.month)
          return true;
 
        if (key.day >= element.day)
          return false;
        return true;
      }
      static inline Bool IsEqual(CustomDate key, CustomDate element)
      {
        if (key.year != element.year)
          return false;
        if (key.month != element.month)
          return false;
        if (key.day != element.day)
          return false;
        return true;
      }
 
      // compare maxon::Int with CustomDate
 
      static inline Bool LessThan(maxon::Int key, CustomDate element)
      {
        return key < element.year;
      }
      static inline Bool IsEqual(maxon::Int key, CustomDate element)
      {
        return key == element.year;
      }
    };
 
    // create data
    maxon::BaseArray<CustomDate> dates;
    dates.Resize(count) iferr_return;
 
    // custom function to fill the array with random dates
    FillWithRandomDates(dates);
 
    // sort array
    DateSort sort;
    sort.Sort(dates);
 
    // search in the array
 
    const CustomDate* const date = sort.Find(2000, dates);
    if (date)
      DiagnosticOutput("@:@:@", date->year, date->month, date->day);
 
    const maxon::Int index = sort.FindIndex(2000, dates.Begin(), dates.GetCount());
    if (index > 0)
      DiagnosticOutput("Index: @", index);
 
    // new element
 
    CustomDate newDate;
    newDate.year  = 1970;
    newDate.month = 1;
    newDate.day = 1;
 
    // insert new element
 
    maxon::Int insertionIndex;
    sort.FindInsertionIndex(newDate, dates, insertionIndex);
    dates.Insert(insertionIndex, newDate) iferr_return;

Table of Contents

About

Create

Sorting

Searching

Further Reading