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 /** 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 node"); 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 newList.size++; 266 list.size--; 267 do { 268 n.list = newList; 269 n = n.next; 270 newList.size++; 271 list.size--; 272 } while (n != newList.head); 273 274 return newList; 275 } 276 277 /** 278 * Splits the list into 2 lists. This node becomes the head of this list. 279 * Then 2nd list is returned. 280 * 281 * @return An empty list if this is a head node. 282 */ 283 public LinkedNodeList<T> splitBefore() { 284 285 if (isHeadNode()) { 286 return new LinkedNodeList<T>(); 287 } 288 289 // Create the new list 290 LinkedNodeList<T> newList = new LinkedNodeList<T>(); 291 newList.head = list.head; 292 list.head = getThis(); 293 294 T newListTail = prev; 295 296 prev = newList.head.prev; // old list: tail<-head 297 prev.next = getThis(); // old list: tail->head 298 newList.head.prev = newListTail; // new list: tail<-head 299 newListTail.next = newList.head; // new list: tail->head 300 301 // Update all the nodes in the new list so that they know of their new 302 // list owner. 303 T n = newList.head; 304 newList.size++; 305 list.size--; 306 do { 307 n.list = newList; 308 n = n.next; 309 newList.size++; 310 list.size--; 311 } while (n != newList.head); 312 313 return newList; 314 } 315 316 public boolean isLinked() { 317 return list != null; 318 } 319 320 public LinkedNodeList<T> getList() { 321 return list; 322 } 323 324 }