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.fusesource.hawtdb.util.list;
018    
019    public abstract class SortedLinkedListNode<T extends SortedLinkedListNode<T>> {
020    
021        protected SortedLinkedList<T> list;
022        protected T next;
023        protected T prev;
024    
025        public SortedLinkedListNode() {
026        }
027    
028        @SuppressWarnings("unchecked")
029        private T getThis() {
030            return (T) this;
031        }
032    
033        public T getHeadNode() {
034            return list.head;
035        }
036    
037        public T getTailNode() {
038            return list.head.prev;
039        }
040    
041        public T getNext() {
042            return isTailNode() ? null : next;
043        }
044    
045        public T getPrevious() {
046            return isHeadNode() ? null : prev;
047        }
048    
049        public T getNextCircular() {
050            return next;
051        }
052    
053        public T getPreviousCircular() {
054            return prev;
055        }
056    
057        public boolean isHeadNode() {
058            return list.head == this;
059        }
060    
061        public boolean isTailNode() {
062            return list.head.prev == this;
063        }
064    
065        /**
066         * Removes this node out of the linked list it is chained in.
067         */
068        public boolean unlink() {
069    
070            // If we are already unlinked...
071            if (list == null) {
072                return false;
073            }
074    
075            if (getThis() == prev) {
076                // We are the only item in the list
077                list.head = null;
078            } else {
079                // given we linked prev<->this<->next
080                next.prev = prev; // prev<-next
081                prev.next = next; // prev->next
082    
083                if (isHeadNode()) {
084                    list.head = next;
085                }
086            }
087            list.index.remove(this.getSequence());
088            list.size--;
089            list = null;
090            return true;
091        }
092    
093        private void addToIndex(T node, SortedLinkedList<T> list) {
094            if (node.list != null) {
095                throw new IllegalArgumentException("You only insert nodes that are not in a list");
096            }
097    
098            T old = list.index.put(node.getSequence(), node);
099            if(old != null)
100            {
101                list.index.put(old.getSequence(), old);
102                throw new IllegalArgumentException("A node with this key is already in the list");
103            }
104    
105            node.list = list;
106            list.size++;
107        }
108    
109        private final void checkLinkOk(T toLink) {
110            if (toLink == this) {
111                throw new IllegalArgumentException("You cannot link to yourself");
112            }
113    
114            if (list == null) {
115                throw new IllegalArgumentException("This node is not yet in a list");
116            }
117        }
118    
119        /**
120         * Adds the specified node to the head of the list.
121         * 
122         * @param sub
123         *            The sub list
124         */
125        protected void linkToHead(SortedLinkedList<T> target) {
126    
127            if (target.head == null) {
128                addToIndex(getThis(), target);
129                next = prev = target.head = getThis();
130            } else {
131                target.head.linkBefore(getThis());
132            }
133        }
134    
135        /**
136         * @param node
137         *            the node to link after this node.
138         * @return this
139         */
140        protected void linkAfter(T node) {
141            checkLinkOk(node);
142            addToIndex(node, list);
143    
144            // given we linked this<->next and are inserting node in between
145            node.prev = getThis(); // link this<-node
146            node.next = next; // link node->next
147            next.prev = node; // link node<-next
148            next = node; // this->node
149        }
150    
151        /**
152         * @param node
153         *            the node to link after this node.
154         * @return
155         * @return this
156         */
157        protected void linkBefore(T node) {
158            checkLinkOk(node);
159            addToIndex(node, list);
160    
161            // given we linked prev<->this and are inserting node in between
162            node.next = getThis(); // node->this
163            node.prev = prev; // prev<-node
164            prev.next = node; // prev->node
165            prev = node; // node<-this
166    
167            if (this == list.head) {
168                list.head = node;
169            }
170        }
171    
172        public abstract long getSequence(); 
173    
174        public boolean isLinked() {
175            return list != null;
176        }
177    
178        public SortedLinkedList<T> getList() {
179            return list;
180        }
181    }