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 */
017package 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 */
025public 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}