exclude: ImplicitSha256Digest bugfix

This commit also improves name::Component test suite.

refs #3665

Change-Id: I8e9a575bf203f0983bacd1dbdb3491510e326d1f
diff --git a/src/exclude.cpp b/src/exclude.cpp
index 300aed7..19091f4 100644
--- a/src/exclude.cpp
+++ b/src/exclude.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -28,6 +28,25 @@
 
 namespace ndn {
 
+Exclude::ExcludeComponent::ExcludeComponent(const name::Component& component1)
+  : isNegInf(false)
+  , component(component1)
+{
+}
+
+Exclude::ExcludeComponent::ExcludeComponent(bool isNegInf1)
+  : isNegInf(true)
+{
+  BOOST_ASSERT(isNegInf1 == true);
+}
+
+bool
+operator>(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b)
+{
+  return a.isNegInf < b.isNegInf ||
+         (a.isNegInf == b.isNegInf && a.component > b.component);
+}
+
 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
 BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
 BOOST_CONCEPT_ASSERT((WireEncodableWithEncodingBuffer<Exclude>));
@@ -35,9 +54,7 @@
 static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
               "Exclude::Error must inherit from tlv::Error");
 
-Exclude::Exclude()
-{
-}
+Exclude::Exclude() = default;
 
 Exclude::Exclude(const Block& wire)
 {
@@ -48,8 +65,8 @@
 size_t
 Exclude::wireEncode(EncodingImpl<TAG>& encoder) const
 {
-  if (m_exclude.empty()) {
-    BOOST_THROW_EXCEPTION(Error("Exclude filter cannot be empty"));
+  if (m_entries.empty()) {
+    BOOST_THROW_EXCEPTION(Error("cannot encode empty Exclude selector"));
   }
 
   size_t totalLength = 0;
@@ -57,12 +74,12 @@
   // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
   // Any     ::= ANY-TYPE TLV-LENGTH(=0)
 
-  for (const auto& item : m_exclude) {
-    if (item.second) {
+  for (const Entry& entry : m_entries) {
+    if (entry.second) {
       totalLength += prependEmptyBlock(encoder, tlv::Any);
     }
-    if (!item.first.empty() || !item.second) {
-      totalLength += item.first.wireEncode(encoder);
+    if (!entry.first.isNegInf) {
+      totalLength += entry.first.component.wireEncode(encoder);
     }
   }
 
@@ -113,111 +130,104 @@
 
   Block::element_const_iterator i = m_wire.elements_begin();
   if (i->type() == tlv::Any) {
-    appendExclude(name::Component(), true);
+    this->appendEntry(true, true);
     ++i;
   }
 
   while (i != m_wire.elements_end()) {
-    name::Component excludedComponent;
+    name::Component component;
     try {
-      excludedComponent = name::Component(*i);
+      component = name::Component(*i);
     }
     catch (const name::Component::Error&) {
       BOOST_THROW_EXCEPTION(Error("Incorrect format of Exclude filter"));
     }
-
     ++i;
 
-    if (i != m_wire.elements_end()) {
-      if (i->type() == tlv::Any) {
-        appendExclude(excludedComponent, true);
-        ++i;
-      }
-      else {
-        appendExclude(excludedComponent, false);
-      }
+    if (i != m_wire.elements_end() && i->type() == tlv::Any) {
+      this->appendEntry(component, true);
+      ++i;
     }
     else {
-      appendExclude(excludedComponent, false);
+      this->appendEntry(component, false);
     }
   }
 }
 
-// example: ANY /b /d ANY /f
+template<typename T>
+void
+Exclude::appendEntry(const T& component, bool hasAny)
+{
+  m_entries.emplace_hint(m_entries.begin(), std::piecewise_construct,
+                         std::forward_as_tuple(component),
+                         std::forward_as_tuple(hasAny));
+}
+
+// example: ANY "b" "d" ANY "f"
+// ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
 //
-// ordered in map as:
-//
-// /f (false); /d (true); /b (false); / (true)
-//
-// lower_bound(/)  -> / (true) <-- excluded (equal)
-// lower_bound(/a) -> / (true) <-- excluded (any)
-// lower_bound(/b) -> /b (false) <--- excluded (equal)
-// lower_bound(/c) -> /b (false) <--- not excluded (not equal and no ANY)
-// lower_bound(/d) -> /d (true) <- excluded
-// lower_bound(/e) -> /d (true) <- excluded
+// lower_bound("")  -> -Inf (true) <-- excluded (ANY)
+// lower_bound("a") -> -Inf (true) <-- excluded (ANY)
+// lower_bound("b") -> "b" (false) <--- excluded (equal)
+// lower_bound("c") -> "b" (false) <--- not excluded (not equal and no ANY)
+// lower_bound("d") -> "d" (true) <- excluded
+// lower_bound("e") -> "d" (true) <- excluded
 bool
 Exclude::isExcluded(const name::Component& comp) const
 {
-  const_iterator lowerBound = m_exclude.lower_bound(comp);
-  if (lowerBound == end())
-    return false;
-
-  if (lowerBound->second)
-    return true;
-  else
-    return lowerBound->first == comp;
+  const_iterator lb = m_entries.lower_bound(comp);
+  return lb != end() && // lb==end() means 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
 }
 
 Exclude&
 Exclude::excludeOne(const name::Component& comp)
 {
   if (!isExcluded(comp)) {
-    m_exclude.insert(std::make_pair(comp, false));
+    this->appendEntry(comp, false);
     m_wire.reset();
   }
   return *this;
 }
 
-// example: ANY /b0 /d0 ANY /f0
-//
-// ordered in map as:
-//
-// /f0 (false); /d0 (true); /b0 (false); / (true)
-//
-// lower_bound(/)  -> / (true) <-- excluded (equal)
-// lower_bound(/a0) -> / (true) <-- excluded (any)
-// lower_bound(/b0) -> /b0 (false) <--- excluded (equal)
-// lower_bound(/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
-// lower_bound(/d0) -> /d0 (true) <- excluded
-// lower_bound(/e0) -> /d0 (true) <- excluded
-
-
-// examples with desired outcomes
-// excludeRange(/, /f0) ->  ANY /f0
-//                          /f0 (false); / (true)
-// excludeRange(/, /f1) ->  ANY /f1
-//                          /f1 (false); / (true)
-// excludeRange(/a0, /e0) ->  ANY /f0
-//                          /f0 (false); / (true)
-// excludeRange(/a0, /e0) ->  ANY /f0
-//                          /f0 (false); / (true)
-
-// excludeRange(/b1, /c0) ->  ANY /b0 /b1 ANY /c0 /d0 ANY /f0
-//                          /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
+Exclude&
+Exclude::excludeBefore(const name::Component& to)
+{
+  return excludeRange(ExcludeComponent(true), to);
+}
 
 Exclude&
 Exclude::excludeRange(const name::Component& from, const name::Component& to)
 {
-  if (from >= to) {
-    BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.toUri() + ", " + to.toUri() + "] "
+  return excludeRange(ExcludeComponent(from), to);
+}
+
+// example: ANY "b" "d" ANY "g"
+// ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
+// possible sequence of operations:
+// excludeBefore("a") -> excludeRange(-Inf, "a") ->  ANY "a"
+//                          "a" (false); -Inf (true)
+// excludeBefore("b") -> excludeRange(-Inf, "b") ->  ANY "b"
+//                          "b" (false); -Inf (true)
+// excludeRange("e", "g") ->  ANY "b" "e" ANY "g"
+//                          "g" (false); "e" (true); "b" (false); -Inf (true)
+// excludeRange("d", "f") ->  ANY "b" "d" ANY "g"
+//                          "g" (false); "d" (true); "b" (false); -Inf (true)
+
+Exclude&
+Exclude::excludeRange(const ExcludeComponent& from, const name::Component& to)
+{
+  if (!from.isNegInf && from.component >= to) {
+    BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.component.toUri() + ", " + to.toUri() + "] "
                                 "(for single name exclude use Exclude::excludeOne)"));
   }
 
-  iterator newFrom = m_exclude.lower_bound(from);
+  iterator newFrom = m_entries.lower_bound(from);
   if (newFrom == end() || !newFrom->second /*without ANY*/) {
-    std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
-    newFrom = fromResult.first;
-    if (!fromResult.second) {
+    bool isNewEntry = false;
+    std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
+    if (!isNewEntry) {
       // this means that the lower bound is equal to the item itself. So, just update ANY flag
       newFrom->second = true;
     }
@@ -225,16 +235,17 @@
   // else
   // nothing special if start of the range already exists with ANY flag set
 
-  iterator newTo = m_exclude.lower_bound(to); // !newTo cannot be end()
+  iterator newTo = m_entries.lower_bound(to);
+  BOOST_ASSERT(newTo != end());
   if (newTo == newFrom || !newTo->second) {
-    std::pair<iterator, bool> toResult = m_exclude.insert(std::make_pair(to, false));
-    newTo = toResult.first;
-    ++ newTo;
+    newTo = m_entries.emplace_hint(newTo, to, false);
+    ++newTo;
   }
   // else
   // nothing to do really
 
-  m_exclude.erase(newTo, newFrom); // remove any intermediate node, since all of the are excluded
+  // remove any intermediate entries, since all of the are excluded
+  m_entries.erase(newTo, newFrom);
 
   m_wire.reset();
   return *this;
@@ -243,11 +254,11 @@
 Exclude&
 Exclude::excludeAfter(const name::Component& from)
 {
-  iterator newFrom = m_exclude.lower_bound(from);
+  iterator newFrom = m_entries.lower_bound(from);
   if (newFrom == end() || !newFrom->second /*without ANY*/) {
-    std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
-    newFrom = fromResult.first;
-    if (!fromResult.second) {
+    bool isNewEntry = false;
+    std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
+    if (!isNewEntry) {
       // this means that the lower bound is equal to the item itself. So, just update ANY flag
       newFrom->second = true;
     }
@@ -255,27 +266,32 @@
   // else
   // nothing special if start of the range already exists with ANY flag set
 
-  if (newFrom != m_exclude.begin()) {
-    // remove any intermediate node, since all of the are excluded
-    m_exclude.erase(m_exclude.begin(), newFrom);
-  }
+  // remove any intermediate node, since all of the are excluded
+  m_entries.erase(m_entries.begin(), newFrom);
 
   m_wire.reset();
   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 auto& item : exclude | boost::adaptors::reversed) {
-    if (!item.first.empty() || !item.second) {
+  for (const Exclude::Entry& entry : exclude | boost::adaptors::reversed) {
+    if (!entry.first.isNegInf) {
       if (!isFirst)
         os << ",";
-      os << item.first.toUri();
+      entry.first.component.toUri(os);
       isFirst = false;
     }
-    if (item.second) {
+    if (entry.second) {
       if (!isFirst)
         os << ",";
       os << "*";
diff --git a/src/exclude.hpp b/src/exclude.hpp
index 7f6ff4f..e850cf7 100644
--- a/src/exclude.hpp
+++ b/src/exclude.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -33,7 +33,7 @@
 namespace ndn {
 
 /**
- * @brief Class to represent Exclude component in NDN interests
+ * @brief Represents Exclude selector in NDN Interest
  */
 class Exclude
 {
@@ -49,7 +49,7 @@
   };
 
   /**
-   * @brief Default constructor an empty exclude
+   * @brief Constructs an empty Exclude
    */
   Exclude();
 
@@ -101,16 +101,17 @@
   excludeOne(const name::Component& comp);
 
   /**
-   * @brief Exclude components from range [from, to]
+   * @brief Exclude components in range [from, to]
    * @param from first element of the range
    * @param to last element of the range
+   * @throw Error \p from equals or comes after \p to in canonical ordering
    * @returns *this to allow chaining
    */
   Exclude&
   excludeRange(const name::Component& from, const name::Component& to);
 
   /**
-   * @brief Exclude all components from range [/, to]
+   * @brief Exclude all components in range (-Inf, to]
    * @param to last element of the range
    * @returns *this to allow chaining
    */
@@ -118,7 +119,7 @@
   excludeBefore(const name::Component& to);
 
   /**
-   * @brief Exclude all components from range [from, +Inf]
+   * @brief Exclude all components in range [from, +Inf)
    * @param from the first element of the range
    * @returns *this to allow chaining
    */
@@ -144,25 +145,46 @@
   bool
   operator!=(const Exclude& other) const;
 
-public: // low-level exclude element API
-  typedef std::map< name::Component, bool /*any*/, std::greater<name::Component> > exclude_type;
+public: // low-level exclude entry API
+  /**
+   * @brief either a name::Component or "negative infinity"
+   */
+  class ExcludeComponent
+  {
+  public:
+    /**
+     * @brief implicitly construct a regular infinity ExcludeComponent
+     * @param component a name component which is excluded
+     */
+    ExcludeComponent(const name::Component& component);
 
-  typedef exclude_type::iterator iterator;
-  typedef exclude_type::const_iterator const_iterator;
-  typedef exclude_type::reverse_iterator reverse_iterator;
-  typedef exclude_type::const_reverse_iterator const_reverse_iterator;
+    /**
+     * @brief construct a negative infinity ExcludeComponent
+     * @param isNegInf must be true
+     */
+    explicit
+    ExcludeComponent(bool isNegInf);
+
+  public:
+    bool isNegInf;
+    name::Component component;
+  };
 
   /**
-   * @brief Method to directly append exclude element
-   * @param name excluded name component
-   * @param any  flag indicating if there is a postfix ANY component after the name
+   * @brief a map of exclude entries
    *
-   * This method is used during conversion from wire format of exclude filter
+   * Each key, except "negative infinity", is a name component that is excluded.
+   * The mapped boolean indicates whether the range between a key and the next greater key
+   * is also excluded. If true, the wire encoding shall have an ANY element.
    *
-   * If there is an error with ranges (e.g., order of components is wrong) an exception is thrown
+   * The map is ordered in descending order to simplify \p isExcluded.
    */
-  void
-  appendExclude(const name::Component& name, bool any);
+  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;
 
   /**
    * @brief Get number of exclude terms
@@ -182,24 +204,22 @@
   const_iterator
   end() const;
 
-  /**
-   * @brief Get begin iterator of the exclude terms
-   */
-  const_reverse_iterator
-  rbegin() const;
-
-  /**
-   * @brief Get end iterator of the exclude terms
-   */
-  const_reverse_iterator
-  rend() const;
-
 private:
+  /**
+   * @brief directly append exclude element
+   * @tparam T either name::Component or bool
+   *
+   * This method is used during conversion from wire format of exclude filter
+   */
+  template<typename T>
+  void
+  appendEntry(const T& component, bool hasAny);
+
   Exclude&
-  excludeRange(iterator fromLowerBound, iterator toLowerBound);
+  excludeRange(const ExcludeComponent& from, const name::Component& to);
 
 private:
-  exclude_type m_exclude;
+  ExcludeType m_entries;
 
   mutable Block m_wire;
 };
@@ -207,59 +227,31 @@
 std::ostream&
 operator<<(std::ostream& os, const Exclude& name);
 
-inline Exclude&
-Exclude::excludeBefore(const name::Component& to)
-{
-  return excludeRange(name::Component(), to);
-}
-
-inline void
-Exclude::appendExclude(const name::Component& name, bool any)
-{
-  m_exclude[name] = any;
-}
+bool
+operator>(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b);
 
 inline bool
 Exclude::empty() const
 {
-  return m_exclude.empty();
-}
-
-inline void
-Exclude::clear()
-{
-  m_exclude.clear();
-  m_wire.reset();
+  return m_entries.empty();
 }
 
 inline size_t
 Exclude::size() const
 {
-  return m_exclude.size();
+  return m_entries.size();
 }
 
 inline Exclude::const_iterator
 Exclude::begin() const
 {
-  return m_exclude.begin();
+  return m_entries.begin();
 }
 
 inline Exclude::const_iterator
 Exclude::end() const
 {
-  return m_exclude.end();
-}
-
-inline Exclude::const_reverse_iterator
-Exclude::rbegin() const
-{
-  return m_exclude.rbegin();
-}
-
-inline Exclude::const_reverse_iterator
-Exclude::rend() const
-{
-  return m_exclude.rend();
+  return m_entries.end();
 }
 
 inline bool
@@ -268,6 +260,6 @@
   return !(*this == other);
 }
 
-} // ndn
+} // namespace ndn
 
 #endif // NDN_EXCLUDE_H
diff --git a/src/meta-info.cpp b/src/meta-info.cpp
index 1fb2d9f..0fd6923 100644
--- a/src/meta-info.cpp
+++ b/src/meta-info.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -227,12 +227,12 @@
     if (m_finalBlockId.type() != tlv::NameComponent)
       {
         /// @todo May or may not throw exception later...
-        m_finalBlockId.reset();
+        m_finalBlockId = name::Component();
       }
     ++val;
   }
   else {
-    m_finalBlockId.reset();
+    m_finalBlockId = name::Component();
   }
 
   // AppMetaInfo (if any)
diff --git a/src/name-component.cpp b/src/name-component.cpp
index ac0f5f1..7941225 100644
--- a/src/name-component.cpp
+++ b/src/name-component.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -383,23 +383,29 @@
 
 ////////////////////////////////////////////////////////////////////////////////
 
+bool
+Component::equals(const Component& other) const
+{
+  return type() == other.type() &&
+         value_size() == other.value_size() &&
+         (empty() || // needed on OSX 10.9 due to STL bug
+          std::equal(value_begin(), value_end(), other.value_begin()));
+}
+
 int
 Component::compare(const Component& other) const
 {
-  // Imitate ndn_Exclude_compareComponents.
-  if (type() < other.type())
-    return -1;
-  else if (type() > other.type())
-    return 1;
-  else if (value_size() < other.value_size())
-    return -1;
-  if (value_size() > other.value_size())
-    return 1;
+  int cmpType = type() - other.type();
+  if (cmpType != 0)
+    return cmpType;
 
-  if (value_size() == 0)
+  int cmpSize = value_size() - other.value_size();
+  if (cmpSize != 0)
+    return cmpSize;
+
+  if (empty()) // needed on OSX 10.9 due to STL bug
     return 0;
 
-  // The components are equal length.  Just do a byte compare.
   return std::memcmp(value(), other.value(), value_size());
 }
 
diff --git a/src/name-component.hpp b/src/name-component.hpp
index 6338477..7b43910 100644
--- a/src/name-component.hpp
+++ b/src/name-component.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2013-2015 Regents of the University of California.
+ * Copyright (c) 2013-2016 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -494,12 +494,9 @@
   bool
   empty() const
   {
-    return !hasValue() || value_size() == 0;
+    return value_size() == 0;
   }
 
-  Component
-  getSuccessor() const;
-
   /**
    * @brief Check if this is the same component as other
    *
@@ -507,17 +504,7 @@
    * @return true if the components are equal, otherwise false.
    */
   bool
-  equals(const Component& other) const
-  {
-    if (value_size() != other.value_size())
-      return false;
-    if (value_size() == 0 /* == other.value_size()*/)
-      return true;
-
-    // somehow, behavior is wrong on OSX 10.9 when component is empty
-    // (probably some bug in STL...)
-    return std::equal(value_begin(), value_end(), other.value_begin());
-  }
+  equals(const Component& other) const;
 
   /**
    * @brief Compare this to the other Component using NDN canonical ordering
@@ -603,6 +590,9 @@
     return compare(other) > 0;
   }
 
+  Component
+  getSuccessor() const;
+
   // !!! NOTE TO IMPLEMENTOR !!!
   //
   // This class MUST NOT contain any data fields.