Purpose: To give you experience implementing and using linked data structures.

Goal 1: To design and implement a class LinkedDS that will act as a linked data structure for accessing Java Objects. Your LinkedDS class will primarily implement two interfaces PrimQ and Reorder. The details of these interfaces are explained in the files PrimQ.java and Reorder.java. Read these files over very carefully before implementing your LinkedDS class.

Goal 2: To utilize your LinkedDS class to store and manipulate arbitrary length hexadecimal numbers. We can think of a hexadecimal number as a sequence of hexadecimal digits. For example, the number BEEF could be stored as the digit 'B' followed by the digit 'E' followed by the digit 'E' followed by the digit 'F'. We can store these digits in an array, or, as is required in this assignment, in a linked chain. Clearly, to perform operations on a number that is stored in this fashion, we must access the digits one at a time in some systematic way. More specific details follow below.

DETAILS Details 1: For the details on the functionality of your LinkedDS class, carefully read over the files PrimQ.java, Reorder.java, and Assig2A.java provided on the CourseWeb folder where you find this assignment description. You must use these files as specified and cannot remove/alter any of the code that is already written in them. There are different ways of implementing the PrimQ and Reorder interface methods, some of which are more efficient than others. Use only the best way of implementing these methods in this assignment. A lot of pencil and paper work is recommended before actually starting to write your code. Your LinkedDS class header should be:

public class LinkedDS implements PrimQ, Reorder

The only instance variables allowed inside the LinkedDS class are:

protected Node firstNode; protected int numOfEntries;

Important Note: The primary data structure within LinkedDS class must be a linked chain. You may not use any predefined Java collection class (e.g., ArrayList) for your LinkedDS data.

Note that the following methods are added to the Reorder interface in this assignment as compared to Assignment 1.

public void leftShift(int num)

Shift the contents of the list num places to the left (assume the beginning is the leftmost node), removing the leftmost num nodes. For example, if a list has 8 nodes in it (numbered from 1 to 8), a leftShift of 3 would shift out nodes 1, 2 and 3 and the old node 4 would now be node 1. If num <= 0 leftShift should do nothing and if num >= the length of the list, the result should be an empty list

public void rightShift(int num)

Same idea as leftShift above, but in the opposite direction. For example, if a list has 8 nodes in it (numbered from 1 to 8) a rightShift of 3 would shift out nodes 8, 7 and 6 and the old node 5 would now be the last node in the list. If num <= 0 rightShift should do nothing and if num >= the length of the list, the result should be an empty list.

public void leftRotate(int num)

In this method you will still shift the contents of the list num places to the left, but rather than removing nodes from the list you will simply change their ordering in a cyclic way. For example, if a list has 8 nodes in it (numbered from 1 to 8), a leftRotate of 3 would shift nodes 1, 2 and 3 to the end of the list, so that the old node 4 would now be node 1, and the old nodes 1, 2 and 3 would now be nodes 6, 7 and 8 (in that order). The rotation should work modulo the length of the list, so, for example, if the list is length 8 then a leftRotate of 10 should be equivalent to a leftRotate of 2. If num < 0, the rotation should still be done but it will in fact be a right rotation rather than a left rotation.

public void rightRotate(int num)

Same idea as leftRotate above, but in the opposite direction. For example, if a list has 8 nodes in it (numbered from 1 to 8), a rightRotate of 3 would shift nodes 8, 7 and 6 to the beginning of the list, so that the old node 8 would now be node 3, the old node 7 would now be node 2 and the old node 6 would now be node 1. The behavior for num > the length of the list and for num < 0 should be analogous to that described above for leftRotate.

public void reverse() This method should reverse the nodes in the list.

Note that in the methods above you may not create any new Node objects. The purpose of these methods is to rearrange the Nodes that already exist. To see how these should work, it is strongly recommended to draw one or more pictures. You will also need to write the following constructors:

public LinkedDS(); public LinkedDS(LinkedDS oldList)

The first constructor simply initializes the list to an empty state, and the second generates a new list that is a copy of the argument list (copying all of the nodes inside the old list).

Finally, you will need to override the following method: public String toString();

This method will return a String that is the result of all of the data in the list being appended together, separated by spaces. After you have finished your coding of LinkedDS, the Assig2A.java file provided for you should compile and run correctly and should give output identical to the output shown in the sample executions

Important Notes:

1) All of your LinkedDS methods must be implemented in an efficient way, utilizing the underlying linked chain. For example, a poor implementation of a left rotation could be done via repeated calls to X = removeItem() and addItem(X). However, doing this would require multiple traversals of the list and has a very bad run-time (think arithmetic series). This and similar implementations are not allowed and if implemented in this way you will not receive credit.

2) The leftRotate(), rightRotate(), and reverse() methods should NOT create any new Node objects. Rather, they should move the Node objects currently in the list into other locations. You may use temporary Node variables for these methods, but you may not create any new Nodes.

Details 2: The second part of this assignment is to write the ReallyLongHex class with the specifications as given below. You may assume all numbers will be non-negative. Inheritance: ReallyLongHex must be a subclass of LinkedDS. However, since LinkedDS is generic while ReallyLongHex is not generic, you should use the following header:

public class ReallyLongHex extends LinkedDS implements Comparable

Note that rather than T, the underlying element data is now Character. This means that the individual digits of your ReallyLongHex will be Character objects. Data: The instance variables for this class are inherited and you may not add any additional instance variables. You will certainly need method variables for the various operations but the only instance variables that you need are those inherited from LinkedDS.

Operations: Your ReallyLongHex class must implement the methods shown below. Note that the compareTo() method is necessary for the Comparable interface.

private ReallyLongHex()

The default constructor will create an "empty" ReallyLongHex. Note that this leaves the number in an inconsistent state (having no actual value), so it should only be used within the class itself as a utility method (for example, you will probably need it in your add() and subtract() methods). For this reason it is a private method.

public ReallyLongHex(String s)

The string s consists of a valid sequence of digits with no leading zeros (except for the number 0 itself special case). Insert the digits as Character objects into your list, such that the least significant digit is at the beginning of the list. For example, the String "456202" would be stored in a ReallyLongHex as: firstNode --> 2 --> 0 --> 2 --> 6 --> 5 --> 4 (note: actual Nodes are not shown but implicit)

public ReallyLongHex(ReallyLongHex rightOp)

This just requires a call to super. However, it is dependent upon a correct implementation of the copy constructor for the LinkedDS class.

public String toString()

Return a string that accurately shows the Character as we would expect to see it. Based on the way we have stored the Character, this should be accomplished by going forward through the list.

public ReallyLongHex add(ReallyLongHex rightOp)

Return a NEW ReallyLongHex that is the sum of the current ReallyLongHex and the parameter ReallyLongHex, without altering the original values. For example: ReallyLongHex X = new ReallyLongHex("123456789"); ReallyLongHex Y = new ReallyLongHex("987654321"); ReallyLongHex Z; Z = X.add(Y); System.out.println(X + " + " + Y + " = " + Z); should produce the output: 0x123456789 + 0x987654321 = 0xAAAAAAAAA Be careful to handle carries correctly and to process the nodes in the correct order. Since the numbers are stored with the most significant digit at the beginning, the add() method can be implemented by first reversing the chains then traversing both chains in a systematic way. This must be done efficiently using references to traverse the lists. In other words, you should start at the beginning of each ReallyLongHex and traverse one time while doing the addition. The KEY is that for add() (and subtract()) you should access each Node in the list only 1 time TOTAL. This is true for other methods as well. Think 5 how you can do this with reference variables. Also, be careful to handle numbers with differing numbers of digits.

public ReallyLongHex subtract(ReallyLongHex rightOp)

Return a NEW ReallyLongHex that is the difference of the current ReallyLongHex and the parameter ReallyLongHex. Since ReallyLongHex is specified to be non-negative, if rightOp is greater than the current ReallyLongHex, you should throw an ArithmeticException. Otherwise, subtract digit by digit (borrowing if necessary) as expected. As with the add() method, you must implement this efficiently via a single traversal of both lists (after reversing the numbers). This method is tricky because it can result in leading zeros, which we don't want. Be careful to handle this case (and consider the tools provided by LinkedDS that will allow you to handle it). For example: ReallyLongHex X = new ReallyLongHex("123456"); ReallyLongHex Y = new ReallyLongHex("123455"); ReallyLongHex Z; Z = X.subtract(Y); System.out.println(X + " - " + Y + " = " + Z); should produce the output: 0x123456 0x123455 = 0x1 As with the add() method, be careful to handle numbers with differing numbers of digits. Also note that borrowing may extend over several digits. See RLHTest.java for some example cases.

public int compareTo (ReallyLongHex rightOp)

Defined the way we expect compareTo to be defined for numbers. If one number has more digits than the other then clearly it is bigger (since there are no leading 0s). Otherwise, the numbers must be compared digit by digit.

public boolean equals(Object rightOp)

Defined the way we expect equals to be defined for objects comparing the data and not the reference. Don't forget to cast rightOp to ReallyLongHex so that its nodes can be accessed (note: the argument here is Object rather than ReallyLongHex because we are overriding equals() from the version defined in class Object). Note: This method can easily be implemented once compareTo() has been completed.

public void mult16ToThe(int num)

Multiply the current ReallyLongHex by 16 num . Note that this can be done very simply through adding of nodes containing 0's.

public void div16ToThe(int num)

Divide the current ReallyLongHex by 16 num . Note that this can be done very simply through shifting. To verify that your ReallyLongHex class works correctly, you will use it with the program RLHTest.java, which will be provided for you on the Assignment page on CourseWeb. Your output should match that shown in RLHTest.txt.

EXTRA CREDIT Here are a couple non-trivial extra credit ideas. Either one done well could get you the full 10 extra credit points. However, don't attempt either until you are confident that your required classes are working correctly. Allow the numbers to be signed, so that we can have both positive and negative numbers. This may require an extra instance variable (for the "sign") and will clearly affect many of your methods. If you choose this extra credit, you must submit it as a separate class (ReallyLongHex2) in addition to your original ReallyLongHex class. You must also submit a separate driver program to test / demonstrate your signed ReallyLongHex2 class. Add a multiply() method to your ReallyLongHex class. If you implement this you should also submit a separate driver program to test / demonstrate the multiply() method.

Provided Code:

Output:

L1: 0 1 2 3 4 5 6 7 8 9

L2: 0 1 2 3 4 5 6 7 8 9

L1.leftShift(2)

L1: 2 3 4 5 6 7 8 9

L2.rightShift(3)

L2: 0 1 2 3 4 5 6

L1.leftRotate(4)

L1: 6 7 8 9 2 3 4 5

L2.rightRotate(2)

L2: 5 6 0 1 2 3 4

Reversing L1

L1: 5 4 3 2 9 8 7 6

Reversing L1 again

L1: 6 7 8 9 2 3 4 5

5 retrieved from Q

6 retrieved from Q

0 retrieved from Q

1 retrieved from Q

2 retrieved from Q

3 retrieved from Q

4 retrieved from Q

Nothing in the Q

L3: Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead

L3.leftRotate(9)

L3: Sinead Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney

L4: Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead

L4.leftRotate(10)

L4: Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead

L5: Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead

L5.leftRotate(11)

L5: Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead Tori

L4.rightRotate(22)

L4: Courtney Sinead Tori Sarah Kate Aimee Shirley Chrissy Debbie Alanis

L4.rightRotate(-3)

L4: Sarah Kate Aimee Shirley Chrissy Debbie Alanis Courtney Sinead Tori

L4.leftRotate(-4)

L4: Alanis Courtney Sinead Tori Sarah Kate Aimee Shirley Chrissy Debbie

Assig2A

Test program for your LinkedDS class -- for full credit you CANNOT MODIFY this code in ANY WAY.

This program should execute without error and produce output identical to the output shown in the file A2Out.txt. If your output does not match mine, think carefully about what your operations are doing and trace them to find the problem.

If your output does not match mine, or if you must change this file to get your code to work, you will lose credit, but you can still get PARTIAL credit for your work, so be sure to turn something in no matter what!

*/

public class Assig2A

{

static final String [] data = {"Tori", "Sarah", "Kate", "Aimee", "Shirley", "Chrissy", "Debbie", "Alanis", "Courtney", "Sinead"};

public static void main (String [] args)

{

// Testing constructor

LinkedDS L1 = new LinkedDS<>();

for (int i = 0; i < 10; i++)

{

L1.addItem(i);

}

System.out.println("L1: " + L1.toString());

// Testing copy constructor

LinkedDS L2 = new LinkedDS<>(L1);

System.out.println("L2: " + L2.toString());

// Testing shift and rotate methods

System.out.println("L1.leftShift(2)");

L1.leftShift(2);

System.out.println("\tL1: " + L1.toString());

System.out.println("L2.rightShift(3)");

L2.rightShift(3);

System.out.println("\tL2: " + L2.toString());

System.out.println("L1.leftRotate(4)");

L1.leftRotate(4);

System.out.println("\tL1: " + L1.toString());

System.out.println("L2.rightRotate(2)");

L2.rightRotate(2);

System.out.println("\tL2: " + L2.toString());

System.out.println("Reversing L1");

L1.reverse();

System.out.println("\tL1: " + L1.toString());

System.out.println("Reversing L1 again");

L1.reverse();

System.out.println("\tL1: " + L1.toString());

System.out.println();

// Testing removeItem

while (!(L2.empty()))

{

Integer oldItem = L2.removeItem();

System.out.println(oldItem + " retrieved from Q");

}

Integer noItem = L2.removeItem();

if (noItem == null)

System.out.println("Nothing in the Q");

// Note that rotating is not limited to the length of the list. If the

// rotation is greater than the length of the list it should "wrap" as many

// times as necessary. However, do not rotate unnecessarily -- think about

// how you can do this very efficiently. Also note that negative rotations

// work as expected!

LinkedDS L3 = new LinkedDS<>();

LinkedDS L4 = new LinkedDS<>();

LinkedDS L5 = new LinkedDS<>();

for (int i = 0; i < data.length; i++)

{

L3.addItem(data[i]);

L4.addItem(data[i]);

L5.addItem(data[i]);

}

System.out.println("L3: " + L3.toString());

System.out.println("L3.leftRotate(9)");

L3.leftRotate(9);

System.out.println("\tL3: " + L3.toString());

System.out.println("L4: " + L4.toString());

System.out.println("L4.leftRotate(10)");

L4.leftRotate(10);

System.out.println("\tL4: " + L4.toString());

System.out.println("L5: " + L5.toString());

System.out.println("L5.leftRotate(11)");

L5.leftRotate(11);

System.out.println("\tL5: " + L5.toString());

System.out.println("L4.rightRotate(22)");

L4.rightRotate(22);

System.out.println("\tL4: " + L4.toString());

System.out.println("L4.rightRotate(-3)");

L4.rightRotate(-3);

System.out.println("\tL4: " + L4.toString());

System.out.println("L4.leftRotate(-4)");

L4.leftRotate(-4);

System.out.println("\tL4: " + L4.toString());

}

}

PrimQ

Assignment 2 PrimQ interface

Carefully read the specifications for each of the operations and implement them correctly in your LinkedDS class.

The overall logic of the PrimQ is the following: Data are logically "added" in the same order that they are "removed". However, there is no requirement for the physical storage of the actual data except that your LinkedDS class has a linked chain of nodes as its primary data structure. You MAY NOT use ArrayList, Vector or any predefined collection class for your LinkedDS data.

*/

public interface PrimQ

{

// Add a new Object to end of the PrimQ. If

// all goes well, return true.

public boolean addItem(T newEntry);

// Remove and return the "oldest" item in the PrimQ. If the PrimQ

// is empty, return null.

public T removeItem();

// Return true if the PrimQ is empty, and false otherwise

public boolean empty();

// Return the number of items currently in the PrimQ

public int size();

// Reset the PrimQ to empty status by reinitializing the variables

// appropriately

public void clear();

}

ReallyLongHex

This is a partial implementation of the ReallyLongHex class. You need to complete the implementations of the remaining methods. Also, for this class to work, you must complete the implementation of the LinkedDS class. See additional comments below.

*/

public class ReallyLongHex extends LinkedDS

implements Comparable

{

// Instance variables are inherited. You may not add any new instance variables

// Default constructor

private ReallyLongHex()

{

super();

}

// Note that we are adding the digits here in the END. This results in the

// MOST significant digit first in the chain.

// It is assumed that String s is a valid representation of an

// unsigned integer with no leading zeros.

public ReallyLongHex(String s)

{

super();

char c;

// Iterate through the String, getting each character and adding it

// at the end of the list.

for (int i = 0; i < s.length(); i++)

{

c = s.charAt(i);

if ((('0' <= c) && (c <= '9')) || (('A' <= c) && (c <= 'F')))

{

this.addItem(c);

}

else throw new NumberFormatException("Illegal digit " + c);

}

}

// Simple call to super to copy the nodes from the argument ReallyLongHex

// into a new one.

public ReallyLongHex(ReallyLongHex rightOp)

{

super(rightOp);

}

// Method to put digits of number into a String. We traverse the chain

// to add the digits to a StringBuilder.

public String toString()

{

StringBuilder sb = new StringBuilder();

if (numOfEntries > 0)

{

sb.append("0x");

for (Node curr = firstNode; curr != null;

curr = curr.getNextNode())

{

sb.append(curr.getData());

}

}

return sb.toString();

}

// You must implement the methods below. See the descriptions in the

// assignment sheet

public ReallyLongHex add(ReallyLongHex rightOp)

{

return null;

}

public ReallyLongHex subtract(ReallyLongHex rightOp)

{

return null;

}

public int compareTo(ReallyLongHex rOp)

{

return 0;

}

public boolean equals(Object rightOp)

{

return false;

}

public void mult16ToThe(int num)

{

}

public void div16ToThe(int num)

{

}

}

Reorder

Assignment 2 Reorder interface

Carefully read the specifications for the methods below and

implement them in your LinkedDS class. You have to use the

most efficient way to implement these methods.

*/

public interface Reorder

{

// Logically reverse the data in the Reorder object so that the item

// that was logically first will now be logically last and vice

// versa. The physical implementation of this can be done in

// many different ways, depending upon how you actually implemented

// your physical LinkedDS class

public void reverse();

// Remove the logical last item of the DS and put it at the

// front. As with reverse(), this can be done physically in

// different ways depending on the underlying implementation.

public void shiftRight();

// Remove the logical first item of the DS and put it at the

// end. As above, this can be done in different ways.

public void shiftLeft();

// Shift the contents of the DS num places to the left (assume the beginning

// is the leftmost node), removing the leftmost num nodes. For example, if

// a list has 8 nodes in it (numbered from 1 to 8), a leftShift of 3 would

// shift out nodes 1, 2 and 3 and the old node 4 would now be node 1.

// If num <= 0 leftShift should do nothing and if num >= the length of the

// list, the result should be an empty list.

public void leftShift(int num);

// Same idea as leftShift above, but in the opposite direction. For example,

// if a list has 8 nodes in it (numbered from 1 to 8) a rightShift of 3 would

// shift out nodes 8, 7 and 6 and the old node 5 would now be the last node

// in the list. If num <= 0 rightShift should do nothing and if num >= the

// length of the list, the result should be an empty list.

public void rightShift(int num);

// In this method you will still shift the contents of the list num places to

// the left, but rather than removing nodes from the list you will simply change

// their ordering in a cyclic way. For example, if a list has 8 nodes in it

// numbered from 1 to 8), a leftRotate of 3 would shift nodes 1, 2 and 3 to the

// end of the list, so that the old node 4 would now be node 1, and the old nodes

// 1, 2 and 3 would now be nodes 6, 7 and 8 (in that order). The rotation should

// work modulo the length of the list, so, for example, if the list is length 8 then

// a leftRotate of 10 should be equivalent to a leftRotate of 2. If num < 0, the

// rotation should still be done but it will in fact be a right rotation rather than

// a left rotation.

public void leftRotate(int num);

// Same idea as leftRotate above, but in the opposite direction. For example, if a list

// has 8 nodes in it (numbered from 1 to 8), a rightRotate of 3 would shift nodes 8, 7 and

// 6 to the beginning of the list, so that the old node 8 would now be node 3, the old node

// 7 would now be node 2 and the old node 6 would now be node 1. The behavior for num > the

// length of the list and for num < 0 should be analogous to that described above for leftRotate.

public void rightRotate(int num);

}

RLH Test

Test program for your ReallyLongHex class -- for full credit you CANNOT MODIFY this code in ANY WAY.

This program should execute without error and produce output identical to the output in the file RLITest.txt. If your output does not match mine, think carefully about what your operations are doing and trace them to find the problem.

If your output does not match mine, or if you must change this file to get your code to work, you will lose credit, but you can still get PARTIAL credit for your work, so be sure to turn something in no matter what!*/

import java.util.*;

public class RLHTest

{

public static void main (String [] args)

{

ReallyLongHex R1 = new ReallyLongHex("123456789ABCDEF");

ReallyLongHex R2 = new ReallyLongHex("FEDCBA987654321");

System.out.println("R1 = " + R1.toString());

System.out.println("R2 = " + R2.toString());

System.out.println();

// Testing add method

ReallyLongHex R3 = R1.add(R2);

System.out.println(R1 + " + " + R2 + " = " + R3);

R1 = new ReallyLongHex("1");

R2 = new ReallyLongHex("FFFFFFFFFFFFFFF");

R3 = R1.add(R2);

ReallyLongHex R4 = R2.add(R1);

System.out.println(R1 + " + " + R2 + " = " + R3);

System.out.println(R2 + " + " + R1 + " = " + R4);

System.out.println();

// Testing subtract method

R1 = new ReallyLongHex("23456");

R2 = new ReallyLongHex("4567");

R3 = R1.subtract(R2);

System.out.println(R1 + " - " + R2 + " = " + R3);

R1 = new ReallyLongHex("1000000");

R2 = new ReallyLongHex("1");

R3 = R1.subtract(R2);

System.out.println(R1 + " - " + R2 + " = " + R3);

R1 = new ReallyLongHex("123456");

R2 = new ReallyLongHex("123455");

R3 = R1.subtract(R2);

System.out.println(R1 + " - " + R2 + " = " + R3);

R1 = new ReallyLongHex("1000");

R2 = new ReallyLongHex("1001");

try

{

R3 = R1.subtract(R2);

}

catch (ArithmeticException e)

{

System.out.println(e);

}

System.out.println();

// Testing copy constructor

ReallyLongHex R5 = new ReallyLongHex(R4);

System.out.println("Copy of " + R4.toString() + " = " + R5.toString());

System.out.println();

// Testing compareTo

ReallyLongHex [] C = new ReallyLongHex[4];

C[0] = new ReallyLongHex("844444444444444");

C[1] = new ReallyLongHex("744444444444444");

C[2] = new ReallyLongHex("844444445444444");

C[3] = new ReallyLongHex("4444");

for (int i = 0; i < C.length; i++)

{

for (int j = 0; j < C.length; j++)

{

int ans = C[i].compareTo(C[j]);

if (ans < 0)

System.out.println(C[i] + " < " + C[j]);

else if (ans > 0)

System.out.println(C[i] + " > " + C[j]);

else

System.out.println(C[i] + " == " + C[j]);

}

}

System.out.println();

Arrays.sort(C);

System.out.println("Here is the sorted array: ");

for (ReallyLongHex R: C)

System.out.println(R);

System.out.println();

// Testing equals

R1 = new ReallyLongHex("12345678987654321");

R2 = new ReallyLongHex("12345678987654321");

R3 = new ReallyLongHex("12345678907654321");

if (R1.equals(R2))

System.out.println(R1 + " equals " + R2);

if (!R1.equals(R3))

System.out.println(R1 + " does not equal " + R3);

System.out.println();

// Testing shift operations

R1 = new ReallyLongHex("1234567");

System.out.println(R1);

R1.mult16ToThe(6);

System.out.println(R1);

R1.div16ToThe(8);

System.out.println(R1);

System.out.println();

}

}

RLH Test text

R1 = 0x123456789ABCDEF R2 = 0xFEDCBA987654321

0x123456789ABCDEF + 0xFEDCBA987654321 = 0x1111111111111110 0x1 + 0xFFFFFFFFFFFFFFF = 0x1000000000000000 0xFFFFFFFFFFFFFFF + 0x1 = 0x1000000000000000

0x23456 - 0x4567 = 0x1EEEF 0x1000000 - 0x1 = 0xFFFFFF 0x123456 - 0x123455 = 0x1 java.lang.ArithmeticException: Invalid Difference -- Negative Number

Copy of 0x1000000000000000 = 0x1000000000000000

0x844444444444444 == 0x844444444444444 0x844444444444444 > 0x744444444444444 0x844444444444444 < 0x844444445444444 0x844444444444444 > 0x4444 0x744444444444444 < 0x844444444444444 0x744444444444444 == 0x744444444444444 0x744444444444444 < 0x844444445444444 0x744444444444444 > 0x4444 0x844444445444444 > 0x844444444444444 0x844444445444444 > 0x744444444444444 0x844444445444444 == 0x844444445444444 0x844444445444444 > 0x4444 0x4444 < 0x844444444444444 0x4444 < 0x744444444444444 0x4444 < 0x844444445444444 0x4444 == 0x4444

Here is the sorted array: 0x4444 0x744444444444444 0x844444444444444 0x844444445444444

0x12345678987654321 equals 0x12345678987654321 0x12345678987654321 does not equal 0x12345678907654321

0x1234567 0x1234567000000 0x12345