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
breaks()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);
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>
BreakList()72 BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) {
73 }
74
75 template<class T>
BreakList(T value)76 BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) {
77 }
78
79 template<class T>
SetValue(T value)80 void BreakList<T>::SetValue(T value) {
81 breaks_.clear();
82 breaks_.push_back(Break(0, value));
83 }
84
85 template<class T>
ApplyValue(T value,const Range & range)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>
SetMax(size_t max)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>
GetBreak(size_t position)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
GetBreak(size_t position)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>
GetRange(const typename BreakList<T>::const_iterator & i)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>
EqualsValueForTesting(T value)146 bool BreakList<T>::EqualsValueForTesting(T value) const {
147 return breaks_.size() == 1 && breaks_[0] == Break(0, value);
148 }
149
150 template<class T>
EqualsForTesting(const std::vector<Break> & breaks)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>
CheckBreaks()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