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 }