001    /////////////////////////////////////////////////
002    //This file is part of Sears project.
003    //Subtitle Editor And Re-Synch
004    //A tool to easily modify and resynch movies subtitles.
005    /////////////////////////////////////////////////
006    //This program is free software; 
007    //you can redistribute it and/or modify it under the terms 
008    //of the GNU General Public License 
009    //as published by the Free Software Foundation; 
010    //either version 2 of the License, or (at your option) any later version.
011    /////////////////////////////////////////////////
012    //Sears project is available under sourceforge
013    //at adress: http://sourceforge.net/projects/sears/
014    //Copyright (C) 2005 Booba Skaya
015    //Mail: booba.skaya@gmail.com
016    /////////////////////////////////////////////////
017    
018    // some suggestions about this class: floriaen@gmail.com
019    
020    package sears.search.data;
021    
022    /**
023     * If elements added is not bigger or equals than the last one it do not correspond and it not added...
024     *
025     */
026    public class ListOfRow {
027            
028            private static final int INITIAL_CAPACITY = 10;
029            
030            // the list's size:
031            private int size;
032            private int[] list;
033            
034            /**
035             * Creates a new list with initial capacity set to default: 10
036             */
037            public ListOfRow() {
038                    this(INITIAL_CAPACITY);
039            }
040            
041            /**
042             * Creates a new empty list with capacity set to <tt>initialCapacity</tt>
043             * @param inititialCapacity     the initial capacity of the list
044             */
045            public ListOfRow(int inititialCapacity) {
046                    if( inititialCapacity <= 0 ) {
047                            inititialCapacity = INITIAL_CAPACITY;
048                    }
049                    list = new int[inititialCapacity];
050                    size = 0;
051                    
052            }
053            
054            /**
055             * Add a new item in the list
056             * Item must be positive and no have entry in the list
057             * @param indexOfOccurrence     a positive <tt>int</tt>
058             * @return                                              true if <tt>indexOfOccurencce</tt> is added in the list, false if not
059             * 
060             * @throws                                              IllegalArgumentException if <tt>indexOfOccurencce</tt> is negative
061             */
062            public boolean add(int indexOfOccurrence) {
063                    if( indexOfOccurrence < 0 ) {
064                            throw new IllegalArgumentException("negative value is not permitted");
065                    }               
066                    boolean isAdding = false;               
067                    if( ensureUnicity(indexOfOccurrence) > -1 ) {
068                            ensureCapacity(size + 1);
069                            list[size++] = indexOfOccurrence;
070                            isAdding = true;
071                    }               
072                    return isAdding;
073            }
074            
075            /**
076             * Gets the row at index given in parameter
077             * @param index the index in the list
078             * @return              the row at <code>index</code>, -1 if the list is empty
079             * @throws              IndexOutOfBoundsException if index is bigger than the list's capacity
080             */
081            public int getRow(int index) {
082                    if( index >= size ) {
083                            throw new IndexOutOfBoundsException("index is out of list's bounds");
084                    }
085                    if( index < 0 ) {
086                            index = 0;
087                    }
088                    int row = -1;
089                    if( !isEmpty() ) {
090                            row = list[index];
091                    }
092                    return row;
093            }
094            
095            /**
096             * Dichotomic search, gets the index of the row contained in the list
097             * @param row   the row to search
098             * @return              the index of the <code>row</code> or -1 if the row is not in the list
099             */
100            public int getIndexOfRow(int row) {
101                    if( row < 0 ) {
102                            throw new IllegalArgumentException("negative value is not a valid value for a row");
103                    }
104                    int middle = 0;
105                    boolean found = false;
106                    if( list != null && !isEmpty()) {
107                            int startAt = 0;
108                            int stopAt = size - 1;
109                            int result = -1;
110                            while( !found && startAt <= stopAt ) {                       
111                                    middle = (startAt + stopAt)/2;
112                                    result = list[middle];
113                                    if( result == row ) {
114                                            found = true;
115                                    } else {
116                                            if( result > row ) {
117                                                    stopAt = middle - 1;
118                                            }
119                                            else if( result < row ) {
120                                                    startAt = middle + 1;
121                                            }
122                                    }
123                            }
124                    }
125                    if( !found ) {
126                            middle = -1;
127                    }
128                    return middle;
129            }
130            
131            /**
132             * Empty the list
133             */
134            public void clear() {
135                    for( int i=0;i<list.length;i++ ) {
136                            list[i] = -1;
137                    }
138                    size = 0;
139            }
140            
141            /**
142             * Ensures the capacity of the list, extends it if needed
143             * @param minCapacity the capacity needed
144             */
145            private void ensureCapacity(int minCapacity) {
146                    int oldCapacity = list.length;
147                    if (minCapacity > oldCapacity) {
148                            int[] oldData = list;
149                            int newCapacity = (oldCapacity * 3)/2 + 1;
150                            if (newCapacity < minCapacity) newCapacity = minCapacity;
151                            list = new int[newCapacity];
152                            System.arraycopy(oldData, 0, list, 0, size);
153                    }
154            }
155            
156            /**
157             * Ensures the unicity of element in the list.
158             * <br> the next added index must be bigger than the last one (and so it's not the same)
159             * @param index         the index to add
160             * @return                      the <code>index</code> given in parameters or -1 if it is not a valid index
161             */
162            private int ensureUnicity(int index) {
163                    if( !isEmpty() ) {
164                            // ensure that index is bigger than the last added index:
165                            if( index <= list[size-1] ) {
166                                    index = -1;
167                            }
168                    }
169                    return index;
170            }
171            
172            /**
173             * Tests if the list is empty or not
174             * @return      true if the list is empty, false if not
175             */
176            public boolean isEmpty() {
177                    return size == 0;
178            }
179            
180            /**
181             * Gets the size of the list
182             * @return the size of the list
183             */
184            public int size() {
185                    return size;
186            }
187            
188            /**
189             * Returns a new <code>LoopIterator</code> object over the list
190             * @return an instance of <code>LoopIterator</code> for this list
191             * @see LoopIterator
192             */
193            public LoopIterator iterator() {
194                    return new LoopIterator(this);
195            }
196    
197            // FOR DEVELOPPERS:
198            // STATIC METHOD WITH STATISTIC VARIABLE 
199            // TO CHOOSE AN OPTIMAL INITIAL CAPACITY
200            // FOR THE LIST
201    
202            // here
203    }