table: Allow iteration over PIT entries

Change-Id: If48d7f827ccb5df0480cfa27bd2f3db4e3f796fa
Refs: #2339
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index e4199e8..5e333aa 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -26,6 +26,10 @@
 #include "pit.hpp"
 #include <type_traits>
 
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
 namespace nfd {
 namespace pit {
 
@@ -36,6 +40,17 @@
 
 } // namespace pit
 
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Pit::const_iterator>));
+// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
+// which doesn't require DefaultConstructible
+#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
+static_assert(std::is_default_constructible<Pit::const_iterator>::value,
+              "Pit::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Pit::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
 Pit::Pit(NameTree& nameTree)
   : m_nameTree(nameTree)
   , m_nItems(0)
@@ -101,4 +116,11 @@
   --m_nItems;
 }
 
+Pit::const_iterator
+Pit::begin() const
+{
+  return const_iterator(m_nameTree.fullEnumerate(
+    [] (const name_tree::Entry& entry) { return entry.hasPitEntries(); }).begin());
+}
+
 } // namespace nfd
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index 00d90ca..3bdf44f 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -78,6 +78,62 @@
   void
   erase(shared_ptr<pit::Entry> pitEntry);
 
+public: // enumeration
+  class const_iterator;
+
+  /** \brief returns an iterator pointing to the first PIT entry
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated if PIT or another NameTree-based
+   *        table is modified
+   */
+  const_iterator
+  begin() const;
+
+  /** \brief returns an iterator referring to the past-the-end PIT entry
+   *  \note The returned iterator may get invalidated if PIT or another NameTree-based
+   *        table is modified
+   */
+  const_iterator
+  end() const;
+
+  class const_iterator : public std::iterator<std::forward_iterator_tag, const pit::Entry>
+  {
+  public:
+    const_iterator();
+
+    explicit
+    const_iterator(const NameTree::const_iterator& it);
+
+    ~const_iterator();
+
+    const pit::Entry&
+    operator*() const;
+
+    shared_ptr<pit::Entry>
+    operator->() const;
+
+    const_iterator&
+    operator++();
+
+    const_iterator
+    operator++(int);
+
+    bool
+    operator==(const const_iterator& other) const;
+
+    bool
+    operator!=(const const_iterator& other) const;
+
+  private:
+    NameTree::const_iterator m_nameTreeIterator;
+    /** \brief Index of the current visiting PIT entry in NameTree node
+     *
+     * Index is used to ensure that dereferencing of m_nameTreeIterator happens only when
+     * const_iterator is dereferenced or advanced.
+     */
+    size_t m_iPitEntry;
+  };
+
 private:
   NameTree& m_nameTree;
   size_t m_nItems;
@@ -89,6 +145,76 @@
   return m_nItems;
 }
 
+inline Pit::const_iterator
+Pit::end() const
+{
+  return const_iterator(m_nameTree.end());
+}
+
+inline
+Pit::const_iterator::const_iterator()
+  : m_iPitEntry(0)
+{
+}
+
+inline
+Pit::const_iterator::const_iterator(const NameTree::const_iterator& it)
+  : m_nameTreeIterator(it)
+  , m_iPitEntry(0)
+{
+}
+
+inline
+Pit::const_iterator::~const_iterator()
+{
+}
+
+inline Pit::const_iterator
+Pit::const_iterator::operator++(int)
+{
+  Pit::const_iterator temp(*this);
+  ++(*this);
+  return temp;
+}
+
+inline Pit::const_iterator&
+Pit::const_iterator::operator++()
+{
+  ++m_iPitEntry;
+  if (m_iPitEntry < m_nameTreeIterator->getPitEntries().size()) {
+    return *this;
+  }
+
+  ++m_nameTreeIterator;
+  m_iPitEntry = 0;
+  return *this;
+}
+
+inline const pit::Entry&
+Pit::const_iterator::operator*() const
+{
+  return *(this->operator->());
+}
+
+inline shared_ptr<pit::Entry>
+Pit::const_iterator::operator->() const
+{
+  return m_nameTreeIterator->getPitEntries().at(m_iPitEntry);
+}
+
+inline bool
+Pit::const_iterator::operator==(const Pit::const_iterator& other) const
+{
+  return m_nameTreeIterator == other.m_nameTreeIterator &&
+         m_iPitEntry == other.m_iPitEntry;
+}
+
+inline bool
+Pit::const_iterator::operator!=(const Pit::const_iterator& other) const
+{
+  return !(*this == other);
+}
+
 } // namespace nfd
 
 #endif // NFD_DAEMON_TABLE_PIT_HPP
diff --git a/tests/daemon/table/pit.cpp b/tests/daemon/table/pit.cpp
index dcf5053..cabbab9 100644
--- a/tests/daemon/table/pit.cpp
+++ b/tests/daemon/table/pit.cpp
@@ -450,6 +450,48 @@
 
 }
 
+BOOST_AUTO_TEST_CASE(Iterator)
+{
+  NameTree nameTree(16);
+  Pit pit(nameTree);
+
+  shared_ptr<Interest> interestA    = makeInterest("/A");
+  shared_ptr<Interest> interestABC1 = makeInterest("/A/B/C");
+  shared_ptr<Interest> interestABC2 = makeInterest("/A/B/C");
+  interestABC2->setSelectors(ndn::Selectors().setMinSuffixComponents(10));
+  shared_ptr<Interest> interestD    = makeInterest("/D");
+
+  BOOST_CHECK_EQUAL(pit.size(), 0);
+  BOOST_CHECK(pit.begin() == pit.end());
+
+  pit.insert(*interestABC1);
+  BOOST_CHECK_EQUAL(pit.size(), 1);
+  BOOST_CHECK(pit.begin() != pit.end());
+  BOOST_CHECK(pit.begin()->getInterest() == *interestABC1);
+  BOOST_CHECK((*pit.begin()).getInterest() == *interestABC1);
+
+  auto i = pit.begin();
+  auto j = pit.begin();
+  BOOST_CHECK(++i == pit.end());
+  BOOST_CHECK(j++ == pit.begin());
+  BOOST_CHECK(j == pit.end());
+
+  pit.insert(*interestA);
+  pit.insert(*interestABC2);
+  pit.insert(*interestD);
+
+  std::set<const Interest*> expected = {&*interestA, &*interestABC1, &*interestABC2, &*interestD};
+  std::set<const Interest*> actual;
+  for (const auto& pitEntry : pit) {
+    actual.insert(&pitEntry.getInterest());
+  }
+  BOOST_CHECK(actual == expected);
+  for (auto actualIt = actual.begin(), expectedIt = expected.begin();
+       actualIt != actual.end() && expectedIt != expected.end(); ++actualIt, ++expectedIt) {
+    BOOST_CHECK_EQUAL(**actualIt, **expectedIt);
+  }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace tests