MSortList.h
/********************************************************************************
* MSortList class template
* Elgrint library, version 1.0
* Created by Dimitry Rotstein
* Copyright(C) 2013 by Miranor
* Description:
* - Defines a sorted linear container with O(lgn) insert/remove/search operations
* - All elements inserted to MSortList are automatically sorted using operator<
* - MSortList is built on top of MWidthList with 'x+y=max(x,y)' definition,
* but ultimately it's built on top of MVector (see MVector.h for more info)
*
*******************************************************************************/
#ifndef MIRANOR_ELGRINT_SORTLIST
#define MIRANOR_ELGRINT_SORTLIST
#include "MWidthList.h"
namespace Elgrint
{
/////////////////////////////////////////////////////////////////////////////////
//////////////////////////// MSortList Declaration //////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
template <class T>
class MSortList
{
public:
// Revealers
// Common (see MVector)
inline MNum cnt() const;
inline bool isError() const;
// Specific
inline bool has(const T& x) const;
inline T getMax() const; // Must be non-empty (use CIter for getMin)
// Mutators
// Common (see MVector)
inline bool operator=(const MSortList& lst); // Needed to return bool
inline bool swapWith(MSortList& lst);
inline bool reset();
inline void setError(bool err);
// Specific
inline bool insert(const T& x); // Insert 'x' while preserving the order
inline bool remove(const T& x); // Remove 'x' if exists
// Auxiliary core type (must be defined before the iterators)
private:
struct _Item
{
T x;
inline explicit _Item(const T& ax) : x(ax) {}
inline bool operator<(const _Item& it) const { return x < it.x; }
inline _Item operator+(const _Item& it) const { return _Item(Max(x,it.x)); }
inline bool operator>(int n) const { return n == 0; }
};
public:
// Iterator (const only - changing values directly may break sorting)
class CIter
{
public:
// Initializers (copy c-tor is implied)
// Common
inline CIter() {}
inline CIter(const MSortList& lst) : m_it(lst.m_lst) {}
// Specific
inline CIter(const MSortList& lst, const T& x) : m_it(lst.m_lst,_Item(x)) {}
// Revealers
// Common
inline bool operator()() const { return m_it(); }
inline bool operator==(const CIter& it) const { return m_it == it.m_it; }
inline bool operator!=(const CIter& it) const { return m_it != it.m_it; }
inline const T& operator*() const
{
M_PARAM_CHECK((*this)(), "Trying to dereference invalid MSortList::CIter");
return (*m_it).x;
}
// Mutators
// Common
inline void operator++() { ++m_it; }
inline void reset() { m_it.reset(); }
// Data members
protected:
typename MWidthList<_Item>::CIter m_it;
};
// Data members
private:
MWidthList<_Item> m_lst;
};
// 'Swap' specialization for better performance (especially if a,b are unshareable)
template <class T>
inline void Swap(MSortList<T>& a, MSortList<T>& b) { a.swapWith(b); }
...