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