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.ArrayList;
018    import java.util.Collection;
019    import java.util.Comparator;
020    import java.util.Iterator;
021    
022    /**
023     * @author Igor Spasic
024     */
025    public class SortedArrayList<E> extends ArrayList<E> {
026    
027            public SortedArrayList() {
028            }
029    
030            public SortedArrayList(Collection<? extends E> c) {
031                    addAll(c);
032            }
033    
034            public SortedArrayList(Comparator<E> comparator) {
035                    _comparator = comparator;
036            }
037    
038            @Override
039            public boolean add(E e) {
040                    int index = 0;
041    
042                    if (!isEmpty()) {
043                            index = _findInsertionPoint(e);
044                    }
045    
046                    super.add(index, e);
047    
048                    return true;
049            }
050    
051            @Override
052            public void add(int index, E e) {
053                    throw new UnsupportedOperationException();
054            }
055    
056            @Override
057            public boolean addAll(Collection<? extends E> c) {
058                    boolean modified = false;
059    
060                    Iterator<? extends E> itr = c.iterator();
061    
062                    while (itr.hasNext()) {
063                            if (add(itr.next()) && !modified) {
064                                    modified = true;
065                            }
066                    }
067    
068                    return modified;
069            }
070    
071            @Override
072            public boolean addAll(int index, Collection<? extends E> c) {
073                    throw new UnsupportedOperationException();
074            }
075    
076            @Override
077            public E set(int index, E e) {
078                    throw new UnsupportedOperationException();
079            }
080    
081            protected int compare(E e1, E e2) {
082                    if (_comparator == null) {
083                            Comparable<E> comparator1 = (Comparable<E>)e1;
084    
085                            return comparator1.compareTo(e2);
086                    }
087    
088                    return _comparator.compare(e1, e2);
089            }
090    
091            private int _findInsertionPoint(E e) {
092                    return _findInsertionPoint(e, 0, size() - 1);
093            }
094    
095            private int _findInsertionPoint(E e, int low, int high) {
096                    while (low <= high) {
097                            int mid = (low + high) >>> 1;
098    
099                            int delta = compare(get(mid), e);
100    
101                            if (delta > 0) {
102                                    high = mid - 1;
103                            }
104                            else {
105                                    low = mid + 1;
106                            }
107                    }
108    
109                    return low;
110            }
111    
112            private Comparator<E> _comparator;
113    
114    }