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    }