DiscreteRange.h

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
// Copyright 2014 Network Geographics
 
#pragma once
#include <algorithm>
#include <limits>
#include <functional>
 
#include "swoc/swoc_version.h"
#include "swoc/swoc_meta.h"
#include "swoc/RBTree.h"
#include "swoc/MemArena.h"
 
 
namespace swoc { inline namespace SWOC_VERSION_NS {
namespace detail {


template <typename M>
constexpr auto
maximum(meta::CaseTag<0>) -> M {
  return std::numeric_limits<M>::max();
}

template <typename M>
constexpr auto
maximum(meta::CaseTag<1>) -> decltype(M::MAX) {
  return M::MAX;
}

template <typename M>
constexpr M
maximum() {
  return maximum<M>(meta::CaseArg);
}

template <typename M>
constexpr auto
minimum(meta::CaseTag<0>) -> M {
  return std::numeric_limits<M>::min();
}

template <typename M>
constexpr auto
minimum(meta::CaseTag<1>) -> decltype(M::MIN) {
  return M::MIN;
}

template <typename M>
constexpr M
minimum() {
  return minimum<M>(meta::CaseArg);
}

} // namespace detail

enum class DiscreteRangeRelation : uint8_t {
  NONE,     
  EQUAL,    
  SUBSET,   
  SUPERSET, 
  OVERLAP,  
  ADJACENT  
};

enum class DiscreteRangeEdgeRelation : uint8_t {
  NONE, 
  GAP,  
  ADJ,  
  OVLP, 
};

template <typename T> class DiscreteRange {
  using self_type = DiscreteRange;
 
protected:
  T _min; 
  T _max; 
 
public:
  using metric_type  = T;                         
  using Relation     = DiscreteRangeRelation;     
  using EdgeRelation = DiscreteRangeEdgeRelation; 

  constexpr DiscreteRange() : _min(detail::maximum<T>()), _max(detail::minimum<T>()) {}

  constexpr DiscreteRange(T const &value) : _min(value), _max(value){};

  constexpr DiscreteRange(T const &min, T const &max) : _min(min), _max(max) {}
 
  ~DiscreteRange() = default;

  bool empty() const;

  self_type &assign(metric_type const &min, metric_type const &max);

  self_type &assign(metric_type const &value);

  self_type &assign_min(metric_type const &min);

  self_type &assign_max(metric_type const &max);

  self_type &clip_max();

  metric_type const &min() const;

  metric_type const &max() const;

  bool operator==(self_type const &that) const;

  bool operator!=(self_type const &that) const;

  bool contains(metric_type const &value) const;

  bool has_intersection_with(self_type const &that) const;

  self_type intersection(self_type const &that) const;

  bool is_adjacent_to(self_type const &that) const;

  bool is_left_adjacent_to(self_type const &that) const;

  bool has_union(self_type const &that) const;

  bool is_superset_of(self_type const &that) const;

  bool is_subset_of(self_type const &that) const;

  bool is_strict_superset_of(self_type const &that) const;

  bool is_strict_subset_of(self_type const &that) const;

  Relation relationship(self_type const &that) const;

  EdgeRelation left_edge_relationship(self_type const &that) const;

  self_type hull(self_type const &that) const;

  bool is_singleton() const;

  bool operator!() const;

  explicit operator bool() const;

  bool is_maximal() const;

  self_type &operator&=(self_type const &that);

  self_type &operator|=(self_type const &that);

  self_type &clear();

  struct lexicographic_order {
    using first_argument_type  = self_type;
    using second_argument_type = self_type;
    using result_type          = bool;

    bool operator()(self_type const &lhs, self_type const &rhs) const;
  };
};
 
template <typename T>
bool
DiscreteRange<T>::operator==(DiscreteRange::self_type const &that) const {
  return _min == that._min && _max == that._max;
}
 
template <typename T>
bool
DiscreteRange<T>::operator!=(DiscreteRange::self_type const &that) const {
  return _min != that._min | _max != that._max;
}
 
template <typename T>
auto
DiscreteRange<T>::clip_max() -> self_type & {
  --_max;
  return *this;
}
 
template <typename T>
bool
DiscreteRange<T>::operator!() const {
  return _min > _max;
}
 
template <typename T> DiscreteRange<T>::operator bool() const {
  return _min <= _max;
}
 
template <typename T>
bool
DiscreteRange<T>::contains(metric_type const &value) const {
  return _min <= value && value <= _max;
}
 
template <typename T>
auto
DiscreteRange<T>::clear() -> self_type & {
  _min = detail::maximum<T>();
  _max = detail::minimum<T>();
  return *this;
}
 
template <typename T>
bool
DiscreteRange<T>::lexicographic_order::operator()(DiscreteRange::self_type const &lhs, DiscreteRange::self_type const &rhs) const {
  return lhs._min == rhs._min ? lhs._max < rhs._max : lhs._min < rhs._min;
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::assign(metric_type const &min, metric_type const &max) {
  _min = min;
  _max = max;
  return *this;
}
 
template <typename T>
DiscreteRange<T>
DiscreteRange<T>::hull(DiscreteRange::self_type const &that) const {
  // need to account for invalid ranges.
  return !*this ? that : !that ? *this : self_type(std::min(_min, that._min), std::max(_max, that._max));
}
 
template <typename T>
auto
DiscreteRange<T>::left_edge_relationship(self_type const &that) const -> EdgeRelation {
  if (_max < that._max) {
    return ++metric_type(_max) < that._max ? EdgeRelation::GAP : EdgeRelation::ADJ;
  }
  return _min >= that._min ? EdgeRelation::NONE : EdgeRelation::OVLP;
}
 
template <typename T>
auto
DiscreteRange<T>::relationship(self_type const &that) const -> Relation {
  Relation retval = Relation::NONE;
  if (this->has_intersection_with(that)) {
    if (*this == that)
      retval = Relation::EQUAL;
    else if (this->is_subset_of(that))
      retval = Relation::SUBSET;
    else if (this->is_superset_of(that))
      retval = Relation::SUPERSET;
    else
      retval = Relation::OVERLAP;
  } else if (this->is_adjacent_to(that)) {
    retval = Relation::ADJACENT;
  }
  return retval;
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::assign(metric_type const &singleton) {
  _min = singleton;
  _max = singleton;
  return *this;
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::assign_min(metric_type const &min) {
  _min = min;
  return *this;
}
 
template <typename T>
bool
DiscreteRange<T>::is_singleton() const {
  return _min == _max;
}
 
template <typename T>
bool
DiscreteRange<T>::empty() const {
  return _min > _max;
}
 
template <typename T>
bool
DiscreteRange<T>::is_maximal() const {
  return _min == detail::minimum<T>() && _max == detail::maximum<T>();
}
 
template <typename T>
bool
DiscreteRange<T>::is_strict_superset_of(DiscreteRange::self_type const &that) const {
  return (_min < that._min && that._max <= _max) || (_min <= that._min && that._max < _max);
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::operator|=(DiscreteRange::self_type const &that) {
  if (!*this) {
    *this = that;
  } else if (that) {
    if (that._min < _min) {
      _min = that._min;
    }
    if (that._max > _max) {
      _max = that._max;
    }
  }
  return *this;
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::assign_max(metric_type const &max) {
  _max = max;
  return *this;
}
 
template <typename T>
bool
DiscreteRange<T>::is_strict_subset_of(DiscreteRange::self_type const &that) const {
  return that.is_strict_superset_of(*this);
}
 
template <typename T>
bool
DiscreteRange<T>::is_subset_of(DiscreteRange::self_type const &that) const {
  return that.is_superset_of(*this);
}
 
template <typename T>
T const &
DiscreteRange<T>::min() const {
  return _min;
}
 
template <typename T>
T const &
DiscreteRange<T>::max() const {
  return _max;
}
 
template <typename T>
bool
DiscreteRange<T>::has_union(DiscreteRange::self_type const &that) const {
  return this->has_intersection_with(that) || this->is_adjacent_to(that);
}
 
template <typename T>
DiscreteRange<T> &
DiscreteRange<T>::operator&=(DiscreteRange::self_type const &that) {
  *this = this->intersection(that);
  return *this;
}
 
template <typename T>
bool
DiscreteRange<T>::has_intersection_with(DiscreteRange::self_type const &that) const {
  return (that._min <= _min && _min <= that._max) || (_min <= that._min && that._min <= _max);
}
 
template <typename T>
bool
DiscreteRange<T>::is_superset_of(DiscreteRange::self_type const &that) const {
  return _min <= that._min && that._max <= _max;
}
 
template <typename T>
bool
DiscreteRange<T>::is_adjacent_to(DiscreteRange::self_type const &that) const {
  return this->is_left_adjacent_to(that) || that.is_left_adjacent_to(*this);
}
 
template <typename T>
bool
DiscreteRange<T>::is_left_adjacent_to(DiscreteRange::self_type const &that) const {
  /* Need to be careful here. We don't know much about T and we certainly don't know if "t+1"
   * even compiles for T. We do require the increment operator, however, so we can use that on a
   * copy to get the equivalent of t+1 for adjacency testing. We must also handle the possibility
   * T has a modulus and not depend on ++t > t always being true. However, we know that if t1 >
   * t0 then ++t0 > t0.
   */
  metric_type max(_max); // some built in integer types don't support increment on rvalues.
  return _max < that._min && ++max == that._min;
}
 
template <typename T>
DiscreteRange<T>
DiscreteRange<T>::intersection(DiscreteRange::self_type const &that) const {
  return {std::max(_min, that._min), std::min(_max, that._max)};
}
 
template <typename T>
bool
operator==(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return lhs.min() == rhs.min() && lhs.max() == rhs.max();
}

template <typename T>
bool
operator!=(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return !(lhs == rhs);
}

template <typename T>
bool
operator^(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return lhs.has_intersection_with(rhs);
}

template <typename T>
inline bool
operator<(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return rhs.is_strict_superset_of(lhs);
}

template <typename T>
inline bool
operator<=(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return rhs.is_superset_of(lhs);
}

template <typename T>
inline bool
operator>(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return lhs.is_strict_superset_of(rhs);
}

template <typename T>
inline bool
operator>=(DiscreteRange<T> const &lhs, DiscreteRange<T> const &rhs) {
  return lhs.is_superset_of(rhs);
}

template <typename METRIC, typename PAYLOAD> class DiscreteSpace {
  using self_type = DiscreteSpace;
 
protected:
  using metric_type  = METRIC;  
  using payload_type = PAYLOAD; 
  using range_type   = DiscreteRange<METRIC>;

  class Node : public detail::RBNode {
    using self_type  = Node;           
    using super_type = detail::RBNode; 
    friend class DiscreteSpace;
 
    range_type _range;  
    range_type _hull;   
    PAYLOAD _payload{}; 
 
  public:
    using Linkage = swoc::IntrusiveLinkageRebind<self_type, super_type::Linkage>;
 
    Node() = default; 

    Node(range_type const &range, PAYLOAD const &payload) : _range(range), _payload(payload) {}

    Node(METRIC const &min, METRIC const &max, PAYLOAD const &payload) : _range(min, max), _payload(payload) {}

    PAYLOAD &payload();

    self_type &assign(range_type const &range);

    self_type &assign(PAYLOAD const &payload);
 
    range_type const &
    range() const {
      return _range;
    }
 
    self_type &
    assign_min(METRIC const &m, bool update_tree = true) {
      _range.assign_min(m);
      if (update_tree)
      {
        this->ripple_structure_fixup();
      }
      return *this;
    }
 
    self_type &
    assign_max(METRIC const &m, bool update_tree = true) {
      _range.assign_max(m);
      if (update_tree)
      {
        this->ripple_structure_fixup();
      }
      return *this;
    }
 
    METRIC const &
    min() const {
      return _range.min();
    }
 
    METRIC const &
    max() const {
      return _range.max();
    }
 
    void structure_fixup() override;
 
    self_type *
    left() {
      return static_cast<self_type *>(_left);
    }
 
    self_type *
    right() {
      return static_cast<self_type *>(_right);
    }
  };
 
  using Direction = typename Node::Direction;
 
  Node *_root = nullptr;                        
  IntrusiveDList<typename Node::Linkage> _list; 
  swoc::MemArena _arena{4000};                  
  swoc::FixedArena<Node> _fa{_arena};           
 
  // Utility methods to avoid having casts scattered all over.
  Node *
  prev(Node *n) {
    return Node::Linkage::prev_ptr(n);
  }
 
  Node *
  next(Node *n) {
    return Node::Linkage::next_ptr(n);
  }
 
  Node *
  left(Node *n) {
    return static_cast<Node *>(n->_left);
  }
 
  Node *
  right(Node *n) {
    return static_cast<Node *>(n->_right);
  }
 
public:
  using iterator       = typename decltype(_list)::iterator;
  using const_iterator = typename decltype(_list)::const_iterator;
 
  DiscreteSpace() = default;
 
  ~DiscreteSpace();

   self_type &mark_bulk(std::vector<std::pair<range_type, PAYLOAD>> &marks, bool is_sorted = false);

   self_type &mark_bulk(std::pair<range_type, PAYLOAD>* start, size_t n, bool is_sorted = false);

  self_type &mark(range_type const &range, PAYLOAD const &payload, bool update_tree = true);

  self_type &erase(range_type const &range);

  template <typename F, typename U = PAYLOAD> self_type &blend(range_type const &range, U const &color, F &&blender);

  self_type &fill(range_type const &range, PAYLOAD const &payload);

  iterator find(METRIC const &metric);

  const_iterator find(METRIC const &metric) const;

  iterator lower_bound(METRIC const &m);

  iterator upper_bound(METRIC const &m);

  std::pair<iterator, iterator> intersection(range_type const &range);

  size_t count() const;

  bool empty() const;

  iterator
  begin() {
    return _list.begin();
  }

  iterator
  end() {
    return _list.end();
  }

  const_iterator
  begin() const {
    return _list.begin();
  }

  const_iterator
  end() const {
    return _list.end();
  }

  void clear();
 
protected:
  Node *lower_node(METRIC const &target);

  Node *upper_node(METRIC const &target);

  Node *head();

  Node *tail();

  void insert_before(Node *spot, Node *node, bool update_tree = true);

  void insert_after(Node *spot, Node *node, bool update_tree = true);

  void prepend(Node *node, bool update_tree = true);

  void append(Node *node, bool update_tree = true);

  void remove(Node *node, bool update_tree = true);
};
 
// ---
 
template <typename METRIC, typename PAYLOAD>
PAYLOAD &
DiscreteSpace<METRIC, PAYLOAD>::Node::payload() {
  return _payload;
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::Node::assign(DiscreteSpace::range_type const &range) -> self_type & {
  _range = range;
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::Node::assign(PAYLOAD const &payload) -> self_type & {
  _payload = payload;
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::Node::structure_fixup() {
  // Invariant: The hulls of all children are correct.
  if (_left && _right) {
    // If both children, local range must be inside the hull of the children and irrelevant.
    _hull.assign(this->left()->_hull.min(), this->right()->_hull.max());
  } else if (_left) {
    _hull.assign(this->left()->_hull.min(), _range.max());
  } else if (_right) {
    _hull.assign(_range.min(), this->right()->_hull.max());
  } else {
    _hull = _range;
  }
}
 
// ---
// Discrete Space
// ---
 
template <typename METRIC, typename PAYLOAD> DiscreteSpace<METRIC, PAYLOAD>::~DiscreteSpace() {
  // Destruct all the payloads - the nodes themselves are in the arena and disappear with it.
  for (auto &node : _list) {
    std::destroy_at(&node.payload());
  }
}
 
template <typename METRIC, typename PAYLOAD>
size_t
DiscreteSpace<METRIC, PAYLOAD>::count() const {
  return _list.count();
}
 
template <typename METRIC, typename PAYLOAD>
bool
DiscreteSpace<METRIC, PAYLOAD>::empty() const {
  return _list.empty();
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::head() -> Node * {
  return static_cast<Node *>(_list.head());
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::tail() -> Node * {
  return static_cast<Node *>(_list.tail());
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::find(METRIC const &metric) -> iterator {
  auto n = _root; // current node to test.
  while (n) {
    if (metric < n->min()) {
      if (n->_hull.contains(metric)) {
        n = n->left();
      } else {
        return this->end();
      }
    } else if (n->max() < metric) {
      if (n->_hull.contains(metric)) {
        n = n->right();
      } else {
        return this->end();
      }
    } else {
      return _list.iterator_for(n);
    }
  }
  return this->end();
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::find(METRIC const &metric) const -> const_iterator {
  return const_cast<self_type *>(this)->find(metric);
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::lower_node(METRIC const &target) -> Node * {
  Node *n    = _root;   // current node to test.
  Node *zret = nullptr; // best node so far.
 
  // Fast check for sequential insertion
  if (auto ln = _list.tail(); ln != nullptr && ln->max() < target) {
    return ln;
  }
 
  while (n) {
    if (target < n->min()) {
      n = left(n);
    } else {
      zret = n; // this is a better candidate.
      if (n->max() < target) {
        n = right(n);
      } else {
        break;
      }
    }
  }
  return zret;
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::upper_node(METRIC const &target) -> Node * {
  Node *n    = _root;   // current node to test.
  Node *zret = nullptr; // best node so far.
 
  // Fast check if there is no range past @a target.
  if (auto ln = _list.tail(); ln == nullptr || ln->min() <= target) {
    return nullptr;
  }
 
  while (n) {
    if (target > n->min()) {
      n = right(n);
    } else {
      zret = n; // this is a better candidate.
      if (n->min() > target) {
        n = left(n);
      } else {
        break;
      }
    }
  }
 
  // Must be past any intersecting range due to STL iteration being half open.
  if (zret && (zret->min() <= target)) {
    zret = next(zret);
  }
 
  return zret;
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::lower_bound(METRIC const &m) -> iterator {
  auto n = this->lower_node(m);
  return n ? iterator(n) : this->end();
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::upper_bound(METRIC const &m) -> iterator {
  auto n = this->upper_node(m);
  return n ? iterator(n) : this->end();
}
 
template <typename METRIC, typename PAYLOAD>
auto
DiscreteSpace<METRIC, PAYLOAD>::intersection(DiscreteSpace::range_type const &range) -> std::pair<iterator, iterator> {
  // Quick checks for null intersection
  if (this->head() == nullptr ||                  // empty
      this->head()->_range.min() > range.max() || // before first range
      this->tail()->_range.max() < range.min()    // after last range
  ) {
    return {this->end(), this->end()};
  }
  // Invariant - the search range intersects the convex hull of the ranges. This doesn't require the search
  // range to intersect any of the actual ranges.
 
  auto *lower = this->lower_node(range.min());
  auto *upper = this->upper_node(range.max());
 
  if (lower == nullptr) {
    lower = this->head();
  } else if (lower->_range.max() < range.min()) {
    lower = next(lower);                     // lower is before @a range so @c next must be at or past.
    if (lower->_range.min() > range.max()) { // @a range is in an uncolored gap.
      return {this->end(), this->end()};
    }
  }
 
  return {_list.iterator_for(lower), upper ? _list.iterator_for(upper) : this->end()};
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::prepend(DiscreteSpace::Node *node, bool update_tree) {
 
  if (update_tree) {
    if (!_root) {
      _root = node;
    } else {
      _root = static_cast<Node *>(_list.head()->set_child(node, Direction::LEFT)->rebalance_after_insert());
    }
  }
 
  _list.prepend(node);
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::append(DiscreteSpace::Node *node, bool update_tree) {
 
  if (update_tree) {
    if (!_root) {
      _root = node;
    } else {
      // The last node has no right child, or it wouldn't be the last.
      _root = static_cast<Node *>(_list.tail()->set_child(node, Direction::RIGHT)->rebalance_after_insert());
    }
  }
 
  _list.append(node);
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::remove(DiscreteSpace::Node *node, bool update_tree) {
  _list.erase(node);
  _fa.destroy(node);
  if (!update_tree) {
    return;
  }
  _root = static_cast<Node *>(node->remove());
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::insert_before(DiscreteSpace::Node *spot, DiscreteSpace::Node *node, bool update_tree) {
 
  if (update_tree) {
    if (left(spot) == nullptr) {
      spot->set_child(node, Direction::LEFT);
    } else {
      // If there's a left child, there's a previous node, therefore spot->_prev is valid.
      // Further, the previous node must be the rightmost descendant node of the left subtree
      // and therefore has no current right child.
      spot->_prev->set_child(node, Direction::RIGHT);
    }
  }
 
  _list.insert_before(spot, node);
 
  if (update_tree) {
    _root = static_cast<Node *>(node->rebalance_after_insert());
  }
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::insert_after(DiscreteSpace::Node *spot, DiscreteSpace::Node *node, bool update_tree) {
 
  if (update_tree) {
    if (right(spot) == nullptr) {
      spot->set_child(node, Direction::RIGHT);
    } else {
      // If there's a right child, there's a successor node, and therefore @a _next is valid.
      // Further, the successor node must be the left most descendant of the right subtree
      // therefore it doesn't have a left child.
      spot->_next->set_child(node, Direction::LEFT);
    }
  }
 
  _list.insert_after(spot, node);
 
  if (update_tree) {
    _root = static_cast<Node *>(node->rebalance_after_insert());
  }
}
 
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
DiscreteSpace<METRIC, PAYLOAD>::erase(DiscreteSpace::range_type const &range) {
  Node *n = this->lower_node(range.min()); // current node.
  while (n) {
    auto nn = next(n);            // cache in case @a n disappears.
    if (n->min() > range.max()) { // cleared the target range, done.
      break;
    }
 
    if (n->max() >= range.min()) {     // some overlap
      if (n->max() <= range.max()) {   // pure left overlap, clip.
        if (n->min() >= range.min()) { // covered, remove.
          this->remove(n);
        } else { // stub on the left, clip to that.
          n->assign_max(--metric_type{range.min()});
        }
      } else if (n->min() >= range.min()) { // pure left overlap, clip.
        n->assign_min(++metric_type{range.max()});
      } else { // @a n covers @a range, must split.
        auto y = _fa.make(range_type{n->min(), --metric_type{range.min()}}, n->payload());
        n->assign_min(++metric_type{range.max()});
        this->insert_before(n, y);
        break;
      }
    }
    n = nn;
  }
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
DiscreteSpace<METRIC, PAYLOAD>::mark_bulk(std::vector<std::pair<DiscreteSpace::range_type, PAYLOAD>> &ranges, bool is_sorted) {
  return this->mark_bulk(ranges.data(), ranges.size(), is_sorted);
}
 
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
DiscreteSpace<METRIC, PAYLOAD>::mark_bulk(std::pair<range_type, PAYLOAD>* start, size_t n, bool is_sorted)
{
  // Sort the input data in-place before processing, if applicable.
  if (!is_sorted)
  {
    // Stable sort allows for duplicate elements.
    std::stable_sort(start, start + n, [](const auto &lhs, const auto &rhs) {
      if (lhs.first.min() != rhs.first.min()) {
        return lhs.first.min() < rhs.first.min();
      }
      return lhs.first.max() < rhs.first.max();
    });
  }
 
  // Verify that this is purely an append operation.
  // If it's not, then we need to rebuild the entire tree each iteration (suboptimal case).
  bool isAppend = !_list.empty() && _list.tail()->max() < start[0].first.min();
 
  // Mark the ranges in the input data.
  for (size_t i = 0; i < n; ++i)
  {
    auto const& [range, payload] = start[i];
    this->mark(range, payload, !isAppend);
  }
 
  // Rebuild the entire red-black tree.
  detail::RBNode* temp_head = _list.head();
  _root = static_cast<Node *>(detail::RBNode::buildTree(temp_head, _list.count()));
 
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
DiscreteSpace<METRIC, PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAYLOAD const &payload, bool update_tree) {
  Node *n = this->lower_node(range.min()); // current node.
  Node *x = nullptr;                       // New node, gets set if we re-use an existing one.
  Node *y = nullptr;                       // Temporary for removing and advancing.
 
  // Use carefully, only in situations where it is known there is no overflow.
  auto max_plus_1 = ++metric_type{range.max()};
 
  /*  We have lots of special cases here primarily to minimize memory
      allocation by re-using an existing node as often as possible.
  */
  if (n) {
    // Watch for wrap.
    auto min_minus_1 = --metric_type{range.min()};
    if (n->min() == range.min()) {
      // Could be another span further left which is adjacent.
      // Coalesce if the data is the same. min_minus_1 is OK because
      // if there is a previous range, min is not zero.
      Node *p = prev(n);
      if (p && p->payload() == payload && p->max() == min_minus_1) {
        x = p;
        n = x; // need to back up n because frame of reference moved.
        x->assign_max(range.max(), update_tree);
      } else if (n->max() <= range.max()) {
        // Span will be subsumed by request span so it's available for use.
        x = n;
        x->assign_max(range.max()).assign(payload);
      } else if (n->payload() == payload) {
        return *this; // request is covered by existing span with the same data
      } else {
        // request span is covered by existing span.
        x = _fa.make(range, payload); //
        n->assign_min(max_plus_1, update_tree);    // clip existing.
        this->insert_before(n, x, update_tree);
        return *this;
      }
    } else if (n->payload() == payload && n->max() >= min_minus_1) {
      // min_minus_1 is safe here because n->min() < min so min is not zero.
      x = n;
      // If the existing span covers the requested span, we're done.
      if (x->max() >= range.max()) {
        return *this;
      }
      x->assign_max(range.max(), update_tree);
    } else if (n->max() <= range.max()) {
      // Can only have left skew overlap, otherwise disjoint.
      // Clip if overlap.
      if (n->max() >= range.min()) {
        n->assign_max(min_minus_1, update_tree);
      } else if (nullptr != (y = next(n)) && y->max() <= range.max()) {
        // because @a n was selected as the minimum it must be the case that
        // y->min >= min (or y would have been selected). Therefore in this
        // case the request covers the next node therefore it can be reused.
        x = y;
        x->assign(range).assign(payload);
        if (update_tree)
        {
            x->ripple_structure_fixup();
        }
        n = x; // this gets bumped again, which is correct.
      }
    } else {
      // Existing span covers new span but with a different payload.
      // We split it, put the new span in between and we're done.
      // max_plus_1 is valid because n->max() > max.
      Node *r;
      x = _fa.make(range, payload);
      r = _fa.make(range_type{max_plus_1, n->max()}, n->payload());
      n->assign_max(min_minus_1, update_tree);
      this->insert_after(n, x, update_tree);
      this->insert_after(x, r, update_tree);
      return *this; // done.
    }
    n = next(n); // lower bound span handled, move on.
    if (!x) {
      x = _fa.make(range, payload);
      if (n) {
        this->insert_before(n, x, update_tree);
      } else {
        this->append(x, update_tree); // note that since n == 0 we'll just return.
      }
    }
  } else if (nullptr != (n = this->head()) &&                    // at least one node in tree.
             n->payload() == payload &&                          // payload matches
             (n->max() <= range.max() || n->min() <= max_plus_1) // overlap or adj.
  ) {
    // Same payload with overlap, re-use.
    x = n;
    n = next(n);
    x->assign_min(range.min(), update_tree);
    if (x->max() < range.max()) {
      x->assign_max(range.max(), update_tree);
    }
  } else {
    x = _fa.make(range, payload);
    this->prepend(x, update_tree);
  }
 
  // At this point, @a x has the node for this span and all existing spans of
  // interest start at or past this span.
  while (n) {
    if (n->max() <= range.max()) { // completely covered, drop span, continue
      y = n;
      n = next(n);
      this->remove(y, update_tree);
    } else if (max_plus_1 < n->min()) { // no overlap, done.
      break;
    } else if (n->payload() == payload) { // skew overlap or adj., same payload
      x->assign_max(n->max(), update_tree);
      y = n;
      n = next(n);
      this->remove(y, update_tree);
    } else if (n->min() <= range.max()) { // skew overlap different payload
      n->assign_min(max_plus_1, update_tree);
      break;
    } else { // n->min() > range.max(), different payloads - done.
      break;
    }
  }
 
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
DiscreteSpace<METRIC, PAYLOAD>::fill(DiscreteSpace::range_type const &range, PAYLOAD const &payload) {
  // Rightmost node of interest with n->min() <= min.
  Node *n = this->lower_node(range.min());
  Node *x = nullptr; // New node (if any).
  // Need copies because we will modify these.
  auto min = range.min();
  auto max = range.max();
 
  // Handle cases involving a node of interest to the left of the
  // range.
  if (n) {
    if (n->min() < min) {
      auto min_1 = min;
      --min_1;                // dec is OK because min isn't zero.
      if (n->max() < min_1) { // no overlap, not adjacent.
        n = next(n);
      } else if (n->max() >= max) { // incoming range is covered, just discard.
        return *this;
      } else if (n->payload() != payload) { // different payload, clip range on left.
        min = n->max();
        ++min;
        n = next(n);
      } else { // skew overlap or adjacent to predecessor with same payload, use node and continue.
        x = n;
        n = next(n);
      }
    }
  } else {
    n = this->head();
  }
 
  // Work through the rest of the nodes of interest.
  // Invariant: n->min() >= min
 
  // Careful here -- because max_plus1 might wrap we need to use it only if we can be certain it
  // didn't. This is done by ordering the range tests so that when max_plus1 is used when we know
  // there exists a larger value than max.
  auto max_plus1 = max;
  ++max_plus1;
 
  /* Notes:
     - max (and thence also max_plus1) never change during the loop.
     - we must have either x != 0 or adjust min but not both for each loop iteration.
  */
  while (n) {
    if (n->payload() == payload) {
      if (x) {
        if (n->max() <= max) { // next range is covered, so we can remove and continue.
          this->remove(n);
          n = next(x);
        } else if (n->min() <= max_plus1) {
          // Overlap or adjacent with larger max - absorb and finish.
          x->assign_max(n->max());
          this->remove(n);
          return *this;
        } else {
          // have the space to finish off the range.
          x->assign_max(max);
          return *this;
        }
      } else {                 // not carrying a span.
        if (n->max() <= max) { // next range is covered - use it.
          x = n;
          x->assign_min(min);
          n = next(n);
        } else if (n->min() <= max_plus1) {
          n->assign_min(min);
          return *this;
        } else { // no overlap, space to complete range.
          this->insert_before(n, _fa.make(min, max, payload));
          return *this;
        }
      }
    } else { // different payload
      if (x) {
        if (max < n->min()) { // range ends before n starts, done.
          x->assign_max(max);
          return *this;
        } else if (max <= n->max()) { // range ends before n, done.
          x->assign_max(--metric_type(n->min()));
          return *this;
        } else { // n is contained in range, skip over it.
          x->assign_max(--metric_type(n->min()));
          x   = nullptr;
          min = n->max();
          ++min; // OK because n->max() maximal => next is null.
          n = next(n);
        }
      } else {                // no carry node.
        if (max < n->min()) { // entirely before next span.
          this->insert_before(n, _fa.make(min, max, payload));
          return *this;
        } else {
          if (min < n->min()) { // leading section, need node.
            auto y = _fa.make(min, --metric_type(n->min()), payload);
            this->insert_before(n, y);
          }
          if (max <= n->max()) { // nothing past node
            return *this;
          }
          min = n->max();
          ++min;
          n = next(n);
        }
      }
    }
  }
  // Invariant: min is larger than any existing range maximum.
  if (x) {
    x->assign_max(max);
  } else {
    this->append(_fa.make(min, max, payload));
  }
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
template <typename F, typename U>
auto
DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const &range, U const &color, F &&blender) -> self_type & {
  // Do a base check for the color to use on unmapped values. If self blending on @a color
  // is @c false, then do not color currently unmapped values.
  PAYLOAD plain_color{};                            // color to paint uncolored metrics.
  bool plain_color_p = blender(plain_color, color); // start with default and blend in @a color.
 
  auto node_cleaner = [&](Node *ptr) -> void { _fa.destroy(ptr); };
  // Used to hold a temporary blended node - @c release if put in space, otherwise cleaned up.
  using unique_node = std::unique_ptr<Node, decltype(node_cleaner)>;
 
  // Rightmost node of interest with n->min() <= range.min().
  Node *n = this->lower_node(range.min());
 
  // This doesn't change, compute outside loop.
  auto range_max_plus_1 = range.max();
  ++range_max_plus_1; // only use in contexts where @a max < METRIC max value.
 
  // Update every loop to track what remains to be filled.
  auto remaining = range;
 
  if (nullptr == n) {
    n = this->head();
  }
 
  // Process @a n, covering the values from the previous range to @a n.max
  while (n) {
    // If there's no overlap, skip because this will be checked next loop, or it's the last node
    // and will be checked post loop. Loop logic is simpler if n->max() >= remaining.min()
    if (n->max() < remaining.min()) {
      n = next(n);
      continue;
    }
    // Invariant - n->max() >= remaining.min();
 
    // Check for left extension. If found, clip that node to be adjacent and put in a
    // temporary that covers the overlap with the original payload.
    if (n->min() < remaining.min()) {
      // @a fill is inserted iff n->max() < remaining.max(), in which case the max is correct.
      // This is needed in other cases only for the color blending result.
      unique_node fill{_fa.make(remaining.min(), n->max(), n->payload()), node_cleaner};
      bool fill_p = blender(fill->payload(), color); // fill or clear?
 
      if (fill_p) {
        bool same_color_p = fill->payload() == n->payload();
        if (same_color_p && n->max() >= remaining.max()) {
          return *this; // incoming range is completely covered by @a n in the same color, done.
        }
        if (!same_color_p) {
          auto fn    = fill.release();
          auto n_max = n->max();                         // save this so @a n can be clipped.
          n->assign_max(--metric_type(remaining.min())); // clip @a n down.
          this->insert_after(n, fn);                     // add intersection node in different color.
          if (n_max > remaining.max()) {                 // right extent too - split and done.
            fn->assign_max(remaining.max());             // fill node stops at end of target range.
            this->insert_after(fn, _fa.make(++metric_type(remaining.max()), n_max, n->payload()));
            return *this;
          }
          n = fn; // skip to use new node as current node.
        }
        remaining.assign_min(++metric_type(n->max())); // going to fill up n->max(), clip target.
      } else {                                         // clear, don't fill.
        auto n_r = n->range();                         // cache to avoid ordering requirements.
        if (n_r.max() > remaining.max()) {             // overhang on the right, must split.
          fill.release();                              // not going to use it,
          n->assign_min(++metric_type(remaining.max()));
          this->insert_before(n, _fa.make(n_r.min(), --metric_type(remaining.min()), n->payload()));
          return *this;
        }
        n->assign_max(--metric_type(remaining.min())); // clip @a n down.
        if (n_r.max() == remaining.max()) {
          return *this;
        }
        remaining.assign_min(++metric_type(n_r.max()));
      }
      continue;
    }
 
    Node *pred = prev(n);
    // invariant
    // - remaining.min() <= n->max()
    // - !pred || pred->max() < remaining.min()
 
    // Calculate and cache key relationships between @a n and @a remaining.
 
    // @a n extends past @a remaining, so the trailing segment must be dealt with.
    bool right_ext_p = n->max() > remaining.max();
    // @a n strictly right overlaps with @a remaining.
    bool right_overlap_p = remaining.contains(n->min());
    // @a n is adjacent on the right to @a remaining.
    bool right_adj_p = !right_overlap_p && remaining.is_left_adjacent_to(n->range());
    // @a n has the same color as would be used for unmapped values.
    bool n_plain_colored_p = plain_color_p && (n->payload() == plain_color);
 
    // Check for no right overlap - that means @a n is past the target range.
    // It may be possible to extend @a n or the previous range to cover
    // the target range. Regardless, all of @a range can be filled at this point.
    if (!right_overlap_p) {
      // @a pred has the same color as would be used for unmapped values
      // and is adjacent to @a remaining.
      bool pred_plain_colored_p = pred && ++metric_type(pred->max()) == remaining.min() && pred->payload() == plain_color;
 
      if (right_adj_p && n_plain_colored_p) { // can pull @a n left to cover
        n->assign_min(remaining.min());
        if (pred_plain_colored_p) { // if that touches @a pred with same color, collapse.
          auto pred_min = pred->min();
          this->remove(pred);
          n->assign_min(pred_min);
        }
      } else if (pred_plain_colored_p) { // can pull @a pred right to cover.
        pred->assign_max(remaining.max());
      } else if (!remaining.empty() && plain_color_p) { // Must add new range if plain color valid.
        this->insert_before(n, _fa.make(remaining.min(), remaining.max(), plain_color));
      }
      return *this;
    }
 
    // Invariant: @n has right overlap with @a remaining
 
    // If there's a gap on the left, fill from @a r.min to @a n.min - 1
    if (plain_color_p && remaining.min() < n->min()) {
      if (n->payload() == plain_color) {
        if (pred && pred->payload() == n->payload()) {
          auto pred_min{pred->min()};
          this->remove(pred);
          n->assign_min(pred_min);
        } else {
          n->assign_min(remaining.min());
        }
      } else {
        auto n_min_minus_1{n->min()};
        --n_min_minus_1;
        if (pred && pred->payload() == plain_color) {
          pred->assign_max(n_min_minus_1);
        } else {
          this->insert_before(n, _fa.make(remaining.min(), n_min_minus_1, plain_color));
        }
      }
    }
 
    // Invariant: Space in @a range and to the left of @a n has been filled.
 
    // Create a node with the blend for the overlap and then update / replace @a n as needed.
    auto max{right_ext_p ? remaining.max() : n->max()}; // smallest boundary of range and @a n.
    unique_node fill{_fa.make(n->min(), max, n->payload()), node_cleaner};
    bool fill_p = blender(fill->payload(), color); // fill or clear?
    auto next_n = next(n);                         // cache this in case @a n is removed.
    remaining.assign_min(++METRIC{fill->max()});   // Update what is left to fill.
 
    // Clean up the range for @a n
    if (fill_p) {
      // Check if @a pred is suitable for extending right to cover the target range.
      bool pred_adj_p =
        nullptr != (pred = prev(n)) && pred->range().is_left_adjacent_to(fill->range()) && pred->payload() == fill->payload();
 
      if (right_ext_p) {
        if (n->payload() == fill->payload()) {
          n->assign_min(fill->min());
        } else {
          n->assign_min(range_max_plus_1);
          if (pred_adj_p) {
            pred->assign_max(fill->max());
          } else {
            this->insert_before(n, fill.release());
          }
        }
        return *this; // @a n extends past @a remaining, -> all done.
      } else {
        // Collapse in to previous range if it's adjacent and the color matches.
        if (pred_adj_p) {
          this->remove(n);
          pred->assign_max(fill->max());
        } else {
          this->insert_before(n, fill.release());
          this->remove(n);
        }
      }
    } else if (right_ext_p) {
      n->assign_min(range_max_plus_1);
      return *this;
    } else {
      this->remove(n);
    }
 
    // Everything up to @a n.max is correct, time to process next node.
    n = next_n;
  }
 
  // Arriving here means there are no more ranges past @a range (those cases return from the loop).
  // Therefore the final fill node is always last in the tree.
  if (plain_color_p && !remaining.empty()) {
    // Check if the last node can be extended to cover because it's left adjacent.
    // Can decrement @a range_min because if there's a range to the left, @a range_min is not minimal.
    n = _list.tail();
    if (n && n->max() >= --metric_type{remaining.min()} && n->payload() == plain_color) {
      n->assign_max(range.max());
    } else {
      this->append(_fa.make(remaining.min(), remaining.max(), plain_color));
    }
  }
 
  return *this;
}
 
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::clear() {
  for (auto &node : _list) {
    std::destroy_at(&node.payload());
  }
  _list.clear();
  _root = nullptr;
  _arena.clear();
  _fa.clear();
}
 
}} // namespace swoc::SWOC_VERSION_NS