summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJim Hahn <jrh3@att.com>2019-04-05 23:32:15 -0400
committerJim Hahn <jrh3@att.com>2019-04-06 08:00:39 -0400
commitc7ebd4c91bdbf00faed2b9935b818c781803edd1 (patch)
tree0f590656ac46ea5d7a8fe1aa225f4a0d35e1e147
parent52229882d7ee3e934641de0bd2df74ed1268130e (diff)
Guaranteed linear-time latestVersion()
This is a proposed revision of the latestVersion() method that's guaranteed to be linear time. Still makes use of the slick idea of sorting the list so that items with the same name are adjacent and in order by version. Revised to use an array list, which is more like the original code. Change-Id: If047d4d9630c426c6335f52cb7e5bdda7b6cc0a9 Issue-ID: POLICY-1542 Signed-off-by: Jim Hahn <jrh3@att.com>
-rw-r--r--models-base/src/main/java/org/onap/policy/models/base/PfObjectFilter.java31
1 files changed, 18 insertions, 13 deletions
diff --git a/models-base/src/main/java/org/onap/policy/models/base/PfObjectFilter.java b/models-base/src/main/java/org/onap/policy/models/base/PfObjectFilter.java
index 0fca00d39..a7d8401f0 100644
--- a/models-base/src/main/java/org/onap/policy/models/base/PfObjectFilter.java
+++ b/models-base/src/main/java/org/onap/policy/models/base/PfObjectFilter.java
@@ -59,26 +59,31 @@ public interface PfObjectFilter<T extends Comparable<T>> {
* @return the filtered list
*/
public default List<T> latestVersionFilter(final List<T> originalList) {
+ if (originalList.size() <= 1) {
+ return originalList;
+ }
+
List<T> filteredList = new ArrayList<>(originalList);
Collections.sort(filteredList);
- List<T> filteredOutList = new ArrayList<>();
-
- for (int i = 1; i < filteredList.size(); i++) {
+ int icur = 0;
+ for (int j = 1; j < filteredList.size(); j++) {
// Get the current and last element
- T thisElement = filteredList.get(i);
- T lastElement = filteredList.get(i - 1);
+ T curElement = filteredList.get(icur);
+ T lastElement = filteredList.get(j);
- // The list is sorted so if the last element name is the same as the current element name, the last element
- // should be removed
- if (((PfNameVersion)thisElement).getName().equals(((PfNameVersion)lastElement).getName())) {
- filteredOutList.add(lastElement);
+ /*
+ * The list is sorted so if the last element name is the same as the current
+ * element name, the current element should be removed.
+ */
+ if (!((PfNameVersion)curElement).getName().equals(((PfNameVersion)lastElement).getName())) {
+ // have a new name - done comparing with the old "current"
+ ++icur;
}
- }
- // We can now remove these elements
- filteredList.removeAll(filteredOutList);
+ filteredList.set(icur, lastElement);
+ }
- return filteredList;
+ return new ArrayList<>(filteredList.subList(0, icur + 1));
}
}