ComparatorUtils

A collection of utilities for comparators. More...

A collection of utilities for comparators.

#include <OpenMS/KERNEL/ComparatorUtils.h>

This file contains some lightweight class templates which simplify the (re-)usage and composition of comparator classes:

• ReverseComparator (reverse the direction of comparison)
• LexicographicComparator (combine comparators lexicographically)
• PointerComparator (compare pointers like the type they point to)

We provide corresponding "make-functions" so that you will not need to write out the type names in the template instantiation.

We explain this with a simple example. First a few prerequisites.

// --------------------------------------------------------------------------
//                   OpenMS -- Open-Source Mass Spectrometry
// --------------------------------------------------------------------------
// Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
// ETH Zurich, and Freie Universitaet Berlin 2002-2018.
//
// This software is released under a three-clause BSD license:
//  * Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//  * Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//  * Neither the name of any author or any participating institution
//    may be used to endorse or promote products derived from this software
//    without specific prior written permission.
// For a full list of authors, refer to the file AUTHORS.
// --------------------------------------------------------------------------
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
// INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

#include <OpenMS/KERNEL/ComparatorUtils.h>
#include <OpenMS/KERNEL/StandardTypes.h>
#include <OpenMS/KERNEL/MSExperiment.h>
#include <OpenMS/CONCEPT/Types.h>

using OpenMS::Int;
using OpenMS::UInt;
using OpenMS::Size;
using OpenMS::String;

The class IntRealString has three data members. The class IntRealStringVector is a vector of IntRealString. We add some print() methods for convenience.

// Simple class with three data members
class IntRealString
{
public:
  IntRealString(Int i, float r, String s) :
    i_(i), r_(r), s_(s) {}
  IntRealString(const IntRealString & rhs) :
    i_(rhs.i_), r_(rhs.r_), s_(rhs.s_) {}

  void print() const
  {
    std::cout << "(" << i_ << ", " << r_ << ", " << s_ << ")" << std::endl;
  }

  Int i_;
  float r_;
  String s_;
};

// A vector of IntRealString objects
class IntRealStringVector :
  public std::vector<IntRealString>
{
public:
  void print() const
  {
    for (Size i = 0; i < size(); ++i) (*this)[i].print();
    std::cout << std::endl;
  }

};

Now we will exercise various ways of sorting such a vector.

Of course, we could use the std::sort algorithm with a comparison function like the following.

// Comparison function
bool lessByInt(IntRealString left, IntRealString right)
{
  return left.i_ < right.i_;
}

This is straightforward but does not generalize well. Instead we introduce three comparator classes:

// Comparator class
struct LessByInt :
  std::binary_function<IntRealString, IntRealString, bool>
{
  bool operator()(IntRealString left, IntRealString right) const { return left.i_ < right.i_; }
};

// Comparator class
struct LessByReal :
  std::binary_function<IntRealString, IntRealString, bool>
{
  bool operator()(IntRealString left, IntRealString right) const { return left.r_ < right.r_; }
};

// Comparator class
struct LessByString :
  std::binary_function<IntRealString, IntRealString, bool>
{
  bool operator()(IntRealString left, IntRealString right) const { return left.s_ < right.s_; }
};

Note how the std::binary_function template provides the necessary type information (sometimes this is called "reflection").

Now we show various uses of the reverseComparator and lexicographicComparator function templates.

Int main()
{
  IntRealStringVector vec;
  vec.push_back(IntRealString(1, 4.5f, "paul"));
  vec.push_back(IntRealString(2, 4.5f, "josie"));
  vec.push_back(IntRealString(1, 4.5f, "john"));
  vec.push_back(IntRealString(2, 3.9f, "kim"));

  std::cout << "After initialization:" << std::endl;
  vec.print();

  std::cout << "Sorted using lessByInt function:" << std::endl;
  std::sort(vec.begin(), vec.end(), lessByInt);
  vec.print();

  std::cout << "Sorted using LessByInt comparator class:" << std::endl;
  std::sort(vec.begin(), vec.end(), LessByInt());
  vec.print();

  std::cout << "Sorted using reversed LessByInt comparator class:" << std::endl;
  std::sort(vec.begin(), vec.end(), OpenMS::reverseComparator(LessByInt()));
  vec.print();

  std::cout << "Sorted using lexicographic order: 1. LessByInt, 2. LessByReal" << std::endl;
  std::sort(vec.begin(), vec.end(), OpenMS::lexicographicComparator(LessByInt(), LessByReal()));
  vec.print();

  std::cout << "Sorted using lexicographic order: 1. reversed LessByInt, 2. LessByReal, 3. LessByString" << std::endl;
  std::sort(vec.begin(), vec.end(),
            OpenMS::lexicographicComparator
              (OpenMS::lexicographicComparator
              (
                OpenMS::reverseComparator(LessByInt()),
                LessByReal()
              ),
              LessByString()
              )
            );
  vec.print();

And here is an application of the pointerComparator function template:

  // vector of pointers into vec
  std::vector<const IntRealString *> ptr_vec;
  for (Size i = 0; i < vec.size(); ++i)
  {
    ptr_vec.push_back(&vec[i]);
  }

  std::cout << "ptr_vec before sorting" << std::endl;
  for (Size i = 0; i < ptr_vec.size(); ++i)
    ptr_vec[i]->print();
  std::cout << std::endl;

  std::sort(ptr_vec.begin(), ptr_vec.end(), OpenMS::pointerComparator(LessByString()));

  std::cout << "ptr_vec after sorting with pointerComparator(LessByString())" << std::endl;
  for (Size i = 0; i < ptr_vec.size(); ++i)
    ptr_vec[i]->print();
  std::cout << std::endl;

  return 0;
} //end of main

The output of the example program is:

After initialization:
  (1, 4.5, paul)
  (2, 4.5, josie)
  (1, 4.5, john)
  (2, 3.9, kim)

Sorted using lessByInt function:
  (1, 4.5, paul)
  (1, 4.5, john)
  (2, 4.5, josie)
  (2, 3.9, kim)

Sorted using LessByInt comparator class:
  (1, 4.5, paul)
  (1, 4.5, john)
  (2, 4.5, josie)
  (2, 3.9, kim)

Sorted using reversed LessByInt comparator class:
  (2, 4.5, josie)
  (2, 3.9, kim)
  (1, 4.5, paul)
  (1, 4.5, john)

Sorted using lexicographic order: 1. LessByInt, 2. LessByReal
  (1, 4.5, paul)
  (1, 4.5, john)
  (2, 3.9, kim)
  (2, 4.5, josie)

Sorted using lexicographic order: 1. reversed LessByInt, 2. LessByReal, 3. LessByString
  (2, 3.9, kim)
  (2, 4.5, josie)
  (1, 4.5, john)
  (1, 4.5, paul)

ptr_vec before sorting
  (2, 3.9, kim)
  (2, 4.5, josie)
  (1, 4.5, john)
  (1, 4.5, paul)

ptr_vec after sorting with pointerComparator(LessByString())
  (1, 4.5, john)
  (2, 4.5, josie)
  (2, 3.9, kim)
  (1, 4.5, paul)

Note that pointerComparator can also be used with full-blown iterator classes. (It should work with everything that provides an operator*(), but the typedefs will always be pointers.)

Note that these templates can also be used with different types for "left" and "right".