source: icXML/icXML-devel/src/icxmlc/RunLengthQueue.hpp @ 2720

Last change on this file since 2720 was 2720, checked in by cameron, 6 years ago

Initial check-in of icXML 0.8 source files

File size: 1.7 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: RunLengthQueue.hpp 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#ifndef RUNLENGTHQUEUE_HPP
14#define RUNLENGTHQUEUE_HPP
15
16#include <icxmlc/XMLConfig.hpp>
17#include <icxmlc/Array.hpp>
18
19template <typename T, size_t initialSize>
20class RunLengthQueue
21{
22                struct RunLengthQueueItem
23                {
24                        T                               item;
25                        size_t                  count;
26
27                        RunLengthQueueItem()
28                        : count(0)
29                        {
30
31                        }
32                };
33
34        public:
35
36                RunLengthQueue()
37                : _topIdx(0)
38                , _bottomIdx(0)
39                {
40
41                }
42
43                void add(T item);
44
45                bool next(T & item);
46
47        private:
48
49                DynamicArray<RunLengthQueueItem, initialSize * 2>               _queue;
50                size_t                                                                                                  _topIdx;
51                size_t                                                                                                  _bottomIdx;
52};
53
54template <typename T, size_t initialSize>
55void
56RunLengthQueue<T,initialSize>::add(T item)
57{
58        RunLengthQueueItem * bottom = &_queue[_bottomIdx];
59
60        if (likely(bottom->item == item))
61        {
62                bottom->count++;
63        }
64        else
65        {
66                if (unlikely(++_bottomIdx == _queue.capacity()))
67                {
68                        _queue.expand(_queue.capacity());
69                }
70                _queue[_bottomIdx];
71                bottom->item = item;
72                bottom->count = 1;
73        }
74}
75
76template <typename T, size_t initialSize>
77bool
78RunLengthQueue<T,initialSize>::next(T & item)
79{
80        RunLengthQueueItem * top = &_queue[_topIdx];
81
82        if (likely(top->count != 0))
83        {
84                top->count--;
85                item = top->item;
86                return 1;
87        }
88
89        if (likely(_topIdx != _bottomIdx))
90        {
91                top = &_queue[++_topIdx];
92                top->count--;
93                item = top->item;
94
95                if (unlikely((top->count == 0) && (_topIdx == _bottomIdx)))
96                {
97                        _topIdx = 0;
98                        _bottomIdx = 0;
99                }
100                return 1;
101        }
102
103        return 0;
104}
105
106#endif // RUNLENGTHQUEUE_HPP
Note: See TracBrowser for help on using the repository browser.