001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2006-2013 Pentaho 008// All Rights Reserved. 009*/ 010package mondrian.util; 011 012import java.util.*; 013 014/** 015 * List backed by a collection of sub-lists. 016 * 017 * @author Luis F. Canals 018 * @since december, 2007 019 */ 020public class ConcatenableList<T> extends AbstractList<T> { 021 private static int nextHashCode = 1000; 022 023 // The backing collection of sublists 024 private final List<List<T>> lists; 025 026 // List containing all elements from backing lists, populated only after 027 // consolidate() 028 private List<T> plainList; 029 private final int hashCode = nextHashCode++; 030 private Iterator<T> getIterator = null; 031 private int previousIndex = -200; 032 private T previousElement = null; 033 private T prePreviousElement = null; 034 035 /** 036 * Creates an empty ConcatenableList. 037 */ 038 public ConcatenableList() { 039 this.lists = new ArrayList<List<T>>(); 040 this.plainList = null; 041 } 042 043 public <T2> T2[] toArray(T2[] a) { 044 consolidate(); 045 //noinspection unchecked,SuspiciousToArrayCall 046 return (T2[]) plainList.toArray((Object []) a); 047 } 048 049 public Object[] toArray() { 050 consolidate(); 051 return plainList.toArray(); 052 } 053 054 /** 055 * Performs a load of all elements into memory, removing sequential 056 * access advantages. 057 */ 058 public void consolidate() { 059 if (this.plainList == null) { 060 this.plainList = new ArrayList<T>(); 061 for (final List<T> list : lists) { 062 // REVIEW: List.addAll is probably more efficient. 063 for (final T t : list) { 064 this.plainList.add(t); 065 } 066 } 067 } 068 } 069 070 public boolean addAll(final Collection<? extends T> collection) { 071 if (this.plainList == null) { 072 final List<T> list = (List<T>) collection; 073 return this.lists.add(list); 074 } else { 075 for (final T e : collection) { 076 this.plainList.add(e); 077 } 078 return true; 079 } 080 } 081 082 public T get(final int index) { 083 if (this.plainList == null) { 084 if (index == 0) { 085 this.getIterator = this.iterator(); 086 this.previousIndex = index; 087 if (this.getIterator.hasNext()) { 088 this.previousElement = this.getIterator.next(); 089 return this.previousElement; 090 } else { 091 this.getIterator = null; 092 this.previousIndex = -200; 093 throw new IndexOutOfBoundsException( 094 "Index " + index + " out of concatenable list range"); 095 } 096 } else if (this.previousIndex + 1 == index 097 && this.getIterator != null) 098 { 099 this.previousIndex = index; 100 if (this.getIterator.hasNext()) { 101 this.prePreviousElement = this.previousElement; 102 this.previousElement = this.getIterator.next(); 103 return this.previousElement; 104 } else { 105 this.getIterator = null; 106 this.previousIndex = -200; 107 throw new IndexOutOfBoundsException( 108 "Index " + index + " out of concatenable list range"); 109 } 110 } else if (this.previousIndex == index) { 111 return this.previousElement; 112 } else if (this.previousIndex - 1 == index) { 113 return this.prePreviousElement; 114 } else { 115 this.previousIndex = -200; 116 this.getIterator = null; 117 final Iterator<T> it = this.iterator(); 118 if (!it.hasNext()) { 119 throw new IndexOutOfBoundsException( 120 "Index " + index + " out of concatenable list range"); 121 } 122 for (int i = 0; i < index; i++) { 123 if (!it.hasNext()) { 124 throw new IndexOutOfBoundsException( 125 "Index " + index 126 + " out of concatenable list range"); 127 } 128 this.prePreviousElement = it.next(); 129 } 130 this.previousElement = it.next(); 131 this.previousIndex = index; 132 this.getIterator = it; 133 return this.previousElement; 134 } 135 } else { 136 this.previousElement = this.plainList.get(index); 137 return this.previousElement; 138 } 139 } 140 141 public boolean add(final T t) { 142 if (this.plainList == null) { 143 return this.lists.add(Collections.singletonList(t)); 144 } else { 145 return this.plainList.add(t); 146 } 147 } 148 149 public void add(final int index, final T t) { 150 if (this.plainList == null) { 151 throw new UnsupportedOperationException(); 152 } else { 153 this.plainList.add(index, t); 154 } 155 } 156 157 public T set(final int index, final T t) { 158 if (this.plainList == null) { 159 throw new UnsupportedOperationException(); 160 } else { 161 return this.plainList.set(index, t); 162 } 163 } 164 165 public int size() { 166 if (this.plainList == null) { 167 // REVIEW: Consider consolidating here. As it stands, this loop is 168 // expensive if called often on a lot of small lists. Amortized cost 169 // would be lower if we consolidated, or partially consolidated. 170 int size = 0; 171 for (final List<T> list : lists) { 172 size += list.size(); 173 } 174 return size; 175 } else { 176 return this.plainList.size(); 177 } 178 } 179 180 public Iterator<T> iterator() { 181 if (this.plainList == null) { 182 return new Iterator<T>() { 183 private final Iterator<List<T>> listsIt = lists.iterator(); 184 private Iterator<T> currentListIt; 185 186 public boolean hasNext() { 187 if (currentListIt == null) { 188 if (listsIt.hasNext()) { 189 currentListIt = listsIt.next().iterator(); 190 } else { 191 return false; 192 } 193 } 194 195 // If the current sub-list iterator has no next, grab the 196 // next sub-list's iterator, and continue until either a 197 // sub-list iterator with a next is found (at which point, 198 // the while loop terminates) or no more sub-lists exist (in 199 // which case, return false). 200 while (!currentListIt.hasNext()) { 201 if (listsIt.hasNext()) { 202 currentListIt = listsIt.next().iterator(); 203 } else { 204 return false; 205 } 206 } 207 return currentListIt.hasNext(); 208 } 209 210 public T next() { 211 if (!hasNext()) { 212 throw new NoSuchElementException(); 213 } else { 214 return currentListIt.next(); 215 } 216 } 217 218 public void remove() { 219 throw new UnsupportedOperationException(); 220 } 221 }; 222 } else { 223 return this.plainList.iterator(); 224 } 225 } 226 227 public boolean isEmpty() { 228 if (this.plainList != null) { 229 return this.plainList.isEmpty(); 230 } 231 if (this.lists.isEmpty()) { 232 return true; 233 } else { 234 for (final List<T> l : lists) { 235 if (!l.isEmpty()) { 236 return false; 237 } 238 } 239 return true; 240 } 241 } 242 243 public void clear() { 244 this.plainList = null; 245 this.lists.clear(); 246 } 247 248 public int hashCode() { 249 return this.hashCode; 250 } 251} 252 253// End ConcatenableList.java