From c7ebd4c91bdbf00faed2b9935b818c781803edd1 Mon Sep 17 00:00:00 2001
From: Jim Hahn <jrh3@att.com>
Date: Fri, 5 Apr 2019 23:32:15 -0400
Subject: [PATCH] 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>
---
 .../onap/policy/models/base/PfObjectFilter.java    | 31 +++++++++++++---------
 1 file 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));
     }
 }
-- 
2.16.6