exclude: excluded range enumeration
refs #3681
Change-Id: I4ed60636aca9f6e6c5963e60eb28efba31a32c30
diff --git a/src/exclude.cpp b/src/exclude.cpp
index 19091f4..7007daf 100644
--- a/src/exclude.cpp
+++ b/src/exclude.cpp
@@ -41,12 +41,53 @@
}
bool
+operator==(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b)
+{
+ return (a.isNegInf && b.isNegInf) ||
+ (a.isNegInf == b.isNegInf && a.component == b.component);
+}
+
+bool
operator>(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b)
{
return a.isNegInf < b.isNegInf ||
(a.isNegInf == b.isNegInf && a.component > b.component);
}
+bool
+Exclude::Range::operator==(const Exclude::Range& other) const
+{
+ return this->fromInfinity == other.fromInfinity && this->toInfinity == other.toInfinity &&
+ (this->fromInfinity || this->from == other.from) &&
+ (this->toInfinity || this->to == other.to);
+}
+
+std::ostream&
+operator<<(std::ostream& os, const Exclude::Range& range)
+{
+ if (range.isSingular()) {
+ return os << '{' << range.from << '}';
+ }
+
+ if (range.fromInfinity) {
+ os << "(-∞";
+ }
+ else {
+ os << '[' << range.from;
+ }
+
+ os << ",";
+
+ if (range.toInfinity) {
+ os << "+∞)";
+ }
+ else {
+ os << range.to << ']';
+ }
+
+ return os;
+}
+
BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
BOOST_CONCEPT_ASSERT((WireEncodableWithEncodingBuffer<Exclude>));
@@ -175,8 +216,8 @@
bool
Exclude::isExcluded(const name::Component& comp) const
{
- const_iterator lb = m_entries.lower_bound(comp);
- return lb != end() && // lb==end() means comp is less than the first excluded component
+ ExcludeMap::const_iterator lb = m_entries.lower_bound(comp);
+ return lb != m_entries.end() && // if false, comp is less than the first excluded component
(lb->second || // comp matches an ANY range
(!lb->first.isNegInf && lb->first.component == comp)); // comp equals an exact excluded component
}
@@ -223,8 +264,8 @@
"(for single name exclude use Exclude::excludeOne)"));
}
- iterator newFrom = m_entries.lower_bound(from);
- if (newFrom == end() || !newFrom->second /*without ANY*/) {
+ ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
+ if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
bool isNewEntry = false;
std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
if (!isNewEntry) {
@@ -235,8 +276,8 @@
// else
// nothing special if start of the range already exists with ANY flag set
- iterator newTo = m_entries.lower_bound(to);
- BOOST_ASSERT(newTo != end());
+ ExcludeMap::iterator newTo = m_entries.lower_bound(to);
+ BOOST_ASSERT(newTo != m_entries.end());
if (newTo == newFrom || !newTo->second) {
newTo = m_entries.emplace_hint(newTo, to, false);
++newTo;
@@ -254,8 +295,8 @@
Exclude&
Exclude::excludeAfter(const name::Component& from)
{
- iterator newFrom = m_entries.lower_bound(from);
- if (newFrom == end() || !newFrom->second /*without ANY*/) {
+ ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
+ if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
bool isNewEntry = false;
std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
if (!isNewEntry) {
@@ -273,18 +314,11 @@
return *this;
}
-void
-Exclude::clear()
-{
- m_entries.clear();
- m_wire.reset();
-}
-
std::ostream&
operator<<(std::ostream& os, const Exclude& exclude)
{
bool isFirst = true;
- for (const Exclude::Entry& entry : exclude | boost::adaptors::reversed) {
+ for (const Exclude::Entry& entry : exclude.m_entries | boost::adaptors::reversed) {
if (!entry.first.isNegInf) {
if (!isFirst)
os << ",";
@@ -312,12 +346,81 @@
bool
Exclude::operator==(const Exclude& other) const
{
- if (empty() && other.empty())
- return true;
- if (empty() || other.empty())
- return false;
+ return m_entries == other.m_entries;
+}
- return wireEncode() == other.wireEncode();
+size_t
+Exclude::size() const
+{
+ return std::distance(begin(), end());
+}
+
+void
+Exclude::clear()
+{
+ m_entries.clear();
+ m_wire.reset();
+}
+
+Exclude::const_iterator::const_iterator(ExcludeMap::const_reverse_iterator it,
+ ExcludeMap::const_reverse_iterator rend)
+ : m_it(it)
+ , m_rend(rend)
+{
+ this->update();
+}
+
+Exclude::const_iterator&
+Exclude::const_iterator::operator++()
+{
+ bool wasInRange = m_it->second;
+ ++m_it;
+ if (wasInRange && m_it != m_rend) {
+ BOOST_ASSERT(m_it->second == false); // consecutive ranges should have been combined
+ ++m_it; // skip over range high limit
+ }
+ this->update();
+ return *this;
+}
+
+Exclude::const_iterator
+Exclude::const_iterator::operator++(int)
+{
+ const_iterator i = *this;
+ this->operator++();
+ return i;
+}
+
+void
+Exclude::const_iterator::update()
+{
+ if (m_it == m_rend) {
+ return;
+ }
+
+ if (m_it->second) { // range
+ if (m_it->first.isNegInf) {
+ m_range.fromInfinity = true;
+ }
+ else {
+ m_range.fromInfinity = false;
+ m_range.from = m_it->first.component;
+ }
+
+ auto next = std::next(m_it);
+ if (next == m_rend) {
+ m_range.toInfinity = true;
+ }
+ else {
+ m_range.toInfinity = false;
+ m_range.to = next->first.component;
+ }
+ }
+ else { // single
+ BOOST_ASSERT(!m_it->first.isNegInf);
+ m_range.fromInfinity = m_range.toInfinity = false;
+ m_range.from = m_range.to = m_it->first.component;
+ }
}
} // namespace ndn
diff --git a/src/exclude.hpp b/src/exclude.hpp
index e850cf7..595f143 100644
--- a/src/exclude.hpp
+++ b/src/exclude.hpp
@@ -126,18 +126,6 @@
Exclude&
excludeAfter(const name::Component& from);
- /**
- * @brief Check if exclude filter is empty
- */
- bool
- empty() const;
-
- /**
- * @brief Clear the exclude filter
- */
- void
- clear();
-
public: // EqualityComparable concept
bool
operator==(const Exclude& other) const;
@@ -145,7 +133,7 @@
bool
operator!=(const Exclude& other) const;
-public: // low-level exclude entry API
+public: // interal storage
/**
* @brief either a name::Component or "negative infinity"
*/
@@ -179,31 +167,106 @@
*
* The map is ordered in descending order to simplify \p isExcluded.
*/
- typedef std::map<ExcludeComponent, bool, std::greater<ExcludeComponent>> ExcludeType;
- typedef ExcludeType::value_type Entry;
- typedef ExcludeType::iterator iterator;
- typedef ExcludeType::const_iterator const_iterator;
- typedef ExcludeType::reverse_iterator reverse_iterator;
- typedef ExcludeType::const_reverse_iterator const_reverse_iterator;
+ typedef std::map<ExcludeComponent, bool, std::greater<ExcludeComponent>> ExcludeMap;
+ typedef ExcludeMap::value_type Entry;
+public: // enumeration API
/**
- * @brief Get number of exclude terms
+ * @brief represent an excluded component or range
*/
- size_t
- size() const;
+ class Range
+ {
+ public:
+ /**
+ * @retval true A single component is excluded
+ * @retval false A range of more than one components are excluded
+ */
+ bool
+ isSingular() const;
- /**
- * @brief Get begin iterator of the exclude terms
- */
+ bool
+ operator==(const Exclude::Range& other) const;
+
+ bool
+ operator!=(const Exclude::Range& other) const;
+
+ public:
+ /**
+ * @brief from negative infinity?
+ */
+ bool fromInfinity;
+
+ /**
+ * @brief from component (inclusive)
+ * @pre valid only if !fromInfinity
+ */
+ name::Component from;
+
+ /**
+ * @brief to positive infinity?
+ */
+ bool toInfinity;
+
+ /**
+ * @brief to component (inclusive)
+ * @pre valid only if !toInfinity
+ */
+ name::Component to;
+ };
+
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const Range>
+ {
+ public:
+ const_iterator() = default;
+
+ const_iterator(ExcludeMap::const_reverse_iterator it, ExcludeMap::const_reverse_iterator rend);
+
+ const Range&
+ operator*() const;
+
+ const Range*
+ operator->() const;
+
+ const_iterator&
+ operator++();
+
+ const_iterator
+ operator++(int);
+
+ bool
+ operator==(const const_iterator& other) const;
+
+ bool
+ operator!=(const const_iterator& other) const;
+
+ private:
+ void
+ update();
+
+ private:
+ ExcludeMap::const_reverse_iterator m_it;
+ ExcludeMap::const_reverse_iterator m_rend;
+ Range m_range;
+ friend class Exclude;
+ };
+
const_iterator
begin() const;
- /**
- * @brief Get end iterator of the exclude terms
- */
const_iterator
end() const;
+ bool
+ empty() const;
+
+ size_t
+ size() const;
+
+ /// \todo const_iterator erase(const_iterator i);
+
+ void
+ clear();
+
private:
/**
* @brief directly append exclude element
@@ -219,47 +282,87 @@
excludeRange(const ExcludeComponent& from, const name::Component& to);
private:
- ExcludeType m_entries;
-
+ ExcludeMap m_entries;
mutable Block m_wire;
+
+ friend std::ostream&
+ operator<<(std::ostream& os, const Exclude& name);
};
std::ostream&
operator<<(std::ostream& os, const Exclude& name);
bool
+operator==(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b);
+
+bool
operator>(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b);
+std::ostream&
+operator<<(std::ostream& os, const Exclude::Range& range);
+
+inline Exclude::const_iterator
+Exclude::begin() const
+{
+ return const_iterator(m_entries.rbegin(), m_entries.rend());
+}
+
+inline Exclude::const_iterator
+Exclude::end() const
+{
+ return const_iterator(m_entries.rend(), m_entries.rend());
+}
+
inline bool
Exclude::empty() const
{
return m_entries.empty();
}
-inline size_t
-Exclude::size() const
-{
- return m_entries.size();
-}
-
-inline Exclude::const_iterator
-Exclude::begin() const
-{
- return m_entries.begin();
-}
-
-inline Exclude::const_iterator
-Exclude::end() const
-{
- return m_entries.end();
-}
-
inline bool
Exclude::operator!=(const Exclude& other) const
{
return !(*this == other);
}
+inline bool
+Exclude::Range::isSingular() const
+{
+ return !this->fromInfinity && !this->toInfinity && this->from == this->to;
+}
+
+inline bool
+Exclude::Range::operator!=(const Exclude::Range& other) const
+{
+ return !this->operator==(other);
+}
+
+inline const Exclude::Range&
+Exclude::const_iterator::operator*() const
+{
+ BOOST_ASSERT(m_it != m_rend);
+ return m_range;
+}
+
+inline const Exclude::Range*
+Exclude::const_iterator::operator->() const
+{
+ BOOST_ASSERT(m_it != m_rend);
+ return &m_range;
+}
+
+inline bool
+Exclude::const_iterator::operator==(const const_iterator& other) const
+{
+ return m_it == other.m_it;
+}
+
+inline bool
+Exclude::const_iterator::operator!=(const const_iterator& other) const
+{
+ return !this->operator==(other);
+}
+
} // namespace ndn
#endif // NDN_EXCLUDE_H