1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 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 UI_GFX_BREAK_LIST_H_ 6 #define UI_GFX_BREAK_LIST_H_ 7 8 #include <utility> 9 #include <vector> 10 11 #include "base/basictypes.h" 12 #include "base/logging.h" 13 #include "ui/gfx/range/range.h" 14 15 namespace gfx { 16 17 // BreakLists manage ordered, non-overlapping, and non-repeating ranged values. 18 // These may be used to apply ranged colors and styles to text, for an example. 19 // 20 // Each break stores the start position and value of its associated range. 21 // A solitary break at position 0 applies to the entire space [0, max_). 22 // |max_| is initially 0 and should be set to match the available ranged space. 23 // The first break always has position 0, to ensure all positions have a value. 24 // The value of the terminal break applies to the range [break.first, max_). 25 // The value of other breaks apply to the range [break.first, (break+1).first). 26 template <typename T> 27 class BreakList { 28 public: 29 // The break type and const iterator, typedef'ed for convenience. 30 typedef std::pair<size_t, T> Break; 31 typedef typename std::vector<Break>::const_iterator const_iterator; 32 33 // Initialize a break at position 0 with the default or supplied |value|. 34 BreakList(); 35 explicit BreakList(T value); 36 37 const std::vector<Break>& breaks() const { return breaks_; } 38 39 // Clear the breaks and set a break at position 0 with the supplied |value|. 40 void SetValue(T value); 41 42 // Adjust the breaks to apply |value| over the supplied |range|. 43 void ApplyValue(T value, const Range& range); 44 45 // Set the max position and trim any breaks at or beyond that position. 46 void SetMax(size_t max); 47 size_t max() const { return max_; } 48 49 // Get the break applicable to |position| (at or preceeding |position|). 50 typename std::vector<Break>::iterator GetBreak(size_t position); 51 typename std::vector<Break>::const_iterator GetBreak(size_t position) const; 52 53 // Get the range of the supplied break; returns the break's start position and 54 // the next break's start position (or |max_| for the terminal break). 55 Range GetRange(const typename BreakList<T>::const_iterator& i) const; 56 57 // Comparison functions for testing purposes. 58 bool EqualsValueForTesting(T value) const; 59 bool EqualsForTesting(const std::vector<Break>& breaks) const; 60 61 private: 62 #ifndef NDEBUG 63 // Check for ordered breaks [0, |max_|) with no adjacent equivalent values. 64 void CheckBreaks(); 65 #endif 66 67 std::vector<Break> breaks_; 68 size_t max_; 69 }; 70 71 template<class T> 72 BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) { 73 } 74 75 template<class T> 76 BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) { 77 } 78 79 template<class T> 80 void BreakList<T>::SetValue(T value) { 81 breaks_.clear(); 82 breaks_.push_back(Break(0, value)); 83 } 84 85 template<class T> 86 void BreakList<T>::ApplyValue(T value, const Range& range) { 87 if (!range.IsValid() || range.is_empty()) 88 return; 89 DCHECK(!breaks_.empty()); 90 DCHECK(!range.is_reversed()); 91 DCHECK(Range(0, max_).Contains(range)); 92 93 // Erase any breaks in |range|, then add start and end breaks as needed. 94 typename std::vector<Break>::iterator start = GetBreak(range.start()); 95 start += start->first < range.start() ? 1 : 0; 96 typename std::vector<Break>::iterator end = GetBreak(range.end()); 97 T trailing_value = end->second; 98 typename std::vector<Break>::iterator i = 99 start == breaks_.end() ? start : breaks_.erase(start, end + 1); 100 if (range.start() == 0 || (i - 1)->second != value) 101 i = breaks_.insert(i, Break(range.start(), value)) + 1; 102 if (trailing_value != value && range.end() != max_) 103 breaks_.insert(i, Break(range.end(), trailing_value)); 104 105 #ifndef NDEBUG 106 CheckBreaks(); 107 #endif 108 } 109 110 template<class T> 111 void BreakList<T>::SetMax(size_t max) { 112 typename std::vector<Break>::iterator i = GetBreak(max); 113 i += (i == breaks_.begin() || i->first < max) ? 1 : 0; 114 breaks_.erase(i, breaks_.end()); 115 max_ = max; 116 117 #ifndef NDEBUG 118 CheckBreaks(); 119 #endif 120 } 121 122 template<class T> 123 typename std::vector<std::pair<size_t, T> >::iterator BreakList<T>::GetBreak( 124 size_t position) { 125 typename std::vector<Break>::iterator i = breaks_.end() - 1; 126 for (; i != breaks_.begin() && i->first > position; --i); 127 return i; 128 } 129 130 template<class T> 131 typename std::vector<std::pair<size_t, T> >::const_iterator 132 BreakList<T>::GetBreak(size_t position) const { 133 typename std::vector<Break>::const_iterator i = breaks_.end() - 1; 134 for (; i != breaks_.begin() && i->first > position; --i); 135 return i; 136 } 137 138 template<class T> 139 Range BreakList<T>::GetRange( 140 const typename BreakList<T>::const_iterator& i) const { 141 const typename BreakList<T>::const_iterator next = i + 1; 142 return Range(i->first, next == breaks_.end() ? max_ : next->first); 143 } 144 145 template<class T> 146 bool BreakList<T>::EqualsValueForTesting(T value) const { 147 return breaks_.size() == 1 && breaks_[0] == Break(0, value); 148 } 149 150 template<class T> 151 bool BreakList<T>::EqualsForTesting(const std::vector<Break>& breaks) const { 152 if (breaks_.size() != breaks.size()) 153 return false; 154 for (size_t i = 0; i < breaks.size(); ++i) 155 if (breaks_[i] != breaks[i]) 156 return false; 157 return true; 158 } 159 160 #ifndef NDEBUG 161 template <class T> 162 void BreakList<T>::CheckBreaks() { 163 DCHECK_EQ(breaks_[0].first, 0U) << "The first break must be at position 0."; 164 for (size_t i = 0; i < breaks_.size() - 1; ++i) { 165 DCHECK_LT(breaks_[i].first, breaks_[i + 1].first) << "Break out of order."; 166 DCHECK_NE(breaks_[i].second, breaks_[i + 1].second) << "Redundant break."; 167 } 168 if (max_ > 0) 169 DCHECK_LT(breaks_.back().first, max_) << "Break beyond max position."; 170 } 171 #endif 172 173 } // namespace gfx 174 175 #endif // UI_GFX_BREAK_LIST_H_ 176
