001 /* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2008-2012 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.Iterator; 024 import java.util.List; 025 026 /** 027 * Provides utility methods for sorted lists. 028 */ 029 public final class SortedListsUtils { 030 031 /** 032 * Returns true if {@code container} contains all elements from {@code list}. 033 * Both lists must be sorted in consistency with {@code comparator}, 034 * that is for any two sequential elements x and y: 035 * {@code (comparator.compare(x, y) <= 0) && (comparator.compare(y, x) >= 0)}. 036 * Running time - O(|container| + |list|). 037 */ 038 public static <T> boolean contains(List<T> container, List<T> list, Comparator<T> comparator) { 039 Iterator<T> listIterator = list.iterator(); 040 Iterator<T> containerIterator = container.iterator(); 041 T listElement = listIterator.next(); 042 T containerElement = containerIterator.next(); 043 while (true) { 044 int r = comparator.compare(containerElement, listElement); 045 if (r == 0) { 046 // current element from list is equal to current element from container 047 if (!listIterator.hasNext()) { 048 // no elements remaining in list - all were matched 049 return true; 050 } 051 // next element from list also can be equal to current element from container 052 listElement = listIterator.next(); 053 } else if (r < 0) { 054 // current element from list is greater than current element from container 055 // need to check next element from container 056 if (!containerIterator.hasNext()) { 057 return false; 058 } 059 containerElement = containerIterator.next(); 060 } else { 061 // current element from list is less than current element from container 062 // stop search, because current element from list would be less than any next element from container 063 return false; 064 } 065 } 066 } 067 068 private SortedListsUtils() { 069 } 070 071 }