001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.foundation;
022:
023: import com.db4o.types.Unversioned;
024:
025: /**
026: * Fast linked list for all usecases.
027: *
028: * @exclude
029: */
030: public class Collection4 implements Iterable4, DeepClone, Unversioned {
031:
032: // FIELDS ARE PUBLIC SO THEY CAN BE REFLECTED ON IN JDKs <= 1.1
033:
034: /**
035: * first element of the linked list
036: *
037: * @sharpen.private
038: */
039: public List4 _first;
040:
041: /**
042: * @sharpen.private
043: */
044: public List4 _last;
045:
046: /**
047: * number of elements collected
048: *
049: * @sharpen.private
050: */
051: public int _size;
052:
053: /**
054: * @sharpen.private
055: */
056: public int _version;
057:
058: public Collection4() {
059: }
060:
061: public Collection4(Object[] elements) {
062: addAll(elements);
063: }
064:
065: public Collection4(Iterable4 other) {
066: addAll(other);
067: }
068:
069: public Collection4(Iterator4 iterator) {
070: addAll(iterator);
071: }
072:
073: public Object singleElement() {
074: if (size() != 1) {
075: throw new IllegalStateException();
076: }
077: return _first._element;
078: }
079:
080: /**
081: * Adds an element to the end of this collection.
082: *
083: * @param element
084: */
085: public final void add(Object element) {
086: doAdd(element);
087: changed();
088: }
089:
090: public final void prepend(Object element) {
091: doPrepend(element);
092: changed();
093: }
094:
095: private void doPrepend(Object element) {
096: if (_first == null) {
097: doAdd(element);
098: } else {
099: _first = new List4(_first, element);
100: _size++;
101: }
102: }
103:
104: private void doAdd(Object element) {
105: if (_last == null) {
106: _first = new List4(element);
107: _last = _first;
108: } else {
109: _last._next = new List4(element);
110: _last = _last._next;
111: }
112: _size++;
113: }
114:
115: public final void addAll(Object[] elements) {
116: assertNotNull(elements);
117: for (int i = 0; i < elements.length; i++) {
118: add(elements[i]);
119: }
120: }
121:
122: public final void addAll(Iterable4 other) {
123: assertNotNull(other);
124: addAll(other.iterator());
125: }
126:
127: public final void addAll(Iterator4 iterator) {
128: assertNotNull(iterator);
129: while (iterator.moveNext()) {
130: add(iterator.current());
131: }
132: }
133:
134: public final void clear() {
135: _first = null;
136: _last = null;
137: _size = 0;
138: changed();
139: }
140:
141: public final boolean contains(Object element) {
142: return find(element) != null;
143: }
144:
145: public boolean containsAll(Iterator4 iter) {
146: assertNotNull(iter);
147: while (iter.moveNext()) {
148: if (!contains(iter.current())) {
149: return false;
150: }
151: }
152: return true;
153: }
154:
155: /**
156: * tests if the object is in the Collection. == comparison.
157: */
158: public final boolean containsByIdentity(Object element) {
159: Iterator4 i = internalIterator();
160: while (i.moveNext()) {
161: Object current = i.current();
162: if (current == element) {
163: return true;
164: }
165: }
166: return false;
167: }
168:
169: private List4 find(Object obj) {
170: List4 current = _first;
171: while (current != null) {
172: if (current.holds(obj)) {
173: return current;
174: }
175: current = current._next;
176: }
177: return null;
178: }
179:
180: /**
181: * returns the first object found in the Collections that equals() the
182: * passed object
183: */
184: public final Object get(Object element) {
185: List4 holder = find(element);
186: return holder == null ? null : holder._element;
187: }
188:
189: public Object deepClone(Object newParent) {
190: Collection4 col = new Collection4();
191: Object element = null;
192: Iterator4 i = internalIterator();
193: while (i.moveNext()) {
194: element = i.current();
195: if (element instanceof DeepClone) {
196: col.add(((DeepClone) element).deepClone(newParent));
197: } else {
198: col.add(element);
199: }
200: }
201: return col;
202: }
203:
204: /**
205: * makes sure the passed object is in the Collection. equals() comparison.
206: */
207: public final Object ensure(Object element) {
208: List4 list = find(element);
209: if (list == null) {
210: add(element);
211: return element;
212: }
213: return list._element;
214: }
215:
216: /**
217: * Iterates through the collection in reversed insertion order which happens
218: * to be the fastest.
219: *
220: * @return
221: */
222: public final Iterator4 iterator() {
223: return _first == null ? Iterators.EMPTY_ITERATOR
224: : new Collection4Iterator(this , _first);
225: }
226:
227: /**
228: * removes an object from the Collection equals() comparison returns the
229: * removed object or null, if none found
230: */
231: public Object remove(Object a_object) {
232: List4 previous = null;
233: List4 current = _first;
234: while (current != null) {
235: if (current.holds(a_object)) {
236: _size--;
237: adjustOnRemoval(previous, current);
238: changed();
239: return current._element;
240: }
241: previous = current;
242: current = current._next;
243: }
244: return null;
245: }
246:
247: public void replace(Object oldObject, Object newObject) {
248: List4 list = find(oldObject);
249: if (list != null) {
250: list._element = newObject;
251: }
252: }
253:
254: private void adjustOnRemoval(List4 previous, List4 removed) {
255: if (removed == _first) {
256: _first = removed._next;
257: } else {
258: previous._next = removed._next;
259: }
260: if (removed == _last) {
261: _last = previous;
262: }
263: }
264:
265: public final int size() {
266: return _size;
267: }
268:
269: public final boolean isEmpty() {
270: return _size == 0;
271: }
272:
273: /**
274: * This is a non reflection implementation for more speed. In contrast to
275: * the JDK behaviour, the passed array has to be initialized to the right
276: * length.
277: */
278: public final Object[] toArray(Object[] a_array) {
279: int j = 0;
280: Iterator4 i = internalIterator();
281: while (i.moveNext()) {
282: a_array[j++] = i.current();
283: }
284: return a_array;
285: }
286:
287: public final Object[] toArray() {
288: Object[] array = new Object[_size];
289: toArray(array);
290: return array;
291: }
292:
293: public String toString() {
294: return Iterators.toString(internalIterator());
295: }
296:
297: private void changed() {
298: ++_version;
299: }
300:
301: int version() {
302: return _version;
303: }
304:
305: private void assertNotNull(Object element) {
306: if (element == null) {
307: throw new ArgumentNullException();
308: }
309: }
310:
311: /**
312: * Leaner iterator for faster iteration (but unprotected against
313: * concurrent modifications).
314: */
315: private Iterator4 internalIterator() {
316: return new Iterator4Impl(_first);
317: }
318:
319: }
|