break_list.h 6.3 KB

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