1 // ******************************************************************************
2 //
3 // Title: Force Field X.
4 // Description: Force Field X - Software for Molecular Biophysics.
5 // Copyright: Copyright (c) Michael J. Schnieders 2001-2025.
6 //
7 // This file is part of Force Field X.
8 //
9 // Force Field X is free software; you can redistribute it and/or modify it
10 // under the terms of the GNU General Public License version 3 as published by
11 // the Free Software Foundation.
12 //
13 // Force Field X is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 // FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
16 // details.
17 //
18 // You should have received a copy of the GNU General Public License along with
19 // Force Field X; if not, write to the Free Software Foundation, Inc., 59 Temple
20 // Place, Suite 330, Boston, MA 02111-1307 USA
21 //
22 // Linking this library statically or dynamically with other modules is making a
23 // combined work based on this library. Thus, the terms and conditions of the
24 // GNU General Public License cover the whole combination.
25 //
26 // As a special exception, the copyright holders of this library give you
27 // permission to link this library with independent modules to produce an
28 // executable, regardless of the license terms of these independent modules, and
29 // to copy and distribute the resulting executable under terms of your choice,
30 // provided that you also meet, for each linked independent module, the terms
31 // and conditions of the license of that module. An independent module is a
32 // module which is not derived from or based on this library. If you modify this
33 // library, you may extend this exception to your version of the library, but
34 // you are not obligated to do so. If you do not wish to do so, delete this
35 // exception statement from your version.
36 //
37 // ******************************************************************************
38 package ffx.numerics.quickhull;
39
40 /**
41 * Maintains a double-linked list of vertices for use by QuickHull3D.
42 *
43 * @author John E. Lloyd, Fall 2004
44 * @author Michael J. Schnieders
45 * @since 1.0
46 */
47 class VertexList {
48
49 private Vertex head;
50
51 private Vertex tail;
52
53 /**
54 * Clears this list.
55 */
56 public void clear() {
57 head = tail = null;
58 }
59
60 /**
61 * Adds a vertex to the end of this list.
62 *
63 * @param vtx Vertex to add
64 */
65 public void add(Vertex vtx) {
66 if (head == null) {
67 head = vtx;
68 } else {
69 tail.next = vtx;
70 }
71 vtx.prev = tail;
72 vtx.next = null;
73 tail = vtx;
74 }
75
76 /**
77 * Adds a chain of vertices to the end of this list.
78 * The provided vertex is assumed to be the head of the chain.
79 *
80 * @param vtx head of the vertex chain to append
81 */
82 public void addAll(Vertex vtx) {
83 if (head == null) {
84 head = vtx;
85 } else {
86 tail.next = vtx;
87 }
88 vtx.prev = tail;
89 while (vtx.next != null) {
90 vtx = vtx.next;
91 }
92 tail = vtx;
93 }
94
95 /**
96 * Deletes a single vertex from this list.
97 *
98 * @param vtx the vertex to remove
99 */
100 public void delete(Vertex vtx) {
101 if (vtx.prev == null) {
102 head = vtx.next;
103 } else {
104 vtx.prev.next = vtx.next;
105 }
106 if (vtx.next == null) {
107 tail = vtx.prev;
108 } else {
109 vtx.next.prev = vtx.prev;
110 }
111 }
112
113 /**
114 * Deletes a contiguous chain of vertices from this list.
115 *
116 * @param vtx1 the first vertex in the chain to remove
117 * @param vtx2 the last vertex in the chain to remove
118 */
119 public void delete(Vertex vtx1, Vertex vtx2) {
120 if (vtx1.prev == null) {
121 head = vtx2.next;
122 } else {
123 vtx1.prev.next = vtx2.next;
124 }
125 if (vtx2.next == null) {
126 tail = vtx1.prev;
127 } else {
128 vtx2.next.prev = vtx1.prev;
129 }
130 }
131
132 /**
133 * Inserts a vertex into this list before another specified vertex.
134 *
135 * @param vtx the vertex to insert
136 * @param next the vertex before which to insert vtx
137 */
138 public void insertBefore(Vertex vtx, Vertex next) {
139 vtx.prev = next.prev;
140 if (next.prev == null) {
141 head = vtx;
142 } else {
143 next.prev.next = vtx;
144 }
145 vtx.next = next;
146 next.prev = vtx;
147 }
148
149 /**
150 * Returns the first vertex in this list (head), or null if empty.
151 *
152 * @return the first Vertex, or null if the list is empty
153 */
154 public Vertex first() {
155 return head;
156 }
157
158 /**
159 * Returns true if this list is empty.
160 *
161 * @return true if there are no vertices in the list
162 */
163 public boolean isEmpty() {
164 return head == null;
165 }
166 }