001 /* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2008-2011 SonarSource 004 * mailto:contact AT sonarsource DOT com 005 * 006 * Sonar is free software; you can redistribute it and/or 007 * modify it under the terms of the GNU Lesser General Public 008 * License as published by the Free Software Foundation; either 009 * version 3 of the License, or (at your option) any later version. 010 * 011 * Sonar is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 * Lesser General Public License for more details. 015 * 016 * You should have received a copy of the GNU Lesser General Public 017 * License along with Sonar; if not, write to the Free Software 018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 019 */ 020 package org.sonar.duplications.utils; 021 022 import java.util.Comparator; 023 import java.util.List; 024 025 /** 026 * Provides utility methods for sorted lists. 027 */ 028 public final class SortedListsUtils { 029 030 /** 031 * Returns true if all elements from second list also presented in first list. 032 * Both lists must be sorted. 033 * And both must implement {@link java.util.RandomAccess}, otherwise this method is inefficient in terms of performance. 034 * Running time - O(|container| + |list|). 035 */ 036 public static <T> boolean contains(List<T> container, List<T> list, Comparator<T> comparator) { 037 int j = 0; 038 for (int i = 0; i < list.size(); i++) { 039 T e1 = list.get(i); 040 boolean found = false; 041 for (; j < container.size(); j++) { 042 T e2 = container.get(j); 043 int c = comparator.compare(e1, e2); 044 if (c == 0) { 045 found = true; 046 break; 047 } else if (c < 0) { 048 // e1 is less than e2 - stop search, because all next elements e2 would be greater than e1 049 return false; 050 } 051 } 052 if (!found) { 053 return false; 054 } 055 } 056 return true; 057 } 058 059 private SortedListsUtils() { 060 } 061 062 }