fork(1) download
copy 
  1. // Experimental sliding window class. (1.01)
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <iterator>
  8. #include <cassert>
  9.  
  10. // class MaxQueue
  11. // Queue that evicts oldest elements when a specified
  12. // size is exceeded.
  13.  
  14. template<typename T>
  15. class MaxQueue : std::deque<T> {
  16.     typedef std::deque<T> _Base;
  17.     std::size_t m_maxlen;
  18.  
  19. public:
  20.     using _Base::front;
  21.     using _Base::empty;
  22.     using _Base::size;
  23.     using _Base::clear;
  24.     using _Base::begin;
  25.     using _Base::end;
  26.  
  27.     MaxQueue(std::size_t maxlen)
  28.     : m_maxlen(maxlen)
  29.     {}
  30.  
  31.     void push(T x) {
  32.         if (m_maxlen == 0)
  33.             return;
  34.         if (m_maxlen == _Base::size())
  35.             _Base::pop_front();
  36.         _Base::push_back(std::move(x));
  37.     }
  38.  
  39.     void pop() {
  40.         _Base::pop_front();
  41.     }
  42. };
  43.  
  44. // class SlidingWindow.
  45. // Group a sequence into sequential n-element chunks.
  46. // SlidingWindow(string("ABCDEF"), 4) -> ABCD, BCDE, CDEF
  47.  
  48. template<typename Iterable>
  49. class SlidingWindow {
  50.     typedef typename Iterable::const_iterator iterator;
  51.     typedef typename Iterable::value_type value_type;
  52.  
  53. public:
  54.     typedef MaxQueue<value_type> result_type;
  55.  
  56.     template<typename Iter>
  57.     SlidingWindow(Iter, Iter, std::size_t n);
  58.     SlidingWindow(Iterable, std::size_t n);
  59.     const result_type& next();
  60.  
  61. private:
  62.     Iterable m_v;
  63.     result_type m_q;
  64.     iterator m_first, m_last;
  65. };
  66.  
  67. #if __cplusplus >= 201703
  68. template<typename Iter>
  69. SlidingWindow(Iter, Iter, std::size_t) ->
  70.     SlidingWindow<std::vector<typename std::iterator_traits<Iter>::value_type>>;
  71. #endif // C++17
  72.  
  73. template<typename Iterable>
  74. template<typename Iter>
  75. SlidingWindow<Iterable>::SlidingWindow(Iter first, Iter last, std::size_t n)
  76. : SlidingWindow({first, last}, n)
  77. {}
  78.  
  79. template<typename Iterable>
  80. SlidingWindow<Iterable>::SlidingWindow(Iterable v, std::size_t n)
  81. : m_v(move(v)), m_q(n), m_first(begin(m_v)), m_last(end(m_v))
  82. {
  83.     for (std::size_t i = 1; i < n && m_first != m_last; i++)
  84.         m_q.push(*m_first++);
  85. }
  86.  
  87. template<typename Iterable>
  88. auto SlidingWindow<Iterable>::next() -> const result_type&
  89. {
  90.     if (m_first != m_last)
  91.         m_q.push(*m_first++);
  92.     else
  93.         m_q.clear();
  94.     return m_q;
  95. }
  96.  
  97. // Test.
  98.  
  99. int main()
  100. {
  101.     using std::cout;
  102.     using std::endl;
  103.  
  104.     // max queue.
  105.     int n = 5;
  106.     MaxQueue<int> q(n);
  107.     // push/size.
  108.     for (int i = 0; i < 2*n; i++) {
  109.         q.push(i);
  110.         int m = q.size();
  111.         assert(m == i+1 || m == n);
  112.         for (auto x : q) cout << x << ' ';
  113.         cout << endl;
  114.     }
  115.     // copy.
  116.     MaxQueue<int> p = q;
  117.     // empty/pop.
  118.     while (!p.empty()) {
  119.         p.pop();
  120.         cout << endl;
  121.         for (auto x : p) cout << x << ' ';
  122.     }
  123.     // clear.
  124.     q.clear();
  125.     assert(q.size() == 0);
  126.  
  127.     // sliding window.
  128.     std::string s = "ABCDEFGH";
  129.     for (size_t i = 0; i <= s.size()+1; i++) {
  130.         // construct(iterable, n).
  131. #if __cplusplus >= 201703
  132.         SlidingWindow sw(s, i);
  133. #else
  134.         SlidingWindow<decltype(s)> sw(s, i);
  135. #endif // C++17
  136.         cout << endl << i << "> ";
  137.         for (;;) {
  138.             auto window = sw.next();
  139.             if (window.empty())
  140.                 break; // done.
  141.             assert(window.size() == i);
  142.             for (auto x : window) cout << x;
  143.             cout << ' ';
  144.         }
  145.     }
  146.     for (size_t i = 0; i <= s.size()+1; i++) {
  147.         // construct(iterator, iterator, n).
  148. #if __cplusplus >= 201703
  149.         SlidingWindow sw(begin(s), end(s), i);
  150. #else
  151.         // The deduction guide uses vector but any iterable container
  152.         // can be used (here we use string).
  153.         SlidingWindow<decltype(s)> sw(begin(s), end(s), i);
  154. #endif // C++17
  155.         cout << endl << i << "> ";
  156.         for (;;) {
  157.             auto window = sw.next();
  158.             if (window.empty())
  159.                 break; // done.
  160.             assert(window.size() == i);
  161.             for (auto x : window) cout << x;
  162.             cout << ' ';
  163.         }
  164.     }
  165. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
1 2 3 4 5 
2 3 4 5 6 
3 4 5 6 7 
4 5 6 7 8 
5 6 7 8 9 

6 7 8 9 
7 8 9 
8 9 
9 

0> 
1> A B C D E F G H 
2> AB BC CD DE EF FG GH 
3> ABC BCD CDE DEF EFG FGH 
4> ABCD BCDE CDEF DEFG EFGH 
5> ABCDE BCDEF CDEFG DEFGH 
6> ABCDEF BCDEFG CDEFGH 
7> ABCDEFG BCDEFGH 
8> ABCDEFGH 
9> 
0> 
1> A B C D E F G H 
2> AB BC CD DE EF FG GH 
3> ABC BCD CDE DEF EFG FGH 
4> ABCD BCDE CDEF DEFG EFGH 
5> ABCDE BCDEF CDEFG DEFGH 
6> ABCDEF BCDEFG CDEFGH 
7> ABCDEFG BCDEFGH 
8> ABCDEFGH 
9>
https://ideone.com/tlAGFh
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!