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    }