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