Java Tutorial/Collections/Collections Search

A binary search implementation.

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 * 
 * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
 * 
 * The contents of this file are subject to the terms of either the GNU
 * General Public License Version 2 only ("GPL") or the Common Development
 * and Distribution License("CDDL") (collectively, the "License").  You
 * may not use this file except in compliance with the License. You can obtain
 * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
 * or glassfish/bootstrap/legal/LICENSE.txt.  See the License for the specific
 * language governing permissions and limitations under the License.
 * 
 * When distributing the software, include this License Header Notice in each
 * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
 * Sun designates this particular file as subject to the "Classpath" exception
 * as provided by Sun in the GPL Version 2 section of the License file that
 * accompanied this code.  If applicable, add the following below the License
 * Header, with the fields enclosed by brackets [] replaced by your own
 * identifying information: "Portions Copyrighted [year]
 * [name of copyright owner]"
 * 
 * Contributor(s):
 * 
 * If you wish your version of this file to be governed by only the CDDL or
 * only the GPL Version 2, indicate your decision by adding "[Contributor]
 * elects to include this software in this distribution under the [CDDL or GPL
 * Version 2] license."  If you don"t indicate a single choice of license, a
 * recipient has the option to distribute your version of this file under
 * either the CDDL, the GPL Version 2 or to extend the choice of license to
 * its licensees as provided above.  However, if you add GPL Version 2 code
 * and therefore, elected the GPL Version 2 license, then the option applies
 * only if the new code is made subject to such option by the copyright
 * holder.
 */
// ----------------------------------------------------------------------------
/**
 * A binary search implementation.
 */
public class BinarySearch {
  public int find(final int[] data, final int key) {
    int low = 0, high = data.length - 1;
    while (low <= high) {
      final int i = (low + high) >> 1;
      final int v = data[i];
      if (v == key)
        return i; // this line does not get covered unless there is a match
      else if (v < key)
        low = i + 1;
      else
        // v > key
        high = i - 1;
    }
    return -1;
  }
}

Binary Searching

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class MainClass {
  public static void main(String args[]) {
    String str[] = { "B", "H", "L", "M", "I", "N", "R" };
    // Convert to list
    List list = new ArrayList(Arrays.asList(str));
    // Ensure list sorted
    Collections.sort(list);
    System.out.println("Sorted list: [length: " + list.size() + "]");
    System.out.println(list);
    // Search for element in list
    int index = Collections.binarySearch(list, "M");
    System.out.println("Found M @ " + index);
    // Search for element not in list
    index = Collections.binarySearch(list, "J");
    System.out.println("Didn"t find J @ " + index);
    // Insert
    int newIndex = -index - 1;
    list.add(newIndex, "J");
    System.out.println("With J added: [length: " + list.size() + "]");
    System.out.println(list);
  }
}

Sorted list: [length: 7]
[B, H, I, L, M, N, R]
Found M @ 4
Didn"t find J @ -4
With J added: [length: 8]
[B, H, I, J, L, M, N, R]

Binary search routines

/*
 * Copyright (c) 1998-2002 Carnegie Mellon University.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS"" AND
 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/**
 * Binary search routines.
 */
public abstract class BinarySearch {

    /**
     * Search a sorted array of integers.
     * @param array Array of integers
     * @param offset Starting offset of subarray to search
     * @param length Length of subarray to search
     * @param x Value to search for
     * @return largest index i in subarray (offset <= i <= offset+length)
     * such that all elements below i in the subarray are strictly less
     * than x.  If x is found in the subarray, then array[i] == x (and i is
     * the first occurence of x in the subarray).  If x is not found, 
     * then array[i] is where x should be inserted in the sort order.
     */
    public static int search (int[] array, int offset, int length, int x) {
        // handle 0-length subarray case right away
        if (length <= 0)
            return offset;
        int low = offset;
        int high = offset+length-1;
        // since length > 0, array[low] and array[high] are valid indices
        if (x <= array[low])
            return low;
        if (x > array[high])
            return high+1;
        
        while (low+1 < high) {
            // loop invariant: array[low] < x <= array[high],
            //                 offset <= low < high < offset+length
            int mid = (low + high)/2;
            if (x <= array[mid])
                high = mid;
            else
                low = mid;
        }
        // now we have array[low] < x <= array[high]
        //             && (low+1 == high || low == high)
        //  implies low+1 == high
        //debug.assertion (low+1 == high);
        return high;
    }
}

Check whether the given Collection contains the given element instance.

import java.util.Arrays;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Properties;
/*
 * Copyright 2002-2007 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * Miscellaneous collection utility methods.
 * Mainly for internal use within the framework.
 *
 * @author Juergen Hoeller
 * @author Rob Harrop
 * @since 1.1.3
 */
abstract class CollectionUtils {

  /**
   * Check whether the given Collection contains the given element instance.
   * Enforces the given instance to be present, rather than returning
   * <code>true</code> for an equal element as well.
   * @param collection the Collection to check
   * @param element the element to look for
   * @return <code>true</code> if found, <code>false</code> else
   */
  public static boolean containsInstance(Collection collection, Object element) {
    if (collection != null) {
      for (Iterator it = collection.iterator(); it.hasNext();) {
        Object candidate = it.next();
        if (candidate == element) {
          return true;
        }
      }
    }
    return false;
  }
  /**
   * Return <code>true</code> if the supplied Collection is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param collection the Collection to check
   * @return whether the given Collection is empty
   */
  public static boolean isEmpty(Collection collection) {
    return (collection == null || collection.isEmpty());
  }
  /**
   * Return <code>true</code> if the supplied Map is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param map the Map to check
   * @return whether the given Map is empty
   */
  public static boolean isEmpty(Map map) {
    return (map == null || map.isEmpty());
  }


  /**
   * Return <code>true</code> if any element in "<code>candidates</code>" is
   * contained in "<code>source</code>"; otherwise returns <code>false</code>.
   * @param source the source Collection
   * @param candidates the candidates to search for
   * @return whether any of the candidates has been found
   */
  public static boolean containsAny(Collection source, Collection candidates) {
    if (isEmpty(source) || isEmpty(candidates)) {
      return false;
    }
    for (Iterator it = candidates.iterator(); it.hasNext();) {
      if (source.contains(it.next())) {
        return true;
      }
    }
    return false;
  }
  /**
   * Return the first element in "<code>candidates</code>" that is contained in
   * "<code>source</code>". If no element in "<code>candidates</code>" is present in
   * "<code>source</code>" returns <code>null</code>. Iteration order is
   * {@link Collection} implementation specific.
   * @param source the source Collection
   * @param candidates the candidates to search for
   * @return the first present object, or <code>null</code> if not found
   */
  public static Object findFirstMatch(Collection source, Collection candidates) {
    if (isEmpty(source) || isEmpty(candidates)) {
      return null;
    }
    for (Iterator it = candidates.iterator(); it.hasNext();) {
      Object candidate = it.next();
      if (source.contains(candidate)) {
        return candidate;
      }
    }
    return null;
  }
  /**
   * Find a value of the given type in the given Collection.
   * @param collection the Collection to search
   * @param type the type to look for
   * @return a value of the given type found, or <code>null</code> if none
   * @throws IllegalArgumentException if more than one value of the given type found
   */
  public static Object findValueOfType(Collection collection, Class type) throws IllegalArgumentException {
    if (isEmpty(collection)) {
      return null;
    }
    Class typeToUse = (type != null ? type : Object.class);
    Object value = null;
    for (Iterator it = collection.iterator(); it.hasNext();) {
      Object obj = it.next();
      if (typeToUse.isInstance(obj)) {
        if (value != null) {
          throw new IllegalArgumentException("More than one value of type [" + typeToUse.getName() + "] found");
        }
        value = obj;
      }
    }
    return value;
  }
  /**
   * Determine whether the given Collection only contains a single unique object.
   * @param collection the Collection to check
   * @return <code>true</code> if the collection contains a single reference or
   * multiple references to the same instance, <code>false</code> else
   */
  public static boolean hasUniqueObject(Collection collection) {
    if (isEmpty(collection)) {
      return false;
    }
    boolean hasCandidate = false;
    Object candidate = null;
    for (Iterator it = collection.iterator(); it.hasNext();) {
      Object elem = it.next();
      if (!hasCandidate) {
        hasCandidate = true;
        candidate = elem;
      }
      else if (candidate != elem) {
        return false;
      }
    }
    return true;
  }
}

Find a value of the given type in the given Collection

import java.util.Arrays;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Properties;
/*
 * Copyright 2002-2007 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * Miscellaneous collection utility methods.
 * Mainly for internal use within the framework.
 *
 * @author Juergen Hoeller
 * @author Rob Harrop
 * @since 1.1.3
 */
abstract class CollectionUtils {

  /**
   * Find a value of the given type in the given Collection.
   * @param collection the Collection to search
   * @param type the type to look for
   * @return a value of the given type found, or <code>null</code> if none
   * @throws IllegalArgumentException if more than one value of the given type found
   */
  public static Object findValueOfType(Collection collection, Class type) throws IllegalArgumentException {
    if (isEmpty(collection)) {
      return null;
    }
    Class typeToUse = (type != null ? type : Object.class);
    Object value = null;
    for (Iterator it = collection.iterator(); it.hasNext();) {
      Object obj = it.next();
      if (typeToUse.isInstance(obj)) {
        if (value != null) {
          throw new IllegalArgumentException("More than one value of type [" + typeToUse.getName() + "] found");
        }
        value = obj;
      }
    }
    return value;
  }
  /**
   * Return <code>true</code> if the supplied Collection is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param collection the Collection to check
   * @return whether the given Collection is empty
   */
  public static boolean isEmpty(Collection collection) {
    return (collection == null || collection.isEmpty());
  }
  /**
   * Return <code>true</code> if the supplied Map is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param map the Map to check
   * @return whether the given Map is empty
   */
  public static boolean isEmpty(Map map) {
    return (map == null || map.isEmpty());
  }

  /**
   * Return the first element in "<code>candidates</code>" that is contained in
   * "<code>source</code>". If no element in "<code>candidates</code>" is present in
   * "<code>source</code>" returns <code>null</code>. Iteration order is
   * {@link Collection} implementation specific.
   * @param source the source Collection
   * @param candidates the candidates to search for
   * @return the first present object, or <code>null</code> if not found
   */
  public static Object findFirstMatch(Collection source, Collection candidates) {
    if (isEmpty(source) || isEmpty(candidates)) {
      return null;
    }
    for (Iterator it = candidates.iterator(); it.hasNext();) {
      Object candidate = it.next();
      if (source.contains(candidate)) {
        return candidate;
      }
    }
    return null;
  }

  /**
   * Determine whether the given Collection only contains a single unique object.
   * @param collection the Collection to check
   * @return <code>true</code> if the collection contains a single reference or
   * multiple references to the same instance, <code>false</code> else
   */
  public static boolean hasUniqueObject(Collection collection) {
    if (isEmpty(collection)) {
      return false;
    }
    boolean hasCandidate = false;
    Object candidate = null;
    for (Iterator it = collection.iterator(); it.hasNext();) {
      Object elem = it.next();
      if (!hasCandidate) {
        hasCandidate = true;
        candidate = elem;
      }
      else if (candidate != elem) {
        return false;
      }
    }
    return true;
  }
}

Get the difference of two collections

import java.util.ArrayList;
import java.util.Collection;


public class Utils {
  public static <T> Collection<T> diff(Collection<T> c1, Collection<T> c2) {
    if (c1 == null || c1.size() == 0 || c2 == null || c2.size() == 0) {
        return c1;
    }
    Collection<T> difference = new ArrayList<T>();
    for (T item : c1) {
        if (!c2.contains(item)) {
            difference.add(item);
        }
    }
    return difference;
}

}

Return the first element in "candidates" that is contained in source

import java.util.Arrays;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Properties;
/*
 * Copyright 2002-2007 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * Miscellaneous collection utility methods.
 * Mainly for internal use within the framework.
 *
 * @author Juergen Hoeller
 * @author Rob Harrop
 * @since 1.1.3
 */
abstract class CollectionUtils {

  /**
   * Return the first element in "<code>candidates</code>" that is contained in
   * "<code>source</code>". If no element in "<code>candidates</code>" is present in
   * "<code>source</code>" returns <code>null</code>. Iteration order is
   * {@link Collection} implementation specific.
   * @param source the source Collection
   * @param candidates the candidates to search for
   * @return the first present object, or <code>null</code> if not found
   */
  public static Object findFirstMatch(Collection source, Collection candidates) {
    if (isEmpty(source) || isEmpty(candidates)) {
      return null;
    }
    for (Iterator it = candidates.iterator(); it.hasNext();) {
      Object candidate = it.next();
      if (source.contains(candidate)) {
        return candidate;
      }
    }
    return null;
  }
  /**
   * Return <code>true</code> if the supplied Collection is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param collection the Collection to check
   * @return whether the given Collection is empty
   */
  public static boolean isEmpty(Collection collection) {
    return (collection == null || collection.isEmpty());
  }
  /**
   * Return <code>true</code> if the supplied Map is <code>null</code>
   * or empty. Otherwise, return <code>false</code>.
   * @param map the Map to check
   * @return whether the given Map is empty
   */
  public static boolean isEmpty(Map map) {
    return (map == null || map.isEmpty());
  }
}