001: /*
002: * @(#)CachedArrayList.java 10/5/2005
003: *
004: * Copyright 2002 - 2005 JIDE Software Inc. All rights reserved.
005: */
006: package com.jidesoft.utils;
007:
008: import java.util.ArrayList;
009: import java.util.Collection;
010: import java.util.HashMap;
011: import java.util.Set;
012:
013: /**
014: * This is a fast access ArrayList that sacrifices memory for speed. It will
015: * reduce the speed of indexOf method from O(n) to O(1). However it will at least double
016: * the memory used by ArrayList. So use it approriately.
017: */
018: public class CachedArrayList<E> extends ArrayList<E> {
019: private HashMap<Object, Integer> _indexCache;
020: private boolean _lazyCaching = false;
021:
022: public CachedArrayList() {
023: }
024:
025: public CachedArrayList(Collection<? extends E> c) {
026: super (c);
027: if (!isLazyCaching()) {
028: cacheAll();
029: }
030: }
031:
032: public CachedArrayList(int initialCapacity) {
033: super (initialCapacity);
034: }
035:
036: @Override
037: public int indexOf(Object elem) {
038: initializeCache();
039: Integer o = _indexCache.get(elem);
040: if (o != null) {
041: return o;
042: } else {
043: int i = super .indexOf(elem);
044: if (i == -1) {
045: uncacheIt(elem);
046: } else {
047: cacheIt(elem, i);
048: }
049: return i;
050: }
051: }
052:
053: /**
054: * Adjusts the cache so that all values that are greater than index will increase by the value specified by the increase parameter.
055: *
056: * @param index the index. All values above this index will be changed.
057: * @param increase a positive number to increase or a negative number to decrease.
058: */
059: protected void adjustCache(int index, int increase) {
060: if (_indexCache != null) {
061: Set<Object> keys = _indexCache.keySet();
062: for (Object key : keys) {
063: int value = _indexCache.get(key);
064: if (value >= index) {
065: _indexCache.put(key, value + increase);
066: }
067: }
068: }
069: }
070:
071: /**
072: * Caches the index of the element.
073: *
074: * @param o the element
075: * @param index the index.
076: */
077: public void cacheIt(Object o, int index) {
078: if (_indexCache != null
079: && (_indexCache.get(o) == null || index < _indexCache
080: .get(o))) {
081: _indexCache.put(o, index);
082: }
083: }
084:
085: /**
086: * Uncaches the index of the element.
087: *
088: * @param o the element
089: */
090: public void uncacheIt(Object o) {
091: if (_indexCache != null) {
092: _indexCache.remove(o);
093: }
094: }
095:
096: @Override
097: public boolean add(E o) {
098: boolean added = super .add(o);
099: if (!isLazyCaching() && added) {
100: initializeCache();
101: cacheIt(o, size() - 1);
102: }
103: return added;
104: }
105:
106: @Override
107: public void add(int index, E element) {
108: super .add(index, element);
109: if (_indexCache != null) {
110: adjustCache(index, 1);
111: cacheIt(element, index);
112: }
113: }
114:
115: private void initializeCache() {
116: if (_indexCache == null) {
117: _indexCache = new HashMap();
118: }
119: }
120:
121: @Override
122: public E remove(int index) {
123: E element = super .remove(index);
124: if (element != null) {
125: uncacheIt(element);
126: adjustCache(index, -1);
127: }
128: return element;
129: }
130:
131: @Override
132: public boolean remove(Object o) {
133: int oldIndex = indexOf(o);
134: boolean removed = super .remove(o);
135: if (removed) {
136: uncacheIt(o);
137: adjustCache(oldIndex, -1);
138: }
139: return removed;
140: }
141:
142: @Override
143: public boolean removeAll(Collection<?> c) {
144: uncacheAll();
145: return super .removeAll(c);
146: }
147:
148: @Override
149: public void clear() {
150: uncacheAll();
151: super .clear();
152: }
153:
154: @Override
155: public boolean addAll(Collection<? extends E> c) {
156: boolean added = super .addAll(c);
157: if (added) {
158: cacheAll();
159: }
160: return added;
161: }
162:
163: @Override
164: public boolean addAll(int index, Collection<? extends E> c) {
165: boolean added = super .addAll(index, c);
166: initializeCache();
167: adjustCache(index, c.size());
168: for (E e : c) {
169: cacheIt(e, index++);
170: }
171: return added;
172: }
173:
174: @Override
175: public E set(int index, E element) {
176: if (!isLazyCaching()) {
177: initializeCache();
178: E e = super .set(index, element);
179: cacheIt(element, index);
180: return e;
181: } else {
182: return super .set(index, element);
183: }
184: }
185:
186: /**
187: * Invalidated the whole cache.
188: */
189: public void invalidateCache() {
190: uncacheAll();
191: }
192:
193: /**
194: * Uncache the whole cache. It is the same as {@link #invalidateCache()}.
195: */
196: public void uncacheAll() {
197: if (_indexCache != null) {
198: _indexCache.clear();
199: _indexCache = null;
200: }
201: }
202:
203: /**
204: * Cache all the element index.
205: */
206: public void cacheAll() {
207: _indexCache = new HashMap();
208: Integer i = 0;
209: for (Object elem : this ) {
210: if (_indexCache.get(elem) == null) {
211: _indexCache.put(elem, i);
212: }
213: i++;
214: }
215: // for (int i = 0; i < size(); i++) {
216: // _indexCache.put(get(i), i);
217: // }
218: // for (int i = size() - 1; i >= 0; i--) {
219: // _indexCache.put(get(i), i);
220: // }
221: }
222:
223: public boolean isLazyCaching() {
224: return _lazyCaching;
225: }
226:
227: public void setLazyCaching(boolean lazyCaching) {
228: _lazyCaching = lazyCaching;
229: }
230:
231: @Override
232: protected void removeRange(int fromIndex, int toIndex) {
233: if (fromIndex == toIndex) {
234: remove(fromIndex);
235: } else {
236: super.removeRange(fromIndex, toIndex);
237: uncacheAll();
238: if (!isLazyCaching()) {
239: cacheAll();
240: }
241: }
242: }
243: }
|