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