Coverage Report - org.crosswire.common.util.ChainLink
 
Classes in this File Line Coverage Branch Coverage Complexity
ChainLink
0%
0/62
0%
0/20
1.8
 
 1  
 /**
 2  
  * Distribution License:
 3  
  * JSword is free software; you can redistribute it and/or modify it under
 4  
  * the terms of the GNU Lesser General Public License, version 2.1 or later
 5  
  * as published by the Free Software Foundation. This program is distributed
 6  
  * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
 7  
  * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 8  
  * See the GNU Lesser General Public License for more details.
 9  
  *
 10  
  * The License is available on the internet at:
 11  
  *      http://www.gnu.org/copyleft/lgpl.html
 12  
  * or by writing to:
 13  
  *      Free Software Foundation, Inc.
 14  
  *      59 Temple Place - Suite 330
 15  
  *      Boston, MA 02111-1307, USA
 16  
  *
 17  
  * © CrossWire Bible Society, 2015 - 2016
 18  
  */
 19  
 package org.crosswire.common.util;
 20  
 
 21  
 import java.util.Comparator;
 22  
 
 23  
 /**
 24  
  * ChainLink allows for a doubly linked list embedded within objects.
 25  
  * This is meant for small lists.
 26  
  *
 27  
  * @param <E> the class to be chained
 28  
  *
 29  
  * @see gnu.lgpl.License The GNU Lesser General Public License for details.
 30  
  * @author DM Smith
 31  
  */
 32  
 public final class ChainLink<E> {
 33  
     /**
 34  
      * Create an empty ChainLink.
 35  
      * It is necessary to call {@code setItem()} for this to be useful.
 36  
      */
 37  
     public ChainLink() {
 38  0
         this(null);
 39  0
     }
 40  
 
 41  
     /**
 42  
      * Create a ChainLink containing an item.
 43  
      * 
 44  
      * @param item this ChainLink's item
 45  
      */
 46  0
     public ChainLink(E item) {
 47  0
         this.item = item;
 48  0
         this.head = true;
 49  0
         this.right = this;
 50  0
         this.left = this;
 51  0
     }
 52  
 
 53  
     /**
 54  
      * Set the item for this ChainLink.
 55  
      * 
 56  
      * @param item this ChainLink's item
 57  
      */
 58  
     public void setItem(E item) {
 59  0
         this.item = item;
 60  0
     }
 61  
 
 62  
     /**
 63  
      * Get the item from this ChainLink.
 64  
      * 
 65  
      * @return the item
 66  
      */
 67  
     public E getItem() {
 68  0
         return item;
 69  
     }
 70  
 
 71  
     /**
 72  
      * One node is marked as the head of the chain.
 73  
      * 
 74  
      * @return whether this node is the head of the chain.
 75  
      */
 76  
     public boolean isHead() {
 77  0
         return head;
 78  
     }
 79  
 
 80  
     /**
 81  
      * Get the node to the left of this node.
 82  
      * The left node of the head is the tail.
 83  
      * 
 84  
      * @return the node to the left
 85  
      */
 86  
     public ChainLink<E> getLeft() {
 87  0
         return left;
 88  
     }
 89  
 
 90  
     /**
 91  
      * Get the node to the right of this node.
 92  
      * The right node of the tail is the head.
 93  
      * 
 94  
      * @return the node to the right
 95  
      */
 96  
     public ChainLink<E> getRight() {
 97  0
         return right;
 98  
     }
 99  
 
 100  
     /**
 101  
      * Remove this ChainLink from the chain.
 102  
      * If the head is removed, then the node that was to the right is now the head.
 103  
      */
 104  
     public void remove() {
 105  
         // First ensure that
 106  
         // this node is removed from its current list
 107  
         // and that that list is still whole
 108  0
         this.right.head = this.head;
 109  0
         this.right.left = this.left;
 110  0
         this.left.right = this.right;
 111  0
         this.head = true;
 112  0
         this.right = this;
 113  0
         this.left = this;
 114  0
     }
 115  
 
 116  
     /**
 117  
      * Add this node before the given node.
 118  
      * If the given node was the head, then this node is now the head.
 119  
      * 
 120  
      * @param node A location in the chain for insertion.
 121  
      */
 122  
     public void addBefore(ChainLink<E> node) {
 123  0
         this.head = node.head; // This is head, iff node was
 124  0
         this.right = node;
 125  0
         this.left = node.left;
 126  0
         node.head = false; // node cannot now be head
 127  0
         node.left.right = this;
 128  0
         node.left = this;
 129  0
     }
 130  
 
 131  
     /**
 132  
      * Add this node after the given node.
 133  
      * If the given node was the head, it still is.
 134  
      * 
 135  
      * @param node A location in the chain for insertion.
 136  
      */
 137  
     public void addAfter(ChainLink<E> node) {
 138  0
         this.head = false; // this can never be head
 139  0
         this.left = node;
 140  0
         this.right = node.right;
 141  0
         node.right.left = this;
 142  0
         node.right = this;
 143  0
     }
 144  
 
 145  
     /**
 146  
      * Find the head of the chain.
 147  
      * Note, this is most efficient if this node is the head.
 148  
      * 
 149  
      * @return the head of the chain.
 150  
      */
 151  
     public ChainLink<E> findHead() {
 152  0
         ChainLink<E> node = this;
 153  0
         while (!node.head) {
 154  0
             node = node.left;
 155  0
             if (this == node) {
 156  
                 // We made it all away round and nothing was marked head.
 157  0
                 node.head = true;
 158  
             }
 159  
         }
 160  0
         return node;
 161  
     }
 162  
 
 163  
     /**
 164  
      * Find the tail of the chain.
 165  
      * Note, this is most efficient if this node is the head.
 166  
      * 
 167  
      * @return the tail of the chain.
 168  
      */
 169  
     public ChainLink<E> findTail() {
 170  0
         return findHead().left;
 171  
     }
 172  
 
 173  
     /**
 174  
      * Add this node as the head of the chain.
 175  
      * Note, this is most efficient if anyNode is the head of the chain.
 176  
      * 
 177  
      * @param anyNode any node in the chain
 178  
      */
 179  
     public void addFirst(ChainLink<E> anyNode) {
 180  0
         ChainLink<E> node = anyNode.findHead();
 181  0
         addBefore(node);
 182  0
     }
 183  
 
 184  
     /**
 185  
      * Add this node as the tail of the chain.
 186  
      * Note, this is most efficient if anyNode is the head of the chain.
 187  
      * 
 188  
      * @param anyNode any node in the chain
 189  
      */
 190  
     public void addLast(ChainLink<E> anyNode) {
 191  0
         ChainLink<E> node = anyNode.findHead();
 192  0
         addAfter(node.left);
 193  0
     }
 194  
 
 195  
     /**
 196  
      * Locate the node or the closest node in the chain using the comparator.
 197  
      * This assumes that the collection is ordered on some characteristic that
 198  
      * comparator assumes.
 199  
      * 
 200  
      * @param element The node to look for
 201  
      * @param comparator The comparator that understands the ordering of the list
 202  
      * @return The node or the closest node.
 203  
      */
 204  
     public ChainLink<E> locate(E element, Comparator<E> comparator) {
 205  
         // this node might be anywhere in the list.
 206  
         // compare it to this one
 207  0
         ChainLink<E> node = this;
 208  0
         int cmp = comparator.compare(element, node.item);
 209  0
         if (cmp < 0) {
 210  0
             while (cmp < 0 && !node.head) {
 211  0
                 node = node.left;
 212  0
                 cmp = comparator.compare(element, node.item);
 213  0
                 if (node == this) {
 214  0
                     node.head = true;
 215  
                 }
 216  
             }
 217  0
             return node;
 218  0
         } else if (cmp > 0) {
 219  
             do {
 220  0
                 node = node.right;
 221  0
                 cmp = comparator.compare(element, node.item);
 222  0
             } while (cmp > 0 && !node.head && node != this);
 223  0
             return node;
 224  
         }
 225  0
         return node;
 226  
     }
 227  
 
 228  
     private E item;
 229  
     private boolean head;
 230  
     private ChainLink<E> left;
 231  
     private ChainLink<E> right;
 232  
 }