my book: the java journal: chapters 17-end

Chapter 17: Recursion

Recursion is when a method calls upon itself. An example of recursion is:

Public void recurse(int i){
If (I == 0)//if I = 0, end the method
Return;
System.out.print(i+” “);//if I != 0 do this
Recurse(i -1);//subtract 1 from i
}

If the original call to recurse() is: recurse(10); then the program will print out the numbers 10-1 in reverse order with a space between them:

10 9 8 7 6 5 4 3 2 1

When building a recursive method, there are 3 main parts:

1) the Parameters -- What values need to be kept track of during my recursion? In the recurse() method above, that value is just the number that needs to be printed.
2) The checks -- Every recursive method must have a base case. That is, a case in which the final solution has been found and recursion should stop. In recurse(), that was when i=0. Testing for the base cases are called the checks, because they check whether or not the method should do anything.
3) The calls -- For a method to be recursive, it must call itself. That’s done in the calls section of the method. The calls run new methods with updated values. It is important to remember that ANY objects passed in these calls will change in the method from which they originated. So if you’re going to be updating an object at any point, ALWAYS send a copy of it in the recursive calls. For example, when sending an ArrayList<String> called list DO NOT put list in your parameters. Sending something like new ArrayList<String>(list); this constructor of the ArrayList class creates as new ArrayList with the same objects as the original.

Public void recurse(int i/*the parameters*/){
If (I == 0)//the check: have I found my stopping point?
Return;
System.out.print(i + “ “);
Recurse(i - 1);//The Call(s)
}

Chapter 18: Algorithms

An Algorithm is a different way of making a program do something. One basic example of an algorithm would be:

Turn left.
Look at wall.
Move forward.
Turn left.

As you can see, the outcome of the above algorithm would be you looking at the back wall, while standing next to the left wall.

An example of algorithms within java would be sorts. A sort is a program that organizes and unorganized array. Some types of sorts are:

The quick sort:
public class Quicksort {
private int[] numbers;
private int number;

public void sort(int[] values) {
// Check for empty or null array
if (values ==null || values.length==0){
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
}

private void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];

// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}

// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}

private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}

The above sorting type is the fastest type of sorting.

Another type of sort is the Bubble Sort:

public class bubblesort(){

public static void main(String[] args) {
int unsortedArray[] = {10, 97, 6, 23, 0, -45, 697, -1000, 1, 0}; //Random set of numbers for example.
int i;

bubbleSort(unsortedArray, unsortedArray.length); //Pass the array to be sorted and its length.

System.out.println("After sorting, the list elements are: "); //Just to show you it worked. :smile:

for(i=0; i<unsortedArray.length; i++) {
System.out.print(unsortedArray[i] + " ");
}
}

private static void bubbleSort(int[] unsortedArray, int length) {
int temp, counter, index;

for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not.
temp = unsortedArray[index]; //These three lines just swap the two elements:
unsortedArray[index] = unsortedArray[index+1];
unsortedArray[index+1] = temp;
}
}
}
}
}


Though this sorting type may seem quick. It is considerably slower than the quicksort.


Another, more advanced algorithm is Djikstra’s shortest path algorithm which finds the shortest path between given points:



import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { name = argName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}

class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();

// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}

public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}

public static void main(String[] args)
{
Vertex v0 = new Vertex("Redvile");
Vertex v1 = new Vertex("Blueville");
Vertex v2 = new Vertex("Greenville");
Vertex v3 = new Vertex("Orangeville");
Vertex v4 = new Vertex("Purpleville");

v0.adjacencies = new Edge[]{ new Edge(v1, 5),
new Edge(v2, 10),
new Edge(v3, 8) };
v1.adjacencies = new Edge[]{ new Edge(v0, 5),
new Edge(v2, 3),
new Edge(v4, 7) };
v2.adjacencies = new Edge[]{ new Edge(v0, 10),
new Edge(v1, 3) };
v3.adjacencies = new Edge[]{ new Edge(v0, 8),
new Edge(v4, 2) };
v4.adjacencies = new Edge[]{ new Edge(v1, 7),
new Edge(v3, 2) };
Vertex[] vertices = { v0, v1, v2, v3, v4 };
computePaths(v0);
for (Vertex v : vertices)
{
System.out.println("Distance to " + v + ": " + v.minDistance);
List<Vertex> path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}
}


Output:

Distance to Redvile: 0.0
Path: [Redvile]
Distance to Blueville: 5.0
Path: [Redvile, Blueville]
Distance to Greenville: 8.0
Path: [Redvile, Blueville, Greenville]
Distance to Orangeville: 8.0
Path: [Redvile, Orangeville]
Distance to Purpleville: 10.0
Path: [Redvile, Orangeville, Purpleville]


Other algorithms are:

- quicksort (generally the fastest sort)
- mergesort (another fast sort, with some other nice properties)
- sieve method for finding prime numbers
- linked lists (and other list implementations)
- trees and common tree-traversals (prefix, infix, postfix)
- balanced trees (AVL is the easiest one)
- B-trees (important in file systems)
- tries (these are cool, but pretty specialized)
- Breadth-First Search and Depth-First Search for graph traversal

Chapter 19: Files

In java, writing and reading from files is very useful for storing information such as usernames, passwords, names, numbers, email addresses, etc. To do this we create a file, open it, read/write to it and close the file:

Creating a file in java:



import java.io.*;

public class CreateFile{
public static void main(String[] args) throws IOException{
File f;
f=new File("myfile.txt");
if(!f.exists()){
f.createNewFile();
System.out.println("New file \"myfile.txt\" has been created
to the current directory");
}
}
}

In the above program, we create a new file called “myfile.txt” by checking if the file exists or now, if it does not exist, we use the .createNewFile() function.

Reading from a file

import java.io.*;
class FileRead
{
public static void main(String args[])
{
try{
// Open the file that is the first
// command line parameter
FileInputStream fstream = new FileInputStream("textfile.txt");
// Get the object of DataInputStream
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
//Read File Line By Line
while ((strLine = br.readLine()) != null) {
// Print the content on the console
System.out.println (strLine);
}
//Close the input stream
in.close();
}catch (Exception e){//Catch exception if any
System.err.println("Error: " + e.getMessage());
}
}
}

In the above program we read text from a file by using:

A FileInputStream -- allows the user to access the file
A DataInputStream -- allows the data within the file to be transferred
A BufferedReader -- reads the text within the file

If the ‘textfile.txt’ had the text:

This
Is
The
Text

The output would be:

This
Is
The
Text

This is because the reader reads line-by-line, not all together at once.

Writing to a file

import java.io.*;
class FileWrite
{
public static void main(String args[])
{
try{
// Create file
FileWriter fstream = new FileWriter("out.txt");
BufferedWriter out = new BufferedWriter(fstream);
out.write("Hello Java");
//Close the output stream
out.close();
}catch (Exception e){//Catch exception if any
System.err.println("Error: " + e.getMessage());
}
}
}

In the above program, we write “Hello Java” to the file “out.txt”. To do this, we use:

A FileWriter -- allows for access to the file
A BufferedWriter -- writes what we want it to in the file

If we combined this program with the file reader the output would be:

Hello Java

User input and files

In java, you can use a scanner to write to a file:


import java.io.*;
import java.util.*;

class ScannerFileWrite
{
public static void main(String args[])
{
try{
Scanner scan = new Scanner(System.in);
String text;
System.out.print("Enter Text: ");
text = scan.next();
// Create file
FileWriter fstream = new FileWriter("out.txt");
BufferedWriter out = new BufferedWriter(fstream);
out.write(text);
//Close the output stream
out.close();

System.out.println(text+ " " + "is now in file: out.txt");
}catch (Exception e){//Catch exception if any
System.err.println("Error: " + e.getMessage());
}
}
}



The above program takes user input and adds it to the file out.txt.



Procedure 4: Login System
In this procedure we will be using files and algorithms to make an advanced login system:



import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


public class LoginSystem {
static File usernames,passwords;
public static void main(String[] args) throws IOException{
run();
}
private static void run() throws IOException {
usernames=new File("usernames.txt");
passwords = new File("passwords.txt");
if(!usernames.exists()){
try {
usernames.createNewFile();
} catch (IOException e) {
e.printStackTrace();//prints error
}
}
if (!passwords.exists()){
try{
passwords.createNewFile();
}catch(IOException e){
e.printStackTrace();
}
}
menu();
}
private static void menu() throws IOException {
Scanner Scan = new Scanner(System.in);
System.out.print("*********************************\n");
System.out.print("* *\n");
System.out.print("* *\n");
System.out.print("* Menu *\n");
System.out.print("* *\n");
System.out.print("* 1.Login *\n");
System.out.print("* 2.Register *\n");
System.out.print("* 3.Exit *\n");
System.out.print("*********************************\n");

int choice = Scan.nextInt();

if(choice == 1){
login();
}
else if (choice == 2){
register();
}
else if (choice == 3){
System.exit(0);
}
else{
menu();
}

}
private static void login() throws IOException {

FileInputStream fstream = new FileInputStream("usernames.txt");
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
FileInputStream stream = new FileInputStream("passwords.txt");
DataInputStream inp = new DataInputStream(stream);
BufferedReader brl = new BufferedReader(new InputStreamReader(inp));
String strLine;
String str;
while ((strLine = br.readLine()) != null){
while((str = brl.readLine()) != null){
Scanner scan = new Scanner(System.in);
System.out.print("Enter Username: ");
String user = scan.next();
System.out.print("Enter Password: ");
String pass = scan.next();

if (strLine.equalsIgnoreCase(user) && str.equalsIgnoreCase(pass)){
System.err.print("Logged in. Congratulations on finishing this book!");
}
else{
login();
}
}
}
in.close();



}
private static void register() {
try{
Scanner scan = new Scanner(System.in);
String user,pass;
System.out.print("Enter Desired Username: ");
user = scan.next();
System.out.print("Enter Desired Password: ");
pass = scan.next();

FileWriter fstream = new FileWriter("usernames.txt");
BufferedWriter out = new BufferedWriter(fstream);
out.write(user);
out.close();
FileWriter stream = new FileWriter("passwords.txt");
BufferedWriter write = new BufferedWriter(stream);
write.write(pass);
write.close();

System.out.println("Username: " + user + " " + "Password: "+ pass);
login();


}catch (Exception e){//Catch exception if any
System.err.println("Error: " + e.getMessage());
}


}
}


~~~!!! End Of Unit 4 !!!~~~














































Thank you to everybody who read this book, it took me a long time and a lot of effort to make. I hope you enjoyed it and found it informational and helpful!

Again great book so far man! Great work