evolvedbinary / j8cu / 103

Committed 25 Feb 2025 06:04PM UTC coverage: 98.219% (+2.3%) from 95.876%

Build # 103

Build Type

push

circleci

Committed by

adamretter

Commit Message

Introduce an interface for bounded linked lists

Run Details

386 of 393 relevant lines covered (98.22%)

0.98 hits per line

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

91.67

/src/main/java/com/evolvedbinary/j8cu/list/linked/OrderedDoublyLinkedList.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 net.jcip.annotations.NotThreadSafe;
import org.jspecify.annotations.Nullable;

/**
 * Basic Linked List implementation where nodes have `next` and `prev` links
 * where elements are kept in order by means of their comparability.
 * Note that any `null` elements will always come at the end of the list.
 *
 * @author <a href="mailto:adam@evolvedbinary.com">Adam Retter</a>
 */
@NotThreadSafe
public class OrderedDoublyLinkedList<T extends Comparable<T>> extends DoublyLinkedList<T> {

    public OrderedDoublyLinkedList() {
        this(0);
    }

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

    @Override
    public boolean add(@Nullable final T element) {
        // small optimisation for empty list
        if (head == null) {
            // list is empty, element should become the head
            final DoublyLinkedNode<T> newNode = createNode(element);
            this.head = newNode;
            this.last = head;
            return true;
        }

        // small optimisation for appending to the list, additionally `null` elements always come last!
        if (element == null || (last.data != null && element.compareTo(last.data) >= 0)) {
            // the element should be appended to the list
            final DoublyLinkedNode<T> newNode = createNode(element);
            newNode.previous = this.last;
            this.last.next = newNode;
            this.last = newNode;
            return true;
        }

        // find the position to insert the node
        @Nullable DoublyLinkedNode<T> node = head;
        @Nullable DoublyLinkedNode<T> prevNode = null;
        while (node != null) {
            if (node.data == null || element.compareTo(node.data) < 0) {
                // found that insertion position should be before this node

                final DoublyLinkedNode<T> newNode = createNode(element);
                node.previous = newNode;
                newNode.next = node;

                if (prevNode == null) {
                    // element should be inserted before the head node
                    head = newNode;

                } else {
                    // the element should be inserted before this node
                    newNode.previous = prevNode;
                    prevNode.next = newNode;
                }

                return true;
            }

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

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

        return false;
    }

    @Override
    protected long remove(@Nullable final T element, final RemovalMode removalMode) {
        // optimisation for removing `null` elements from the end of the list
        if (element == null && RemovalMode.REMOVE_FIRST != removalMode) {
            long removed = 0;
            while (last != null && last.data == null) {
                // remove the last element which is null

                @Nullable final DoublyLinkedNode<T> prevNode = last.previous;
                if (prevNode == null) {
                    // last is head, i.e. only one node present, remove it
                    head = null;
                    discardNode(last);
                    last = null;

                } else {
                    prevNode.next = null;
                    discardNode(last);
                    last = prevNode;
                }

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

                if (removalMode != RemovalMode.REMOVE_ALL) {
                    break;
                }
            }

            return removed;
        }

        // fallback to regular removal
        return super.remove(element, removalMode);
    }
}

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 net.jcip.annotations.NotThreadSafe;
30	import org.jspecify.annotations.Nullable;
31
32	/**
33	* Basic Linked List implementation where nodes have `next` and `prev` links
34	* where elements are kept in order by means of their comparability.
35	* Note that any `null` elements will always come at the end of the list.
36	*
37	* @author <a href="mailto:adam@evolvedbinary.com">Adam Retter</a>
38	*/
39	@NotThreadSafe
40	public class OrderedDoublyLinkedList<T extends Comparable<T>> extends DoublyLinkedList<T> {
41
42	public OrderedDoublyLinkedList() {
43	this(0);	1✔
44	}	1✔
45
46	/**
47	* @param nodeCacheSize the size of the cache to use for reusing nodes that are removed.
48	*/
49	public OrderedDoublyLinkedList(final int nodeCacheSize) {
50	super(nodeCacheSize);	1✔
51	}	1✔
52
53	@Override
54	public boolean add(@Nullable final T element) {
55	// small optimisation for empty list
56	if (head == null) {	1✔
57	// list is empty, element should become the head
58	final DoublyLinkedNode<T> newNode = createNode(element);	1✔
59	this.head = newNode;	1✔
60	this.last = head;	1✔
61	return true;	1✔
62	}
63
64	// small optimisation for appending to the list, additionally `null` elements always come last!
65	if (element == null \|\| (last.data != null && element.compareTo(last.data) >= 0)) {	1✔
66	// the element should be appended to the list
67	final DoublyLinkedNode<T> newNode = createNode(element);	1✔
68	newNode.previous = this.last;	1✔
69	this.last.next = newNode;	1✔
70	this.last = newNode;	1✔
71	return true;	1✔
72	}
73
74	// find the position to insert the node
75	@Nullable DoublyLinkedNode<T> node = head;	1✔
76	@Nullable DoublyLinkedNode<T> prevNode = null;	1✔
77	while (node != null) {	1✔
78	if (node.data == null \|\| element.compareTo(node.data) < 0) {	1✔
79	// found that insertion position should be before this node
80
81	final DoublyLinkedNode<T> newNode = createNode(element);	1✔
82	node.previous = newNode;	1✔
83	newNode.next = node;	1✔
84
85	if (prevNode == null) {	1✔
86	// element should be inserted before the head node
87	head = newNode;	1✔
88
89	} else {
90	// the element should be inserted before this node
91	newNode.previous = prevNode;	1✔
92	prevNode.next = newNode;	1✔
93	}
94
95	return true;	1✔
96	}
97
98	// store the node as the previous node for the next iteration
99	prevNode = node;	1✔
100
101	// prepare for next iteration...
102	node = node.next;	1✔
103	}
104
105	return false;	×
106	}
107
108	@Override
109	protected long remove(@Nullable final T element, final RemovalMode removalMode) {
110	// optimisation for removing `null` elements from the end of the list
111	if (element == null && RemovalMode.REMOVE_FIRST != removalMode) {	1✔
112	long removed = 0;	1✔
113	while (last != null && last.data == null) {	1✔
114	// remove the last element which is null
115
116	@Nullable final DoublyLinkedNode<T> prevNode = last.previous;	1✔
117	if (prevNode == null) {	1✔
118	// last is head, i.e. only one node present, remove it
119	head = null;	×
120	discardNode(last);	×
121	last = null;	×
122
123	} else {
124	prevNode.next = null;	1✔
125	discardNode(last);	1✔
126	last = prevNode;	1✔
127	}
128
129	if (removed < Long.MAX_VALUE) {	1✔
130	removed++;	1✔
131	}
132
133	if (removalMode != RemovalMode.REMOVE_ALL) {	1✔
134	break;	1✔
135	}
136	}	1✔
137
138	return removed;	1✔
139	}
140
141	// fallback to regular removal
142	return super.remove(element, removalMode);	1✔
143	}
144	}

evolvedbinary / j8cu / 103

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