Design Pattern: Strategy

 Strategy pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. It lets the algorithm vary independently from clients that use it.

Strategy Design Pattern
Strategy Design Pattern

Abstract Class: Duck.java

We create objects  after sub classing it into a concrete class from an abstract type. In our case, is the Duck Class. This provides the basis for all the XxxDuck objects that are created. Two things to be mentioned;

  1. We are programming the different “behavior” to an interface. And this could be an abstract class as well. References to these instance variables are provided as instance variables in the Class Definition.
  2. Public “Setters” are provided so that the behavior of the object can be set or changed dynamically as shown in this example.
package com.npk.strategy;

public abstract class Duck {

FlyBehavior flyBehavior;
QuackBehavior quackBehavior;

public abstract void display();

public void setFlyBehavior(FlyBehavior flyBehavior){
this.flyBehavior = flyBehavior;
}

public void setQuackBehavior(QuackBehavior quackBehavior){
this.quackBehavior = quackBehavior;
}

public void performFly(){
flyBehavior.fly();
}

public void performQuack(){
quackBehavior.quack();
}

public void performSwim(){
System.out.println("All ducks can swim!");
}
}

Interface: FlyBehavior.java and QuackBehavior.java

Any variable behavior of an object are to be programmed to an interface.
This way, you get two things:

  1. Compostion
  2. Loosely coupled objects.

Both of which are good OO Designs aspects.


package com.npk.strategy;

public interface FlyBehavior {

public void fly();
}

package com.npk.strategy;

public interface QuackBehavior {

public void quack();
}

Concrete Implementation: DummyDuck.java

We subclass the abstract Duck class to get a concrete DummyDuck class where we can set the behavior in the class constructor ( optional )


package com.npk.strategy;

public class DummyDuck extends Duck {

public DummyDuck(){
this.setFlyBehavior(new FlyNoWay());
this.setQuackBehavior(new SquekQuack());
}

@Override
public void display() {
System.out.println("This is a dummy duck.");

}

}

Concrete classes: FlyNoWay.java and SquekQuack.java

These form the actual implementation of the FlyBehavior and the QuackBehavior interfaces respectively.


package com.npk.strategy;

public class FlyNoWay implements FlyBehavior {

@Override
public void fly() {
System.out.println("Cannot fly.");

}

}

package com.npk.strategy;

public class SquekQuack implements QuackBehavior {

@Override
public void quack() {
System.out.println("Duck squeking.");

}

}

The Application Launcher We show two things here.

  1. Setting the behavior using the constructor.
  2. Changing the set behavior using the setters provided.

package com.npk.strategy;

public class Launcher {

public static void main(String[] args) {
Duck duck = new DummyDuck();
duck.display();
duck.performFly();
duck.performQuack();

System.out.println("---------------------");
duck.setFlyBehavior(new FlyWithWings());
duck.setQuackBehavior(new MuteQuack());

duck.performFly();
duck.performQuack();
}

}

The final output


This is a dummy duck.
Cannot fly.
Duck squeking.
---------------------
Duck flying.
Mute quack.

Design Pattern: Strategy

Linked Lists in Java

You might want to check out these before continuing:

https://linuxjunkies.wordpress.com/2010/11/18/data-structures-using-java-part-6-linked-lists-part-1/

https://linuxjunkies.wordpress.com/2010/11/26/data-structures-using-java-part-7-linked-lists-part-2-doubly-linked/

Linked List

ListNode Class


public class ListNode {

	Object data;
	ListNode nextNode;
	
	ListNode (Object object, ListNode node){
		data = object;
		nextNode = node;
	}
	
	ListNode (Object object){
		this(object,null);
	}
	
	Object getObject(){
		return data;
	}
	
	ListNode getNext(){
		return nextNode;
	}
}

List Class


public class List {

	private ListNode firstNode;
	private ListNode lastNode;
	private String name;
	
	public List(){
		this("list");
	}
	
	public List(String listname){
		name = listname;
		firstNode = lastNode = null;
	}
	
	public void insertAtFront(Object item){
		if (isEmpty())
			firstNode = lastNode = new ListNode(item);
		else
			firstNode = new ListNode(item, firstNode);
	}
	
	public void insertAtBack(Object item){
		if (isEmpty())
			firstNode = lastNode = new ListNode(item);
		else
			lastNode = lastNode.nextNode = new ListNode(item);
	}
	
	public Object removeFromFront() throws EmptyListException{
		if (isEmpty())
			throw new EmptyListException(name);
		Object removed = firstNode.data;
		
		if( firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.nextNode;
		
		return removed;
	}
	
	public Object removeFromBack() throws EmptyListException{
		if (isEmpty())
			throw new EmptyListException(name);
		
		Object removed = lastNode.data;
		
		if( firstNode == lastNode)
			firstNode = lastNode = null;
		else{
			
			ListNode current = firstNode;
			
			while(current.nextNode != lastNode)
				current = current.nextNode;
			
			lastNode = current;
			current.nextNode = null;	
		}
		return removed;
		
	}
	
	public boolean isEmpty(){
		return firstNode == null;
	}
	
	public void print(){
		if (isEmpty()){
			System.out.println("List is empty");
			return;
		}
		
		ListNode current = firstNode;
		while (current != null){
			System.out.printf("%s --> ", current.data);
			current = current.nextNode;
		}
		System.out.println();
	}
	
	public int length(){
		int length = 0;
		
		if (isEmpty()){
			return 0;
		}
		
		ListNode current = firstNode;
		while (current != null){
			current = current.nextNode;
			length++;
		}
		return length;
	}
	
	public int recursiveSize(){
		return recursiveLength(firstNode);
	}
	
	public int recursiveLength(ListNode current){
		
		if (isEmpty()){
			return 0;
		}
		
		if (current == null)
			return 0;
		
		return (1 + recursiveLength(current.nextNode));
	}
	
}
	

ListTest Class


public class ListTest {

	public static void main(String[] args){
		
		List list = new List();
		
		list.insertAtFront( "four" ); 
		list.print();             
		list.insertAtFront( "two" ); 
		list.print();            
		list.insertAtBack( "six" );  
		list.print();          
		list.insertAtBack( "nine" );  
		list.print();            
		
		System.out.printf("Length: %d%n", list.recursiveSize());
		System.out.printf("Length: %d%n", list.length());
		
		try{
		    System.out.printf( "%s removed\n", list.removeFromFront());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromFront());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromBack());
		    list.print();
		    System.out.printf( "%s removed\n", list.removeFromBack());
		    list.print();
		}catch ( EmptyListException e ){
			e.printStackTrace();
		}
		
		System.out.printf("Length: %d%n", list.recursiveSize());
		System.out.printf("Length: %d%n", list.length());
		
		       
	}
}

This is what you get

four --> 
two --> four --> 
two --> four --> six --> 
two --> four --> six --> nine --> 
Length: 4
Length: 4
two removed
four --> six --> nine --> 
four removed
six --> nine --> 
nine removed
six --> 
six removed
List is empty
Length: 0
Length: 0
Linked Lists in Java

Binary Tree and Tree Traversals using Java

    The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.A leaf node has no children.
    The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
    The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
    Siblings are nodes that share the same parent node.
    A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p.
    The size of a node is the number of descendants it has including itself.
    In-degree of a node is the number of edges arriving at that node.
    Out-degree of a node is the number of edges leaving that node.
    The root is the only node in the tree with In-degree = 0.

BInary Tree

TreeNode Class


public class TreeNode{

	TreeNode leftNode;
	TreeNode rightNode;
	int data;
	
	public TreeNode(int value){
		data = value;
		leftNode = rightNode = null;
	}
	
	public void insert(int value){
		if (value < data){
			if (leftNode == null)
				leftNode = new TreeNode(value);
			else
				leftNode.insert(value);
		}
		else if (value > data){
			if (rightNode == null)
				rightNode = new TreeNode(value);
			else
				rightNode.insert(value);
		}
	}

}

Preorder Traversal

  preorder(node)
  if node = null then return
  print node.value
  preorder(node.left) 
  preorder(node.right)

Preorder Traversal

Postorder Traversal

  postorder(node)
  if node = null then return
  postorder(node.left)
  postorder(node.right)
  print node.value

PostOrder Traversal

Inorder Traversal

  inorder(node)
  if node = null then return
  inorder(node.left)
  print node.value
  inorder(node.right)

Inorder Traversal

Queue based Level order Traversal

levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

Level Order

Tree Class


public class Tree {

	private TreeNode root;
	
	Queue queue = new Queue();
	
	public Tree(){
		root = null;
	}
	
	public void insertNode(int value){
		
		if ( root == null)
			root = new TreeNode(value);
		else
			root.insert(value);
	}
	
	public void preorderTraversal(){
		preorder(root);
	}
	
	public void inorderTraversal(){
		inorder(root);
	}
	
	public void postorderTraversal(){
		postorder(root);
	}
	
	public void levelorderTraversal(){
		levelorder(root);
	}
	
	public void levelorder(TreeNode node){
		if (node == null)
			return;

		if (node == root)
			queue.offer(node);
		
		if (node.leftNode != null)
			queue.offer(node.leftNode);
		if (node.rightNode != null)
			queue.offer(node.rightNode);
		
		System.out.printf("%d ", queue.poll().data);
		
		levelorder(queue.peek());
	}
	
	public void preorder(TreeNode node){
		
		if (node == null)
			return;
		
		System.out.printf("%d ", node.data);
		preorder(node.leftNode);
		preorder(node.rightNode);
		
	}

	public void postorder(TreeNode node){
		
		if (node == null)
			return;
		
		postorder(node.leftNode);
		postorder(node.rightNode);
		System.out.printf("%d ", node.data);
	}

	public void inorder(TreeNode node){
		
		if (node == null)
			return;
		
		inorder(node.leftNode);
		System.out.printf("%d ", node.data);
		inorder(node.rightNode);
	}

}

TreeTest Class

import java.util.Random;


public class TreeTest {

	public static void main(String[] args){
		Tree tree = new Tree();
		int value;
		Random random = new Random();
		
		System.out.println("Inserting values");
		for (int i=1; i<=10;i++){
			value=random.nextInt(100);
			System.out.printf("%d ", value);
			tree.insertNode(value);
		}
		System.out.println();
		System.out.println("Preorder");
		tree.preorderTraversal();
		System.out.println();
		System.out.println("Postorder");
		tree.postorderTraversal();
		System.out.println();
		System.out.println("Inorder");
		tree.inorderTraversal();
		System.out.println();
		System.out.println("Levelorder");
		tree.levelorderTraversal();
	}
}

Of course, you need the Queue DS for level order traversal.


import java.util.ArrayList;
import java.util.List;


public class Queue {

	private List qlist;
	
	public Queue(){
		qlist = new ArrayList();
	}
	
	public void offer(TreeNode o){
		if (qlist.isEmpty())
			qlist.add(0, o);
		else
			qlist.add(qlist.size(), o);
	}
	
	public TreeNode poll(){
		if (qlist.isEmpty())
			return null;
		else
			return qlist.remove(0);
	}
	
	public TreeNode peek(){
		if (qlist.isEmpty())
			return null;
		else
		return qlist.get(0);
	}
}

And finally the output

Inserting values
87 77 81 89 4 26 23 27 57 1 
Preorder
87 77 4 1 26 23 27 57 81 89 
Postorder
1 23 57 27 26 4 81 77 89 87 
Inorder
1 4 23 26 27 57 77 81 87 89 
Levelorder
87 77 89 4 81 1 26 23 27 57 
Binary Tree and Tree Traversals using Java

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 11: Java Interfaces, Java Packages, Building packages, Compiling packing, Using packages

Data Structures using Java Part 10: Inheritence, Constructors, invoking orverriden methods, protected keyword, dynamic method lookup, Abstract class


Inheritence
————-
TailList is a subclass of SList.
SList is the superclass of TailList.

A subclass can modify a superclass in three different ways:
1. It can declare new fields.
2. It can declare new methods.
3. It can override old methods with new implementations. It is not necessary to orverride all.

public class TailList extends SList{

	// the head and size is inherited

	private SListNode tail;

	// override the insertEnd method
	public void insertEnd(Object obj){
	// solution
	}

}

Inheritence and Constructors
——————————–
Java executes the TailList constructor, but first it executes SList() constructor.

public TailList(){
	//SList constructor is called

	//additional
	Tail = null;
}

Zero parameter constructor is called by default. To change:

public TailList(int x){
	super(x); // calls the super class constructor and must be executed FIRST.
	tail = null;
}

Invoking overridden methods
——————————-

public void insertFront(Object obj){
	super.insertFront(obj); // for the superclass and  not necessarly the first line.
	if(size == 1){
	tail = head;
	}
}

The “protected” keyword
—————————-

public class SList{

	protected SListNode head;
	protected int size;
}

Both “protected ” field and method is visible to the declaring class and to all its subclasses.
In contrast, “private ” fields are not visible to subclasses.

Dynamic method lookup
————————
For Java “Every TailList is an SList”.

SList s = new TailList(); // TailList is a subclass of SList and SList is not abstract
s.insertFront(obj);

Abstract class
—————-
A class whose sole purpose it to be inherited. This is an ADT. An abstract method lacks the implementation.

public abstract class List{

	protected int size;

	public int lenght(){
		return size;
	}

	public abstract void insertFront(Object obj);

}

List mylist;
mylist = new List(); //compile time error

A non abstract class may never
1. contain an abstract method.
2. inherit one without providing an implementation.

List mylist = new SList(); // correct!
mylist.insertFront(obj);

One list sorter can sort every kind of list.

public void listSort(List l){
//code
}

Subclasses of List: SList, DList,TailList
TimedList: record amount of time doint list operations
TransactionList: Logs all the changes on a disk for power outage.

Data Structures using Java Part 10: Inheritence, Constructors, invoking orverriden methods, protected keyword, dynamic method lookup, Abstract class

Data Structures using Java Part 9: equals(), Degree of equality and Testing

equals
——-
Every class has one equals() method.

r1.equals(r2);
r1 == r2;

Now, if the content of the object (same or not same) pointed by r1 and r2 are the same then the first statement is true. The second statement is true iff both point to the same object. Many classes define equals() to compare the contents of the two objects.

Four degrees of equality
————————–
1. Reference equality, ==
2. Shallow Strutural equality, ie fields ==
3. Deep structural equality, ie fields equals()
4. Logical equality
a. Fractions 1/3 and 2/6 are “equals” from a mathematical point of view
b. “Set” objects are “equals” if they contain the same elements, irrelevent of the order.

public class SList{
public boolean equals(SList other){
if (size != other.size)
return false; // two SLists with different size cannot be same

SListNode n1 = head;     // initial offsets of both the SLists
SListNode n2 = other.head;

while(n1 != null){
if(!n1.item.equals(n2.item)){
return false;
}
n1 = n1.next;
n2 = n2.next;
} // end of while

return true;
}
}
Data Structures using Java Part 9: equals(), Degree of equality and Testing

Data Structures using Java Part 8: Heaps and Stack, Binary Search, Recursion, Scope, Parameter passing

The Stack and the Heap
————————–
The heap stores all objects, including arrays and all the class variables.
The stack stores all the local variables including parameters.

When a method is called Java creates a stack frame (or called an activation record). It stores the parameters and the local variables. The JVM maintains an entire stack of “stack frames”. When the method completes, its stack frame is erased. Most OS give enough space for a few thousands of stack frames.

Thread.dumpstack()
———————-
This method when called will print out the contents of the stack frame. Its present in the java.lang package and so doesnt need to be imported.

Parameter passing
——————–
In Java , the parameters are passed by value. That is they are copied.

class IntBox{

	static void donothing(int x){
		x = 2;
	}

	public int i;

	static void set3(Intbox ib){
	ib.i = 3;
	}

	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
}

// called
	static void donothing(int x){
		x = 2;
	}

// calling
	int a = 1;
	donothing(a);

The variable a will be created in present stack frame. When the function donothing() is called, a new stack frame is created on top of the previous frame and the variable x resides in this frame. Note that no change happens to a after the function completes. The frame is erased once the function exits.

When the parameter is a reference, the reference is copied and not the object it is pointing to.

//called

	static void set3(Intbox ib){
	ib.i = 3;
	}

//calling
	IntBox b = new IntBox();
	set3(b);

In the local stack variable b is created. The object is created in heap with the variable i inside it. b points to object. set3() creates a parameter ib, both in new stack frame and then ib points to object pointed by b. The value of the object is changed by ib which is reflected on b, since both point to the same thing.

// called
	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
//calling
	IntBox b = new IntBox();
	badSet4(b);

The difference here is that now a new object is created by the setBad() function and its value of ib is being set. The old heap object still retains its value. This happens to be a common programming error.

Binary Search
—————-
Used to search a sorted array. Suppose we want to search in a sorted int array. In this example , we try to find whether the variable “find” exists in the array, if so then return its array index. If not, return failure. This is going to be a predefined constant like FAILURE = -1. I have used a recursive algorithm.

Binary Search Procedure
// Binary Search
public static final int FAILURE = -1; // set as -1 because no index is less than 0 and final implies constant

public static int binarySearch(int[] i, int left, int right, int find){

	if (left > right)				// this is the base case; exit if the case.
		return FAILURE;

	int mid = (left + right)/2;          // find the middle element ; base case

	if (find = i[mid]){
		return mid;			// found!
	}else if (find < i[mid]){		// less implies the left subarray
		return binarySearch(i, left, mid -1, find);
	}else {					// more implies the right subarray
		return binarySearch(i, mid + 1, right,  find);
	}
	}
}

Recursion base cases:
1. if find = middle element: return index
2. if subarray is of length 0, nothing is there to search, return 0.

How fast is it?
Takes log n (base 2) recursive binarySearch calls.

Scope and Recursion
———————-
Scope of a variable : is portion of the program , actual lines of code, that can access the variable.
1. Class variables: (static fields) are in scope everywhere in the class except where shadowed by local variables. (like when using “this”)
2. Fully qualified class variable:For example “System.out” is not ambiguous. They are in scope everywhere in the class and are not shadowed. If public, they are in scope in ALL classes.
3. Instance variables: These are in scope in methods that are not static, except when shadowed.
4. Fully qualified instance variable: For example: “this.name” Same as 2.
5. Local variables: which includes parameters, only in scope in the block that defines them.

Data Structures using Java Part 8: Heaps and Stack, Binary Search, Recursion, Scope, Parameter passing