| ChainLink.java |
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 this(null);
39 }
40
41 /**
42 * Create a ChainLink containing an item.
43 *
44 * @param item this ChainLink's item
45 */
46 public ChainLink(E item) {
47 this.item = item;
48 this.head = true;
49 this.right = this;
50 this.left = this;
51 }
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 this.item = item;
60 }
61
62 /**
63 * Get the item from this ChainLink.
64 *
65 * @return the item
66 */
67 public E getItem() {
68 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 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 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 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 this.right.head = this.head;
109 this.right.left = this.left;
110 this.left.right = this.right;
111 this.head = true;
112 this.right = this;
113 this.left = this;
114 }
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 this.head = node.head; // This is head, iff node was
124 this.right = node;
125 this.left = node.left;
126 node.head = false; // node cannot now be head
127 node.left.right = this;
128 node.left = this;
129 }
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 this.head = false; // this can never be head
139 this.left = node;
140 this.right = node.right;
141 node.right.left = this;
142 node.right = this;
143 }
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 ChainLink<E> node = this;
153 while (!node.head) {
154 node = node.left;
155 if (this == node) {
156 // We made it all away round and nothing was marked head.
157 node.head = true;
158 }
159 }
160 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 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 ChainLink<E> node = anyNode.findHead();
181 addBefore(node);
182 }
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 ChainLink<E> node = anyNode.findHead();
192 addAfter(node.left);
193 }
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 ChainLink<E> node = this;
208 int cmp = comparator.compare(element, node.item);
209 if (cmp < 0) {
210 while (cmp < 0 && !node.head) {
211 node = node.left;
212 cmp = comparator.compare(element, node.item);
213 if (node == this) {
214 node.head = true;
215 }
216 }
217 return node;
218 } else if (cmp > 0) {
219 do {
220 node = node.right;
221 cmp = comparator.compare(element, node.item);
222 } while (cmp > 0 && !node.head && node != this);
223 return node;
224 }
225 return node;
226 }
227
228 private E item;
229 private boolean head;
230 private ChainLink<E> left;
231 private ChainLink<E> right;
232 }
233