Coverage Report

Coverage Report - org.crosswire.common.util.ChainLink

Classes in this File

Line Coverage

Branch Coverage

Complexity

ChainLink

0/62

0/20

1.8

 /**
  * Distribution License:
  * JSword is free software; you can redistribute it and/or modify it under
  * the terms of the GNU Lesser General Public License, version 2.1 or later
  * as published by the Free Software Foundation. This program is distributed
  * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
  * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU Lesser General Public License for more details.
  *
  * The License is available on the internet at:
  *      http://www.gnu.org/copyleft/lgpl.html
  * or by writing to:
  *      Free Software Foundation, Inc.
  *      59 Temple Place - Suite 330
  *      Boston, MA 02111-1307, USA
  *
  * © CrossWire Bible Society, 2015 - 2016
  */
 package org.crosswire.common.util;
 
 import java.util.Comparator;
 
 /**
  * ChainLink allows for a doubly linked list embedded within objects.
  * This is meant for small lists.
  *
  * @param <E> the class to be chained
  *
  * @see gnu.lgpl.License The GNU Lesser General Public License for details.
  * @author DM Smith
  */
 public final class ChainLink<E> {
     /**
      * Create an empty ChainLink.
      * It is necessary to call {@code setItem()} for this to be useful.
      */
     public ChainLink() {
         this(null);
     }
 
     /**
      * Create a ChainLink containing an item.
      * 
      * @param item this ChainLink's item
      */
     public ChainLink(E item) {
         this.item = item;
         this.head = true;
         this.right = this;
         this.left = this;
     }
 
     /**
      * Set the item for this ChainLink.
      * 
      * @param item this ChainLink's item
      */
     public void setItem(E item) {
         this.item = item;
     }
 
     /**
      * Get the item from this ChainLink.
      * 
      * @return the item
      */
     public E getItem() {
         return item;
     }
 
     /**
      * One node is marked as the head of the chain.
      * 
      * @return whether this node is the head of the chain.
      */
     public boolean isHead() {
         return head;
     }
 
     /**
      * Get the node to the left of this node.
      * The left node of the head is the tail.
      * 
      * @return the node to the left
      */
     public ChainLink<E> getLeft() {
         return left;
     }
 
     /**
      * Get the node to the right of this node.
      * The right node of the tail is the head.
      * 
      * @return the node to the right
      */
     public ChainLink<E> getRight() {
         return right;
     }
 
     /**
      * Remove this ChainLink from the chain.
      * If the head is removed, then the node that was to the right is now the head.
      */
     public void remove() {
         // First ensure that
         // this node is removed from its current list
         // and that that list is still whole
         this.right.head = this.head;
         this.right.left = this.left;
         this.left.right = this.right;
         this.head = true;
         this.right = this;
         this.left = this;
     }
 
     /**
      * Add this node before the given node.
      * If the given node was the head, then this node is now the head.
      * 
      * @param node A location in the chain for insertion.
      */
     public void addBefore(ChainLink<E> node) {
         this.head = node.head; // This is head, iff node was
         this.right = node;
         this.left = node.left;
         node.head = false; // node cannot now be head
         node.left.right = this;
         node.left = this;
     }
 
     /**
      * Add this node after the given node.
      * If the given node was the head, it still is.
      * 
      * @param node A location in the chain for insertion.
      */
     public void addAfter(ChainLink<E> node) {
         this.head = false; // this can never be head
         this.left = node;
         this.right = node.right;
         node.right.left = this;
         node.right = this;
     }
 
     /**
      * Find the head of the chain.
      * Note, this is most efficient if this node is the head.
      * 
      * @return the head of the chain.
      */
     public ChainLink<E> findHead() {
         ChainLink<E> node = this;
         while (!node.head) {
             node = node.left;
             if (this == node) {
                 // We made it all away round and nothing was marked head.
                 node.head = true;
             }
         }
         return node;
     }
 
     /**
      * Find the tail of the chain.
      * Note, this is most efficient if this node is the head.
      * 
      * @return the tail of the chain.
      */
     public ChainLink<E> findTail() {
         return findHead().left;
     }
 
     /**
      * Add this node as the head of the chain.
      * Note, this is most efficient if anyNode is the head of the chain.
      * 
      * @param anyNode any node in the chain
      */
     public void addFirst(ChainLink<E> anyNode) {
         ChainLink<E> node = anyNode.findHead();
         addBefore(node);
     }
 
     /**
      * Add this node as the tail of the chain.
      * Note, this is most efficient if anyNode is the head of the chain.
      * 
      * @param anyNode any node in the chain
      */
     public void addLast(ChainLink<E> anyNode) {
         ChainLink<E> node = anyNode.findHead();
         addAfter(node.left);
     }
 
     /**
      * Locate the node or the closest node in the chain using the comparator.
      * This assumes that the collection is ordered on some characteristic that
      * comparator assumes.
      * 
      * @param element The node to look for
      * @param comparator The comparator that understands the ordering of the list
      * @return The node or the closest node.
      */
     public ChainLink<E> locate(E element, Comparator<E> comparator) {
         // this node might be anywhere in the list.
         // compare it to this one
         ChainLink<E> node = this;
         int cmp = comparator.compare(element, node.item);
         if (cmp < 0) {
             while (cmp < 0 && !node.head) {
                 node = node.left;
                 cmp = comparator.compare(element, node.item);
                 if (node == this) {
                     node.head = true;
                 }
             }
             return node;
         } else if (cmp > 0) {
             do {
                 node = node.right;
                 cmp = comparator.compare(element, node.item);
             } while (cmp > 0 && !node.head && node != this);
             return node;
         }
         return node;
     }
 
     private E item;
     private boolean head;
     private ChainLink<E> left;
     private ChainLink<E> right;
 }

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		}