Issues with generics < E > and < E extends Comparable > in code below. What changes are needed in the code below to prevent DLList.push_front() and DLList.push_back() from accepting strings instead of Integers?
The following code is a sub-set of C++ std::list, implemented as a circular double linked list that includes an internal node list where list.next is a reference to the first node, and list.prev is a reference to the last node. list is the equivalent of std::list::end(). References to nodes are used instead of std::list::iterator.
DLList.sort() is a recursive merge sort, but instead of scanning lists to split them, it recursively divides a count (size) by 2 until a base case of size == 1 is reached. DLList.merge() uses DLList.splice() to move one or more nodes at a time within a list to sort the list. Visual Studio 2022 now uses this method in std::list::sort(). On my old desktop with Intel 3770K CPU, it takes about 2 seconds to sort 4,194,304 Integers from sequentially allocated nodes, and about 3 seconds for scattered nodes (tested by refilling sorted list with random numbers and sorting again).
In the Visual Studio 2022 and my C++ implementations for std::list::sort() a pointer to the beginning node is passed by reference and a pointer to the ending node is returned. Java doesn't have pass by reference, so a static instance (one time allocation) of a node pair np is used instead, passed to and returned by sortr(). sortr() uses np.beg and sz as inputs, returns np, and only sets np.end in base cases where sz == 1.
I use one working directory with NetBeans, copying source files to x.java for testing, which is why package x is used.
package x;
import java.util.Random;
class DLNode<E>{
DLNode<E> next;
DLNode<E> prev;
E element;
DLNode(){
next = null;
prev = null;
element = null;
}
DLNode(E e){
next = null;
prev = null;
element = e;
}
}
class NodePair{
DLNode beg;
DLNode end;
NodePair(){
beg = null;
end = null;
}
}
class DLList<E>{
DLNode<E> list;
int size;
DLList(){
list = new <E> DLNode();
list.next = list;
list.prev = list;
size = 0;
}
public int size() {
return size;
}
public DLNode<E> begin(){
return list.next;
}
public DLNode<E> end(){
return list;
}
public E front() {
if(size == 0)
return null;
return (E) list.next.element;
}
public E back() {
if(size == 0)
return null;
return (E) list.prev.element;
}
public void push_front(E element) {
DLNode<E> node = new DLNode(element);
size++;
node.next = list.next;
node.prev = list;
list.next.prev = node;
list.next = node;
}
public void push_back(E element) {
DLNode<E> node = new DLNode(element);
size++;
node.next = list;
node.prev = list.prev;
list.prev.next = node;
list.prev = node;
}
public E pop_front() {
if(size == 0)
return null;
size--;
DLNode<E> node = list.next;
DLNode<E> next = node.next;
next.prev = list;
list.next = next;
return (E) node.element;
}
public E pop_back() {
if(size == 0)
return null;
size--;
DLNode<E> node = list.prev;
DLNode<E> prev = node.prev;
prev.next = list;
list.prev = prev;
return (E) node.element;
}
// move rgt node to just before lft node
public void splice(DLNode lft, DLNode rgt){
rgt.prev.next = rgt.next; // remove rgt node
rgt.next.prev = rgt.prev;
rgt.prev = lft.prev; // insert before lft
rgt.next = lft;
lft.prev.next = rgt;
lft.prev = rgt;
}
// move rgt to end.prev nodes to just before lft node
public void splice(DLNode lft, DLNode rgt, DLNode end){
DLNode lst = end.prev; // reference to last node
rgt.prev.next = end; // remove rgt nodes
end.prev = rgt.prev;
rgt.prev = lft.prev; // insert before lft
lst.next = lft;
lft.prev.next = rgt;
lft.prev = lst;
}
// merge two sorted runs using splice to rearrange nodes within list
private <E extends Comparable> DLNode<E> merge(DLNode<E> lft, DLNode<E> rgt, DLNode<E> end){
DLNode<E> nxt;
DLNode<E> rtn = lft; // set reference to first merged node
if(lft.element.compareTo(rgt.element) > 0)
rtn = rgt;
while(true){ // merge runs
// advance lft until lft > rgt
while(lft.element.compareTo(rgt.element) < 1){
lft = lft.next;
if(lft == rgt)
return rtn;
}
// advance nxt undil nxt >= lft */
nxt = rgt.next;
while(nxt != end && nxt.element.compareTo(lft.element) < 1)
nxt = nxt.next;
// move rgt to nxt.prev to before lft
splice(lft, rgt, nxt);
rgt = nxt;
if(rgt == end)
return rtn;
}
}
// merge sort using stack to track sorted run boundaries
// lft and sz are local, np is one time allocation
private NodePair sortr(NodePair np, int sz){
if(sz == 1){
np.end = np.beg.next;
return np;
}
np = sortr(np, sz-sz/2); // lft run
DLNode lft = np.beg;
np.beg = np.end; // rgt run
np = sortr(np, sz/2);
np.beg = merge(lft,np.beg,np.end); // merge
return np;
}
public void sort(){
if(size() < 2)
return;
NodePair np = new NodePair();
np.beg = list.next;
sortr(np, size);
}
}
public class x {
public static void main(String[] args) {
DLList list = new <Integer> DLList();
final int COUNT = 4*1024*1024;
Random r = new Random();
DLNode<Integer> node;
Integer i;
Integer j;
long bgn, end;
// test sort with sequentially allocated nodes
for(i = 0; i < COUNT; i++)
list.push_back((Integer)r.nextInt());
bgn = System.currentTimeMillis();
list.sort();
end = System.currentTimeMillis();
System.out.println("milliseconds " + (end-bgn));
// test sort with scattered nodes
for(node = list.begin(); node != list.end(); node = node.next)
node.element = (Integer)r.nextInt();
bgn = System.currentTimeMillis();
list.sort();
end = System.currentTimeMillis();
System.out.println("milliseconds " + (end-bgn));
// verify sort worked
node = list.begin();
i = node.element;
j = i;
for(node = node.next; node != list.end(); node = node.next){
j = node.element;
if(i.compareTo(j) > 0)
break;
i = j;
}
if(i.compareTo(j) == 0)
System.out.println("passed");
else
System.out.println("failed");
// remove all nodes from list
while (0 != list.size())
list.pop_front();
}
}
```
