Save This Page
Home » activemq-parent-5.3.1-source-release » org.apache.kahadb.util » [javadoc | source]
    1   /**
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
   10    *
   11    * Unless required by applicable law or agreed to in writing, software
   12    * distributed under the License is distributed on an "AS IS" BASIS,
   13    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   14    * See the License for the specific language governing permissions and
   15    * limitations under the License.
   16    */
   17   package org.apache.kahadb.util;
   18   
   19   /**
   20    * Provides a base class for you to extend when you want object to maintain a
   21    * doubly linked list to other objects without using a collection class.
   22    * 
   23    * @author chirino
   24    */
   25   public class LinkedNode<T extends LinkedNode<T>> {
   26   
   27       protected LinkedNodeList<T> list;
   28       protected T next;
   29       protected T prev;
   30   
   31       public LinkedNode() {
   32       }
   33   
   34       @SuppressWarnings("unchecked")
   35       private T getThis() {
   36           return (T) this;
   37       }
   38   
   39       public T getHeadNode() {
   40           return list.head;
   41       }
   42   
   43       public T getTailNode() {
   44           return list.head.prev;
   45       }
   46   
   47       public T getNext() {
   48           return isTailNode() ? null : next;
   49       }
   50   
   51       public T getPrevious() {
   52           return isHeadNode() ? null : prev;
   53       }
   54   
   55       public T getNextCircular() {
   56           return next;
   57       }
   58   
   59       public T getPreviousCircular() {
   60           return prev;
   61       }
   62   
   63       public boolean isHeadNode() {
   64           return list.head == this;
   65       }
   66   
   67       public boolean isTailNode() {
   68           return list.head.prev == this;
   69       }
   70   
   71       /**
   72        * @param node
   73        *            the node to link after this node.
   74        * @return this
   75        */
   76       public void linkAfter(T node) {
   77           if (node == this) {
   78               throw new IllegalArgumentException("You cannot link to yourself");
   79           }
   80           if (node.list != null) {
   81               throw new IllegalArgumentException("You only insert nodes that are not in a list");
   82           }
   83           if (list == null) {
   84               throw new IllegalArgumentException("This node is not yet in a list");
   85           }
   86   
   87           node.list = list;
   88   
   89           // given we linked this<->next and are inserting node in between
   90           node.prev = getThis(); // link this<-node
   91           node.next = next; // link node->next
   92           next.prev = node; // link node<-next
   93           next = node; // this->node
   94           list.size++;
   95       }
   96   
   97       /**
   98        * @param rightList
   99        *            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   }

Save This Page
Home » activemq-parent-5.3.1-source-release » org.apache.kahadb.util » [javadoc | source]