001    /*--------------------------------------------------------------------------+
002    $Id: PairList.java 28497 2010-06-22 09:27:40Z deissenb $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.collections;
019    
020    import java.util.ArrayList;
021    import java.util.List;
022    
023    import edu.tum.cs.commons.assertion.CCSMPre;
024    
025    /**
026     * A list for storing pairs in a specific order.
027     * 
028     * @author hummelb
029     * @author $Author: deissenb $
030     * @version $Rev: 28497 $
031     * @levd.rating GREEN Hash: 5510B017A5CFB62174A38A897F2160AD
032     */
033    public class PairList<S, T> {
034    
035            /** The current size. */
036            private int size = 0;
037    
038            /** The array used for storing the S. */
039            private Object[] firstElements;
040    
041            /** The array used for storing the T. */
042            private Object[] secondElements;
043    
044            /** Constructor. */
045            public PairList() {
046                    this(16);
047            }
048    
049            /** Constructor. */
050            public PairList(int initialCapacity) {
051                    firstElements = new Object[initialCapacity];
052                    secondElements = new Object[initialCapacity];
053            }
054    
055            /** Copy constructor. */
056            public PairList(PairList<S, T> other) {
057                    this(other.size);
058                    addAll(other);
059            }
060    
061            /** Returns whether the list is empty. */
062            public boolean isEmpty() {
063                    return size == 0;
064            }
065    
066            /** Returns the size of the list. */
067            public int size() {
068                    return size;
069            }
070    
071            /** Add the given pair to the list. */
072            public void add(S first, T second) {
073                    ensureSpace(size + 1);
074                    firstElements[size] = first;
075                    secondElements[size] = second;
076                    ++size;
077            }
078    
079            /** Adds all pairs from another list. */
080            public void addAll(PairList<S, T> other) {
081                    // we have to store this in a local var, as other.size may change if
082                    // other == this
083                    int otherSize = other.size;
084    
085                    ensureSpace(size + otherSize);
086                    for (int i = 0; i < otherSize; ++i) {
087                            firstElements[size] = other.firstElements[i];
088                            secondElements[size] = other.secondElements[i];
089                            ++size;
090                    }
091            }
092    
093            /** Make sure there is space for at least the given amount of elements. */
094            protected void ensureSpace(int space) {
095                    if (space <= firstElements.length) {
096                            return;
097                    }
098    
099                    Object[] oldFirst = firstElements;
100                    Object[] oldSecond = secondElements;
101                    int newSize = firstElements.length * 2;
102                    while (newSize < space) {
103                            newSize *= 2;
104                    }
105    
106                    firstElements = new Object[newSize];
107                    secondElements = new Object[newSize];
108                    System.arraycopy(oldFirst, 0, firstElements, 0, size);
109                    System.arraycopy(oldSecond, 0, secondElements, 0, size);
110            }
111    
112            /** Returns the first element at given index. */
113            @SuppressWarnings("unchecked")
114            public S getFirst(int i) {
115                    checkWithinBounds(i);
116                    return (S) firstElements[i];
117            }
118    
119            /**
120             * Checks whether the given <code>i</code> is within the bounds. Throws an
121             * exception otherwise.
122             */
123            private void checkWithinBounds(int i) {
124                    if (i < 0 || i >= size) {
125                            throw new IndexOutOfBoundsException("Out of bounds: " + i);
126                    }
127            }
128    
129            /** Sets the first element at given index. */
130            public void setFirst(int i, S value) {
131                    checkWithinBounds(i);
132                    firstElements[i] = value;
133            }
134    
135            /** Returns the second element at given index. */
136            @SuppressWarnings("unchecked")
137            public T getSecond(int i) {
138                    checkWithinBounds(i);
139                    return (T) secondElements[i];
140            }
141    
142            /** Sets the first element at given index. */
143            public void setSecond(int i, T value) {
144                    checkWithinBounds(i);
145                    secondElements[i] = value;
146            }
147    
148            /** Creates a new list containing all first elements. */
149            @SuppressWarnings("unchecked")
150            public List<S> extractFirstList() {
151                    List<S> result = new ArrayList<S>(size + 1);
152                    for (int i = 0; i < size; ++i) {
153                            result.add((S) firstElements[i]);
154                    }
155                    return result;
156            }
157    
158            /** Creates a new list containing all second elements. */
159            @SuppressWarnings("unchecked")
160            public List<T> extractSecondList() {
161                    List<T> result = new ArrayList<T>(size + 1);
162                    for (int i = 0; i < size; ++i) {
163                            result.add((T) secondElements[i]);
164                    }
165                    return result;
166            }
167    
168            /**
169             * Swaps the pairs of this list. Is S and T are different types, this will
170             * be extremely dangerous.
171             */
172            public void swapPairs() {
173                    Object[] temp = firstElements;
174                    firstElements = secondElements;
175                    secondElements = temp;
176            }
177    
178            /** Clears this list. */
179            public void clear() {
180                    size = 0;
181            }
182    
183            /** Removes the last element of the list. */
184            public void removeLast() {
185                    CCSMPre.isTrue(size > 0, "Size must be positive!");
186                    size -= 1;
187            }
188    }