name: partial Name comparison
refs #2090
Change-Id: I8de11b7064a2da894f9ddb4b4b1623a7b6d5c0ae
diff --git a/src/name.cpp b/src/name.cpp
index f9d91db..afcfb18 100644
--- a/src/name.cpp
+++ b/src/name.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2015 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -41,6 +41,8 @@
static_assert(std::is_base_of<tlv::Error, Name::Error>::value,
"Name::Error must inherit from tlv::Error");
+const size_t Name::npos = std::numeric_limits<size_t>::max();
+
template<bool T>
size_t
Name::wireEncode(EncodingImpl<T>& encoder) const
@@ -244,19 +246,11 @@
{
Name result;
- size_t iEnd = iStartComponent + nComponents;
- for (size_t i = iStartComponent; i < iEnd && i < size(); ++i)
- result.append(at(i));
+ size_t iEnd = this->size();
+ if (nComponents != npos)
+ iEnd = std::min(this->size(), iStartComponent + nComponents);
- return result;
-}
-
-Name
-Name::getSubName(size_t iStartComponent) const
-{
- Name result;
-
- for (size_t i = iStartComponent; i < size(); ++i)
+ for (size_t i = iStartComponent; i < iEnd; ++i)
result.append(at(i));
return result;
@@ -305,27 +299,21 @@
return true;
}
-
int
-Name::compare(const Name& other) const
+Name::compare(size_t pos1, size_t count1, const Name& other, size_t pos2, size_t count2) const
{
- for (size_t i = 0; i < size() && i < other.size(); ++i) {
- int comparison = at(i).compare(other.at(i));
- if (comparison == 0)
- // The components at this index are equal, so check the next components.
- continue;
+ count1 = std::min(count1, this->size() - pos1);
+ count2 = std::min(count2, other.size() - pos2);
+ size_t count = std::min(count1, count2);
- // Otherwise, the result is based on the components at this index.
- return comparison;
+ for (size_t i = 0; i < count; ++i) {
+ int comp = this->at(pos1 + i).compare(other.at(pos2 + i));
+ if (comp != 0) { // i-th component differs
+ return comp;
+ }
}
-
- // The components up to min(this.size(), other.size()) are equal, so the shorter name is less.
- if (size() < other.size())
- return -1;
- else if (size() > other.size())
- return 1;
- else
- return 0;
+ // [pos1, pos1+count) of this Name equals [pos2, pos2+count) of other Name
+ return (count1 > count2) - (count1 < count2); // signum(count1 - count2)
}
std::ostream&
diff --git a/src/name.hpp b/src/name.hpp
index 9743a96..a9716e9 100644
--- a/src/name.hpp
+++ b/src/name.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2015 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -223,20 +223,11 @@
* Get a new name, constructed as a subset of components.
* @param iStartComponent The index if the first component to get.
* @param nComponents The number of components starting at iStartComponent.
+ * Use npos to get the sub Name until the end of this Name.
* @return A new name.
*/
Name
- getSubName(size_t iStartComponent, size_t nComponents) const;
-
- /**
- * @brief Get a new name, constructed as a subset of components starting at
- * iStartComponent until the end of the name.
- *
- * @param iStartComponent The index if the first component to get.
- * @return A new name.
- */
- Name
- getSubName(size_t iStartComponent) const;
+ getSubName(size_t iStartComponent, size_t nComponents = npos) const;
/**
* @brief Return a new Name with the first nComponents components of this Name.
@@ -460,14 +451,28 @@
* std::sort gives: /a/b/d /a/b/cc /c /c/a /bb . This is intuitive because all names with
* the prefix /a are next to each other. But it may be also be counter-intuitive because
* /c comes before /bb according to NDN canonical ordering since it is shorter. @param
- * other The other Name to compare with. @return 0 If they compare equal, -1 if *this
- * comes before other in the canonical ordering, or 1 if *this comes after other in the
- * canonical ordering.
+ * other The other Name to compare with.
+ *
+ * @retval 0 if they compare equal
+ * @retval -1 if *this comes before other in the canonical ordering
+ * @retval 1 if *this comes after other in the canonical ordering
*
* @see http://named-data.net/doc/ndn-tlv/name.html#canonical-order
*/
int
- compare(const Name& other) const;
+ compare(const Name& other) const
+ {
+ return this->compare(0, npos, other);
+ }
+
+ /** \brief compares [pos1, pos1+count1) components in this Name
+ * to [pos2, pos2+count2) components in \p other
+ *
+ * This is equivalent to this->getSubName(pos1, count1).compare(other.getSubName(pos2, count2));
+ */
+ int
+ compare(size_t pos1, size_t count1,
+ const Name& other, size_t pos2 = 0, size_t count2 = npos) const;
/**
* Append the component
@@ -591,6 +596,11 @@
return const_reverse_iterator(begin());
}
+public:
+ /** \brief indicates "until the end" in getSubName and compare
+ */
+ static const size_t npos;
+
private:
mutable Block m_nameBlock;
};
diff --git a/tests/unit-tests/test-name.cpp b/tests/unit-tests/test-name.cpp
index 8c86d79..54ceb54 100644
--- a/tests/unit-tests/test-name.cpp
+++ b/tests/unit-tests/test-name.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2013-2014 Regents of the University of California.
+ * Copyright (c) 2013-2015 Regents of the University of California.
*
* This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
*
@@ -374,6 +374,54 @@
BOOST_CHECK_NE(n.get(0), n2.get(1));
}
+BOOST_AUTO_TEST_CASE(Compare)
+{
+ BOOST_CHECK_EQUAL( 0, Name("/A") .compare(Name("/A")));
+ BOOST_CHECK_EQUAL( 0, Name("/A") .compare(Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/A") .compare(Name("/B")));
+ BOOST_CHECK_EQUAL( 1, Name("/B") .compare(Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/A") .compare(Name("/AA")));
+ BOOST_CHECK_EQUAL( 1, Name("/AA") .compare(Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/A") .compare(Name("/A/C")));
+ BOOST_CHECK_EQUAL( 1, Name("/A/C").compare(Name("/A")));
+
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/A")));
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/B")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/B/Y") .compare(1, 1, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/AA")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/AA/Y") .compare(1, 1, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/A/C")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/A/C/Y").compare(1, 2, Name("/A")));
+
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A") .compare(1, Name::npos, Name("/A")));
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A") .compare(1, Name::npos, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A") .compare(1, Name::npos, Name("/B")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/B") .compare(1, Name::npos, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A") .compare(1, Name::npos, Name("/AA")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/AA") .compare(1, Name::npos, Name("/A")));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A") .compare(1, Name::npos, Name("/A/C")));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/A/C").compare(1, Name::npos, Name("/A")));
+
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/X/A/W"), 1, 1));
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/X/A/W"), 1, 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/B/W"), 1, 1));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/B/Y") .compare(1, 1, Name("/X/A/W"), 1, 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/AA/W"), 1, 1));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/AA/Y") .compare(1, 1, Name("/X/A/W"), 1, 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/A/C/W"), 1, 2));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/A/C/Y").compare(1, 2, Name("/X/A/W"), 1, 1));
+
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/X/A"), 1));
+ BOOST_CHECK_EQUAL( 0, Name("/Z/A/Y") .compare(1, 1, Name("/X/A"), 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/B"), 1));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/B/Y") .compare(1, 1, Name("/X/A"), 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/AA"), 1));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/AA/Y") .compare(1, 1, Name("/X/A"), 1));
+ BOOST_CHECK_EQUAL(-1, Name("/Z/A/Y") .compare(1, 1, Name("/X/A/C"), 1));
+ BOOST_CHECK_EQUAL( 1, Name("/Z/A/C/Y").compare(1, 2, Name("/X/A"), 1));
+}
+
BOOST_AUTO_TEST_SUITE_END()
} // namespace ndn