Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
ChainLink |
|
| 1.8;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 | } |