Tuesday, May 31, 2022

Java Program to Delete a Node From Binary Search Tree (BST)

In the post Binary Tree Implementation in Java - Insertion, Traversal And Search we have already seen Binary search tree implementation in Java for insertion, search and traversal operations. In this post we’ll see how to delete a node from Binary search tree in Java. Since deletion of a node from binary search tree is considered the most complex operation, having many scenarios so it is taken up as a separate post.

Deleting a node in binary search tree

Deleting a node consists of two operations-

  1. Search for the node that has to be deleted.
  2. Delete the node once it is found.

When the node is found and you are going to delete it you need to consider the following three cases.

  1. The node that has to be deleted is a leaf node (has no children).
  2. The node that has to be deleted has one child.
  3. The node that has to be deleted has two children.

Based on these cases logic for deleting a node differs so we’ll go through these cases for deleting a node in binary search tree one by one.

Once all the scenarios are explained we'll see the full Java program for binary search tree node deletion using both-

Deleting a node in binary search tree - Node has no children

If node to be deleted is a leaf node that is the simplest binary search tree node deletion case. In this case left or right reference of the parent node (parent of the node that has to be deleted) is set to null based on whether the deleted node is the left child or the right child.

deleting node in BST

If node to be deleted is current and its parent is called parent then the code for deleting a leaf node can be written as-

// if root node is to be deleted
if(current == root){
 root = null;
}
// left child
else if(isLeftChild){
 parent.left = null;
}
// right child
else{
 parent.right = null;
}

Deleting a node in binary search tree - Node has one child

If a node to be deleted has one child then there are two scenarios-

If deleted node has a left child then that child becomes the left child of the parent if deleted node is the left child otherwise child of the deleted node becomes the right child of the parent if deleted node is the right child.

If deleted node has a right child then that child becomes the left child of the parent if deleted node is the left child otherwise child of the deleted node becomes the right child of the parent if deleted node is the right child.

binary search tree node deletion java

If node to be deleted is current and its parent is parent then the code for deleting a node with one child can be written as-

// if node to be deleted has right child
if(current.left == null){
 // if root node is to be deleted
 if(current == root){
  root = current.right;
 }
 // if deleted node is left child
 else if(isLeftChild){
  parent.left = current.right;
 }
 // if deleted node is right child
 else{
  parent.right = current.right;
 }
}
//if node to be deleted has left child
else if(current.right == null){
 if(current == root){
  root = current.left;
 }
 // if deleted node is left child
 else if(isLeftChild){
  parent.left = current.left;
 }
 // if deleted node is right child
 else{
  parent.right = current.left;
 }
}

Deleting a node in binary search tree - Node has two children

Case when node to be deleted has two children is the most complex out of the three cases.

To delete a node with two children in binary search tree you need to find the inorder successor of the node to be deleted. In-order successor is the next highest node and to find it you need to go to the right child of the deleted node and from there traverse the left subtree until null is encountered, that last node is the in-order successor of the node to be deleted.

Once the in-order successor is found there are two scenarios-

  1. In-order successor is the right child of the node to be deleted, as there is no left subtree to traverse.
  2. In-order successor is a node in the left subtree which you start traversing after going to the right child of the deleted node.

Let’s see both of these scenarios, when deleting a node with two children in binary search tree, in detail.

In-order successor right child of the node to be deleted

If right child of the node to be deleted has no left child then that right child itself is the in-order successor of the node to be deleted and it has to take the place of the deleted node.

  1. Parent of the node to be deleted should start referencing to the in-order successor.
  2. Left child of the node to be deleted should become the left child of the successor.
delete node in BST

If node to be deleted is current, its parent is parent and in-order successor is called successor then the pseudo code for deleting a node in this case can be written as-

// Find successor
Node successor = findSuccessor(deleteNode)
// if node to be deleted is left child
if(isLeftChild){
 parent.left = successor;
}else{
 parent.right = successor;
}
successor.left = current.left;

In-order successor is in the left subtree

If the in-order successor is found in the left subtree of the right child of the node to be deleted then the following steps are required for deleting a node.

  1. Successor’s right child should become the left child of the successor’s parent.
  2. Right child of the node to be deleted should become the right child of the successor.
  3. Left child of the node to be deleted becomes the left child of the successor.
  4. Parent of the node to be deleted should start referencing in-order successor of the node to be deleted.

If node to be deleted is current, its parent is parent, in-order successor is called successor and its parent is successorParent then the code for deleting a node in this case can be written as-

// Find successor
Node successor = findSuccessor(deleteNode)
// if node to be deleted is left child
if(isLeftChild){
 parent.left = successor;
}else{
 parent.right = successor;
}
successorParent.left = successor.right;
successor.right = current.right;
successor.left = current.left;

Deleting a node in binary search tree Java implementation – Iterative

Now when we have a good understanding of all the scenarios while deleting a node in BST we’ll have the Java implementation for deleting a node in BST. It can be written as both iterative method and recursive method. Both approaches are shown here.

public class BinaryTree {
  // first node
  private Node root;
  BinaryTree(){
    root = null;
  }
  // Class representing tree nodes
  static class Node{
    int value;
    Node left;
    Node right;
    Node(int value){
      this.value = value;
      left = null;
      right = null;        
    }
    public void displayData(){
      System.out.print(value + " ");
    }
  }
    
  public void insert(int i){
    root = insert(root, i);
  }
    
    
  //Inserting node - recursive method
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
    
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      inOrder(node.left);
      node.displayData();
      inOrder(node.right);
    }
  }
    
  public boolean delete(int value){
    Node current = root;
    Node parent = root;
    boolean isLeftChild = false;
    while(current.value != value){
      parent = current;
      if(value < current.value){
        // Move to the left if searched value is less
        current = current.left;
        isLeftChild = true;
      }
      else{
        // Move to the right if searched value is >=
        current = current.right;
        isLeftChild = false;
      }
      if(current == null){
        return false;
      }
    }
    // if reached here means node to be deleted is found
    
    // Leaf node deletion case
    if(current.left == null && current.right == null){
      System.out.println("Leaf node deletion case");
      // if root node is to be deleted
      if(current == root){
        root = null;
      }
      // left child
      else if(isLeftChild){
        parent.left = null;
      }
      // right child
      else{
        parent.right = null;
      }
    }
    // Node to be deleted has one child case
    // Node to be deleted has right child
    else if(current.left == null){
      System.out.println("One right child deletion case");
      // if root node is to be deleted
      if(current == root){
        root = current.right;
      }
      // if deleted node is left child
      else if(isLeftChild){
        parent.left = current.right;
      }
      // if deleted node is right child
      else{
        parent.right = current.right;
      }
    }
    // Node to be deleted has left child
    else if(current.right == null){
      System.out.println("One left child deletion case");
      if(current == root){
        root = current.left;
      }
      // if deleted node is left child
      else if(isLeftChild){
        parent.left = current.left;
      }
      // if deleted node is right child
      else{
        parent.right = current.left;
      }
    }
    // Node to be deleted has two children case
    else{
      System.out.println("Two children deletion case");
      // find in-order successor of the node to be deleted
      Node successor = findSuccessor(current);
      if(current == root){
        root = successor;
      }
      // if deleted node is left child
      else if(isLeftChild){
        parent.left = successor;
      }
      // if deleted node is right child
      else{
        parent.right = successor;
      }
      successor.left = current.left;
    }
    return true;
  }
  // Method to find the in-order successor of the deleted node
  private Node findSuccessor(Node node){
    Node successor = node;
    Node successorParent = node;
    // Start from the right child of the node to be deleted
    Node current = node.right;
    while(current != null){
      successorParent = successor;
      successor = current;
      current = current.left;
    }
    // When In-order successor is in the left subtree 
    // perform two ref changes here as we have 
    // access to successorParent
    if(successor != node.right){
      successorParent.left = successor.right;
      // applicable only when successor is not right child
      // so doing here
      successor.right = node.right;
    }
    return successor;
  }
    
  public static void main(String[] args) {
    BinaryTree bst = new BinaryTree();
    bst.insert(50);
    bst.insert(70);
    bst.insert(30);
    bst.insert(15);
    bst.insert(35);
    bst.insert(7);
    bst.insert(22);
    bst.insert(31);
    System.out.println("Inorder traversal of binary tree");
    bst.inOrder(bst.root);
    System.out.println();
    boolean deleteFlag = bst.delete(35);
    if(deleteFlag)
      System.out.println("Node successfully deleted");
    System.out.println("Inorder traversal after deletion");
    bst.inOrder(bst.root);
    System.out.println();
  }
}

Deleting a node in binary search tree Java implementation – Recursive

Following method shows the recursive Java implementation for deleting a node in binary search tree.

public Node deleteNode_recur(Node node, int value){
  if(node == null)
    return null;
  if(value < node.value){
    node.left = deleteNode_recur(node.left, value);
  }else if (value > node.value){
    node.right = deleteNode_recur(node.right, value);
  }else{
    // Leaf node deletion case
    if(node.left == null && node.right == null){
      System.out.println("Leaf node deletion case");
      node = null;
    }
    // Node to be deleted has one child case
    // Node to be deleted has right child
    else if(node.left == null){
      System.out.println("Having One right child deletion case");
      node = node.right;
    }
    // Node to be deleted has left child
    else if(node.right == null){
      System.out.println("Having One left child deletion case");
      node = node.left;
    }
    // Node to be deleted has two children case
    else{
      System.out.println("Two children deletion case");
      Node successor = findSuccessor_recur(node.right);
      // Copy the value
      node.value = successor.value;
      // delete successor node instead
      node.right = deleteNode_recur(node.right, successor.value);
    }
  }
  return node;
}
private Node findSuccessor_recur(Node node){
  if(node.left == null)
    return node;
  else 
    return findSuccessor_recur(node.left);  
}

Which can then be executed using following method call.

newRoot = bst.deleteNode_recur(bst.root, 15);
bst.inOrder(newRoot);

That's all for this topic Java Program to Delete a Node From Binary Search Tree (BST). If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Sorted Linked List In Java
  2. Doubly Linked List Implementation Java Program
  3. Radix Sort Program in Java
  4. Find The First Repeated Character in a String Java Program
  5. Java Program to Display Prime Numbers

You may also like-

  1. How to Create PDF in Java Using OpenPDF
  2. How to Create Deadlock in Java
  3. How to Display Time in AM-PM Format in Java
  4. How to Read Input From Console in Java
  5. Heap Memory Allocation in Java
  6. Nested Class And Inner Class in Java
  7. Java Exception Handling Interview Questions And Answers
  8. Spring Expression Language (SpEL) With Examples

Monday, May 30, 2022

Deque Implementation in Java Using Doubly Linked List

In this post we’ll see an implementation of Deque in Java using Doubly Linked list.

Deque data structure

A Deque is a generalized queue structure that permits insertion and removal of elements at both ends where as in queue element can only be added at one end and removed from the other end.

Following image shows an implementation of Deque as doubly linked list with head and tail references.

Deque implementation in Java

Operations in a Deque

Mainly following operations are implemented for a Deque-

  1. insertFirst- To insert an element at the beginning of a deque.
  2. insertLast- To insert element at the last.
  3. removeFirst- To remove item from the head of the queue.
  4. removeLast- To remove item from the tail of the queue.
  5. getFirst()- Read value from the front of the queue.
  6. getLast()- Read last value from the queue.

For more information on these methods implementations refer Doubly Linked List Implementation Java Program.

Java program for Deque using doubly linked list

For representing nodes of the doubly linked list a separate class is used which apart from the data also has two references for storing next and previous references to itself.

class Node{
 //data
 int i;
 // next node in the list
 Node next;
 // previous node in the list
 Node prev;
}

There are also two references head and tail of type Node in the implementation class which are used to point to the first node of the Linked list (front of the queue) and the last node of the Linked list (rear of the queue) respectively.

public class LinkedListDeque {
 private Node head;
 private Node tail;
 
 static class Node{
  //data
  int i;
  // next node in the list
  Node next;
  // previous node in the list
  Node prev;
  Node(int i){
   this.i = i;
  }
  public void displayData(){
   System.out.print(i + " ");
  }
 }
 // constructor
 public LinkedListDeque(){
  this.head = null;
  this.tail = null;
 }
 
 public boolean isEmpty(){
  return head == null;
 }
 
 public void insertFirst(int i){
  //Create a new node
  Node newNode = new Node(i);
  // if first insertion tail should
  // also point to this node
  if(isEmpty()){
   tail = newNode;
  }else{
   head.prev = newNode;
  }
  newNode.next = head;
  head = newNode;
 }
 

 public void insertLast(int i){
  Node newNode = new Node(i);
  // if first insertion head should
  // also point to this node
  if(isEmpty()){
   head = newNode;
  }else{
   tail.next = newNode;
   newNode.prev = tail;
  }
  tail = newNode;
 }
 
 public Node removeFirst(){
  if(head == null){
   throw new RuntimeException("Deque is empty");
  }
  Node first = head;
  if(head.next == null){
   tail = null;
  }else{
   // previous of next node (new first) becomes null
   head.next.prev = null;
  }
  head = head.next;
  return first;
 }
 
 public Node removeLast(){
  if(tail == null){
   throw new RuntimeException("Deque is empty");
  }
  Node last = tail;
  if(head.next == null){
   head = null;
  }else{
   // next of previous node (new last) becomes null
   tail.prev.next = null;
  }
  tail = tail.prev;
  return last;
 }
 
 public int getFirst(){
  if(isEmpty()){
   throw new RuntimeException("Deque is empty");
  }
  return head.i;
 }
 
 public int getLast(){
  if(isEmpty()){
   throw new RuntimeException("Deque is empty");
  }
  return tail.i;
 }
 
 // Method for forward traversal
 public void displayForward(){
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
  System.out.println("");
 }
 
 // Method to traverse and display all nodes
 public void displayBackward(){
  Node current = tail;
  while(current != null){
   current.displayData();
   current = current.prev;
  }
  System.out.println("");
 }

 public static void main(String[] args) {
  LinkedListDeque deque = new LinkedListDeque(); 
  //deque.getLast();
  deque.insertFirst(2);  
  deque.insertFirst(1);
  deque.insertLast(3);
  deque.insertLast(4);
  deque.displayForward();
  Node node = deque.removeFirst();
  System.out.println("Node with value "+ node.i + " deleted");
  deque.displayForward();
  System.out.println("First element in the deque " + deque.getFirst());
  System.out.println("Last element in the deque " + deque.getLast());
 }
}

Output

1 2 3 4 
Node with value 1 deleted
2 3 4 
First element in the deque 2
Last element in the deque 4

That's all for this topic Deque Implementation in Java Using Doubly Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Java Program to Detect And Remove Loop in a Linked List
  2. Sorted Linked List In Java
  3. Merge Sort Program in Java
  4. Producer-Consumer Java Program Using volatile
  5. Arrange Non-Negative Integers to Form Largest Number - Java Program

You may also like-

  1. Java Program to Convert a File to Byte Array
  2. Find The Maximum Element in Each Row of a Matrix Java Program
  3. How to Convert Date And Time Between Different Time-Zones in Java
  4. Comparing Enum to String in Java
  5. Lambda Expressions in Java 8
  6. Optional Class in Java With Examples
  7. strictfp in Java
  8. Spring MVC JSON as Response Example

Sunday, May 29, 2022

Inheritance in Python

Inheritance is one of the four fundamental OOPS concepts. The other three being-

What is inheritance

Inheritance is a mechanism, by which one class acquires, all the properties and behaviors of another class. The class whose members are inherited is called the Super class (or base class), and the class that inherits those members is called the Sub class (or derived class).


Syntax of inheritance in Python

In Python a derived class can inherit a base class using the following syntax.

class DerivedClass(BaseClass):

Benefits of inheritance

Using inheritance you can write hierarchical code where you move from generic code (in Parent class) to specific code (in child class).

Inheritance OOPS concept relates to removing redundancy and write reusable code. Let’s try to clear it with an example.

Python inheritance example

Suppose we have an Account class with fields name, accountNum and methods to withdraw and deposit. There is another class PrivilegedAccount which has the same fields as in Account and provides the same methods to withdraw and deposit. Apart from that privileged account also provides extra facility to schedule appointment. Using inheritance PrivilegedAccount can inherit fields and methods of Account class (reuse that functionality) and just have extra method for appointment scheduling facility.

class Account:
  def __init__(self, name, acct_num):
    self.name = name
    self.acct_num = acct_num

  def withdraw(self, amount):
    print('Withdrawing amount for ', self.acct_num)

  def deposit(self, amount):
    print('Depositing amount for ', self.acct_num)

class PrivilegedAccount(Account):
  def scheduleAppointment(self):
    print('Scheduling appointment for ', self.acct_num)

#PrivilegedAccount class object
pa = PrivilegedAccount('Ian', 1001)
pa.withdraw(100)
pa.deposit(500)
pa.scheduleAppointment()

Output

Withdrawing amount for  1001
Depositing amount for  1001
Scheduling appointment for  1001

In the example, object of PrivilegedAccount is created since it has inherited the methods of the Super class so withdraw and deposit methods can be called on the PrivilegedAccount class object.

Constructor overriding and method overriding with inheritance

When a class inherits another class in Python, constructor in the super class is also available by default to the child class. You may have some extra fields in the child class which you need to initialize in the child class thus you can override the constructor in the child class to initialize the fields there.

To change the implementation of an already defined method in super class you can override it in child class this concept is known as method overriding.

Suppose there is a class Person with fields name, age and there is a method displayData to display those fields. There is another class Employee with fields name, age, empId and there is a method displayData to display those fields. Employee class is almost similar to Person class except an additional field empId so Employee class reuses Person class by inheriting it.

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def displayData(self):
    print('In parent class displayData method')
    print(self.name)
    print(self.age)

class Employee(Person):
  def __init__(self, name, age, id):
    # calling constructor of super class
    super().__init__(name, age)
    self.empId = id

  def displayData(self):
    print('In child class displayData method')
    #calling super class method
    super().displayData()
    print(self.empId)

#Employee class object
emp = Employee('John', 40, 'E005')
emp.displayData()

Output

In child class displayData method
In parent class displayData method
John
40
E005

As you can see only the empId field is initialized in the __init__() function of the Employee class, for initializing the other two fields __init__() function of the Person class (Base class) is called using the super() method.

Method overriding is also used in this example where the parent class’ displayData() method is overridden in the child class. For calling the displayData() method of the parent class again super() is used.

Types of Inheritance

As per OOPS concepts there are 5 types of Inheritance.

Single Inheritance

In this type of inheritance a sub class is derived from a single Super class. We have already seen Python examples of single inheritance above.

Single Inheritance in Java

Multi-level inheritance

In multi-level inheritance, a subclass inherits from another sub class which in turn may inherit from another subclass thus having levels (parent – child – grand child) of hierarchy.

class Parent:
    ...
    ...
#inherits Parent
class Child(Parent):
    ...
    ...
#inherits Child
class GrandChild(Child):
    ...
    ...
Multi-level inheritance in java

Multiple Inheritance

In multiple inheritance, a sub class is created using more than one super class.

class Parent1:
    ...
    ...
class Parent2:
    ...
    ...
#inherits Parent1 and Parent2
class Child(Parent1, Parent2):
    ...
    ...
Multiple Inheritance

Hierarchical Inheritance

In this type of inheritance more than one sub classes are created from the same super class.

class Parent:
    ...
    ...
#inherits Parent
class Child1(Parent):
    ...
    ...
#inherits Parent
class Child2(Parent):
    ...
    ...
Hierarchical Inheritance

Hybrid inheritance

Hybrid inheritance is the combination of more than one inheritance types. Hence, it may be a combination of Multilevel and Multiple inheritance or Hierarchical and Multilevel inheritance or Hierarchical and Multiple inheritance.

Hybrid inheritance

That's all for this topic Inheritance in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Python Installation on Windows
  2. Operator Overloading in Python
  3. Abstract Class in Python
  4. Local, Nonlocal And Global Variables in Python
  5. Python return Statement With Examples

You may also like-

  1. self in Python
  2. Removing Spaces From String in Python
  3. Python Program to Display Fibonacci Series
  4. Global Keyword in Python With Examples
  5. Installing Ubuntu Along With Windows
  6. How to Read File From The Last Line in Java
  7. Dependency Injection in Spring Framework
  8. Word Count MapReduce Program in Hadoop

Saturday, May 28, 2022

Binary Tree Implementation in Java - Insertion, Traversal And Search

In this post we’ll see an implementation of binary tree in Java. Operations covered in this post are-

Since deletion of a node from binary search tree is a complex operation having many scenarios so it is taken up as a separate post- Java Program to Delete a Node From Binary Search Tree (BST)

Binary tree data structure

A binary tree is a tree where each node can have at most two children. So a node in binary tree can have only a left child, or a right child, or both or it can have no children which makes it a leaf node.

Binary tree data structure gives the best of both linked list and an ordered array. You can insert and delete nodes fast as in linked list and search a node fast as in an ordered array.

Binary Search tree

Implementation shown here is actually a binary search tree which is a kind of binary tree. In Binary search tree for each node the node’s left child must have a value less than its parent node and the node’s right child must have a value greater than or equal to its parent. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node and the right subtree must have nodes with values greater than the root node.

binary search tree

Binary Search tree implementation in Java

To represent each node in the binary search tree a node class is used which apart from data also has two references for left and right child.

class Node{
  int value;
  Node left;
  Node right;
  Node(int value){
    this.value = value;
    left = null;
    right = null;        
  }
}

In the Binary tree implementation class in Java apart from the methods for insertion, traversal and search there is a single field of type Node that holds the root.

class BinaryTree{
  Node root;
  ...
}

Inserting node in a Binary Search tree

When a new node is inserted in a binary search tree you need to find the location to insert the new node. Start from the root and compare the value of the root node with the value of the new node. You need to go to the left child if value is less than the root node value otherwise you need to go to the right child. This traversal is followed until you encounter null that’s the location where new node has to be inserted.

binary tree insertion java

Binary tree insertion Java program can be written as both-

Binary tree insertion Java program – Iterative

public void insert(int i){
  Node newNode = new Node(i);
  if(root == null){
    root = newNode;
  }else{
    Node current = root;
    Node parent;
    while(true){
      parent = current;
      if(i < current.value){
        current = current.left;
        if(current == null){
          parent.left = newNode;
          return;
        }
      }else{
        current = current.right;
        if(current == null){
          parent.right = newNode;
          return;
        }
      }
    }
  }
}

Binary tree insertion Java program – Recursive

public Node insert(Node node, int value){
  if(node == null){
    return new Node(value);
  }
  // Move to the left if passed value is 
  // less than the current node
  if(value < node.value){
    node.left = insert(node.left, value);
  }
  // Move to the right if passed value is 
  // greater than the current node
  else if(value > node.value){
    node.right = insert(node.right, value);
  }
  return node;
}

Searching node in Binary Search tree

Logic for finding a node in binary tree is very similar to binary tree insertion logic. Only difference is that in insertion logic node is inserted when null is encountered where as if null is encountered when searching for a node that means searched node is not found in the binary tree.

Java program to search a node in Binary Search tree

public Node find(int searchedValue){
  Node current = root;
  while(current.value != searchedValue){
    if(searchedValue < current.value)
      // Move to the left if searched value is less
      current = current.left;
    else
      // Move to the right if searched value is >=
      current = current.right;
    if(current == null){
      return null;
    }
  }
  return current;
}

Binary tree traversal

When you traverse a tree you visit each node in a specified order. The order that can be used for traversal are-

Binary tree Inorder traversal Java program

Logic for Inorder traversal of binary search tree is as follows-

  • Recursively traverse the left subtree
  • Visit the root node
  • Recursively traverse the right subtree

Note that inorder traversal of the binary search tree visit the nodes in ascending order so inorder traversal is also used for tree sort.

// For traversing in order
public void inOrder(Node node){
  if(node != null){
    inOrder(node.left);
    node.displayData();
    inOrder(node.right);
  }
}

Binary tree Preoder traversal Java program

Logic for preorder traversal of binary search tree is as follows-

  • Visit the root node
  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree
// Preorder traversal
public void preOrder(Node node){
  if(node != null){
    node.displayData();
    preOrder(node.left);        
    preOrder(node.right);
  }
}

Binary tree Postorder traversal Java program

Logic for postorder traversal of binary search tree is as follows-

  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree
  • Visit the root node
// Postorder traversal
public void postOrder(Node node){
  if(node != null){
    postOrder(node.left);
    postOrder(node.right);
    node.displayData();       
  }
}

Binary Search tree Java implementation – Insertion, traversal and search node

Here is a complete binary search tree implementation program in Java with methods for inserting a node in BST, traversing binary search tree in preorder, posrtorder and inorder, search a node in binary search tree.

public class BinaryTree {
  // first node
  private Node root;
  BinaryTree(){
    root = null;
  }
  // Class representing tree nodes
  static class Node{
    int value;
    Node left;
    Node right;
    Node(int value){
      this.value = value;
      left = null;
      right = null;        
    }
    public void displayData(){
      System.out.print(value + " ");
    }
  }
    
  public void insert(int i){
    root = insert(root, i);
  }
    
  //Inserting node - recursive method
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
  // Search node in binary search tree
  public Node find(int searchedValue){
    Node current = root;
    while(current.value != searchedValue){
      if(searchedValue < current.value)
        // Move to the left if searched value is less
        current = current.left;
      else
        // Move to the right if searched value is >=
        current = current.right;
      if(current == null){
        return null;
      }
    }
    return current;
  }
    
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      inOrder(node.left);
      node.displayData();
      inOrder(node.right);
    }
  }
  // Preorder traversal
  public void preOrder(Node node){
    if(node != null){
      node.displayData();
      preOrder(node.left);           
      preOrder(node.right);
    }
  }
  // Postorder traversal
  public void postOrder(Node node){
    if(node != null){
      postOrder(node.left);
      postOrder(node.right);
      node.displayData();          
    }
  }
    
  public static void main(String[] args) {
    BinaryTree bst = new BinaryTree();
    bst.insert(50);
    bst.insert(70);
    bst.insert(15);
    bst.insert(35);
    bst.insert(30);
    bst.insert(31);
    System.out.println("Inorder traversal of binary tree");
    bst.inOrder(bst.root);
    System.out.println();
    Node node = bst.find(16);
    System.out.println((node == null)? "Node not found" : String.valueOf(node.value));
    System.out.println("Preorder traversal of binary tree");
    bst.preOrder(bst.root);
    System.out.println();
    System.out.println("Postorder traversal of binary tree");
    bst.postOrder(bst.root);
    System.out.println();
  }
}

Output

Inorder traversal of binary tree
15 30 31 35 50 70 
Node not found
Preorder traversal of binary tree
50 15 35 30 31 70 
Postorder traversal of binary tree
31 30 35 15 70 50 

That's all for this topic Binary Tree Implementation in Java - Insertion, Traversal And Search. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  2. Doubly Linked List Implementation Java Program
  3. Interpolation Search Program in Java
  4. Shell Sort Program in Java
  5. Armstrong Number or Not Java Program

You may also like-

  1. Creating PDF in Java Using iText
  2. How to Create Password Protected Zip File in Java
  3. Convert String to Byte Array Java Program
  4. Array Rotation Java Program
  5. Just In Time Compiler (JIT) in Java
  6. Method Reference in Java
  7. static Block in Java
  8. Spring Bean Life Cycle

Friday, May 27, 2022

Spring Boot + Spring Security JWT Authentication Example

In this tutorial we’ll see how to create a Spring Boot application that uses Spring Security and JWT token based authentication to bring authentication and authorization to the exposed REST APIs. DB used is MySQL.

What does JWT do

JWT (JSON Web Token) is used for securing REST APIs.

In the JWT authentication process a client application first need to authenticate using credentials. The server side verifies the sent credentials, if valid then it generates and returns a JWT.

Once the client has been authenticated it has to sent the token in the request’s Authorization header in the Bearer Token form with each request. The server will check the validity of the token to verify the validity of the client and authorize or reject requests. You can also store roles and method usage will be authorized based on the role.

You can also configure the URLs that should be authenticated and those that will be permitted without authentication.

Spring Boot + Spring Security with JWT authentication example

In the application we’ll have the user signup and user signin logic. Once the signup is done user should be authenticated when logging in, that configuration would be done using Spring security and JWT.

Thursday, May 26, 2022

Abstract Class in Python

An abstract class is a class that contains one or more abstract methods. An Abstract method is a method that generally doesn’t have any implementation, it is left to the sub classes to provide implementation for the abstract methods. Here note that in Python, abstract method can have implementation in the abstract class too but the sub class inheriting that abstract class is still forced to override the abstract methods.


Abstract class in Python

In Python abstract class is created by deriving from the meta class ABC which belongs to the abc (Abstract Base Class) module.

Syntax for creating abstract class in Python

from abc import ABC
Class MyClass(ABC):

From abc module ABC meta class has to be imported and abstract class has to inherit ABC class in order to be considered as an abstract class.

Abstract method in Python

For defining abstract methods in an abstract class method has to be decorated with @abstractmethod decorator. From abc module @abstractmethod decorator has to be imported to use that annotation.

Syntax for defining abstract method in abstract class in Python is as given below.

from abc import ABC, abstractmethod
Class MyClass(ABC):
 @abstractmethod
 def mymethod(self):
  #empty body
  pass

Important points about abstract class in Python

  1. Abstract class can have both concrete methods as well as abstract methods.
  2. Abstract class works as a template for other classes. Using an abstract class you can define a generalized structure without providing complete implementation of every method. Methods which provide common functionality to be used for all derived classes are defined as concrete methods in abstract class where as the methods where implementation may vary are defined as abstract methods.
  3. Abstract class can’t be instantiated so it is not possible to create objects of an abstract class.
  4. Generally abstract methods defined in abstract class don’t have any body but it is possible to have abstract methods with implementation in abstract class. Any sub class deriving from such abstract class still needs to provide implementation for such abstract methods.
  5. If any abstract method is not implemented by the derived class Python throws an error.

Python abstract class example

In the example there is an abstract class with a concrete method common and an abstract method vary. Two sub classes Child1 and Child2 inherit the abstract class Parent and implement the abstract method vary.

from abc import ABC, abstractmethod
class Parent(ABC):
  #common functionality
  def common(self):
    print('In common method of Parent')
  @abstractmethod
  def vary(self):
    pass

class Child1(Parent):
  def vary(self):
    print('In vary method of Child1')

class Child2(Parent):
  def vary(self):
    print('In vary method of Child2')

# object of Child1 class
obj = Child1()
obj.common()
obj.vary()
# object of Child2 class
obj = Child2()
obj.common()
obj.vary()

Output

In common method of Parent
In vary method of Child1
In common method of Parent
In vary method of Child2

As you can see when common method is called the common() method of Parent is invoked. When vary method is called, method defined with in the subclass is invoked.

Python abstract class with abstract method implemented

Even if you provide implementation of abstract method in abstract class sub class is still forced to implement the abstract method.

from abc import ABC, abstractmethod
class Parent(ABC):
  #common functionality
  def common(self):
    print('In common method of Parent')
  @abstractmethod
  def vary(self):
    print('In vary method of Parent')

class Child(Parent):
  pass

# object of Child1 class
obj = Child()
obj.common()
obj.vary()

Output

Traceback (most recent call last):
  File "F:/NETJS/NetJS_2017/Python/Test/Parent.py", line 18, in <module>
    obj = Child()
TypeError: Can't instantiate abstract class Child with abstract methods vary

If you implement vary() method in subclass then it works fine.

from abc import ABC, abstractmethod
class Parent(ABC):
  #common functionality
  def common(self):
    print('In common method of Parent')
  @abstractmethod
  def vary(self):
    print('In vary method of Parent')

class Child(Parent):
  def vary(self):
    print('In vary method of Child')

# object of Child class
obj = Child()
obj.common()
obj.vary()

Output

In common method of Parent
In vary method of Child

Not implementing all abstract methods

If subclass doesn’t implement all the abstract methods defined in the inherited abstract class that also results in an error.

from abc import ABC, abstractmethod
class Parent(ABC):
  #common functionality
  def common(self):
    print('In common method of Parent')
  @abstractmethod
  def vary(self):
    pass
  @abstractmethod
  def test(self):
    pass
    
class Child(Parent):
  def vary(self):
    print('In vary method of Child')

# object of Child class
obj = Child()
obj.common()
obj.vary()

Output

Traceback (most recent call last):
  File "F:/NETJS/NetJS_2017/Python/Test/Parent.py", line 17, in <module>
    obj = Child()
TypeError: Can't instantiate abstract class Child with abstract methods test

Instantiating abstract class in Pyhton

Since abstract class are supposed to have abstract methods having no body so abstract classes are not considered as complete concrete classes, thus it is not possible to instantiate an abstract class.

from abc import ABC, abstractmethod
class Parent(ABC):
  def __init__(self, value):
    self.value = value;
    super().__init__()
  #common functionality
  def common(self):
    print('In common method of Parent', self.value)
  @abstractmethod
  def vary(self):
    pass

class Child(Parent):
  def vary(self):
    print('In vary method of Child')

# trying to instantiate abstract class
obj = Parent(3)
obj.common()
obj.vary()

Output

Traceback (most recent call last):
  File "F:/NETJS/NetJS_2017/Python/Test/Parent.py", line 18, in <module>
    obj = Parent(3)
TypeError: Can't instantiate abstract class Parent with abstract methods vary

That's all for this topic Abstract Class in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Interface in Python
  2. Method Overloading in Python
  3. Inheritance in Python
  4. Abstraction in Python
  5. Python String isdigit() Method

You may also like-

  1. Constructor in Python - __init__() function
  2. String Length in Python - len() Function
  3. raise Statement in Python Exception Handling
  4. Default Arguments in Python
  5. Java Semaphore With Examples
  6. Reverse Each Word in a String Java Program
  7. Bean Scopes in Spring With Examples
  8. Parquet File Format in Hadoop

Wednesday, May 25, 2022

finally Block in Java Exception Handling

In the post try-catch Block in Java we have already seen how to use try catch block for exception handling. In this post we'll get to know about finally block in Java which is used along with try catch block.

finally block in Java

When an exception occurs in the code, the flow of the execution may change or even end abruptly. That may cause problem if some resources were opened in the method where exception occurred.

For example, In a method a file was opened, while executing code in the method some exception occurred so the opened file was never closed, which effectively means that the resources will remain open consuming memory. Let's try to understand it with the following code.

1   public static void main(String[] args) {
2     BufferedReader br = null;
3     try{
4      String strLine;
5      // Instance of FileReader wrapped in a BufferedReader
6      br = new BufferedReader(new java.io.FileReader("F:\\abc.txt"));
7      ...
8      ...
9      ... //Exception happens here
10     ...
11     br.close()
12    }catch(IOException ioExp){
13     System.out.println("Error while reading file " + ioExp.getMessage());
14    }
15  }

At line 6 a BufferedReader stream is opened, which is closed in line 11. Suppose exception occurs at line 9 which changes the flow of the code execution because now the execution moves to catch block directly. Because of the exception, code execution moves from line 9 directly to line 13, meaning line 11 where stream is closed never getting executed.

You do need some mechanism to handle such scenarios. That's where finally block in Java helps by providing exception-handling mechanism to clean up.

Code with in the finally block will be executed after try/catch block has completed. Also note that the finally block in Java is always executed whether or not an exception is thrown.

If the code with in try block executes without throwing any exception, the finally block is executed immediately after the completion of try block. If an exception is thrown with in the try block, the finally block is executed immediately after executing the catch block (if exists) which handled the thrown exception.

Example of finally in Java

Note that, even if there is a return statement in try block, finally will be executed.

public class FinallyDemo {

 public static void main(String[] args) {
  int i = displayValue();
  System.out.println("Value of i " + i);
 }
 
 static int displayValue(){
  try{
   System.out.println("In try block");
   return 1;
  }finally{
   System.out.println("In finally block");
   return 2;
  }
 }
}

Output

In try block
In finally block
Value of i 2

It can be seen, though try block has a return value and no exception is thrown, still finally is executed. Ultimately return value is what finally returns.

Even if the exception is thrown still return value will be what finally returns. Let's see the same example again, this time an exception will be thrown.

public class FinallyDemo {

 public static void main(String[] args) {
  int i = displayValue();
  System.out.println("Value of i " + i);
 }
 
 static int displayValue(){
  try{
   System.out.println("In try block");
   throw new NullPointerException();
  }catch(NullPointerException nExp){
   System.out.println("Exception caught in catch block of displayValue");
   return 2;
  }finally{
   System.out.println("In finally block");
   //return 3;
  }
 }
}

Output

In try block
Exception caught in catch block of displayValue
In finally block
Value of i 3

Please note that it is not a good idea to return any thing from finally as it will suppress the exception. finally must be used for cleaning up.

Finally block Java example for cleaning up

A very good scenario when you should use finally block is when you are reading a file in Java. It is always advisable to close input and output streams in finally block in such cases to avoid resource kept opened in case of any exception.

public class FileRead {

 public static void main(String[] args) {
  BufferedReader br = null;
  try{
   String strLine;
   // Instance of FileReader wrapped in a BufferedReader
   br = new BufferedReader(new java.io.FileReader("F:\\abc.txt"));
   ...
   ...
  }catch(IOException ioExp){
   System.out.println("Error while reading file " + ioExp.getMessage());
  }finally {
   try {
    // Close the stream
    if(br != null){
     br.close();
    }
   } catch (IOException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
  }
 }
}

Points to note-

  • Every try block must be followed by at least one catch or a finally clause. So we can have any of these combinations try-catch, try-finally or try-catch-finally blocks.
  • When method is about to return from its try-catch block after normal execution flow or because of an uncaught exception, finally block is executed just before the method returns.
  • If there are multiple catch blocks and none of them can handle the exception thrown, even then the finally bock is executed.
  • Though there can be multiple catch blocks associated with a single try statement but there can only be single finally block associated with a try block. In case of nested try blocks there can be associated finally blocks with respective try blocks.
  • Finally block in Java is used to close the allocated resources (like file handles, database connections) before returning from the method.
  • It's not a good idea to return any value from finally as it may cause any exceptions that are not caught in the method to be lost.
  • If the JVM exits (through System.exit() or JVM crash) while the try or catch code is being executed, then the finally block may not execute. In case of multithreading if the thread executing the try or catch code is interrupted or killed, the finally block may not execute even though the application as a whole continues.

That's all for this topic finally Block in Java Exception Handling. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. final Vs finally Vs finalize in Java
  2. Creating Custom Exception Class in Java
  3. throws Keyword in Java Exception Handling
  4. Exception Handling in Java Lambda Expressions
  5. Java Exception Handling Interview Questions And Answers

You may also like-

  1. What Are JVM, JRE And JDK in Java
  2. Java Automatic Numeric Type Promotion
  3. Interface Static Methods in Java
  4. Creating a Thread in Java
  5. Synchronization in Java - Synchronized Method And Block
  6. How to Read Input From Console in Java
  7. How to Create PDF From XML Using Apache FOP
  8. Lambda Expression Examples in Java

Tuesday, May 24, 2022

How to Create PDF From XML in Java Using Apache FOP

In this post we'll see how to create PDF from XML in Java using Apache FOP.

What is Apache FOP

Apache™ FOP (Formatting Objects Processor) is a print formatter driven by XSL formatting objects (XSL-FO) and an output independent formatter. It is a Java application that reads a formatting object (FO) tree and renders the resulting pages to a specified output.
FOP uses the standard XSL-FO file format as input, lays the content out into pages, then renders it to the requested output.
Read more about it here- https://xmlgraphics.apache.org/fop/

How to get Apache FOP

Get the FOP download from here.
https://xmlgraphics.apache.org/fop/download.html

I have used fop-2.0 for this example code.
Needed jars (found in the lib and build directory in the fop download)-

  • Commons-io
  • Commons-logging
  • Xml-apis
  • Xmlgraphics-commons
  • Fop
  • Batik-all
  • Avalon-framework
If you want to add maven dependency for Apache FOP then it is as following.
<dependency>
  <groupId>org.apache.xmlgraphics</groupId>
  <artifactId>fop</artifactId>
  <version>2.7</version>
  <exclusions>
  <exclusion>
      <groupId>xml-apis</groupId>
      <artifactId>xml-apis</artifactId>
  </exclusion>
 </exclusions>
</dependency>

Here we have an exclusion for xml-apis because of the javax.xml package conflict, this package is present in Java too and that's what will be used.


Steps for creating a PDF from XML in Java using Apache FOP

To produce a PDF file from a XML file, first step is that we need an XSLT stylesheet that converts the XML to XSL-FO. Created XSL-FO file is also an XML file which contains formatted objects.
The second step will be done by FOP when it reads the generated XSL-FO document and formats it to a PDF document.

Creating PDF using FOP Java example

XML used for creating PDF is as follows.
<?xml version="1.0"?>

<employees>
<companyname>ABC Inc.</companyname>
 <employee>
  <id>101</id>
  <name>Ram</name>
  <designation>Manager</designation>
 </employee>

 <employee>
  <id>102</id>
  <name>Prabhu</name>
  <designation>Executive</designation>
 </employee>

 <employee>
  <id>103</id>
  <name>John</name>
  <designation>Executive</designation>
 </employee>
</employees>

Stylesheet Used

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.1" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
    xmlns:fo="http://www.w3.org/1999/XSL/Format" exclude-result-prefixes="fo">
  <xsl:template match="employees">
    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format">
      <fo:layout-master-set>
        <fo:simple-page-master master-name="simpleA4" page-height="29.7cm" page-width="21cm" margin-top="2cm" margin-bottom="2cm" margin-left="2cm" margin-right="2cm">
          <fo:region-body/>
        </fo:simple-page-master>
      </fo:layout-master-set>
      <fo:page-sequence master-reference="simpleA4">
        <fo:flow flow-name="xsl-region-body">
          <fo:block font-size="16pt" font-weight="bold" space-after="5mm">Company Name: <xsl:value-of select="companyname"/>
          </fo:block>
          <fo:block font-size="10pt">
          <fo:table table-layout="fixed" width="100%" border-collapse="separate">    
            <fo:table-column column-width="4cm"/>
            <fo:table-column column-width="4cm"/>
            <fo:table-column column-width="5cm"/>
            <fo:table-body>
              <xsl:apply-templates select="employee"/>
            </fo:table-body>
          </fo:table>
          </fo:block>
        </fo:flow>
      </fo:page-sequence>
    </fo:root>
  </xsl:template>
  <xsl:template match="employee">
    <fo:table-row>   
     <xsl:if test="designation = 'Manager'">
            <xsl:attribute name="font-weight">bold</xsl:attribute>
      </xsl:if>
      <fo:table-cell>
        <fo:block>
          <xsl:value-of select="id"/>
        </fo:block>
      </fo:table-cell>
       
      <fo:table-cell>
        <fo:block>
          <xsl:value-of select="name"/>
        </fo:block>
      </fo:table-cell>   
      <fo:table-cell>
        <fo:block>
      <xsl:value-of select="designation"/>
        </fo:block>
      </fo:table-cell>
    </fo:table-row>
  </xsl:template>
</xsl:stylesheet>

If you see the XSL, first I am looking for the employees element to get the company Name and also there some formatting is done like how many columns are needed and what should be the width. Then I am looking for the employee element and printing the values, also some logic is there to print the field values in bold if the designation is manager.

Copying the output of PDF I got, that will make it easy to understand the XSL.

PDF from XML in Java using Apache FOP

Java code

import java.io.File;
import java.io.IOException;
import java.io.OutputStream;

import javax.xml.transform.Result;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerException;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.sax.SAXResult;
import javax.xml.transform.stream.StreamResult;
import javax.xml.transform.stream.StreamSource;

import org.apache.fop.apps.FOPException;
import org.apache.fop.apps.FOUserAgent;
import org.apache.fop.apps.Fop;
import org.apache.fop.apps.FopFactory;
import org.apache.fop.apps.MimeConstants;

public class FOPPdfDemo {

  public static void main(String[] args) {
    FOPPdfDemo fOPPdfDemo = new FOPPdfDemo();
    try {
      fOPPdfDemo.convertToFO();
    } catch (FOPException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    } catch (IOException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    } catch (TransformerException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }
  }
	
	
	/**
	 * Method that will convert the given XML to PDF 
	 * @throws IOException
	 * @throws FOPException
	 * @throws TransformerException
	 */
	public void convertToPDF()  throws IOException, FOPException, TransformerException {
    // the XSL FO file
    File xsltFile = new File("D:\\NETJS\\xml\\template.xsl");
    // the XML file which provides the input
    StreamSource xmlSource = new StreamSource(new File("D:\\NETJS\\xml\\Employees.xml"));
    
    // create an instance of fop factory
    FopFactory fopFactory = FopFactory.newInstance(new File(".").toURI());
    // a user agent is needed for transformation
    FOUserAgent foUserAgent = fopFactory.newFOUserAgent();
    // Setup output
    OutputStream out;
    
    out = new java.io.FileOutputStream("D:\\NETJS\\xml\\employee.pdf");

    try {
      // Construct fop with desired output format
      Fop fop = fopFactory.newFop(MimeConstants.MIME_PDF, foUserAgent, out);

      // Setup XSLT
      TransformerFactory factory = TransformerFactory.newInstance();
      Transformer transformer = factory.newTransformer(new StreamSource(xsltFile));

      // Resulting SAX events (the generated FO) must be piped through to FOP
      Result res = new SAXResult(fop.getDefaultHandler());

      // Start XSLT transformation and FOP processing
      // That's where the XML is first transformed to XSL-FO and then 
      // PDF is created
      transformer.transform(xmlSource, res);
    } finally {
      out.close();
    }
	}
	
	/**
	 * This method will convert the given XML to XSL-FO
	 * @throws IOException
	 * @throws FOPException
	 * @throws TransformerException
  */
	public void convertToFO()  throws IOException, FOPException, TransformerException {
    // the XSL FO file
    File xsltFile = new File("D:\\NETJS\\xml\\template.xsl");
    
    
    /*TransformerFactory factory = TransformerFactory.newInstance();
    Transformer transformer = factory.newTransformer(new StreamSource("F:\\Temp\\template.xsl"));*/
    
    // the XML file which provides the input
    StreamSource xmlSource = new StreamSource(new File("D:\\NETJS\\xml\\Employees.xml"));
    
    // a user agent is needed for transformation
    /*FOUserAgent foUserAgent = fopFactory.newFOUserAgent();*/
    // Setup output
    OutputStream out;
    
    out = new java.io.FileOutputStream("D:\\NETJS\\xml\\temp.fo");
	
    try {
      // Setup XSLT
      TransformerFactory factory = TransformerFactory.newInstance();
      Transformer transformer = factory.newTransformer(new StreamSource(xsltFile));

      // Resulting SAX events (the generated FO) must be piped through to FOP
      //Result res = new SAXResult(fop.getDefaultHandler());

      Result res = new StreamResult(out);

      //Start XSLT transformation and FOP processing
      transformer.transform(xmlSource, res);


      // Start XSLT transformation and FOP processing
      // That's where the XML is first transformed to XSL-FO and then 
      // PDF is created
      transformer.transform(xmlSource, res);
    } finally {
      out.close();
    }
  }
}

In the code there are two methods convertToPDF() and convertToFO(), convertToPDF() method is used to convert XML to PDF. convertToFO() method will create the XSL-FO from the XML using the XSLT. If you want to see the created FO which in turn is used to create PDF please call this method.

Create PDF in web application using Apache FOP

In case of web application if you want to provide PDF as a download, here is a Servlet method as reference-

    protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
      try{
        FopFactory fopFactory = FopFactory.newInstance(new File(".").toURI());

        //Setup a buffer to obtain the content length
        ByteArrayOutputStream out = new ByteArrayOutputStream();

        Fop fop = fopFactory.newFop(MimeConstants.MIME_PDF, out);
        TransformerFactory factory = TransformerFactory.newInstance();
        Transformer transformer = factory.newTransformer(new StreamSource(PATH_TO_XSL));
        //Make sure the XSL transformation's result is piped through to FOP
        Result res = new SAXResult(fop.getDefaultHandler());

        //Setup input
        Source src = new StreamSource(new File("./resources/Employees.xml"));

        //Start the transformation and rendering process
        transformer.transform(src, res);

        //Prepare response
        response.setContentType("application/pdf");
        response.setContentLength(out.size());

        //Send content to Browser
        response.getOutputStream().write(out.toByteArray());
        response.getOutputStream().flush();
      }catch(Exception e){
        e.printStackTrace();
      }
    }

That's all for this topic How to Create PDF From XML in Java Using Apache FOP. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. How to Create PDF in Java Using OpenPDF
  2. Creating PDF in Java Using Apache PDFBox
  3. HTML to PDF in Java + Flying Saucer and OpenPDF
  4. Convert HTML to PDF in Java + Openhtmltopdf and PDFBox
  5. Unzip File in Java

You may also like-

  1. Spring MVC PDF Generation Example
  2. Add Double Quotes to a String Java Program
  3. Print Odd-Even Numbers Using Threads And Semaphore Java Program
  4. Method Overloading in Java
  5. Race Condition in Java Multi-Threading
  6. How to Fix The Target Type of This Expression Must be a Functional Interface Error
  7. Callable and Future in Java With Examples
  8. Unmodifiable or Immutable Map in Java

Method Overloading in Python

Method overloading is an OOPS concept which provides ability to have several methods having the same name with in the class where the methods differ in types or number of arguments passed.

Method overloading in Python

Method overloading in its traditional sense (as defined above) as exists in other languages like method overloading in Java doesn’t exist in Python.

In Python if you try to overload a function by having two or more functions having the same name but different number of arguments only the last defined function is recognized, calling any other overloaded function results in an error.

For example in the given class there are two methods having the name sum but number of parameters differ.

class OverloadDemo:
  # first sum method, two parameters
  def sum(self, a, b):
    s = a + b
    print(s)
  # overloaded sum method, three parameters
  def sum(self, a, b, c):
    s = a + b + c
    print(s)

od =  OverloadDemo()
od.sum(7, 8)

Output

File "F:/NETJS/NetJS_2017/Python/Test/OverloadDemo.py", line 10, in <module>
    od.sum(7, 8)
TypeError: sum() missing 1 required positional argument: 'c'

As you can here when calling the method with two parameters an error is thrown as this sum() method is not the latest.

If you call the method having three parameters code runs fine.

class OverloadDemo:
  # first sum method, two parameters
  def sum(self, a, b):
    s = a + b
    print(s)
  # overloaded sum method, three parameters
  def sum(self, a, b, c):
    s = a + b + c
    print(s)

od =  OverloadDemo()
od.sum(7, 8, 9)

Output

24

Process finished with exit code 0

Achieving method overloading in Python

Since using the same method name again to overload the method is not possible in Python, so achieving method overloading in Python is done by having a single method with several parameters. Then you need to check the actual number of arguments passed to the method and perform the operation accordingly.

For example if we take the same method sum() as used above with the capability to pass two or three parameters, in Python this method overloading can be done as shown in the below example.

class OverloadDemo:
  # sum method with default as None for parameters
  def sum(self, a=None, b=None, c=None):
    # When three params are passed
    if a!=None and b!=None and c!=None:
      s = a + b + c
      print('Sum = ', s)
    # When two params are passed
    elif a!=None and b!=None:
      s = a + b
      print('Sum = ', s)

od =  OverloadDemo()
od.sum(7, 8)
od.sum(7, 8, 9)

Output

Sum =  15
Sum =  24

Process finished with exit code 0

That's all for this topic Method Overloading in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Python Installation on Windows
  2. Python First Program - Hello World
  3. Encapsulation in Python
  4. Name Mangling in Python
  5. Namespace And Variable Scope in Python

You may also like-

  1. Check String Empty or Not in Python
  2. Abstract Class in Python
  3. Concatenating Lists in Python
  4. Python Generator, Generator Expression, Yield Statement
  5. Marker interface in Java
  6. How Linked List class works internally in Java
  7. Race Condition in Java Multi-Threading
  8. What is Hadoop Distributed File System (HDFS)

Sorted Linked List In Java Program

In this post we’ll see an implementation of sorted Linked List in Java. In a sorted linked list data is maintained in sorted order. For each insertion in the sorted list, item needs to be inserted at the appropriate location. You need to find the first item that is greater than the inserted item (in case of ascending order) and element should be inserted just before that item.

Java program for Sorted Linked List

In the Java program for sorted list there are two operations.

  1. Insertion in the sorted list
  2. Removing first item from the list (deleting minimum value).

For representing nodes of the linked list a separate class is used which apart from the data also holds a reference to itself.

static class Node{
 //data
 int i;
 // Reference to next node
 Node next;
}

In the sorted list class there is also a reference head of type Node that points to the first node of the sorted list.

Insertion in the sorted list

For insertion in the sorted linked list 2 references are maintained previous and current, you start with-

Node current = head;
Node previous = null;
Then you keep moving through the nodes while the inserted data is greater than the data stored in the traversed node.
while(current != null && data > current.i){
  previous = current;
  current = current.next;
}

At that location new node is inserted so that the previous node starts pointing to the new node and new node points to the current node.

previous.next = newNode;
newNode.next = current;

Following image shows how insertion in sorted linked list works.

Sorted Linked List In Java

Sorted Linked List – Full Java program

public class SortedLinkedList {
  // reference to first node
  private Node head;
  SortedLinkedList(){
    head = null;
  }
  // Class for nodes
  static class Node{
    //data
    int i;
    Node next;
    Node(int i){
      this.i = i;
      this.next = null;
    }
    public void displayData(){
      System.out.print(i + " ");
    }
  }
    
  public void insert(int data){
    Node newNode = new Node(data);
    Node current = head;
    Node previous = null;
    while(current != null && data > current.i){
      previous = current;
      current = current.next;
    }
    // insertion at beginning of the list
    if(previous == null){
      head = newNode;
    }else{
      previous.next = newNode;
    }
    newNode.next = current;
  }
    
  public Node remove(){
    if(head == null){
      throw new RuntimeException("List is empty..");
    }
    Node temp = head;
    head = head.next;
    return temp;
  }
    
  // Method to traverse and display all nodes
  public void displayList(){
    Node current = head;
    while(current != null){
      current.displayData();
      current = current.next;
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    SortedLinkedList list = new SortedLinkedList();
    list.insert(10);
    list.insert(30);
    list.insert(60);
    System.out.println("After initial insertions--");
    list.displayList();
    list.insert(20);
    list.insert(40);
    list.insert(5);
    list.insert(70);
    System.out.println("After insertions--");
    list.displayList();
    Node node = list.remove();
    System.out.println("Item removed-- " + node.i);
    list.displayList();
  }
}

Output

After initial insertions--
10 30 60 
After insertions--
5 10 20 30 40 60 70 
Item removed-- 5
10 20 30 40 60 70

That's all for this topic Sorted Linked List In Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Doubly Linked List Implementation Java Program
  2. How to Reverse a Linked List in Java
  3. Binary Tree Traversal Using Depth First Search Java Program
  4. Ternary Search Program in Java
  5. Convert Numbers to Words Java Program

You may also like-

  1. Java Program to Get All DB Schemas
  2. Convert String to Byte Array Java Program
  3. Find Largest and Second Largest Number in Given Array Java Program
  4. Java Lambda Expression Comparator Example
  5. CompletableFuture in Java With Examples
  6. AutoBoxing And UnBoxing in Java
  7. Association, Aggregation And Composition in Java
  8. Spring Profiles With Examples