ui/gfx/break_list.h

   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
  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);
  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>
  72 BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) {
  73 }
  74
  75 template<class T>
  76 BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) {
  77 }
  78
  79 template<class T>
  80 void BreakList<T>::SetValue(T value) {
  81   breaks_.clear();
  82   breaks_.push_back(Break(0, value));
  83 }
  84
  85 template<class T>
  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>
 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>
 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
 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>
 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>
 146 bool BreakList<T>::EqualsValueForTesting(T value) const {
 147   return breaks_.size() == 1 && breaks_[0] == Break(0, value);
 148 }
 149
 150 template<class T>
 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>
 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_