package heap;
public class SortedList {
class SLNode {
ComparableObject data;
SLNode next;
public SLNode(ComparableObject data,SLNode next){
this.data = data;
this.next = next;
}
public SLNode(int ComparableObject){
this.data = data;
}
}//class SLNode
//Fields
private SLNode first;
//Methods
public SortedList(){
first = null;
}//Constructor
public boolean empty(){
return (first == null);
}
public void insert(ComparableObject data){
SLNode curr, foll;
if ((first == null) || (data.compareTo(first.data) <= 0)) // Insertion at the beginning
first = new SLNode(data,first);
else {
curr = first; foll = first.next;
while ((foll != null) && (foll.data.compareTo(data) <= 0)){
curr = foll; foll = foll.next;
}
curr.next = new SLNode(data,foll);
}
}//insert
public void insert(ComparableObject[] dataArr){
for (int i = 0;i < dataArr.length;i++)
insert(dataArr[i]);
}
public void merge(SortedList l){
SLNode p1,p2,curr;
//if (first == null) first = l.first;
//else if (!l.empty()) { // this and l are not empty
p1 = first; p2 = l.first;
if (p1.data.compareTo(p2.data) <= 0) p1 = p1.next;
else { first = p2; p2 = p2.next; }
curr = first;
while ((p1 != null) && (p2 != null)){
if (p1.data.compareTo(p2.data) <= 0){
curr.next = p1;
p1 = p1.next;
}
else {
curr.next = p2;
p2 = p2.next;
}
curr = curr.next;
}
if (p1 == null) curr.next = p2;
else curr.next = p1;
//}
}
public String toString(){
String out = "[";
SLNode aux = first;
while (aux != null){
out += aux.data;
aux = aux.next;
if (aux != null) out += ",";
}//while
out += "]";
return out;
}
public static void main(String[] args) {
SortedList l1 = new SortedList();
MyInteger i1 = new MyInteger(3); l1.insert(i1);
MyInteger i2 = new MyInteger(3); l1.insert(i2);
System.out.println(l1);
SortedList l2 = new SortedList();
MyInteger i3 = new MyInteger(2); l2.insert(i3);
MyInteger i4 = new MyInteger(4); l2.insert(i4);
System.out.println(l2);
l1.merge(l2);
System.out.println(l1);
}
}
|