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 */
020package org.sonar.duplications.utils;
021
022import java.util.Comparator;
023import java.util.Iterator;
024import java.util.List;
025
026/**
027 * Provides utility methods for sorted lists.
028 */
029public 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}