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