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/base/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 ui::Range& range);
  44
  45   // Set the max position and trim any breaks at or beyond that position.
  46   void SetMax(size_t max);
  47
  48   // Get the break applicable to |position| (at or preceeding |position|).
  49   typename std::vector<Break>::iterator GetBreak(size_t position);
  50
  51   // Get the range of the supplied break; returns the break's start position and
  52   // the next break's start position (or |max_| for the terminal break).
  53   ui::Range GetRange(const typename BreakList<T>::const_iterator& i) const;
  54
  55   // Comparison functions for testing purposes.
  56   bool EqualsValueForTesting(T value) const;
  57   bool EqualsForTesting(const std::vector<Break>& breaks) const;
  58
  59  private:
  60 #ifndef NDEBUG
  61   // Check for ordered breaks [0, |max_|) with no adjacent equivalent values.
  62   void CheckBreaks();
  63 #endif
  64
  65   std::vector<Break> breaks_;
  66   size_t max_;
  67 };
  68
  69 template<class T>
  70 BreakList<T>::BreakList() : breaks_(1, Break(0, T())), max_(0) {
  71 }
  72
  73 template<class T>
  74 BreakList<T>::BreakList(T value) : breaks_(1, Break(0, value)), max_(0) {
  75 }
  76
  77 template<class T>
  78 void BreakList<T>::SetValue(T value) {
  79   breaks_.clear();
  80   breaks_.push_back(Break(0, value));
  81 }
  82
  83 template<class T>
  84 void BreakList<T>::ApplyValue(T value, const ui::Range& range) {
  85   if (!range.IsValid() || range.is_empty())
  86     return;
  87   DCHECK(!breaks_.empty());
  88   DCHECK(!range.is_reversed());
  89   DCHECK(ui::Range(0, max_).Contains(range));
  90
  91   // Erase any breaks in |range|, then add start and end breaks as needed.
  92   typename std::vector<Break>::iterator start = GetBreak(range.start());
  93   start += start->first < range.start() ? 1 : 0;
  94   typename std::vector<Break>::iterator end = GetBreak(range.end());
  95   T trailing_value = end->second;
  96   typename std::vector<Break>::iterator i =
  97       start == breaks_.end() ? start : breaks_.erase(start, end + 1);
  98   if (range.start() == 0 || (i - 1)->second != value)
  99     i = breaks_.insert(i, Break(range.start(), value)) + 1;
 100   if (trailing_value != value && range.end() != max_)
 101     breaks_.insert(i, Break(range.end(), trailing_value));
 102
 103 #ifndef NDEBUG
 104   CheckBreaks();
 105 #endif
 106 }
 107
 108 template<class T>
 109 void BreakList<T>::SetMax(size_t max) {
 110   typename std::vector<Break>::iterator i = GetBreak(max);
 111   i += (i == breaks_.begin() || i->first < max) ? 1 : 0;
 112   breaks_.erase(i, breaks_.end());
 113   max_ = max;
 114
 115 #ifndef NDEBUG
 116   CheckBreaks();
 117 #endif
 118 }
 119
 120 template<class T>
 121 typename std::vector<std::pair<size_t, T> >::iterator BreakList<T>::GetBreak(
 122     size_t position) {
 123   typename std::vector<Break>::iterator i = breaks_.end() - 1;
 124   for (; i != breaks_.begin() && i->first > position; --i);
 125   return i;
 126 }
 127
 128 template<class T>
 129 ui::Range BreakList<T>::GetRange(
 130     const typename BreakList<T>::const_iterator& i) const {
 131   const typename BreakList<T>::const_iterator next = i + 1;
 132   return ui::Range(i->first, next == breaks_.end() ? max_ : next->first);
 133 }
 134
 135 template<class T>
 136 bool BreakList<T>::EqualsValueForTesting(T value) const {
 137   return breaks_.size() == 1 && breaks_[0] == Break(0, value);
 138 }
 139
 140 template<class T>
 141 bool BreakList<T>::EqualsForTesting(const std::vector<Break>& breaks) const {
 142   if (breaks_.size() != breaks.size())
 143     return false;
 144   for (size_t i = 0; i < breaks.size(); ++i)
 145     if (breaks_[i] != breaks[i])
 146       return false;
 147   return true;
 148 }
 149
 150 #ifndef NDEBUG
 151 template <class T>
 152 void BreakList<T>::CheckBreaks() {
 153   DCHECK_EQ(breaks_[0].first, 0U) << "The first break must be at position 0.";
 154   for (size_t i = 0; i < breaks_.size() - 1; ++i) {
 155     DCHECK_LT(breaks_[i].first, breaks_[i + 1].first) << "Break out of order.";
 156     DCHECK_NE(breaks_[i].second, breaks_[i + 1].second) << "Redundant break.";
 157   }
 158   if (max_ > 0)
 159     DCHECK_LT(breaks_.back().first, max_) << "Break beyond max position.";
 160 }
 161 #endif
 162
 163 }  // namespace gfx
 164
 165 #endif  // UI_GFX_BREAK_LIST_H_