From c7ebd4c91bdbf00faed2b9935b818c781803edd1 Mon Sep 17 00:00:00 2001 From: Jim Hahn Date: Fri, 5 Apr 2019 23:32:15 -0400 Subject: 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 --- .../onap/policy/models/base/PfObjectFilter.java | 31 +++++++++++++--------- 1 file changed, 18 insertions(+), 13 deletions(-) (limited to 'models-base/src/main/java') 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> { * @return the filtered list */ public default List latestVersionFilter(final List originalList) { + if (originalList.size() <= 1) { + return originalList; + } + List filteredList = new ArrayList<>(originalList); Collections.sort(filteredList); - List 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)); } } -- cgit 1.2.3-korg