exclude: Porting implementation Exclude filter from ndn.cxx
Change-Id: I406161bf3cf75fc0a243201da9833432fd185a90
diff --git a/Makefile.am b/Makefile.am
index 6ed2873..6966f3b 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -104,6 +104,7 @@
src/encoding/element-listener.cpp \
src/encoding/oid.cpp \
src/encoding/wire-format.cpp \
+ src/exclude.cpp \
src/face.cpp \
src/forwarding-entry.cpp \
src/interest.cpp \
diff --git a/include/ndn-cpp/exclude.hpp b/include/ndn-cpp/exclude.hpp
new file mode 100644
index 0000000..8fee29e
--- /dev/null
+++ b/include/ndn-cpp/exclude.hpp
@@ -0,0 +1,199 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_EXCLUDE_H
+#define NDN_EXCLUDE_H
+
+#include "name.hpp"
+
+#include <map>
+
+namespace ndn {
+
+namespace error {
+struct Exclude : public std::runtime_error { Exclude(const std::string &what) : std::runtime_error(what) {} };
+}
+
+/**
+ * @brief Class to represent Exclude component in NDN interests
+ */
+class Exclude
+{
+public:
+ typedef std::map< Name::Component, bool /*any*/, std::greater<Name::Component> > exclude_type;
+
+ 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 Default constructor an empty exclude
+ */
+ Exclude ();
+
+ /**
+ * @brief Check if name component is excluded
+ * @param comp Name component to check against exclude filter
+ */
+ bool
+ isExcluded (const Name::Component &comp) const;
+
+ /**
+ * @brief Exclude specific name component
+ * @param comp component to exclude
+ * @returns *this to allow chaining
+ */
+ Exclude &
+ excludeOne (const Name::Component &comp);
+
+ /**
+ * @brief Exclude components from range [from, to]
+ * @param from first element of the range
+ * @param to last element of the range
+ * @returns *this to allow chaining
+ */
+ Exclude &
+ excludeRange (const Name::Component &from, const Name::Component &to);
+
+ /**
+ * @brief Exclude all components from range [/, to]
+ * @param to last element of the range
+ * @returns *this to allow chaining
+ */
+ inline Exclude &
+ excludeBefore (const Name::Component &to);
+
+ /**
+ * @brief Exclude all components from range [from, +Inf]
+ * @param to last element of the range
+ * @returns *this to allow chaining
+ */
+ Exclude &
+ excludeAfter (const Name::Component &from);
+
+ /**
+ * @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
+ *
+ * This method is used during conversion from wire format of exclude filter
+ *
+ * If there is an error with ranges (e.g., order of components is wrong) an exception is thrown
+ */
+ void
+ appendExclude (const Name::Component &name, bool any);
+
+ /**
+ * @brief Check if exclude filter is empty
+ */
+ inline bool
+ empty () const;
+
+ /**
+ * @brief Get number of exclude terms
+ */
+ inline size_t
+ size () const;
+
+ /**
+ * @brief Get begin iterator of the exclude terms
+ */
+ inline const_iterator
+ begin () const;
+
+ /**
+ * @brief Get end iterator of the exclude terms
+ */
+ inline const_iterator
+ end () const;
+
+ /**
+ * @brief Get begin iterator of the exclude terms
+ */
+ inline const_reverse_iterator
+ rbegin () const;
+
+ /**
+ * @brief Get end iterator of the exclude terms
+ */
+ inline const_reverse_iterator
+ rend () const;
+
+ /**
+ * @brief Get escaped string representation (e.g., for use in URI) of the exclude filter
+ */
+ inline std::string
+ toUri () const;
+
+private:
+ Exclude &
+ excludeRange (iterator fromLowerBound, iterator toLowerBound);
+
+private:
+ exclude_type m_exclude;
+};
+
+std::ostream&
+operator << (std::ostream &os, const Exclude &name);
+
+inline Exclude &
+Exclude::excludeBefore (const Name::Component &to)
+{
+ return excludeRange (Name::Component (), to);
+}
+
+inline bool
+Exclude::empty () const
+{
+ return m_exclude.empty ();
+}
+
+inline size_t
+Exclude::size () const
+{
+ return m_exclude.size ();
+}
+
+inline Exclude::const_iterator
+Exclude::begin () const
+{
+ return m_exclude.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 ();
+}
+
+inline std::string
+Exclude::toUri () const
+{
+ std::ostringstream os;
+ os << *this;
+ return os.str();
+}
+
+} // ndn
+
+#endif // NDN_EXCLUDE_H
diff --git a/src/exclude.cpp b/src/exclude.cpp
new file mode 100644
index 0000000..4d65b6c
--- /dev/null
+++ b/src/exclude.cpp
@@ -0,0 +1,176 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ * Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include <ndn-cpp/exclude.hpp>
+
+namespace ndn
+{
+
+Exclude::Exclude ()
+{
+}
+
+// example: ANY /b /d ANY /f
+//
+// 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
+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;
+
+ return false;
+}
+
+Exclude &
+Exclude::excludeOne (const Name::Component &comp)
+{
+ if (!isExcluded (comp))
+ {
+ m_exclude.insert (std::make_pair (comp, false));
+ }
+ 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::excludeRange (const Name::Component &from, const Name::Component &to)
+{
+ if (from >= to)
+ {
+ throw error::Exclude ("Invalid exclude range [" +
+ from.toEscapedString() + ", " +
+ to.toEscapedString() +
+ "] (for single name exclude use Exclude::excludeOne)");
+ }
+
+ iterator newFrom = m_exclude.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)
+ {
+ // this means that the lower bound is equal to the item itself. So, just update ANY flag
+ newFrom->second = true;
+ }
+ }
+ // 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 ()
+ if (newTo == newFrom || !newTo->second)
+ {
+ std::pair<iterator, bool> toResult = m_exclude.insert (std::make_pair (to, false));
+ newTo = toResult.first;
+ ++ newTo;
+ }
+ else
+ {
+ // nothing to do really
+ }
+
+ m_exclude.erase (newTo, newFrom); // remove any intermediate node, since all of the are excluded
+
+ return *this;
+}
+
+Exclude &
+Exclude::excludeAfter (const Name::Component &from)
+{
+ iterator newFrom = m_exclude.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)
+ {
+ // this means that the lower bound is equal to the item itself. So, just update ANY flag
+ newFrom->second = true;
+ }
+ }
+ // else
+ // nothing special if start of the range already exists with ANY flag set
+
+ if (newFrom != m_exclude.begin ())
+ {
+ m_exclude.erase (m_exclude.begin (), newFrom); // remove any intermediate node, since all of the are excluded
+ }
+
+ return *this;
+}
+
+
+std::ostream&
+operator << (std::ostream &os, const Exclude &exclude)
+{
+ bool empty = true;
+ for (Exclude::const_reverse_iterator i = exclude.rbegin (); i != exclude.rend (); i++)
+ {
+ if (!i->first.empty())
+ {
+ if (!empty) os << ",";
+ os << i->first.toEscapedString ();
+ empty = false;
+ }
+ if (i->second)
+ {
+ if (!empty) os << ",";
+ os << "*";
+ empty = false;
+ }
+ }
+ return os;
+}
+
+
+} // ndn