Source Code Cross Referenced for FastList.java in  » Development » Javolution » javolution » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Development » Javolution » javolution.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /*
0002:         * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
0003:         * Copyright (C) 2005 - Javolution (http://javolution.org/)
0004:         * All rights reserved.
0005:         * 
0006:         * Permission to use, copy, modify, and distribute this software is
0007:         * freely granted, provided that this notice is preserved.
0008:         */
0009:        package javolution.util;
0010:
0011:        import java.io.IOException;
0012:
0013:        import j2me.io.ObjectInputStream;
0014:        import j2me.io.ObjectOutputStream;
0015:        import j2me.io.Serializable;
0016:        import j2me.lang.IllegalStateException;
0017:        import j2me.util.Collection;
0018:        import j2me.util.Iterator;
0019:        import j2me.util.List;
0020:        import j2me.util.ListIterator;
0021:        import j2mex.realtime.MemoryArea;
0022:        import java.util.NoSuchElementException;
0023:
0024:        import javolution.context.ObjectFactory;
0025:        import javolution.context.PersistentContext;
0026:        import javolution.lang.Reusable;
0027:
0028:        /**
0029:         * <p> This class represents a linked list with real-time behavior; 
0030:         *     smooth capacity increase and no memory allocation as long as the
0031:         *     list size does not exceed its initial capacity.</p>
0032:         * 
0033:         * <p> All of the operations perform as could be expected for a doubly-linked
0034:         *     list ({@link #addLast insertion}/{@link #removeLast() deletion}
0035:         *     at the end of the list are nonetheless the fastest). 
0036:         *     Operations that index into the list will traverse the list from
0037:         *     the begining or the end whichever is closer to the specified index. 
0038:         *     Random access operations can be significantly accelerated by 
0039:         *     {@link #subList splitting} the list into smaller ones.</p> 
0040:         * 
0041:         * <p> {@link FastList} (as for any {@link FastCollection} sub-class) supports
0042:         *     thread-safe, fast iterations without using iterators.[code]
0043:         *     FastList<String> list = new FastList<String>();
0044:         *     for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
0045:         *         String value = n.getValue(); // No typecast necessary.    
0046:         *     }[/code]</p>
0047:         *     
0048:         * <p> {@link FastList} are fully {@link Reusable reusable}, they maintain 
0049:         *     internal pools of {@link Node nodes} objects. When a node is removed
0050:         *     from its list, it is automatically restored to its pool.</p>
0051:         * 
0052:         * <p> Custom list implementations may override the {@link #newNode} method 
0053:         *     in order to return their own {@link Node} implementation (with 
0054:         *     additional fields for example).</p>
0055:         *     
0056:         * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
0057:         * @version 4.2, December 18, 2006
0058:         */
0059:        public class FastList/*<E>*/extends FastCollection/*<E>*/
0060:        implements  List/*<E>*/, Reusable {
0061:
0062:            /**
0063:             * Holds the main list factory.
0064:             */
0065:            private static final ObjectFactory FACTORY = new ObjectFactory() {
0066:
0067:                public Object create() {
0068:                    return new FastList();
0069:                }
0070:
0071:                public void cleanup(Object obj) {
0072:                    ((FastList) obj).reset();
0073:                }
0074:            };
0075:
0076:            /**
0077:             * Holds the node marking the beginning of the list (not included).
0078:             */
0079:            private transient Node/*<E>*/_head = newNode();
0080:
0081:            /**
0082:             * Holds the node marking the end of the list (not included).
0083:             */
0084:            private transient Node/*<E>*/_tail = newNode();
0085:
0086:            /**
0087:             * Holds the value comparator.
0088:             */
0089:            private transient FastComparator/*<? super  E>*/_valueComparator = FastComparator.DEFAULT;
0090:
0091:            /**
0092:             * Holds the current size.
0093:             */
0094:            private transient int _size;
0095:
0096:            /**
0097:             * Creates a list of small initial capacity.
0098:             */
0099:            public FastList() {
0100:                this (4);
0101:            }
0102:
0103:            /**
0104:             * Creates a persistent list associated to the specified unique identifier
0105:             * (convenience method).
0106:             * 
0107:             * @param id the unique identifier for this map.
0108:             * @throws IllegalArgumentException if the identifier is not unique.
0109:             * @see javolution.context.PersistentContext.Reference
0110:             */
0111:            public FastList(String id) {
0112:                this ();
0113:                new PersistentContext.Reference(id, this ) {
0114:                    protected void notifyChange() {
0115:                        FastList.this .clear();
0116:                        FastList.this .addAll((FastList) this .get());
0117:                    }
0118:                };
0119:            }
0120:
0121:            /**
0122:             * Creates a list of specified initial capacity; unless the list size 
0123:             * reaches the specified capacity, operations on this list will not allocate
0124:             * memory (no lazy object creation).
0125:             * 
0126:             * @param capacity the initial capacity.
0127:             */
0128:            public FastList(int capacity) {
0129:                _head._next = _tail;
0130:                _tail._previous = _head;
0131:                Node/*<E>*/previous = _tail;
0132:                for (int i = 0; i++ < capacity;) {
0133:                    Node/*<E>*/newNode = newNode();
0134:                    newNode._previous = previous;
0135:                    previous._next = newNode;
0136:                    previous = newNode;
0137:                }
0138:            }
0139:
0140:            /**
0141:             * Creates a list containing the specified values, in the order they
0142:             * are returned by the collection's iterator.
0143:             *
0144:             * @param values the values to be placed into this list.
0145:             */
0146:            public FastList(Collection/*<? extends E>*/values) {
0147:                this (values.size());
0148:                addAll(values);
0149:            }
0150:
0151:            /**
0152:             * Returns a new, preallocated or {@link #recycle recycled} list instance
0153:             * (on the stack when executing in a {@link javolution.context.StackContext
0154:             * StackContext}).
0155:             *
0156:             * @return a new, preallocated or recycled list instance.
0157:             */
0158:            public static/*<E>*/FastList/*<E>*/newInstance() {
0159:                return (FastList/*<E>*/) FACTORY.object();
0160:            }
0161:
0162:            /**
0163:             * Recycles a list {@link #newInstance() instance} immediately
0164:             * (on the stack when executing in a {@link javolution.context.StackContext
0165:             * StackContext}). 
0166:             */
0167:            public static void recycle(FastList instance) {
0168:                FACTORY.recycle(instance);
0169:            }
0170:
0171:            /**
0172:             * Appends the specified value to the end of this list
0173:             * (equivalent to {@link #addLast}).
0174:             *
0175:             * @param value the value to be appended to this list.
0176:             * @return <code>true</code> (as per the general contract of the
0177:             *         <code>Collection.add</code> method).
0178:             */
0179:            public final boolean add(Object/*{E}*/value) {
0180:                addLast(value);
0181:                return true;
0182:            }
0183:
0184:            /**
0185:             * Returns the hash code value for this list.  The hash code of a list
0186:             * is defined to be the result of the following calculation:[code]
0187:             *  h = 1;
0188:             *  Iterator i = list.iterator();
0189:             *  while (i.hasNext()) {
0190:             *      Object obj = i.next();
0191:             *      h = 31 * h +  this.getValueComparator().hashCodeOf(obj);
0192:             *  }[/code]
0193:             *
0194:             * @return the hash code value for this list.
0195:             */
0196:            public int hashCode() {
0197:                final FastComparator comp = this .getValueComparator();
0198:                int h = 1;
0199:                for (Node n = _head, end = _tail; (n = n._next) != end;) {
0200:                    h = 31 * h + comp.hashCodeOf(n._value);
0201:                }
0202:                return h;
0203:            }
0204:
0205:            /**
0206:             * Returns the value at the specified position in this list.
0207:             *
0208:             * @param index the index of value to return.
0209:             * @return the value at the specified position in this list.
0210:             * @throws IndexOutOfBoundsException if <code>(index < 0) || 
0211:             *         (index >= size())</code>
0212:             */
0213:            public final Object/*{E}*/get(int index) {
0214:                if ((index < 0) || (index >= _size))
0215:                    throw new IndexOutOfBoundsException("index: " + index);
0216:                return nodeAt(index)._value;
0217:            }
0218:
0219:            /**
0220:             * Replaces the value at the specified position in this list with the
0221:             * specified value.
0222:             *
0223:             * @param index the index of value to replace.
0224:             * @param value the value to be stored at the specified position.
0225:             * @return the value previously at the specified position.
0226:             * @throws IndexOutOfBoundsException if <code>(index < 0) || 
0227:             *         (index >= size())</code>
0228:             */
0229:            public final Object/*{E}*/set(int index, Object/*{E}*/value) {
0230:                if ((index < 0) || (index >= _size))
0231:                    throw new IndexOutOfBoundsException("index: " + index);
0232:                final Node/*<E>*/node = nodeAt(index);
0233:                Object/*{E}*/previousValue = node._value;
0234:                node._value = value;
0235:                return previousValue;
0236:            }
0237:
0238:            /**
0239:             * Inserts the specified value at the specified position in this list.
0240:             * Shifts the value currently at that position
0241:             * (if any) and any subsequent values to the right (adds one to their
0242:             * indices).
0243:             *
0244:             * @param index the index at which the specified value is to be inserted.
0245:             * @param value the value to be inserted.
0246:             * @throws IndexOutOfBoundsException if <code>(index < 0) || 
0247:             *         (index > size())</code>
0248:             */
0249:            public final void add(int index, Object/*{E}*/value) {
0250:                if ((index < 0) || (index > _size))
0251:                    throw new IndexOutOfBoundsException("index: " + index);
0252:                addBefore(nodeAt(index), value);
0253:            }
0254:
0255:            /**
0256:             * Inserts all of the values in the specified collection into this
0257:             * list at the specified position. Shifts the value currently at that
0258:             * position (if any) and any subsequent values to the right 
0259:             * (increases their indices). 
0260:             *
0261:             * @param index the index at which to insert first value from the specified
0262:             *        collection.
0263:             * @param values the values to be inserted into this list.
0264:             * @return <code>true</code> if this list changed as a result of the call;
0265:             *         <code>false</code> otherwise.
0266:             * @throws IndexOutOfBoundsException if <code>(index < 0) || 
0267:             *         (index > size())</code>
0268:             */
0269:            public final boolean addAll(int index,
0270:                    Collection/*<? extends E>*/values) {
0271:                if ((index < 0) || (index > _size))
0272:                    throw new IndexOutOfBoundsException("index: " + index);
0273:                final Node indexNode = nodeAt(index);
0274:                Iterator/*<? extends E>*/i = values.iterator();
0275:                while (i.hasNext()) {
0276:                    addBefore(indexNode, i.next());
0277:                }
0278:                return values.size() != 0;
0279:            }
0280:
0281:            /**
0282:             * Removes the value at the specified position in this list.
0283:             * Shifts any subsequent values to the left (subtracts one
0284:             * from their indices). Returns the value that was removed from the
0285:             * list.
0286:             *
0287:             * @param index the index of the value to removed.
0288:             * @return the value previously at the specified position.
0289:             * @throws IndexOutOfBoundsException if <code>(index < 0) || 
0290:             *         (index >= size())</code>
0291:             */
0292:            public final Object/*{E}*/remove(int index) {
0293:                if ((index < 0) || (index >= _size))
0294:                    throw new IndexOutOfBoundsException("index: " + index);
0295:                final Node/*<E>*/node = nodeAt(index);
0296:                Object/*{E}*/previousValue = node._value;
0297:                delete(node);
0298:                return previousValue;
0299:            }
0300:
0301:            /**
0302:             * Returns the index in this list of the first occurrence of the specified
0303:             * value, or -1 if this list does not contain this value.
0304:             *
0305:             * @param value the value to search for.
0306:             * @return the index in this list of the first occurrence of the specified
0307:             *         value, or -1 if this list does not contain this value.
0308:             */
0309:            public final int indexOf(Object value) {
0310:                final FastComparator comp = this .getValueComparator();
0311:                int index = 0;
0312:                for (Node n = _head, end = _tail; (n = n._next) != end; index++) {
0313:                    if (comp == FastComparator.DEFAULT ? defaultEquals(value,
0314:                            n._value) : comp.areEqual(value, n._value))
0315:                        return index;
0316:                }
0317:                return -1;
0318:            }
0319:
0320:            /**
0321:             * Returns the index in this list of the last occurrence of the specified
0322:             * value, or -1 if this list does not contain this value.
0323:             *
0324:             * @param value the value to search for.
0325:             * @return the index in this list of the last occurrence of the specified
0326:             *         value, or -1 if this list does not contain this value.
0327:             */
0328:            public final int lastIndexOf(Object value) {
0329:                final FastComparator comp = this .getValueComparator();
0330:                int index = size() - 1;
0331:                for (Node n = _tail, end = _head; (n = n._previous) != end; index--) {
0332:                    if (comp == FastComparator.DEFAULT ? defaultEquals(value,
0333:                            n._value) : comp.areEqual(value, n._value))
0334:                        return index;
0335:                }
0336:                return -1;
0337:            }
0338:
0339:            /**
0340:             * Returns a simple iterator over the elements in this list 
0341:             * (allocated on the stack when executed in a 
0342:             * {@link javolution.context.StackContext StackContext}).
0343:             *
0344:             * @return an iterator over this list values.
0345:             */
0346:            public Iterator/*<E>*/iterator() {
0347:                return listIterator();
0348:            }
0349:
0350:            /**
0351:             * Returns a list iterator over the elements in this list 
0352:             * (allocated on the stack when executed in a 
0353:             * {@link javolution.context.StackContext StackContext}).
0354:             *
0355:             * @return an iterator over this list values.
0356:             */
0357:            public ListIterator/*<E>*/listIterator() {
0358:                return FastListIterator.valueOf(this , _head._next, 0, _size);
0359:            }
0360:
0361:            /**
0362:             * Returns a list iterator from the specified position
0363:             * (allocated on the stack when executed in a 
0364:             * {@link javolution.context.StackContext StackContext}).
0365:             * 
0366:             * The specified index indicates the first value that would be returned by
0367:             * an initial call to the <code>next</code> method.  An initial call to
0368:             * the <code>previous</code> method would return the value with the
0369:             * specified index minus one.
0370:             *
0371:             * @param index index of first value to be returned from the
0372:             *        list iterator (by a call to the <code>next</code> method).
0373:             * @return a list iterator over the values in this list
0374:             *         starting at the specified position in this list.
0375:             * @throws IndexOutOfBoundsException if the index is out of range
0376:             *        [code](index < 0 || index > size())[/code].
0377:             */
0378:            public ListIterator/*<E>*/listIterator(int index) {
0379:                if ((index < 0) || (index > _size))
0380:                    throw new IndexOutOfBoundsException("index: " + index);
0381:                return FastListIterator.valueOf(this , nodeAt(index), index,
0382:                        _size);
0383:            }
0384:
0385:            /**
0386:             * Returns a view of the portion of this list between the specified
0387:             * indexes (allocated from the "stack" when executing in a 
0388:             * {@link javolution.context.StackContext StackContext}).
0389:             * If the specified indexes are equal, the returned list is empty. 
0390:             * The returned list is backed by this list, so non-structural changes in
0391:             * the returned list are reflected in this list, and vice-versa. 
0392:             *
0393:             * This method eliminates the need for explicit range operations (of
0394:             * the sort that commonly exist for arrays). Any operation that expects
0395:             * a list can be used as a range operation by passing a subList view
0396:             * instead of a whole list.  For example, the following idiom
0397:             * removes a range of values from a list:
0398:             * <code>list.subList(from, to).clear();</code>
0399:             * Similar idioms may be constructed for <code>indexOf</code> and
0400:             * <code>lastIndexOf</code>, and all of the algorithms in the
0401:             * <code>Collections</code> class can be applied to a subList.
0402:             *
0403:             * The semantics of the list returned by this method become undefined if
0404:             * the backing list (i.e., this list) is <i>structurally modified</i> in
0405:             * any way other than via the returned list (structural modifications are
0406:             * those that change the size of this list, or otherwise perturb it in such
0407:             * a fashion that iterations in progress may yield incorrect results).
0408:             *
0409:             * @param fromIndex low endpoint (inclusive) of the subList.
0410:             * @param toIndex high endpoint (exclusive) of the subList.
0411:             * @return a view of the specified range within this list.
0412:             * 
0413:             * @throws IndexOutOfBoundsException if [code](fromIndex < 0 ||
0414:             *          toIndex > size || fromIndex < toIndex)[/code]
0415:             */
0416:            public final List/*<E>*/subList(int fromIndex, int toIndex) {
0417:                if ((fromIndex < 0) || (toIndex > _size)
0418:                        || (fromIndex > toIndex))
0419:                    throw new IndexOutOfBoundsException("fromIndex: "
0420:                            + fromIndex + ", toIndex: " + toIndex
0421:                            + " for list of size: " + _size);
0422:                return SubList.valueOf(this , nodeAt(fromIndex)._previous,
0423:                        nodeAt(toIndex), toIndex - fromIndex);
0424:            }
0425:
0426:            /**
0427:             * Returns the first value of this list.
0428:             *
0429:             * @return this list's first value.
0430:             * @throws NoSuchElementException if this list is empty.
0431:             */
0432:            public final Object/*{E}*/getFirst() {
0433:                final Node/*<E>*/node = _head._next;
0434:                if (node == _tail)
0435:                    throw new NoSuchElementException();
0436:                return node._value;
0437:            }
0438:
0439:            /**
0440:             * Returns the last value of this list.
0441:             *
0442:             * @return this list's last value.
0443:             * @throws NoSuchElementException if this list is empty.
0444:             */
0445:            public final Object/*{E}*/getLast() {
0446:                final Node/*<E>*/node = _tail._previous;
0447:                if (node == _head)
0448:                    throw new NoSuchElementException();
0449:                return node._value;
0450:            }
0451:
0452:            /**
0453:             * Inserts the specified value at the beginning of this list.
0454:             * 
0455:             * @param value the value to be inserted.
0456:             */
0457:            public final void addFirst(Object/*{E}*/value) {
0458:                addBefore(_head._next, value);
0459:            }
0460:
0461:            /**
0462:             * Appends the specified value to the end of this list <i>(fast)</i>.
0463:             * 
0464:             * @param value the value to be inserted.
0465:             */
0466:            public void addLast(Object/*{E}*/value) { // Optimized.
0467:                if (_tail._next == null) {
0468:                    increaseCapacity();
0469:                }
0470:                _tail._value = value;
0471:                _tail = _tail._next;
0472:                _size += ONE_VOLATILE; // Done last.
0473:            }
0474:
0475:            /**
0476:             * Removes and returns the first value of this list.
0477:             *
0478:             * @return this list's first value before this call.
0479:             * @throws NoSuchElementException if this list is empty.
0480:             */
0481:            public final Object/*{E}*/removeFirst() {
0482:                final Node/*<E>*/first = _head._next;
0483:                if (first == _tail)
0484:                    throw new NoSuchElementException();
0485:                Object/*{E}*/previousValue = first._value;
0486:                delete(first);
0487:                return previousValue;
0488:            }
0489:
0490:            /**
0491:             * Removes and returns the last value of this list <i>(fast)</i>.
0492:             *
0493:             * @return this list's last value before this call.
0494:             * @throws NoSuchElementException if this list is empty.
0495:             */
0496:            public final Object/*{E}*/removeLast() {
0497:                if (_size == 0)
0498:                    throw new NoSuchElementException();
0499:                _size -= ONE_VOLATILE; // Done first.
0500:                final Node/*<E>*/last = _tail._previous;
0501:                final Object/*{E}*/previousValue = last._value;
0502:                _tail = last;
0503:                last._value = null;
0504:                return previousValue;
0505:            }
0506:
0507:            ///////////////////////
0508:            // Nodes operations. //
0509:            ///////////////////////
0510:
0511:            /**
0512:             * Inserts the specified value before the specified Node.
0513:             * 
0514:             * @param next the Node before which this value is inserted.
0515:             * @param value the value to be inserted.   
0516:             */
0517:            public final void addBefore(Node/*<E>*/next, Object/*{E}*/value) {
0518:                if (_tail._next == null) {
0519:                    increaseCapacity();// Increases capacity.
0520:                }
0521:                final Node newNode = _tail._next;
0522:                // Detaches newNode.
0523:                final Node tailNext = _tail._next = newNode._next;
0524:                if (tailNext != null) {
0525:                    tailNext._previous = _tail;
0526:                }
0527:                // Inserts before next.
0528:                final Node previous = next._previous;
0529:                previous._next = newNode;
0530:                next._previous = newNode;
0531:                newNode._next = next;
0532:                newNode._previous = previous;
0533:
0534:                newNode._value = value;
0535:                _size += ONE_VOLATILE; // Done last.
0536:            }
0537:
0538:            /**
0539:             * Returns the node at the specified index. This method returns
0540:             * the {@link #headNode} node when [code]index < 0 [/code] or 
0541:             * the {@link #tailNode} node when [code]index >= size()[/code].
0542:             * 
0543:             * @param index the index of the Node to return.
0544:             */
0545:            private final Node/*<E>*/nodeAt(int index) {
0546:                // We cannot do backward search because of thread-safety.
0547:                Node/*<E>*/node = _head;
0548:                for (int i = index; i-- >= 0;) {
0549:                    node = node._next;
0550:                }
0551:                return node;
0552:            }
0553:
0554:            // Implements FastCollection abstract method.
0555:            public final Record/*Node<E>*/head() {
0556:                return _head;
0557:            }
0558:
0559:            // Implements FastCollection abstract method.
0560:            public final Record/*Node<E>*/tail() {
0561:                return _tail;
0562:            }
0563:
0564:            // Implements FastCollection abstract method.
0565:            public final Object/*{E}*/valueOf(Record record) {
0566:                return ((Node/*<E>*/) record)._value;
0567:            }
0568:
0569:            // Implements FastCollection abstract method.
0570:            public final void delete(Record record) {
0571:                Node/*<E>*/node = (Node/*<E>*/) record;
0572:                _size -= ONE_VOLATILE; // Done first.
0573:                node._value = null;
0574:                // Detaches.
0575:                node._previous._next = node._next;
0576:                node._next._previous = node._previous;
0577:                // Inserts after _tail.
0578:                final Node/*<E>*/next = _tail._next;
0579:                node._previous = _tail;
0580:                node._next = next;
0581:                _tail._next = node;
0582:                if (next != null) {
0583:                    next._previous = node;
0584:                }
0585:            }
0586:
0587:            // Overrides (optimization).
0588:            public final boolean contains(Object value) {
0589:                return indexOf(value) >= 0;
0590:            }
0591:
0592:            ///////////////////////
0593:            // Contract Methods. //
0594:            ///////////////////////
0595:
0596:            // Implements abstract method.
0597:            public final int size() {
0598:                return _size;
0599:            }
0600:
0601:            // Overrides (optimization).
0602:            public final void clear() {
0603:                _size = ONE_VOLATILE - 1; // Done first.
0604:                for (Node/*<E>*/n = _head, end = _tail; (n = n._next) != end;) {
0605:                    n._value = null;
0606:                }
0607:                _tail = _head._next;
0608:            }
0609:
0610:            // Implements Reusable interface.
0611:            public void reset() {
0612:                this .clear();
0613:                _valueComparator = FastComparator.DEFAULT;
0614:            }
0615:
0616:            /**
0617:             * Sets the comparator to use for value equality.
0618:             *
0619:             * @param comparator the value comparator.
0620:             * @return <code>this</code>
0621:             */
0622:            public FastList/*<E>*/setValueComparator(
0623:                    FastComparator/*<? super  E>*/comparator) {
0624:                _valueComparator = comparator;
0625:                return this ;
0626:            }
0627:
0628:            // Overrides.
0629:            public FastComparator/*<? super  E>*/getValueComparator() {
0630:                return _valueComparator;
0631:            }
0632:
0633:            // Overrides  to return a list (JDK1.5+).
0634:            public Collection/*List<E>*/unmodifiable() {
0635:                return (Collection/*List<E>*/) super .unmodifiable();
0636:            }
0637:
0638:            /**
0639:             * Returns a new node for this list; this method can be overriden by 
0640:             * custom list implementation. 
0641:             *
0642:             * @return a new node.
0643:             */
0644:            protected Node/*<E>*/newNode() {
0645:                return new Node();
0646:            }
0647:
0648:            // Requires special handling during de-serialization process.
0649:            private void readObject(ObjectInputStream stream)
0650:                    throws IOException, ClassNotFoundException {
0651:
0652:                // Initial setup.
0653:                _head = new Node();
0654:                _tail = new Node();
0655:                _head._next = _tail;
0656:                _tail._previous = _head;
0657:
0658:                setValueComparator((FastComparator) stream.readObject());
0659:                final int size = stream.readInt();
0660:                for (int i = size; i-- != 0;) {
0661:                    addLast((Object/*{E}*/) stream.readObject());
0662:                }
0663:            }
0664:
0665:            // Requires special handling during serialization process.
0666:            private void writeObject(ObjectOutputStream stream)
0667:                    throws IOException {
0668:                stream.writeObject(getValueComparator());
0669:                stream.writeInt(_size);
0670:                Node node = _head;
0671:                for (int i = _size; i-- != 0;) {
0672:                    node = node._next;
0673:                    stream.writeObject(node._value);
0674:                }
0675:            }
0676:
0677:            // Increases capacity (_tail._next == null)
0678:            private void increaseCapacity() {
0679:                MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
0680:                    public void run() {
0681:                        Node/*<E>*/newNode0 = newNode();
0682:                        _tail._next = newNode0;
0683:                        newNode0._previous = _tail;
0684:
0685:                        Node/*<E>*/newNode1 = newNode();
0686:                        newNode0._next = newNode1;
0687:                        newNode1._previous = newNode0;
0688:
0689:                        Node/*<E>*/newNode2 = newNode();
0690:                        newNode1._next = newNode2;
0691:                        newNode2._previous = newNode1;
0692:
0693:                        Node/*<E>*/newNode3 = newNode();
0694:                        newNode2._next = newNode3;
0695:                        newNode3._previous = newNode2;
0696:                    }
0697:                });
0698:            }
0699:
0700:            /**
0701:             * This class represents a {@link FastList} node; it allows for direct 
0702:             * iteration over the list {@link #getValue values}.
0703:             * Custom {@link FastList} may use a derived implementation.
0704:             * For example:[code]
0705:             *    static class MyList<E,X> extends FastList<E> {
0706:             *        protected MyNode newNode() {
0707:             *            return new MyNode();
0708:             *        }
0709:             *        class MyNode extends Node<E> {
0710:             *            X xxx; // Additional node field (e.g. cross references).
0711:             *        }        
0712:             *    }[/code]
0713:             */
0714:            public static class Node/*<E>*/implements  Record, Serializable {
0715:
0716:                /**
0717:                 * Holds the next node.
0718:                 */
0719:                private Node/*<E>*/_next;
0720:
0721:                /**
0722:                 * Holds the previous node.
0723:                 */
0724:                private Node/*<E>*/_previous;
0725:
0726:                /**
0727:                 * Holds the node value.
0728:                 */
0729:                private Object/*{E}*/_value;
0730:
0731:                /**
0732:                 * Default constructor.
0733:                 */
0734:                protected Node() {
0735:                }
0736:
0737:                /**
0738:                 * Returns the value for this node.
0739:                 * 
0740:                 * @return the node value.
0741:                 */
0742:                public final Object/*{E}*/getValue() {
0743:                    return _value;
0744:                }
0745:
0746:                // Implements Record interface.
0747:                public final Record/*Node<E>*/getNext() {
0748:                    return _next;
0749:                }
0750:
0751:                // Implements Record interface.
0752:                public final Record/*Node<E>*/getPrevious() {
0753:                    return _previous;
0754:                }
0755:
0756:            }
0757:
0758:            /**
0759:             * This inner class implements a sub-list.
0760:             */
0761:            private static final class SubList extends FastCollection implements 
0762:                    List, Serializable {
0763:
0764:                private static final ObjectFactory FACTORY = new ObjectFactory() {
0765:                    protected Object create() {
0766:                        return new SubList();
0767:                    }
0768:
0769:                    protected void cleanup(Object obj) {
0770:                        SubList sl = (SubList) obj;
0771:                        sl._list = null;
0772:                        sl._head = null;
0773:                        sl._tail = null;
0774:                    }
0775:                };
0776:
0777:                private FastList _list;
0778:
0779:                private Node _head;
0780:
0781:                private Node _tail;
0782:
0783:                private int _size;
0784:
0785:                public static SubList valueOf(FastList list, Node head,
0786:                        Node tail, int size) {
0787:                    SubList subList = (SubList) FACTORY.object();
0788:                    subList._list = list;
0789:                    subList._head = head;
0790:                    subList._tail = tail;
0791:                    subList._size = size;
0792:                    return subList;
0793:                }
0794:
0795:                public int size() {
0796:                    return _size;
0797:                }
0798:
0799:                public Record head() {
0800:                    return _head;
0801:                }
0802:
0803:                public Record tail() {
0804:                    return _tail;
0805:                }
0806:
0807:                public Object valueOf(Record record) {
0808:                    return _list.valueOf(record);
0809:                }
0810:
0811:                public void delete(Record record) {
0812:                    _list.delete(record);
0813:                }
0814:
0815:                public boolean addAll(int index, Collection values) {
0816:                    if ((index < 0) || (index > _size))
0817:                        throw new IndexOutOfBoundsException("index: " + index);
0818:                    final Node indexNode = nodeAt(index);
0819:                    Iterator i = values.iterator();
0820:                    while (i.hasNext()) {
0821:                        _list.addBefore(indexNode, i.next());
0822:                    }
0823:                    return values.size() != 0;
0824:                }
0825:
0826:                public Object get(int index) {
0827:                    if ((index < 0) || (index >= _size))
0828:                        throw new IndexOutOfBoundsException("index: " + index);
0829:                    return nodeAt(index)._value;
0830:                }
0831:
0832:                public Object set(int index, Object value) {
0833:                    if ((index < 0) || (index >= _size))
0834:                        throw new IndexOutOfBoundsException("index: " + index);
0835:                    final Node node = nodeAt(index);
0836:                    Object previousValue = node._value;
0837:                    node._value = value;
0838:                    return previousValue;
0839:                }
0840:
0841:                public void add(int index, Object element) {
0842:                    if ((index < 0) || (index > _size))
0843:                        throw new IndexOutOfBoundsException("index: " + index);
0844:                    _list.addBefore(nodeAt(index), element);
0845:                }
0846:
0847:                public Object remove(int index) {
0848:                    if ((index < 0) || (index >= _size))
0849:                        throw new IndexOutOfBoundsException("index: " + index);
0850:                    final Node node = nodeAt(index);
0851:                    Object previousValue = node._value;
0852:                    _list.delete(node);
0853:                    return previousValue;
0854:                }
0855:
0856:                public int indexOf(Object value) {
0857:                    final FastComparator comp = _list.getValueComparator();
0858:                    int index = 0;
0859:                    for (Node n = _head, end = _tail; (n = n._next) != end; index++) {
0860:                        if (comp.areEqual(value, n._value))
0861:                            return index;
0862:                    }
0863:                    return -1;
0864:                }
0865:
0866:                public int lastIndexOf(Object value) {
0867:                    final FastComparator comp = this .getValueComparator();
0868:                    int index = size() - 1;
0869:                    for (Node n = _tail, end = _head; (n = n._previous) != end; index--) {
0870:                        if (comp.areEqual(value, n._value)) {
0871:                            return index;
0872:                        }
0873:                    }
0874:                    return -1;
0875:                }
0876:
0877:                public ListIterator listIterator() {
0878:                    return listIterator(0);
0879:                }
0880:
0881:                public ListIterator listIterator(int index) {
0882:                    if ((index >= 0) && (index <= _size)) {
0883:                        return FastListIterator.valueOf(_list, nodeAt(index),
0884:                                index, _size);
0885:                    } else {
0886:                        throw new IndexOutOfBoundsException("index: " + index
0887:                                + " for list of size: " + _size);
0888:                    }
0889:                }
0890:
0891:                public List subList(int fromIndex, int toIndex) {
0892:                    if ((fromIndex < 0) || (toIndex > _size)
0893:                            || (fromIndex > toIndex))
0894:                        throw new IndexOutOfBoundsException("fromIndex: "
0895:                                + fromIndex + ", toIndex: " + toIndex
0896:                                + " for list of size: " + _size);
0897:                    SubList subList = SubList.valueOf(_list,
0898:                            nodeAt(fromIndex)._previous, nodeAt(toIndex),
0899:                            toIndex - fromIndex);
0900:                    return subList;
0901:                }
0902:
0903:                private final Node nodeAt(int index) {
0904:                    if (index <= (_size >> 1)) { // Forward search.
0905:                        Node node = _head;
0906:                        for (int i = index; i-- >= 0;) {
0907:                            node = node._next;
0908:                        }
0909:                        return node;
0910:                    } else { // Backward search.
0911:                        Node node = _tail;
0912:                        for (int i = _size - index; i-- > 0;) {
0913:                            node = node._previous;
0914:                        }
0915:                        return node;
0916:                    }
0917:                }
0918:            }
0919:
0920:            /**
0921:             * This inner class implements a fast list iterator.
0922:             */
0923:            private static final class FastListIterator implements  ListIterator {
0924:
0925:                private static final ObjectFactory FACTORY = new ObjectFactory() {
0926:                    protected Object create() {
0927:                        return new FastListIterator();
0928:                    }
0929:
0930:                    protected void cleanup(Object obj) {
0931:                        FastListIterator i = (FastListIterator) obj;
0932:                        i._list = null;
0933:                        i._currentNode = null;
0934:                        i._nextNode = null;
0935:                    }
0936:                };
0937:
0938:                private FastList _list;
0939:
0940:                private Node _nextNode;
0941:
0942:                private Node _currentNode;
0943:
0944:                private int _length;
0945:
0946:                private int _nextIndex;
0947:
0948:                public static FastListIterator valueOf(FastList list,
0949:                        Node nextNode, int nextIndex, int size) {
0950:                    FastListIterator itr = (FastListIterator) FACTORY.object();
0951:                    itr._list = list;
0952:                    itr._nextNode = nextNode;
0953:                    itr._nextIndex = nextIndex;
0954:                    itr._length = size;
0955:                    return itr;
0956:                }
0957:
0958:                public boolean hasNext() {
0959:                    return (_nextIndex != _length);
0960:                }
0961:
0962:                public Object next() {
0963:                    if (_nextIndex == _length)
0964:                        throw new NoSuchElementException();
0965:                    _nextIndex++;
0966:                    _currentNode = _nextNode;
0967:                    _nextNode = _nextNode._next;
0968:                    return _currentNode._value;
0969:                }
0970:
0971:                public int nextIndex() {
0972:                    return _nextIndex;
0973:                }
0974:
0975:                public boolean hasPrevious() {
0976:                    return _nextIndex != 0;
0977:                }
0978:
0979:                public Object previous() {
0980:                    if (_nextIndex == 0)
0981:                        throw new NoSuchElementException();
0982:                    _nextIndex--;
0983:                    _currentNode = _nextNode = _nextNode._previous;
0984:                    return _currentNode._value;
0985:                }
0986:
0987:                public int previousIndex() {
0988:                    return _nextIndex - 1;
0989:                }
0990:
0991:                public void add(Object o) {
0992:                    _list.addBefore(_nextNode, o);
0993:                    _currentNode = null;
0994:                    _length++;
0995:                    _nextIndex++;
0996:                }
0997:
0998:                public void set(Object o) {
0999:                    if (_currentNode == null)
1000:                        throw new IllegalStateException();
1001:                    _currentNode._value = o;
1002:                }
1003:
1004:                public void remove() {
1005:                    if (_currentNode == null)
1006:                        throw new IllegalStateException();
1007:                    if (_nextNode == _currentNode) { // previous() has been called.
1008:                        _nextNode = _nextNode._next;
1009:                    } else {
1010:                        _nextIndex--;
1011:                    }
1012:                    _list.delete(_currentNode);
1013:                    _currentNode = null;
1014:                    _length--;
1015:                }
1016:            }
1017:
1018:            // For inlining of default comparator. 
1019:            private static boolean defaultEquals(Object o1, Object o2) {
1020:                return (o1 == null) ? (o2 == null) : (o1 == o2)
1021:                        || o1.equals(o2);
1022:            }
1023:
1024:            static volatile int ONE_VOLATILE = 1; // To prevent reordering.
1025:
1026:            private static final long serialVersionUID = 1L;
1027:
1028:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.