evolvedbinary / j8cu / 92

Committed 25 Feb 2025 12:59AM UTC coverage: 95.844% (-4.2%) from 100.0%

Build # 92

Build Type

push

circleci

Committed by

adamretter

Commit Message

Add reverse to string to doubly linked list for debugging

Run Details

0 of 9 new or added lines in 1 file covered. (0.0%)

2 existing lines in 1 file now uncovered.

369 of 385 relevant lines covered (95.84%)

0.96 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.0

/src/main/java/com/evolvedbinary/j8cu/list/linked/DoublyLinkedList.java

/*
 * Copyright © 2025, Evolved Binary Ltd. <tech@evolvedbinary.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.evolvedbinary.j8cu.list.linked;

import org.jspecify.annotations.Nullable;

import java.util.Collections;
import java.util.Iterator;

/**
 * Basic Linked List implementation where nodes have `next` and `prev` links.
 *
 * @author <a href="mailto:adam@evolvedbinary.com">Adam Retter</a>
 */
public class DoublyLinkedList<T> extends AbstractLinkedList<T, DoublyLinkedNode<T>> {

    public DoublyLinkedList() {
        this(0);
    }

    /**
     * @param nodeCacheSize the size of the cache to use for reusing nodes that are removed.
     */
    public DoublyLinkedList(final int nodeCacheSize) {
        super(nodeCacheSize);
    }

    @Override
    public boolean add(@Nullable final T element) {
        final DoublyLinkedNode<T> newNode = createNode(element);
        if (head == null) {
            this.head = newNode;
        } else {
            newNode.previous = this.last;
            this.last.next = newNode;
        }

        this.last = newNode;
        return true;
    }

    @Override
    DoublyLinkedNode<T> newNode(final T element) {
        return new DoublyLinkedNode<>(element);
    }

    /**
     * Return an iterator that progresses over this list in reverse order (i.e. from end to start).
     *
     * @return an iterator that moves in a reverse direction over this list.
     */
    public Iterator<T> reverseIterator() {
        if (last == null) {
            // is empty
            return Collections.emptyIterator();
        }
        return new LinkedListReverseIterator<>(last);
    }

    @Override
    protected long remove(@Nullable final T element, final RemovalMode removalMode) {
        if (RemovalMode.REMOVE_ONE == removalMode && last != null && last.data == element) {
            // optimisation for removing the `last` node when removing any one node
            DoublyLinkedNode<T> node = last;
            if (last == head) {
                // there was only one node
                head = null;
                last = null;
            } else {
                last = last.previous;
                last.next = null;
            }
            discardNode(node);
            return 1;
        }

        long removed = 0;

        @Nullable DoublyLinkedNode<T> node = head;
        @Nullable DoublyLinkedNode<T> prevNode = null;
        while (node != null) {

            if (element == node.data) {
                // matched element

                if (prevNode == null) {
                    // element matched the head node

                    if (last == head) {
                        // list only had one item, so we also need to reset `last`
                        last = null;
                    }

                    // move the current node to the `head` node
                    final DoublyLinkedNode<T> next = node.next;
                    if (next != null) {
                        next.previous = null;
                    }
                    head = next;

                } else {
                    // element matched a non-head node

                    if (last == node) {
                        // we are unlinking the last node, so we need to update the `last` reference
                        last = prevNode;
                    }

                    // unlink this `node`
                    final DoublyLinkedNode<T> next = node.next;
                    if (next != null) {
                        next.previous = prevNode;
                    }
                    prevNode.next  = next;
                }

                discardNode(node);

                if (removed < Long.MAX_VALUE) {
                    removed++;
                }

                if (RemovalMode.REMOVE_ALL != removalMode) {
                    // REMOVE_FIRST or REMOVE_ONE so we just need one result
                    break;
                }

            } else {
                // store the node as the previous node for the next iteration
                prevNode = node;
            }

            // prepare for next iteration...
            node = node.next;
        }

        return removed;
    }

    /**
     * Similar to {@link AbstractLinkedList#toString()}
     * but prints out the elements in reverse order.
     */
    public String toReverseString() {
        final StringBuilder builder = new StringBuilder();
        builder.append('[');
        final Iterator<T> iterator = reverseIterator();
        while (iterator.hasNext()) {
            builder.append(iterator.next());
            if (iterator.hasNext()) {
                builder.append(", ");
            }
        }
        builder.append(']');
        return builder.toString();
    }
}

1	/*
2	* Copyright © 2025, Evolved Binary Ltd. <tech@evolvedbinary.com>
3	* All rights reserved.
4	*
5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions are met:
7	* * Redistributions of source code must retain the above copyright
8	* notice, this list of conditions and the following disclaimer.
9	* * Redistributions in binary form must reproduce the above copyright
10	* notice, this list of conditions and the following disclaimer in the
11	* documentation and/or other materials provided with the distribution.
12	* * Neither the name of the <organization> nor the
13	* names of its contributors may be used to endorse or promote products
14	* derived from this software without specific prior written permission.
15	*
16	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19	* DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
20	* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21	* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22	* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25	* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26	*/
27	package com.evolvedbinary.j8cu.list.linked;
28
29	import org.jspecify.annotations.Nullable;
30
31	import java.util.Collections;
32	import java.util.Iterator;
33
34	/**
35	* Basic Linked List implementation where nodes have `next` and `prev` links.
36	*
37	* @author <a href="mailto:adam@evolvedbinary.com">Adam Retter</a>
38	*/
39	public class DoublyLinkedList<T> extends AbstractLinkedList<T, DoublyLinkedNode<T>> {
40
41	public DoublyLinkedList() {
42	this(0);	1✔
43	}	1✔
44
45	/**
46	* @param nodeCacheSize the size of the cache to use for reusing nodes that are removed.
47	*/
48	public DoublyLinkedList(final int nodeCacheSize) {
49	super(nodeCacheSize);	1✔
50	}	1✔
51
52	@Override
53	public boolean add(@Nullable final T element) {
54	final DoublyLinkedNode<T> newNode = createNode(element);	1✔
55	if (head == null) {	1✔
56	this.head = newNode;	1✔
57	} else {
58	newNode.previous = this.last;	1✔
59	this.last.next = newNode;	1✔
60	}
61
62	this.last = newNode;	1✔
63	return true;	1✔
64	}
65
66	@Override
67	DoublyLinkedNode<T> newNode(final T element) {
68	return new DoublyLinkedNode<>(element);	1✔
69	}
70
71	/**
72	* Return an iterator that progresses over this list in reverse order (i.e. from end to start).
73	*
74	* @return an iterator that moves in a reverse direction over this list.
75	*/
76	public Iterator<T> reverseIterator() {
77	if (last == null) {	1✔
78	// is empty
79	return Collections.emptyIterator();	1✔
80	}
81	return new LinkedListReverseIterator<>(last);	1✔
82	}
83
84	@Override
85	protected long remove(@Nullable final T element, final RemovalMode removalMode) {
86	if (RemovalMode.REMOVE_ONE == removalMode && last != null && last.data == element) {	1✔
87	// optimisation for removing the `last` node when removing any one node
88	DoublyLinkedNode<T> node = last;	1✔
89	if (last == head) {	1✔
90	// there was only one node
91	head = null;	1✔
92	last = null;	1✔
93	} else {
94	last = last.previous;	1✔
95	last.next = null;	1✔
96	}
97	discardNode(node);	1✔
98	return 1;	1✔
99	}
100
101	long removed = 0;	1✔
102
103	@Nullable DoublyLinkedNode<T> node = head;	1✔
104	@Nullable DoublyLinkedNode<T> prevNode = null;	1✔
105	while (node != null) {	1✔
106
107	if (element == node.data) {	1✔
108	// matched element
109
110	if (prevNode == null) {	1✔
111	// element matched the head node
112
113	if (last == head) {	1✔
114	// list only had one item, so we also need to reset `last`
115	last = null;	1✔
116	}
117
118	// move the current node to the `head` node
119	final DoublyLinkedNode<T> next = node.next;	1✔
120	if (next != null) {	1✔
121	next.previous = null;	1✔
122	}
123	head = next;	1✔
124
125	} else {	1✔
126	// element matched a non-head node
127
128	if (last == node) {	1✔
129	// we are unlinking the last node, so we need to update the `last` reference
130	last = prevNode;	1✔
131	}
132
133	// unlink this `node`
134	final DoublyLinkedNode<T> next = node.next;	1✔
135	if (next != null) {	1✔
136	next.previous = prevNode;	1✔
137	}
138	prevNode.next = next;	1✔
139	}
140
141	discardNode(node);	1✔
142
143	if (removed < Long.MAX_VALUE) {	1✔
144	removed++;	1✔
145	}
146
147	if (RemovalMode.REMOVE_ALL != removalMode) {	1✔
148	// REMOVE_FIRST or REMOVE_ONE so we just need one result
149	break;	1✔
150	}
151
152	} else {
153	// store the node as the previous node for the next iteration
154	prevNode = node;	1✔
155	}
156
157	// prepare for next iteration...
158	node = node.next;	1✔
159	}
160
161	return removed;	1✔
162	}
163
164	/**
165	* Similar to {@link AbstractLinkedList#toString()}
166	* but prints out the elements in reverse order.
167	*/
168	public String toReverseString() {
NEW 169	final StringBuilder builder = new StringBuilder();	×
NEW 170	builder.append('[');	×
NEW 171	final Iterator<T> iterator = reverseIterator();	×
NEW 172	while (iterator.hasNext()) {	×
NEW 173	builder.append(iterator.next());	×
NEW 174	if (iterator.hasNext()) {	×
NEW 175	builder.append(", ");	×
176	}
177	}
NEW 178	builder.append(']');	×
NEW 179	return builder.toString();	×
180	}
181	}

evolvedbinary / j8cu / 92

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous