// Copyright (c) 2012 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef UI_GFX_BREAK_LIST_H_ #define UI_GFX_BREAK_LIST_H_ #include #include #include #include "base/check_op.h" #include "ui/gfx/range/range.h" namespace gfx { // BreakLists manage ordered, non-overlapping, and non-repeating ranged values. // These may be used to apply ranged colors and styles to text, for an example. // // Each break stores the start position and value of its associated range. // A solitary break at position 0 applies to the entire space [0, max_). // |max_| is initially 0 and should be set to match the available ranged space. // The first break always has position 0, to ensure all positions have a value. // The value of the terminal break applies to the range [break.first, max_). // The value of other breaks apply to the range [break.first, (break+1).first). template class BreakList { public: // The break type and const iterator, typedef'ed for convenience. using Break = std::pair; using const_iterator = typename std::vector::const_iterator; // Initialize a break at position 0 with the default or supplied |value|. BreakList(); explicit BreakList(T value); const std::vector& breaks() const { return breaks_; } // Clear the breaks and set a break at position 0 with the supplied |value|. // Returns whether or not the breaks changed while applying the |value|. bool SetValue(T value); // Adjust the breaks to apply |value| over the supplied |range|. // Range |range| must be between [0, max_). // Returns true if the breaks changed while applying the |value|. bool ApplyValue(T value, const Range& range); // Set the max position and trim any breaks at or beyond that position. void SetMax(size_t max); size_t max() const { return max_; } // Get the break applicable to |position| (at or preceding |position|). // |position| must be between [0, max_). // Returns a valid iterator. Can't return |break_.end()|. const_iterator GetBreak(size_t position) const; // Get the range of the supplied break; returns the break's start position and // the next break's start position (or |max_| for the terminal break). // Iterator |i| must be valid and must not be |break_.end()|. Range GetRange(const const_iterator& i) const; // Comparison functions for testing purposes. bool EqualsValueForTesting(T value) const; bool EqualsForTesting(const std::vector& breaks) const; private: #ifndef NDEBUG // Check for ordered breaks [0, |max_|) with no adjacent equivalent values. void CheckBreaks(); #endif std::vector breaks_; size_t max_ = 0; }; template BreakList::BreakList() : breaks_(1, Break(0, T())) {} template BreakList::BreakList(T value) : breaks_(1, Break(0, value)) {} template bool BreakList::SetValue(T value) { // Return false if setting |value| does not change the breaks. if (breaks_.size() == 1 && breaks_[0].second == value) return false; breaks_.clear(); breaks_.push_back(Break(0, value)); return true; } template bool BreakList::ApplyValue(T value, const Range& range) { if (!range.IsValid() || range.is_empty()) return false; DCHECK(!breaks_.empty()); DCHECK(!range.is_reversed()); DCHECK(Range(0, static_cast(max_)).Contains(range)); // Return false if setting |value| does not change the breaks. const_iterator start = GetBreak(range.start()); if (start->second == value && GetRange(start).Contains(range)) return false; // Erase any breaks in |range|, then add start and end breaks as needed. start += start->first < range.start() ? 1 : 0; const_iterator end = range.end() == max_ ? breaks_.cend() - 1 : GetBreak(range.end()); T trailing_value = end->second; const_iterator i = start == breaks_.cend() ? start : breaks_.erase(start, end + 1); if (range.start() == 0 || (i - 1)->second != value) i = breaks_.insert(i, Break(range.start(), value)) + 1; if (trailing_value != value && range.end() != max_) breaks_.insert(i, Break(range.end(), trailing_value)); #ifndef NDEBUG CheckBreaks(); #endif return true; } template void BreakList::SetMax(size_t max) { if (max < max_) { const_iterator i = GetBreak(max); if (i == breaks_.begin() || i->first < max) i++; breaks_.erase(i, breaks_.end()); } max_ = max; #ifndef NDEBUG CheckBreaks(); #endif } template typename BreakList::const_iterator BreakList::GetBreak( size_t position) const { DCHECK(!breaks_.empty()); DCHECK_LT(position, max_); // Find the iterator with a 'strictly greater' position and return the // previous one. return std::upper_bound(breaks_.cbegin(), breaks_.cend(), position, [](size_t offset, const Break& value) { return offset < value.first; }) - 1; } template Range BreakList::GetRange( const typename BreakList::const_iterator& i) const { // BreakLists are never empty. Iterator should always be valid. DCHECK(i != breaks_.end()); const const_iterator next = i + 1; return Range(i->first, next == breaks_.end() ? max_ : next->first); } template bool BreakList::EqualsValueForTesting(T value) const { return breaks_.size() == 1 && breaks_[0] == Break(0, value); } template bool BreakList::EqualsForTesting(const std::vector& breaks) const { if (breaks_.size() != breaks.size()) return false; for (size_t i = 0; i < breaks.size(); ++i) if (breaks_[i] != breaks[i]) return false; return true; } #ifndef NDEBUG template void BreakList::CheckBreaks() { DCHECK(!breaks_.empty()) << "BreakList cannot be empty"; DCHECK_EQ(breaks_[0].first, 0U) << "The first break must be at position 0."; for (size_t i = 0; i < breaks_.size() - 1; ++i) { DCHECK_LT(breaks_[i].first, breaks_[i + 1].first) << "Break out of order."; DCHECK_NE(breaks_[i].second, breaks_[i + 1].second) << "Redundant break."; } if (max_ > 0) DCHECK_LT(breaks_.back().first, max_) << "Break beyond max position."; } #endif } // namespace gfx #endif // UI_GFX_BREAK_LIST_H_