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/base/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 ui::Range& range); 44 45 // Set the max position and trim any breaks at or beyond that position. 46 void SetMax(size_t max); 47 48 // Get the break applicable to |position| (at or preceeding |position|). 49 typename std::vector<Break>::iterator GetBreak(size_t position); 50 typename std::vector<Break>::const_iterator GetBreak(size_t position) const; 51 52 // Get the range of the supplied break; returns the break's start position and 53 // the next break's start position (or |max_| for the terminal break). 54 ui::Range GetRange(const typename BreakList<T>::const_iterator& i) const; 55 56 // Comparison functions for testing purposes. 57 bool EqualsValueForTesting(T value) const; 58 bool EqualsForTesting(const std::vector<Break>& breaks) const; 59 60 private: 61 #ifndef NDEBUG 62 // Check for ordered breaks [0, |max_|) with no adjacent equivalent values. 63 void CheckBreaks(); 64 #endif 65 66 std::vector<Break> breaks_; 67 size_t max_; 68 }; 69 70 template<class T> 71 BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) { 72 } 73 74 template<class T> 75 BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) { 76 } 77 78 template<class T> 79 void BreakList<T>::SetValue(T value) { 80 breaks_.clear(); 81 breaks_.push_back(Break(0, value)); 82 } 83 84 template<class T> 85 void BreakList<T>::ApplyValue(T value, const ui::Range& range) { 86 if (!range.IsValid() || range.is_empty()) 87 return; 88 DCHECK(!breaks_.empty()); 89 DCHECK(!range.is_reversed()); 90 DCHECK(ui::Range(0, max_).Contains(range)); 91 92 // Erase any breaks in |range|, then add start and end breaks as needed. 93 typename std::vector<Break>::iterator start = GetBreak(range.start()); 94 start += start->first < range.start() ? 1 : 0; 95 typename std::vector<Break>::iterator end = GetBreak(range.end()); 96 T trailing_value = end->second; 97 typename std::vector<Break>::iterator i = 98 start == breaks_.end() ? start : breaks_.erase(start, end + 1); 99 if (range.start() == 0 || (i - 1)->second != value) 100 i = breaks_.insert(i, Break(range.start(), value)) + 1; 101 if (trailing_value != value && range.end() != max_) 102 breaks_.insert(i, Break(range.end(), trailing_value)); 103 104 #ifndef NDEBUG 105 CheckBreaks(); 106 #endif 107 } 108 109 template<class T> 110 void BreakList<T>::SetMax(size_t max) { 111 typename std::vector<Break>::iterator i = GetBreak(max); 112 i += (i == breaks_.begin() || i->first < max) ? 1 : 0; 113 breaks_.erase(i, breaks_.end()); 114 max_ = max; 115 116 #ifndef NDEBUG 117 CheckBreaks(); 118 #endif 119 } 120 121 template<class T> 122 typename std::vector<std::pair<size_t, T> >::iterator BreakList<T>::GetBreak( 123 size_t position) { 124 typename std::vector<Break>::iterator i = breaks_.end() - 1; 125 for (; i != breaks_.begin() && i->first > position; --i); 126 return i; 127 } 128 129 template<class T> 130 typename std::vector<std::pair<size_t, T> >::const_iterator 131 BreakList<T>::GetBreak(size_t position) const { 132 typename std::vector<Break>::const_iterator i = breaks_.end() - 1; 133 for (; i != breaks_.begin() && i->first > position; --i); 134 return i; 135 } 136 137 template<class T> 138 ui::Range BreakList<T>::GetRange( 139 const typename BreakList<T>::const_iterator& i) const { 140 const typename BreakList<T>::const_iterator next = i + 1; 141 return ui::Range(i->first, next == breaks_.end() ? max_ : next->first); 142 } 143 144 template<class T> 145 bool BreakList<T>::EqualsValueForTesting(T value) const { 146 return breaks_.size() == 1 && breaks_[0] == Break(0, value); 147 } 148 149 template<class T> 150 bool BreakList<T>::EqualsForTesting(const std::vector<Break>& breaks) const { 151 if (breaks_.size() != breaks.size()) 152 return false; 153 for (size_t i = 0; i < breaks.size(); ++i) 154 if (breaks_[i] != breaks[i]) 155 return false; 156 return true; 157 } 158 159 #ifndef NDEBUG 160 template <class T> 161 void BreakList<T>::CheckBreaks() { 162 DCHECK_EQ(breaks_[0].first, 0U) << "The first break must be at position 0."; 163 for (size_t i = 0; i < breaks_.size() - 1; ++i) { 164 DCHECK_LT(breaks_[i].first, breaks_[i + 1].first) << "Break out of order."; 165 DCHECK_NE(breaks_[i].second, breaks_[i + 1].second) << "Redundant break."; 166 } 167 if (max_ > 0) 168 DCHECK_LT(breaks_.back().first, max_) << "Break beyond max position."; 169 } 170 #endif 171 172 } // namespace gfx 173 174 #endif // UI_GFX_BREAK_LIST_H_ 175
