uqueue.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // uqueue.h
   7 //
   8
   9 #ifndef UQUEUE_H_27F01FDB0D59B75277E0E5C41ABC6B5B
  10 #define UQUEUE_H_27F01FDB0D59B75277E0E5C41ABC6B5B
  11
  12 namespace ustl {
  13
  14 /// \class queue uqueue.h ustl.h
  15 /// \ingroup Sequences
  16 ///
  17 /// \brief Queue adapter to uSTL containers.
  18 ///
  19 /// The most efficient way to use this implementation is to fill the queue
  20 /// and the completely empty it before filling again.
  21 ///
  22 template <typename Sequence>
  23 class queue {
  24 public:
  25     typedef typename Sequence::value_type       value_type;
  26     typedef typename Sequence::size_type        size_type;
  27     typedef typename Sequence::difference_type  difference_type;
  28     typedef typename Sequence::reference        reference;
  29     typedef typename Sequence::const_reference  const_reference;
  30     typedef typename Sequence::pointer          pointer;
  31 public:
  32     inline                      queue (void)                    : m_Storage (), m_Front (0) { }
  33     explicit inline             queue (const Sequence& s)       : m_Storage (s), m_Front (0) { }
  34     inline size_type            size (void) const               { return (m_Storage.size() - m_Front); }
  35     inline bool                 empty (void) const              { return (!size()); }
  36     inline reference            front (void)                    { return (m_Storage [m_Front]); }
  37     inline const_reference      front (void) const              { return (m_Storage [m_Front]); }
  38     inline reference            back (void)                     { return (m_Storage.back()); }
  39     inline const_reference      back (void) const               { return (m_Storage.back()); }
  40     inline void                 push (const value_type& v);
  41     inline void                 pop (void);
  42     inline bool                 operator== (const queue& s)     { return (m_Storage == s.m_Storage && m_Front == s.m_Front); }
  43     inline bool                 operator< (const queue& s)      { return (size() < s.size()); }
  44 private:
  45     Sequence                    m_Storage;      ///< Where the data actually is.
  46     size_type                   m_Front;        ///< Index of the element returned by next pop.
  47 };
  48
  49 /// Pushes \p v on the queue.
  50 template <class Sequence>
  51 inline void queue<Sequence>::push (const value_type& v)
  52 {
  53     if (m_Front) {
  54         m_Storage.erase (m_Storage.begin(), m_Front);
  55         m_Front = 0;
  56     }
  57     m_Storage.push_back (v);
  58 }
  59
  60 /// Pops the topmost element from the queue.
  61 template <class Sequence>
  62 inline void queue<Sequence>::pop (void)
  63 {
  64     if (++m_Front >= m_Storage.size())
  65         m_Storage.resize (m_Front = 0);
  66 }
  67
  68 } // namespace ustl
  69
  70 #endif
  71