001    /**
002     * Copyright (c) 2000-2013 Liferay, Inc. All rights reserved.
003     *
004     * This library is free software; you can redistribute it and/or modify it under
005     * the terms of the GNU Lesser General Public License as published by the Free
006     * Software Foundation; either version 2.1 of the License, or (at your option)
007     * any later version.
008     *
009     * This library is distributed in the hope that it will be useful, but WITHOUT
010     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
011     * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
012     * details.
013     */
014    
015    package com.liferay.portal.kernel.util;
016    
017    import java.util.Comparator;
018    import java.util.List;
019    
020    /**
021     * @author Igor Spasic
022     */
023    public abstract class BinarySearch<E> {
024    
025            public static <T extends Comparable<T>> BinarySearch<T> forList(
026                    final List<T> list) {
027    
028                    return new BinarySearch<T>() {
029    
030                            @Override
031                            protected int compare(int index, T e) {
032                                    return list.get(index).compareTo(e);
033                            }
034    
035                            @Override
036                            protected int getLastIndex() {
037                                    return list.size() - 1;
038                            }
039    
040                    };
041            }
042    
043            public static <T> BinarySearch<T> forList(
044                    final List<T> list, final Comparator<T> comparator) {
045    
046                    return new BinarySearch<T>() {
047    
048                            @Override
049                            protected int compare(int index, T e) {
050                                    return comparator.compare(list.get(index), e);
051                            }
052    
053                            @Override
054                            protected int getLastIndex() {
055                                    return list.size() - 1;
056                            }
057    
058                    };
059            }
060    
061            public int find(E e) {
062                    return find(e, 0, getLastIndex());
063            }
064    
065            public int find(E e, int low) {
066                    return find(e, low, getLastIndex());
067            }
068    
069            public int find(E e, int low, int high) {
070                    while (low <= high) {
071                            int mid = (low + high) >>> 1;
072    
073                            int delta = compare(mid, e);
074    
075                            if (delta < 0) {
076                                    low = mid + 1;
077                            }
078                            else if (delta > 0) {
079                                    high = mid - 1;
080                            }
081                            else {
082                                    return mid;
083                            }
084                    }
085    
086                    return -(low + 1);
087            }
088    
089            public int findFirst(E e) {
090                    return findFirst(e, 0, getLastIndex());
091            }
092    
093            public int findFirst(E e, int low) {
094                    return findFirst(e, low, getLastIndex());
095            }
096    
097            public int findFirst(E e, int low, int high) {
098                    int index = -1;
099    
100                    while (low <= high) {
101                            int mid = (low + high) >>> 1;
102    
103                            int delta = compare(mid, e);
104    
105                            if (delta < 0) {
106                                    low = mid + 1;
107                            }
108                            else {
109                                    if (delta == 0) {
110                                            index = mid;
111                                    }
112    
113                                    high = mid - 1;
114                            }
115                    }
116    
117                    if (index == -1) {
118                            return -(low + 1);
119                    }
120    
121                    return index;
122            }
123    
124            public int findLast(E e) {
125                    return findLast(e, 0, getLastIndex());
126            }
127    
128            public int findLast(E e, int low) {
129                    return findLast(e, low, getLastIndex());
130            }
131    
132            public int findLast(E e, int low, int high) {
133                    int index = -1;
134    
135                    while (low <= high) {
136                            int mid = (low + high) >>> 1;
137    
138                            int delta = compare(mid, e);
139    
140                            if (delta > 0) {
141                                    high = mid - 1;
142                            }
143                            else {
144                                    if (delta == 0) {
145                                            index = mid;
146                                    }
147    
148                                    low = mid + 1;
149                            }
150                    }
151    
152                    if (index == -1) {
153                            return -(low + 1);
154                    }
155    
156                    return index;
157            }
158    
159            protected abstract int compare(int index, E element);
160    
161            protected abstract int getLastIndex();
162    
163    }