Data Structures using Java Part 11: Java Interfaces, Java Packages, Building packages, Compiling packing, Using packages

Java Interfaces
——————
Are public method prototype and behaviour. We make use of the “interface” keyword.
It is like an abstract class with two differences:
1. A class can inherit from only one class, but can “implement” as many interfaces you want.
2. A Java interface
cannot implement any methods at all.
nor cannot include any fields except “static final” constants
Only contains method prototype and constants.

//Nukeable.java
public interface Nukeable{
	public void nuke(); // no body
}

// in java.lang
public interface Comparable{
	public int compareTo(Object o);
}

public class SList extends List implements Nukeable, Comparable{
	// all that matters
	public void nuke(){
		head = null;
		size = 0;
	}
	
	public int compareTo(Object o){
		// code that retruns a number thats less than 0 if <0 and 0 if =0 and >0 if >0
	}
}

Nukeable n = new SList(); // correct!
Comparable c = (Comparable)n; // need to use a cast as some Nukeable are not Comparable
n.nuke();
if (c.compareTo > 0){
// do something
}

Arrays class in java.util sorts arrays of Comparable objects.

public static void sort(Object[] a){ }

Runtime error occurs if any item in a is not Comparable. An interface can have a subinterface and it can itself have sub interfaces.

//NOTE this!!
public interface NukeAndCompare extends Nukeable, Comparable{ }

Java Packages
—————
Package is a collection of classes, Java interfaces and subpackages.

Three benifits:
1. Packages can contain hidden classes not visible outside package.
2. Classes can have fields and methods visible inside the package only.
3. Different packages can have classes with same name.

Example: java.io standard library.

Using Packages
—————-
Fully qualified name:

java.lang.System.out.println();

import java.io.File; // can now refer to File class
import java.io.*; // refer to all things in io

Every program implicitly import java.lang.*

Also x.y.z.Classfile should be in x/y/z/Classfile.class

Building packages
——————

//list/SList.java
package list;

public class SList{
	
	SListNode head;
	int size;
}

//list/SListNode.java
package list;

class SListNode{ //"Package protection"
	Object item; //"Package protection"
	SListNode list; //"Package protection"
}

Package protection is between private and protected.

A class/variable has package protection is visible to any class in the same package.
But it is not visible at all outside the package. ie files outside that directory.
The files that are outside only see the public classes/methods inside the package.

Public class must be declared in a file named after the class. The “package” class can appear in any *.java file.

Compiling and running
———————–
Must be done from outside the package.

//How to compile?

javac -g list/SList.java
javac -g list/ *.java
javac -g heap / *.java / *.java // this takes care of dependancies also

// How to run?
java list.Slist 

The four levels of protection
——————————-

			in same package	         in a subclass	everywhere	
1. public 			x				x			x
2. protected		x				x
3. package		        x
4. private

Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)

private field
————–
private field is invisible and inacessable to other classes.
Reasons:
1. To prevent data to be corrupted by other classes.
2. You can improve the implementation without causing the other classes to fail.

public class Date{

	private int day;
	private int month;

	public void setMonth(int m){
		month  = m;
	}

	public Date(int month , int date){
	// implementation and error checking code
	}
}

public class Evil{

	public void tamper(){

	Date d = new Date(10,10,2010); // this step is possible

	// these are not going to work!
	d.day =2000;
	d.setMonth(56);
	}
}

Interfaces
————
The interface of a class is made up of two things:
1. prototype for public methods and
2. the descriptions of the method behaviour.

Abstract Data Types(ADT)
——————————
ADT is a class(s) that has a well defined interface, but whose implementation details are firmly hidden from other classes.

Invarient
———-
Invarient is a fact about a data structure that is always true. (assuming there are no bugs). For example the “Date” object always represents a valid date.
Not all classes are ADTs. Some are just store data(no invarients).

The SList ADT
—————–

Another advantage of having a seperate SList class is that it enforces two invarients:
1. “size” is always correct.
2. list is never circularly linked.

Both of these goals are accomplised through simple Java mechanisms. Only the SList methods can change the lists.

SList ensures this:
1. The fields of the SList class are private. The “head” and “size” are private.
2. No method of SList returns an SListNode.

Doubly Linked Lists
———————

Doubly linked list

Inserting or deleting an element at the front of list is easy:

public void deleteFront(){
	if (head != null){
	head = head.next;
	size--;
	}
}

Inserting or deleting the item from the end of the list takes a lot of time in traversals.

public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

public class DList{

	private DListNode head; // points to start of the list
	private DListNode tail; // points to the end of the list
}

Insert and delete items at both ends in constant running time.
Removes the tail node (at least 2 items in DList):

tail.prev.next = null;
tail = tail.prev;

Sentinel
———
A special node that does not represent an item. It is to be noted that the sentinel node does not store an item.

Circularly linked Doubly linked list
————————————

 // no changes here
 public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

// changes here
public class DList{

	private DListNode head; // head will point to the sentinel
	private int size; // keeps track of the size of the list excluding the sentine.
}

DList invarients with sentinel:
——————————–
1. For any DList data structure d, d.head will never be null.
2. For any DListNode x, x.next is never null.
3. For any DListNode x, x.perv is never null.
4. For any DListNode x, if x.next is == y, then y.perv ==x.
5. For any DListNode x, x.prev ==y, then y.next ==x.
6. A DLists “size” field is number of DListNodes, NOT COUNTING sentinel. The sentinel is always hidden.
7. In empty DLists, the sentinels next and prev point to itselfs.