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); }

...

Miranor Home | About Miranor | About Elgrint | Create account | Login | Account settings | Contact Us | Privacy Policy | Site map

© Copyright 2014 by Miranor. All rights reserved. By using this site you agree to the Terms of Use.

Page last updated on August 10th, 2014.