12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef UI_GFX_BREAK_LIST_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define UI_GFX_BREAK_LIST_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <utility> 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <vector> 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 1358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#include "ui/gfx/range/range.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace gfx { 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// BreakLists manage ordered, non-overlapping, and non-repeating ranged values. 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// These may be used to apply ranged colors and styles to text, for an example. 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Each break stores the start position and value of its associated range. 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// A solitary break at position 0 applies to the entire space [0, max_). 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// |max_| is initially 0 and should be set to match the available ranged space. 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The first break always has position 0, to ensure all positions have a value. 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The value of the terminal break applies to the range [break.first, max_). 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The value of other breaks apply to the range [break.first, (break+1).first). 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class BreakList { 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The break type and const iterator, typedef'ed for convenience. 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::pair<size_t, T> Break; 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename std::vector<Break>::const_iterator const_iterator; 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Initialize a break at position 0 with the default or supplied |value|. 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BreakList(); 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit BreakList(T value); 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const std::vector<Break>& breaks() const { return breaks_; } 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Clear the breaks and set a break at position 0 with the supplied |value|. 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void SetValue(T value); 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Adjust the breaks to apply |value| over the supplied |range|. 43d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) void ApplyValue(T value, const Range& range); 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Set the max position and trim any breaks at or beyond that position. 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void SetMax(size_t max); 47d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) size_t max() const { return max_; } 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Get the break applicable to |position| (at or preceeding |position|). 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator GetBreak(size_t position); 51558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch typename std::vector<Break>::const_iterator GetBreak(size_t position) const; 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Get the range of the supplied break; returns the break's start position and 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // the next break's start position (or |max_| for the terminal break). 55d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) Range GetRange(const typename BreakList<T>::const_iterator& i) const; 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Comparison functions for testing purposes. 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool EqualsValueForTesting(T value) const; 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool EqualsForTesting(const std::vector<Break>& breaks) const; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef NDEBUG 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Check for ordered breaks [0, |max_|) with no adjacent equivalent values. 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void CheckBreaks(); 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<Break> breaks_; 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t max_; 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) { 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) { 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void BreakList<T>::SetValue(T value) { 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) breaks_.clear(); 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) breaks_.push_back(Break(0, value)); 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 86d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)void BreakList<T>::ApplyValue(T value, const Range& range) { 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!range.IsValid() || range.is_empty()) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!breaks_.empty()); 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!range.is_reversed()); 91d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) DCHECK(Range(0, max_).Contains(range)); 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erase any breaks in |range|, then add start and end breaks as needed. 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator start = GetBreak(range.start()); 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) start += start->first < range.start() ? 1 : 0; 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator end = GetBreak(range.end()); 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T trailing_value = end->second; 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator i = 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) start == breaks_.end() ? start : breaks_.erase(start, end + 1); 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (range.start() == 0 || (i - 1)->second != value) 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) i = breaks_.insert(i, Break(range.start(), value)) + 1; 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (trailing_value != value && range.end() != max_) 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) breaks_.insert(i, Break(range.end(), trailing_value)); 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef NDEBUG 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CheckBreaks(); 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void BreakList<T>::SetMax(size_t max) { 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator i = GetBreak(max); 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) i += (i == breaks_.begin() || i->first < max) ? 1 : 0; 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) breaks_.erase(i, breaks_.end()); 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) max_ = max; 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef NDEBUG 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CheckBreaks(); 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)typename std::vector<std::pair<size_t, T> >::iterator BreakList<T>::GetBreak( 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t position) { 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename std::vector<Break>::iterator i = breaks_.end() - 1; 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (; i != breaks_.begin() && i->first > position; --i); 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return i; 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 131558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdochtypename std::vector<std::pair<size_t, T> >::const_iterator 132558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch BreakList<T>::GetBreak(size_t position) const { 133558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch typename std::vector<Break>::const_iterator i = breaks_.end() - 1; 134558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch for (; i != breaks_.begin() && i->first > position; --i); 135558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch return i; 136558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch} 137558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch 138558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdochtemplate<class T> 139d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)Range BreakList<T>::GetRange( 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const typename BreakList<T>::const_iterator& i) const { 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const typename BreakList<T>::const_iterator next = i + 1; 142d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return Range(i->first, next == breaks_.end() ? max_ : next->first); 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool BreakList<T>::EqualsValueForTesting(T value) const { 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return breaks_.size() == 1 && breaks_[0] == Break(0, value); 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class T> 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool BreakList<T>::EqualsForTesting(const std::vector<Break>& breaks) const { 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (breaks_.size() != breaks.size()) 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < breaks.size(); ++i) 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (breaks_[i] != breaks[i]) 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef NDEBUG 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <class T> 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void BreakList<T>::CheckBreaks() { 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_EQ(breaks_[0].first, 0U) << "The first break must be at position 0."; 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < breaks_.size() - 1; ++i) { 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_LT(breaks_[i].first, breaks_[i + 1].first) << "Break out of order."; 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_NE(breaks_[i].second, breaks_[i + 1].second) << "Redundant break."; 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (max_ > 0) 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_LT(breaks_.back().first, max_) << "Break beyond max position."; 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace gfx 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // UI_GFX_BREAK_LIST_H_ 176