001    /**
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.activemq.store.kahadb.disk.util;
018    
019    /**
020     * Provides a base class for you to extend when you want object to maintain a
021     * doubly linked list to other objects without using a collection class.
022     * 
023     * @author chirino
024     */
025    public class LinkedNode<T extends LinkedNode<T>> {
026    
027        protected LinkedNodeList<T> list;
028        protected T next;
029        protected T prev;
030    
031        public LinkedNode() {
032        }
033    
034        @SuppressWarnings("unchecked")
035        private T getThis() {
036            return (T) this;
037        }
038    
039        public T getHeadNode() {
040            return list.head;
041        }
042    
043        public T getTailNode() {
044            return list.head.prev;
045        }
046    
047        public T getNext() {
048            return isTailNode() ? null : next;
049        }
050    
051        public T getPrevious() {
052            return isHeadNode() ? null : prev;
053        }
054    
055        public T getNextCircular() {
056            return next;
057        }
058    
059        public T getPreviousCircular() {
060            return prev;
061        }
062    
063        public boolean isHeadNode() {
064            return list.head == this;
065        }
066    
067        public boolean isTailNode() {
068            return list.head.prev == this;
069        }
070    
071        /**
072         * @param node
073         *            the node to link after this node.
074         * @return this
075         */
076        public void linkAfter(T node) {
077            if (node == this) {
078                throw new IllegalArgumentException("You cannot link to yourself");
079            }
080            if (node.list != null) {
081                throw new IllegalArgumentException("You only insert nodes that are not in a list");
082            }
083            if (list == null) {
084                throw new IllegalArgumentException("This node is not yet in a list");
085            }
086    
087            node.list = list;
088    
089            // given we linked this<->next and are inserting node in between
090            node.prev = getThis(); // link this<-node
091            node.next = next; // link node->next
092            next.prev = node; // link node<-next
093            next = node; // this->node
094            list.size++;
095        }
096    
097        /**
098         * @param rightList
099         *            the node to link after this node.
100         * @return this
101         */
102        public void linkAfter(LinkedNodeList<T> rightList) {
103    
104            if (rightList == list) {
105                throw new IllegalArgumentException("You cannot link to yourself");
106            }
107            if (list == null) {
108                throw new IllegalArgumentException("This node is not yet in a list");
109            }
110    
111            T rightHead = rightList.head;
112            T rightTail = rightList.head.prev;
113            list.reparent(rightList);
114    
115            // given we linked this<->next and are inserting list in between
116            rightHead.prev = getThis(); // link this<-list
117            rightTail.next = next; // link list->next
118            next.prev = rightTail; // link list<-next
119            next = rightHead; // this->list
120        }
121    
122        /**
123         * @param node
124         *            the node to link after this node.
125         * @return
126         * @return this
127         */
128        public void linkBefore(T node) {
129    
130            if (node == this) {
131                throw new IllegalArgumentException("You cannot link to yourself");
132            }
133            if (node.list != null) {
134                throw new IllegalArgumentException("You only insert nodes that are not in a list");
135            }
136            if (list == null) {
137                throw new IllegalArgumentException("This node is not yet in a list");
138            }
139    
140            node.list = list;
141    
142            // given we linked prev<->this and are inserting node in between
143            node.next = getThis(); // node->this
144            node.prev = prev; // prev<-node
145            prev.next = node; // prev->node
146            prev = node; // node<-this
147    
148            if (this == list.head) {
149                list.head = node;
150            }
151            list.size++;
152        }
153    
154        /**
155         * @param leftList
156         *            the node to link after this node.
157         * @return
158         * @return this
159         */
160        public void linkBefore(LinkedNodeList<T> leftList) {
161    
162            if (leftList == list) {
163                throw new IllegalArgumentException("You cannot link to yourself");
164            }
165            if (list == null) {
166                throw new IllegalArgumentException("This node is not yet in a list");
167            }
168    
169            T leftHead = leftList.head;
170            T leftTail = leftList.head.prev;
171            list.reparent(leftList);
172    
173            // given we linked prev<->this and are inserting list in between
174            leftTail.next = getThis(); // list->this
175            leftHead.prev = prev; // prev<-list
176            prev.next = leftHead; // prev->list
177            prev = leftTail; // list<-this
178    
179            if (isHeadNode()) {
180                list.head = leftHead;
181            }
182        }
183    
184        public void linkToTail(LinkedNodeList<T> target) {
185            if (list != null) {
186                throw new IllegalArgumentException("This node is already linked to a node");
187            }
188    
189            if (target.head == null) {
190                next = prev = target.head = getThis();
191                list = target;
192                list.size++;
193            } else {
194                target.head.prev.linkAfter(getThis());
195            }
196        }
197    
198        public void linkToHead(LinkedNodeList<T> target) {
199            if (list != null) {
200                throw new IllegalArgumentException("This node is already linked to a list");
201            }
202    
203            if (target.head == null) {
204                next = prev = target.head = getThis();
205                list = target;
206                list.size++;
207            } else {
208                target.head.linkBefore(getThis());
209            }
210        }
211    
212        /**
213         * Removes this node out of the linked list it is chained in.
214         */
215        public boolean unlink() {
216    
217            // If we are allready unlinked...
218            if (list == null) {
219                return false;
220            }
221    
222            if (getThis() == prev) {
223                // We are the only item in the list
224                list.head = null;
225            } else {
226                // given we linked prev<->this<->next
227                next.prev = prev; // prev<-next
228                prev.next = next; // prev->next
229    
230                if (isHeadNode()) {
231                    list.head = next;
232                }
233            }
234            list.size--;
235            list = null;
236            return true;
237        }
238    
239        /**
240         * Splits the list into 2 lists. This node becomes the tail of this list.
241         * Then 2nd list is returned.
242         * 
243         * @return An empty list if this is a tail node.
244         */
245        public LinkedNodeList<T> splitAfter() {
246    
247            if (isTailNode()) {
248                return new LinkedNodeList<T>();
249            }
250    
251            // Create the new list
252            LinkedNodeList<T> newList = new LinkedNodeList<T>();
253            newList.head = next;
254    
255            // Update the head and tail of the new list so that they point to each
256            // other.
257            newList.head.prev = list.head.prev; // new list: tail<-head
258            newList.head.prev.next = newList.head; // new list: tail->head
259            next = list.head; // old list: tail->head
260            list.head.prev = getThis(); // old list: tail<-head
261    
262            // Update all the nodes in the new list so that they know of their new
263            // list owner.
264            T n = newList.head;
265            do {
266                n.list = newList;
267                n = n.next;
268                newList.size++;
269                list.size--;
270            } while (n != newList.head);
271    
272            return newList;
273        }
274    
275        /**
276         * Splits the list into 2 lists. This node becomes the head of this list.
277         * Then 2nd list is returned.
278         * 
279         * @return An empty list if this is a head node.
280         */
281        public LinkedNodeList<T> splitBefore() {
282    
283            if (isHeadNode()) {
284                return new LinkedNodeList<T>();
285            }
286    
287            // Create the new list
288            LinkedNodeList<T> newList = new LinkedNodeList<T>();
289            newList.head = list.head;
290            list.head = getThis();
291    
292            T newListTail = prev;
293    
294            prev = newList.head.prev; // old list: tail<-head
295            prev.next = getThis(); // old list: tail->head
296            newList.head.prev = newListTail; // new list: tail<-head
297            newListTail.next = newList.head; // new list: tail->head
298    
299            // Update all the nodes in the new list so that they know of their new
300            // list owner.
301            T n = newList.head;
302            do {
303                n.list = newList;
304                n = n.next;
305                newList.size++;
306                list.size--;
307            } while (n != newList.head);
308    
309            return newList;
310        }
311    
312        public boolean isLinked() {
313            return list != null;
314        }
315    
316            public LinkedNodeList<T> getList() {
317                    return list;
318            }
319    
320    }