xref: /aosp_15_r20/external/libchrome-gestures/include/vector.h (revision aed3e5085e770be5b69ce25295ecf6ddf906af95)
1 // Copyright 2011 The ChromiumOS Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef GESTURES_VECTOR_H__
6 #define GESTURES_VECTOR_H__
7 
8 #include <algorithm>
9 
10 #include "include/logging.h"
11 
12 namespace gestures {
13 
14 // This class allows range-based for loops to iterate over a subset of
15 // array elements, by only yielding those elements for which the
16 // AcceptMethod returns true.
17 // This class wraps around a pair of iterators, all changes to the
18 // yielded elements will modify the original array.
19 template <typename ValueType>
20 class FilteredRange {
21  public:
22   typedef bool (*AcceptMethod)(const ValueType&);
23 
24   // This class defineds a basic forward iterator that iterates over
25   // an array but skips elements for which the AcceptMethod yields false.
26   class RangeIterator {
27    public:
28     // creates a new iterator and advances to the first accepted
29     // element in the array.
RangeIterator(ValueType * i,ValueType * end,AcceptMethod accept)30     RangeIterator(ValueType* i, ValueType* end, AcceptMethod accept)
31         : iter_(i), end_(end), accept_(accept) {
32       NextAcceptedIter();
33     }
34 
35     // operator++ is required by the STL for forward iterators.
36     // Instead of advancing to the next array element, this iterator
37     // will advance to the next accepted array element
38     ValueType* operator++ () {
39       ++iter_;
40       NextAcceptedIter();
41       return iter_;
42     }
43 
44     // operator* is required by the STL for forward iterators.
45     ValueType& operator*() {
46       return *iter_;
47     }
48 
49     // operator-> is required by the STL for forward iterators.
50     ValueType& operator->() {
51       return *iter_;
52     }
53 
54     // operator!= is required by the STL for forward iterators.
55     bool operator!= (const RangeIterator& o) {
56       return iter_ != o.iter_;
57     }
58 
59     // operator== is required by the STL for forward iterators.
60     bool operator== (const RangeIterator& o) {
61       return iter_ == o.iter_;
62     }
63 
64    private:
NextAcceptedIter()65     void NextAcceptedIter() {
66       while (!accept_(*iter_) && iter_ != end_)
67         ++iter_;
68     }
69 
70     ValueType* iter_;
71     ValueType* end_;
72     AcceptMethod accept_;
73   };
74 
75   // Create a new filtered range from begin/end pointer to an array.
FilteredRange(ValueType * begin,ValueType * end,AcceptMethod accept)76   FilteredRange(ValueType* begin, ValueType* end, AcceptMethod accept)
77       : begin_(begin), end_(end), accept_(accept) {}
78 
79   // Returns a forward iterator to the first accepted element of the array.
begin()80   RangeIterator begin() {
81     return RangeIterator(begin_, end_, accept_);
82   }
83 
84   // Returns an iterator to the element after the last element of the array.
end()85   RangeIterator end() {
86     return RangeIterator(end_, end_, accept_);
87   }
88 
89  private:
90   ValueType* begin_;
91   ValueType* end_;
92   AcceptMethod accept_;
93 };
94 
95 // The vector class mimicks a subset of the std::vector functionality
96 // while using a fixed size of memory to avoid calls to malloc/free.
97 // The limitations of this class are:
98 // - All insert operations might invalidate existing iterators
99 // - Currently, the ValueType type should be a POD type or aggregate of PODs,
100 //   since ctors/dtors aren't called propertly on ValueType objects.
101 // - Out of range element access will always return the end() iterator
102 //   and print an error, instead of throwing an exception.
103 // This class includes a non-standard extension to return a
104 // FilteredRange object iterating over the underlying array.
105 template<typename ValueType, size_t kMaxSize>
106 class vector {
107  public:
108   typedef ValueType value_type;
109   typedef ValueType* iterator;
110   typedef const ValueType* const_iterator;
111   typedef std::reverse_iterator<iterator> reverse_iterator;
112   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
113   typedef bool (*AcceptMethod)(const ValueType&);
114 
vector()115   vector() : size_(0) {}
vector(const vector<ValueType,kMaxSize> & that)116   vector(const vector<ValueType, kMaxSize>& that) {
117     *this = that;
118   }
119   template<size_t kThatSize>
vector(const vector<ValueType,kThatSize> & that)120   vector(const vector<ValueType, kThatSize>& that) {
121     *this = that;
122   }
123 
size()124   size_t size() const { return size_; }
empty()125   bool empty() const { return size() == 0; }
126 
127   // methods for const element access
128 
begin()129   const_iterator begin() const { return buffer_; }
end()130   const_iterator end() const { return &buffer_[size_]; }
rbegin()131   const_reverse_iterator rbegin() const {
132     return const_reverse_iterator(end());
133   }
rend()134   const_reverse_iterator rend() const {
135     return const_reverse_iterator(begin());
136   }
find(const ValueType & value)137   const_iterator find(const ValueType& value) const {
138     for (size_t i = 0; i < size_; ++i)
139       if (buffer_[i] == value)
140         return const_iterator(&buffer_[i]);
141     return end();
142   }
at(size_t idx)143   const ValueType& at(size_t idx) const {
144     if (idx >= size()) {
145       Err("vector::at: index out of range");
146       idx = size() - 1;
147     }
148     return buffer_[idx];
149   }
150   const ValueType& operator[](size_t idx) const { return buffer_[idx]; }
151 
152   // methods for non-const element access:
153 
begin()154   iterator begin() { return buffer_; }
end()155   iterator end() { return &buffer_[size_]; }
rbegin()156   reverse_iterator rbegin() { return reverse_iterator(end()); }
rend()157   reverse_iterator rend() { return reverse_iterator(begin()); }
find(const ValueType & value)158   iterator find(const ValueType& value) {
159     return const_cast<iterator>(
160         const_cast<const vector<ValueType, kMaxSize>*>(this)->find(value));
161   }
at(size_t idx)162   ValueType& at(size_t idx) {
163     return const_cast<ValueType&>(
164         const_cast<const vector<ValueType, kMaxSize>*>(this)->at(idx));
165   }
166   ValueType& operator[](size_t idx) { return buffer_[idx]; }
167 
168   // methods for inserting elements
169   // note that all these methods might invalidate existing iterators
170 
push_back(const ValueType & value)171   void push_back(const ValueType& value) {
172     insert(end(), value);
173   }
174 
insert(iterator position,const ValueType & value)175   iterator insert(iterator position, const ValueType& value) {
176     return insert(position, &value, (&value) + 1);
177   }
178 
insert(iterator position,const_iterator first,const_iterator last)179   iterator insert(iterator position, const_iterator first,
180                   const_iterator last) {
181     size_t count = last - first;
182     if (size_ + count > kMaxSize) {
183       Err("vector::insert: out of space!");
184       return end();
185     }
186 
187     std::copy(rbegin(), reverse_iterator(position),
188               reverse_iterator(end() + count));
189     size_ = size_ + count;
190     std::copy(first, last, position);
191     return position;
192   }
193 
194   // methods for erasing elements
195   // note that all these methods might invalidate existing iterators
196 
erase(iterator it)197   iterator erase(iterator it) {
198     return erase(it, it + 1);
199   }
200 
erase(iterator first,iterator last)201   iterator erase(iterator first, iterator last) {
202     size_t count = last - first;
203     std::copy(last, end(), first);
204     for (iterator it = end() - count, e = end(); it != e; ++it)
205       (*it).~ValueType();
206     size_ = size_ - count;
207     return first;
208   }
209 
clear()210   void clear() {
211     erase(begin(), end());
212   }
213 
214   template<size_t kThatSize>
215   vector<ValueType, kMaxSize>& operator=(
216       const vector<ValueType, kThatSize>& that) {
217     clear();
218     insert(begin(), that.begin(), that.end());
219     return *this;
220   }
221 
222  private:
223   ValueType buffer_[kMaxSize];
224   size_t size_;
225 };
226 
227 }  // namespace gestures
228 
229 #endif  // GESTURES_VECTOR_H__
230