litesoft
@ 976
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 |
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" ); } } } |