litesoft
@ 589
litesoft / trunk / GWT_Sandbox / UIdesign / src / com / test / uidesign / ArrayLinkList.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
package com.test.uidesign; /** * Simple Single Linked List backed by an Array. */ public class ArrayLinkList<T> { public static class Node<T> { private T mValue; private CtrlStructure<T> mCtrlStructure; private Integer mNextIndex; public Node( T pValue ) { mValue = pValue; } public T getValue() { return mValue; } public Node<T> getNext() { return ((mCtrlStructure != null) && (mNextIndex != null)) ? mCtrlStructure.mArray[mNextIndex] : null; } public void insertAfter( Node<T> pNode ) { pNode.validateAddable(); // implicit NPE if ( mCtrlStructure == null ) { throw new IllegalStateException( "Can't insert after a Node that is not currently attached to a list" ); } int zIndex = mCtrlStructure.add( pNode ); // implicit space check pNode.mNextIndex = mNextIndex; mNextIndex = zIndex; } private void validateAddable() { if ( mCtrlStructure != null ) { throw new IllegalArgumentException( "Node already attached to a list, and removal not currently supported" ); } } } private CtrlStructure<T> mCtrlStructure; private Integer mFirstIndex; public ArrayLinkList( int pMaxNodes ) { mCtrlStructure = new CtrlStructure( pMaxNodes ); } public Node<T> getFirstNode() { return (mFirstIndex != null) ? mCtrlStructure.mArray[mFirstIndex] : null; } /** * Note: this requires a scan of the List! */ public void insertAfter( Node<T> pNodeToLocate, Node<T> pNodeToInsert ) { mCtrlStructure.findRequired( pNodeToLocate ).insertAfter( pNodeToInsert ); } /** * Note: this requires a scan of the List! */ public void append( Node<T> pNode ) { if ( mCtrlStructure.mCellsUsed == 0 ) { insertFront( pNode ); } else { mCtrlStructure.findTail().insertAfter( pNode ); } } public void insertFront( Node<T> pNode ) { pNode.validateAddable(); // implicit NPE int zIndex = mCtrlStructure.add( pNode ); pNode.mNextIndex = mFirstIndex; mFirstIndex = zIndex; } private static class CtrlStructure<T> { private int mCellsUsed = 0; private Node<T>[] mArray; CtrlStructure( int pMaxNodes ) { mArray = new Node[pMaxNodes]; // implicit negative check } public int add( Node<T> pNode ) { if ( mArray.length <= mCellsUsed ) { throw new IllegalStateException( "Max Nodes (" + mArray.length + ") already used" ); } pNode.mCtrlStructure = this; mArray[mCellsUsed] = pNode; return mCellsUsed++; } public Node<T> findTail() { for ( int i = 0; i < mCellsUsed; i++ ) { Node<T> zNode = mArray[i]; if ( zNode.mNextIndex == null ) { return zNode; } } return null; } public Node<T> findRequired( Node<T> pNode ) { if ( pNode.mCtrlStructure == this ) // implicit NPE { for ( int i = 0; i < mCellsUsed; i++ ) { Node<T> zNode = mArray[i]; if ( zNode == pNode ) // Ownership controlled, so instance == is acceptable { return zNode; } } } throw new IllegalArgumentException( "Node Not a member of this list" ); } } } |
Commits for litesoft/trunk/GWT_Sandbox/UIdesign/src/com/test/uidesign/ArrayLinkList.java
Revision | Author | Commited | Message |
---|---|---|---|
589 | GeorgeS | Wed 18 Jan, 2012 19:16:02 +0000 | Unchecked & FE |