View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.mina.util.byteaccess;
21  
22  import java.util.NoSuchElementException;
23  
24  /**
25   * A linked list that stores <code>ByteArray</code>s and maintains several useful invariants.
26   *
27   * @author <a href="http://mina.apache.org">Apache MINA Project</a>
28   */
29  class ByteArrayList {
30  
31      /**
32       * A {@link Node} which indicates the start and end of the list and does not
33       * hold a value. The value of <code>next</code> is the first item in the
34       * list. The value of of <code>previous</code> is the last item in the list.
35       */
36      private final Node header;
37  
38      /**
39       * The first byte in the array list
40       */
41      private int firstByte;
42  
43      /**
44       * The last byte in the array list
45       */
46      private int lastByte;
47  
48      /**
49       * 
50       * Creates a new instance of ByteArrayList.
51       *
52       */
53      protected ByteArrayList() {
54          header = new Node();
55      }
56  
57      /**
58       * 
59       * Returns the last byte in the array list
60       *
61       * @return
62       *  The last byte in the array list
63       */
64      public int lastByte() {
65          return lastByte;
66      }
67  
68      /**
69       * 
70       * Returns the first byte in the array list
71       *
72       * @return
73       *  The first byte in the array list
74       */
75      public int firstByte() {
76          return firstByte;
77      }
78  
79      /**
80       * 
81       * Check to see if this is empty
82       *
83       * @return
84       *  True if empty, otherwise false
85       */
86      public boolean isEmpty() {
87          return header.next == header;
88      }
89  
90      /**
91       * Returns the first node in the byte array
92       *
93       * @return
94       *  
95       */
96      public Node getFirst() {
97          return header.getNextNode();
98      }
99  
100     /**
101      * Returns the last {@link Node} in the list
102      *
103      * @return
104      *  The last node in the list
105      */
106     public Node getLast() {
107         return header.getPreviousNode();
108     }
109 
110     /**
111      * Adds the specified {@link ByteArray} to 
112      * the beginning of the list
113      *
114      * @param ba
115      *  The ByteArray to be added to the list
116      */
117     public void addFirst(ByteArray ba) {
118         addNode(new Node(ba), header.next);
119         firstByte -= ba.last();
120     }
121 
122     /**
123      * Add the specified {@link ByteArray} to 
124      * the end of the list 
125      *
126      * @param ba
127      *  The ByteArray to be added to the list
128      */
129     public void addLast(ByteArray ba) {
130         addNode(new Node(ba), header);
131         lastByte += ba.last();
132     }
133 
134     /**
135      * Removes the first node from this list
136      *
137      * @return
138      *  The node that was removed
139      */
140     public Node removeFirst() {
141         Node node = header.getNextNode();
142         firstByte += node.ba.last();
143         return removeNode(node);
144     }
145 
146     /**
147      * Removes the last node in this list
148      *
149      * @return
150      *  The node that was taken off of the list
151      */
152     public Node removeLast() {
153         Node node = header.getPreviousNode();
154         lastByte -= node.ba.last();
155         return removeNode(node);
156     }
157 
158     //-----------------------------------------------------------------------
159 
160     /**
161      * Inserts a new node into the list.
162      *
163      * @param nodeToInsert  new node to insert
164      * @param insertBeforeNode  node to insert before
165      */
166     protected void addNode(Node nodeToInsert, Node insertBeforeNode) {
167         // Insert node.
168         nodeToInsert.next = insertBeforeNode;
169         nodeToInsert.previous = insertBeforeNode.previous;
170         insertBeforeNode.previous.next = nodeToInsert;
171         insertBeforeNode.previous = nodeToInsert;
172     }
173 
174     /**
175      * Removes the specified node from the list.
176      *
177      * @param node  the node to remove
178      */
179     protected Node removeNode(Node node) {
180         // Remove node.
181         node.previous.next = node.next;
182         node.next.previous = node.previous;
183         node.removed = true;
184         return node;
185     }
186 
187     //-----------------------------------------------------------------------
188     /**
189      * A node within the linked list.
190      * <p>
191      * From Commons Collections 3.1, all access to the <code>value</code> property
192      * is via the methods on this class.
193      */
194     public class Node {
195 
196         /** A pointer to the node before this node */
197         private Node previous;
198 
199         /** A pointer to the node after this node */
200         private Node next;
201 
202         /** The ByteArray contained within this node */
203         private ByteArray ba;
204 
205         private boolean removed;
206 
207         /**
208          * Constructs a new header node.
209          */
210         private Node() {
211             super();
212             previous = this;
213             next = this;
214         }
215 
216         /**
217          * Constructs a new node with a value.
218          */
219         private Node(ByteArray ba) {
220             super();
221 
222             if (ba == null) {
223                 throw new IllegalArgumentException("ByteArray must not be null.");
224             }
225 
226             this.ba = ba;
227         }
228 
229         /**
230          * Gets the previous node.
231          *
232          * @return the previous node
233          */
234         public Node getPreviousNode() {
235             if (!hasPreviousNode()) {
236                 throw new NoSuchElementException();
237             }
238             return previous;
239         }
240 
241         /**
242          * Gets the next node.
243          *
244          * @return the next node
245          */
246         public Node getNextNode() {
247             if (!hasNextNode()) {
248                 throw new NoSuchElementException();
249             }
250             return next;
251         }
252 
253         public boolean hasPreviousNode() {
254             return previous != header;
255         }
256 
257         public boolean hasNextNode() {
258             return next != header;
259         }
260 
261         public ByteArray getByteArray() {
262             return ba;
263         }
264 
265         public boolean isRemoved() {
266             return removed;
267         }
268     }
269 
270 }