About Me

My photo
"Enoughtheory.com" had its humble beginning in the year 2011 by ( Founder of Enoughtheory.com ) Mr Ravi Kant Soni , an Enterprise Java and Spring Framework Specialist, with a bachelor degree (B.E) in Information Science and Engineering from Reva Institute of Technology at Bangalore. He has been into the software development discipline for many years now. Ravi has worn many hats throughout his tenure, ranging from software development, designing multi-tenant applications, integration of new technology into an existing system, to his current love of writing a Spring Framework book. Currently, he is a lead engineer at HCL Technology. Ravi has focused on Web and Enterprise development using Spring Framework for most of his career and has been extensively involved in application design and implementation. He has developed applications for Core-Bank, HR and Payroll System, and e-Commerce systems using Spring Framework. Ravi Kant Soni is author of book "Learning Spring Application development" http://learningspringapplicationdevelopment.com

Friday, 27 November 2015

Pagination using JQuery



[don't copy paste]

var pageNo = 1;
var numPages;
var currentPage = 0;
numPages = response.pagination.pageCount;
var paginationToShow = '';
paginationToShow += "<ul class='pagination pagination-sm'>";
if(response.pagination.pageNo > 1){
 paginationToShow += "<li id='NA'></li>";
 paginationToShow += "<li id='first'><a href='#'>First</a></li>";
 paginationToShow += "<li id='previous'><a href='#'>Prev</a></li>";
}else{
 paginationToShow += "<li id='NA'></li>";
 paginationToShow += "<li id='first'></li>";
 paginationToShow += "<li id='previous'></li>";
}
// paginationToShow +=  "<li><a href='#' rel='1'>1<span class='sr-only'>(current)</span></a></li>";
var pageCount = numPages;
var pageNumber = response.pagination.pageNo;
var paginationValues = [];
var activePosition = 0;
var i = 0;
if (pageNumber > 4) {   
 var leftCount = 8 - ((pageCount - pageNumber) >= 4 ? 4
   : (pageCount - pageNumber));
 leftCount = leftCount < pageNumber ? leftCount
   : (pageNumber - 1);
 while (i <= leftCount) {
  paginationValues[i] = pageNumber + i - leftCount;
  i++;
 }
} else {
 while (i < pageNumber) {
  paginationValues[i] = i + 1;
  i++;
 }
}
activePosition = i+3;
if (pageNumber < pageCount) {
 var value = pageNumber + 1;
 var rightCount = 9 - paginationValues.length;
 var j = 0;
 while ((value <= pageCount) && (j < rightCount)) {
  paginationValues[i++] = value++;
  j++;
 }
}
console.log(paginationValues);
console.log(activePosition);  
for (var i = 0; i < paginationValues.length; i++) {
 paginationToShow += "<li><a href='#' rel='" + paginationValues[i] + "'>" + paginationValues[i]
   + "</a></li>";
}
if(response.pagination.pageNo < numPages){
 paginationToShow += "<li id='next'><a href='#'>Next</a></li>";
 paginationToShow += "<li id='last'><a href='#'>Last</a></li>";
 paginationToShow += "<li id='NA'></li>";
}else{
 paginationToShow += "<li id='next'></li>";
 paginationToShow += "<li id='last'></li>";
 paginationToShow += "<li id='NA'></li>";
}
paginationToShow += "</ul>";
$('#page_navigation').html(paginationToShow);
$(
  "#page_navigation li:nth-child("
    + (activePosition) + ")").addClass(
  'active');
flag = true;
currentPage = response.pagination.pageNo;

Friday, 14 August 2015

Encapsulation - the first Pillars of OOPS

Introduction 

Encapsulation is the first pillar or principle of object-oriented programming. “Encapsulation is a process of binding data members (variables, properties) and member functions (methods) into a single unit”. And Class is the best example of encapsulation.  

Encapsulation is an Object Oriented Programming concept that binds together the data and functions that manipulate the data, and that keeps both safe from outside interference and misuse. Encapsulation is the packing of data and functions into a single component. Encapsulation can be described as a protective barrier that prevents the code and data being randomly accessed by other code defined outside the class.

  • Through encapsulation a class can hide the internal details of how an object does something. Encapsulation solves the problem at the implementation level.
  • With the help of encapsulation, a class can change the internal implementation without hurting the overall functionality of the system.
  • A class or structure can specify how accessible each of its members (variables, properties, and methods) is to code outside of the class or structure. 
  • Encapsulation simplifies the interaction between objects. An object can use another object without knowing all its data or how its data is maintained. For example, a Client object might have name, address, company, and department properties. If a Bank object wants to use a Client object, it can request the name and address for the bank without needing to know the company and department details of the Client object.  
 The main benefit of encapsulation is the ability to modify our implemented code without breaking the code of others who use our code. With this feature Encapsulation gives maintainability, flexibility and extensibility to our code.

Why do we encapsulate?

  •  To hide and prevent code (data) from the outside world (here the world means other classes and assemblies).
  • To prevent code (data) from accidental corruption due to programming errors so that we can deliver expected output. Due to programming mistakes, code may not behave properly and it has an effect on data and then it will affect the functionality of the system. With encapsulation we can make variables, properties, and methods private so it is not accessible to all but accessible through proper channels only to protect it from accidental corruption from other classes.
  • To have a class better control over its fields (validating values etc…).

Encapsulation in Java

Encapsulation is the technique of making the fields in a class private and providing access to the fields via public methods. If a field is declared private, it cannot be accessed by anyone outside the class, thereby hiding the fields within the class. For this reason, encapsulation is also referred to as data hiding.

Example  

public class Class {
    private String message;
    public void setaString(String message) {
        this.message = message;
    }
    public String getMessage() {
        return message;
    }
}

You can completely encapsulate a member be it a variable or method in Java by using private keyword and you can even achieve a lesser degree of encapsulation in Java by using other access modifier like protected or public.

Advantage of Encapsulation in Java 

  • Encapsulated Code is more flexible and easy to change with new requirements.
  • Encapsulation in Java makes unit testing easy.
  • Encapsulation in Java allows you to control who can access what.
  • Encapsulation also helps to write immutable class in Java which are a good choice in multi-threading environment.
  • Encapsulation reduce coupling of modules and increase cohesion inside a module because all piece of one thingare encapsulated in one place.
  • Encapsulation allows you to change one part of code without affecting other part of code.

Design Pattern based on Encapsulation in Java 

Factory pattern is one of the design pattern in Java uses encapsulation concept which is used to create objects whose creation logic can vary and also for creating different implementation of same interface.

Why Getters and Setters? 

Why we need accessor and mutator methods in Java, why can’t we just access the data directly? But the purpose of encapsulation here is is not to hide the data itself, but the implementation details on how this data is manipulated. So, once more what we want is a way to provide a public interface through which we can gain access to this data. We can later change the internal representation of the data without compromising the public interface of the class. 

  • You can limit the values that can be stored in a field (i.e. gender must be F or M).
  • You can take actions when the field is modified (trigger event, validate, etc).
  • You can provide thread safety by synchronizing the method.
  • You can switch to a new data representation (i.e. calculated fields, different data type)

Saturday, 5 October 2013

Multithreading and Concurrency in Java

A lot of people have talked about threading, which is one approach, but consider another way of doing it. What if you had several JVM's started up, connected to the network, and waiting for work to come their way? How would you program an application so that it could leverage all of those JVMs without knowing whether or not they are on the same CPU?

Thread-based Concurrent programming to implement Application Parallelism

  •  A modern computer has several CPU's or several cores within one CPU. The ability to leverage these multi-cores can be the key for a successful high-volume application. 
  • Concurrency is the ability to run several programs or several parts of a program in parallel.  
  • If a time consuming task can be performed asynchronously or in parallel, this improve the throughput and the interactivity of the program. 
Back in the old days a computer had a single CPU, and was only capable of executing a single program at a time. Later came multitasking which meant that computers could execute multiple programs (AKA tasks or processes) at the same time. It wasn't really "at the same time" though. The single CPU was shared between the programs. The operating system would switch between the programs running, executing each of them for a little while before switching.  

Multithreading which mean that you could have multiple threads of execution inside the same program. A thread of execution can be thought of as a CPU executing the program. When you have multiple threads executing the same program, it is like having multiple CPU's execute within the same program.  

Multithreading and Concurrency in Java 

  • Java was one of the first languages to make multithreading easily available to developers
  • Threading enable developers to write concurrent applications where different threads execute simultaneously
  • Threading hazards like deadlock, thread starvation, and race conditions, which result from incorrect use of primitives, are also hard to detect and debug
  •  Relying on synchronized to coordinate access between threads leads to performance issues that affect application scalability, a requirement for many modern applications
  • The JSR 166: Concurrency Utilities framework was designed to meet the need for a high-level threading facility

Inside the Java Concurrency Utilities

  • The Java Concurrency Utilities framework is a library of types that are designed to be used as building blocks for creating concurrent classes or applications
  •  These types are thread-safe, have been thoroughly tested, and offer high performance
  •  Types in the Java Concurrency Utilities are organized into small frameworks;
    • Executor framework
    • synchronizer, 
    • concurrent collections, 
    • locks, 
    • atomic variables, and 
    • Fork/Join
  • java.util.concurrent contains high-level utility types that are commonly used in concurrent programming
    • The java.util.concurrent.atomic subpackage contains low-level utility classes that support lock-free thread-safe programming on single variables.  
    • The java.util.concurrent.locks sub-package contains low-level utility types for locking and waiting for conditions, which are different from using Java's low-level synchronization and monitors. 

The Executor framework

  • Because an application creates a new thread for each request, it doesn't scale well when faced with a huge number of requests. For example, each created thread requires memory, and too many threads may exhaust the available memory, forcing the application to terminate
  • Rather than always creating a new thread, you could use a thread pool, in which a fixed number of threads would service incoming tasks
  • The Executor framework is based on the Executor interface
  • Executor as Object capable of executing java.lang.Runnable tasks 
  • Declares the following method for executing a Runnable task
    • void execute(Runnable command) 
  • If the executor cannot execute the task for any reason, this method will throw a RejectedExecutionException
  • The runnable task is thus able to execute via a new thread, a pooled thread, the calling thread, and so on
  • ExecutorService's methods are as
    • boolean awaitTermination(long timeout, TimeUnit unit) blocks the calling thread until all tasks have completed execution after a shutdown request, the timeout occurs, or the current thread is interrupted, whichever happens first.
    • boolean isShutdown() returns true when the executor has been shut down 

If, want to use one thread pool with one thread which executes several runnables you can use the Executors.newSingleThreadExecutor() method

Threads pools with the Executor Framework 

  • Thread pools manage a pool of worker threads. The thread pools contains a work queue which holds tasks waiting to get executed.  
  • A thread pool can be described as a collection of Runnable objects (work queue) and a connections of running threads.
  •  These threads are constantly running and are checking the work query for new work.
  • If there is new work to be done they execute this Runnable.  
  • The Thread class itself provides a method, e.g. execute(Runnable r) to add a new Runnable object to the work queue. 
  • The ExecutorService adds lifecycle methods to the Executor, which allows to shutdown the Executor and to wait for termination

Java Thread Pool Example using Executors


First we need to have a Runnable class
 
package com.enoughtheory.threadpool;

/** * MyRunnable is the task which will be performed * * @author RaviKantSoni * */
public class MyRunnable implements Runnable { 
  private final long countUntil;

  MyRunnable(long countUntil) {
    this.countUntil = countUntil;
  }

  @Override
  public void run() {
    long sum = 0;
    for (long i = 1; i < countUntil; i++) {
      sum += i;
    }
    System.out.println(sum);
  }
} 
 
Now you run your Runnable with the executor framework 


package com.enoughtheory.threadpool;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class SimpleThreadPool {

    public static void main(String[] args) {
        ExecutorService executor = Executors.newFixedThreadPool(5);
        for (int i = 0; i < 10; i++) {
            Runnable worker = new WorkerThread('' + i);
            executor.execute(worker);
          }
         // This will make the executor accept no new threads
        // and finish all existing threads in the queue
        executor.shutdown();
        // Wait until all threads are finish
        executor.awaitTermination();
        System.out.println('Finished all threads');
    }

}







Monday, 2 September 2013

Just Java

  • Why use Inner class
    • The use is to increase encapsulation and hide some implementation details. Classes like Semaphore use internal objects for locking, etc.
  • Serialization
    • Serialization purpose is not persistence, there are DB's for that. Use of serialization is to transfer objects over network. We can write the Java object as byte array in memory, and later again construct the object from byte array in memory.
  • ConcurrentModificationException
    • arraylist is getting modified by other thread
  • Ensure that instance is never garbage collected
    • static reference to a singleton, so it won't be eligible for garbage collection until the classloader is eligible for garbage collection
  • Java Runtime Memory Management
    • MemoryManagement is Garbage Collection and memory allocation
  • Local Variables are thread safe, local variables can be used to confine objects to a thread
  • Immutable objects are always thread safe. A properly consturcted(this doesn't escapes), and state can't be modified, and may be all fields are final. No requirement for safe publication.

Friday, 30 August 2013

Singleton Pattern

Motivation

Sometimes it's important to have only one instance for a class. For example, in a system there should be only one window manager (or only a file system or only a print spooler). Usually singletons are used for centralized management of internal or external resources and they provide a global point of access to themselves.
The singleton pattern is one of the simplest design patterns: it involves only one class which is responsible to instantiate itself, to make sure it creates not more than one instance; in the same time it provides a global point of access to that instance. In this case the same instance can be used from everywhere, being impossible to invoke directly the constructor each time.

Intent

  • Ensure that only one instance of a class is created.
  • Provide a global point of access to the object.


Implementation

The implementation involves a static member in the "Singleton" class, a private constructor and a static public method that returns a reference to the static member.

Singleton Implementation - UML Class Diagram
The Singleton Pattern defines a getInstance operation which exposes the unique instance which is accessed by the clients. getInstance() is is responsible for creating its class unique instance in case it is not created yet and to return that instance.

class Singleton
{
 private static Singleton instance;
 private Singleton()
 {
  ...
 }

 public static synchronized Singleton getInstance()
 {
  if (instance == null)
   instance = new Singleton();

  return instance;
 }
 ...
 public void doSomething()
 {
  ... 
 }
}

You can notice in the above code that getInstance method ensures that only one instance of the class is created. The constructor should not be accessible from the outside of the class to ensure the only way of instantiating the class would be only through the getInstance method.
The getInstance method is used also to provide a global point of access to the object and it can be used in the following manner:


Singleton.getInstance().doSomething();



Applicability & Examples

According to the definition the singleton pattern should be used when there must be exactly one instance of a class, and when it must be accessible to clients from a global access point. Here are some real situations where the singleton is used:

Example 1 - Logger Classes

The Singleton pattern is used in the design of logger classes. This classes are ussualy implemented as a singletons, and provides a global logging access point in all the application components without being necessary to create an object each time a logging operations is performed.

Example 2 - Configuration Classes

The Singleton pattern is used to design the classes which provides the configuration settings for an application. By implementing configuration classes as Singleton not only that we provide a global access point, but we also keep the instance we use as a cache object. When the class is instantiated( or when a value is read ) the singleton will keep the values in its internal structure. If the values are read from the database or from files this avoids the reloading the values each time the configuration parameters are used.

Example 3 - Accesing resources in shared mode

It can be used in the design of an application that needs to work with the serial port. Let's say that there are many classes in the application, working in an multi-threading environment, which needs to operate actions on the serial port. In this case a singleton with synchronized methods could be used to be used to manage all the operations on the serial port.

Example 4 - Factories implemented as Singletons

Let's assume that we design an application with a factory to generate new objects(Acount, Customer, Site, Address objects) with their ids, in an multithreading environment. If the factory is instantiated twice in 2 different threads then is possible to have 2 overlapping ids for 2 different objects. If we implement the Factory as a singleton we avoid this problem. Combining Abstract Factory or Factory Method and Singleton design patterns is a common practice.

Specific problems and implementation



Thread-safe implementation for multi-threading use.

A robust singleton implementation should work in any conditions. This is why we need to ensure it works when multiple threads uses it. As seen in the previous examples singletons can be used specifically in multi-threaded application to make sure the reads/writes are synchronized.

Lazy instantiation using double locking mechanism.

The standard implementation shown in the above code is a thread safe implementation, but it's not the best thread-safe implementation beacuse synchronization is very expensive when we are talking about the performance. We can see that the synchronized method getInstance does not need to be checked for syncronization after the object is initialized. If we see that the singleton object is already created we just have to return it without using any syncronized block. This optimization consist in checking in an unsynchronized block if the object is null and if not to check again and create it in an syncronized block. This is called double locking mechanism.
In this case case the singleton instance is created when the getInstance() method is called for the first time. This is called lazy instantiation and it ensures that the singleton instance is created only when it is needed.

//Lazy instantiation using double locking mechanism.
class Singleton
{
 private static Singleton instance;

 private Singleton()
 {
 System.out.println("Singleton(): Initializing Instance");
 }

 public static Singleton getInstance()
 {
  if (instance == null)
  {
   synchronized(Singleton.class)
   {
    if (instance == null)
    {
     System.out.println("getInstance(): First time getInstance was invoked!");
     instance = new Singleton();
    }
   }            
  }

  return instance;
 }

 public void doSomething()
 {
  System.out.println("doSomething(): Singleton does something!");
 }
}

A detialed discussion(double locking mechanism) can be found on http://www-128.ibm.com/developerworks/java/library/j-dcl.html?loc=j

Early instantiation using implementation with static field

In the following implementattion the singleton object is instantiated when the class is loaded and not when it is first used, due to the fact that the instance member is declared static. This is why in we don't need to synchronize any portion of the code in this case. The class is loaded once this guarantee the uniquity of the object.
Singleton - A simple example (java)

//Early instantiation using implementation with static field.
class Singleton
{
 private static Singleton instance = new Singleton();

 private Singleton()
 {
  System.out.println("Singleton(): Initializing Instance");
 }

 public static Singleton getInstance()
 {    
  return instance;
 }

 public void doSomething()
 {
  System.out.println("doSomething(): Singleton does something!");
 }
}


Protected constructor

It is possible to use a protected constructor to in order to permit the subclassing of the singeton. This techique has 2 drawbacks that makes singleton inheritance impractical:
  • First of all, if the constructor is protected, it means that the class can be instantiated by calling the constructor from another class in the same package. A possible solution to avoid it is to create a separate package for the singleton.
  • Second of all, in order to use the derived class all the getInstance calls should be changed in the existing code from Singleton.getInstance() to NewSingleton.getInstance().


Multiple singleton instances if classes loaded by different classloaders access a singleton.

If a class(same name, same package) is loaded by 2 diferent classloaders they represents 2 different clasess in memory.


Serialization

If the Singleton class implements the java.io.Serializable interface, when a singleton is serialized and then deserialized more than once, there will be multiple instances of Singleton created. In order to avoid this the readResolve method should be implemented. See Serializable () and readResolve Method () in javadocs.

 public class Singleton implements Serializable {
  ...

  // This method is called immediately after an object of this class is deserialized.
  // This method returns the singleton instance.
  protected Object readResolve() {
   return getInstance();
  }
 }


Abstract Factory and Factory Methods implemented as singletons.

There are certain situations when the a factory should be unique. Having 2 factories might have undesired effects when objects are created. To ensure that a factory is unique it should be implemented as a singleton. By doing so we also avoid to instantiate the class before using it.

Hot Spot:



  • Multithreading - A special care should be taken when singleton has to be used in a multithreading application.
  • Serialization - When Singletons are implementing Serializable interface they have to implement readResolve method in order to avoid having 2 different objects.
  • Classloaders - If the Singleton class is loaded by 2 different class loaders we'll have 2 different classes, one for each class loader.
  • Global Access Point represented by the class name - The singleton instance is obtained using the class name. At the first view this is an easy way to access it, but it is not very flexible. If we need to replace the Sigleton class, all the references in the code should be changed accordinglly.


Friday, 16 August 2013

Algorithms and Data Structures

Asymptotic Analysis
  • measuring the cost or complexity of an algorithm
  • Analyzing what happens as the number of inputs becomes very large is referred to as asymptotic analysis

Rate of Growth
  • Rate of growth describes how an algorithm’s complexity changes as the input size grows
  • represented using Big-O notation
  • Big-O notation uses a capital O (“order”) and a formula that expresses the complexity of the algorithm
  • The formula may have a variable, n, which represents the size of the input
  • Constant – O(1) : complexity is constant regardless of how large the input size is. The point is that the size of the input does not influence the time the operation takes.
public int GetCount(int[] items)
{
return items.Length;
}
  • Linear – O(n) : complexity grows linearly with the size of the input.
public long GetSum(int[] items)
{
long sum = 0;
foreach (int i in items)
{
sum += i;
}
return sum;
}

  • Logarithmic – O(log n): complexity is logarithmic to its size. The binary search tree Contains method implements an O(log n) algorithm
  • Linearithmic – O(n log n): A linearithmic algorithm, or loglinear, is an algorithm that has a complexity of O(n log n). Merge sort and quick sort.
  • Quadratic – O(n2):

Linked-List
  • The Node: A node is a container that provides the ability to both store data and connect to other nodes.
public class Node
{
public int Value { get; set; }
public Node Next { get; set; }
}

  • Starts with the node first and ends with the node last.
  • The Next property for the last node points to null which is the end-of-list indicator.
private static void PrintList(Node node)
{
while (node != null)
{
Console.WriteLine(node.Value);
node = node.Next;
}
}

Performance: O(1)

Adding an item to a linked list involves three steps
  1. Allocate the new LinkedListNode instance
  2. Find the last node of the existing list
  3. Point the Next property of the last node to the new node

private LinkedListNode<T> _head;
private LinkedListNode<T> _tail;
Keep track of the last node (the “tail” node) in the list and when we add the new node we simply access our stored reference directly. This is an O(1) algorithm and therefore the preferred approach.



Doubly Linked List
  • LinkedListNode class to have a new property named Previous

Array List
  • Direct indexing of array
  • default constructor initializing the array to size 0
  • Performance: O(n)

Stack
  • A stack is a collection that returns objects to the caller in a Last-In-First-Out (LIFO) pattern.
  • last object added to the collection will be the first object returned
  • The Stack class defines Push, Pop, and Peek methods, a Count property, and uses the LinkedList<T> class to store the values contained in the stack.
  • PUSH: performance – O(1)
  • Pop: performance – O(1)
  • Peek: performance – O(1)
  • Count: performance – O(1)

Queue
  • Queues are a First-In-First-Out (FIFO) collection
  • This means that items are removed from the queue in the same order that they were added
  • backed by a LinkedList
  • Enqueue (to add items), Dequeue (to remove items), Peek, and Count
  • Enqueue : O(1)  ; To the end of queue
  • Dequeue : O(1)  ; To the oldest item
  • Peek: O(1)  ;  Returns the next item that would be returned if Dequeue were called
  • Count: O(1); Returns the number of items currently in the queue. Returns 0 if the queue is empty.

Binary Search Tree
  • Binary search trees take the general tree structure
  • A tree is a data structure where each node has 0 or more children
  • A binary search tree uses the same basic structure
    • Each node can have 0, 1, or 2 children
    • Any value less than the node’s value goes to the left child (or a child of the left child).
    • Any value greater than, or equal to, the node’s value goes to the right child (or a child thereof)
BinaryTree<int> tree = new BinaryTree<int>();
tree.Add(8);
tree.Add(4);
tree.Add(2);
tree.Add(3);
tree.Add(10);
tree.Add(6);
tree.Add(7);






  • Node Class
    • BinaryTreeNode represents a single node in the tree.
    • references to the left and right children (null if there are none)
    • node’s value
    • CompareTo method which allows comparing the node values
  • Binary Search Tree
    • Add, Remove, a Contains method
    • Count and Clear methods
    • To initialize the tree; represents the head (root) node of the tree
    • integer that keeps track of how many items are in the tree
    • ADD: O(log n) on average; O(n) in the worst case
    • Remove: O(log n) on average; O(n) in the worst case
    • Contains: O(log n) on average; O(n) in the worst case
    • Count: O(1)
    • Clear: O(1); head=null; count=0
  • Traversal
    • allow processing each value in the tree

Sorting Algorithm
  • Bubble sort & Quick Sort
  • Swap
    • swap values in an array by index
void Swap(T[] items, int left, int right)
{
if (left != right)
{
T temp = items[left];
items[left] = items[right];
items[right] = temp;
}
}

  • Bubble Sort

Behavior
Sorts the input array using the bubble sort algorithm.
Complexity
Best Case
Average Case
Worst Case
Time
O(n)
O(n2)
O(n2)
Space
O(1)
O(1)
O(1)

    • each time moving the largest unsorted value to the right (end) of the array
public void Sort(T[] items)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < items.Length; i++)
{
if (items[i - 1].CompareTo(items[i]) > 0)
{
Swap(items, i - 1, i);
swapped = true;
}
}
} while (swapped != false);
}


  • Insertion Sort
    • Insertion sort works by making a single pass through the array
    • inserting the current value into the already sorted (beginning) portion of the array
    • The important concept is that insertion sort works by sorting items as they are encountered
    • Since it processes the array from left to right
    • we know that everything to the left of the current index is sorted
    • When the sorting process begins, the sorting algorithm starts at index 0
    • Now, array indexes 0–1 are known to be sorted, and 2–n are in an unknown state
    • Now, array from index 0 to 2 is now known to be sorted
    •  
  • Merge Sort
    • Divide and Conquer: algorithms operate by breaking down large problems into smaller, more easily solvable problems
    • example, we use a divide and conquer algorithm when searching a phone book
    • Merge sort operates by cutting the array in half over and over again until each piece is only 1 item long
    • A way to split the arrays recursively
    • A way to merge the items together in sort-order
  • Quick sort
    • divide and conquer sorting algorithm
    • works by recursively performing the algorithm
      • Pick a pivot index and partition the array into two arrays ; using a random number in the sample code
      • Put all values less than the pivot value to the left of the pivot point and the values above the pivot value to the right 

Monday, 12 August 2013

Linked List Implementation In Java

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.


Singly-linked-list.svg

Linked List Implementation In Java 

1. Insert at The end of the list
2. get size of list
3. print content of list
4.add element at the end
5. add element at specified position
6. remove element at index

Output

----------Size of list---------------
4
----------Content of list----------------
[ 1 ][ 2 ][ 3 ][ 4 ]
----------get element of list-----------------
2
----------remove element from list-----------
true
----------Content of list----------------
[ 1 ][ 3 ][ 4 ]
---add new element to specified position----
----------Content of list----------------
[ 1 ][ M ][ 3 ][ 4 ]

CODE 

/**
 * 1. Insert at The end of the list. 2. get size of list 3. print content of
 * list 4.add element at the end 5. add element at specified position 6. remove
 * element at index
 *
 * Note: The link object doesn't contain the another link object Next Link is
 * actually a reference to another link
 *
 * @author RaviKantSoni[12-August-2013]
 *
 */
public class testSingleLinkedList {

    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");

        System.out.println("----------Size of list---------------");
        System.out.println(linkedList.size());
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());
        System.out.println("----------get element of list-----------------");
        System.out.println(linkedList.get(2));
        System.out.println("----------remove element from list-----------");
        System.out.println(linkedList.remove(2));
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());
        System.out.println("---add new element to specified position----");
        linkedList.add("M", 2);
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());

    }
}

class SingleLinkedList {
    // reference to Head Node
    private Node head;
    private int listCount;

    // LinkedList Constructor
    public SingleLinkedList() {
        // this is empty list so the reference to the head node is set to a new
        // node with no data
        head = new Node(null);
        listCount = 0;
    }

    // add new element to the end of the list
    public void add(String data) {
        Node temp = new Node(data);
        Node current = head;
        // starting at the head node, crawl to the end of the list
        while (current.getNext() != null) {
            current = current.getNext();
        }
        // the last node's next reference set to new node
        current.setNext(temp);
        listCount++;
    }

    // to print content of list
    public String toString() {
        Node current = head.getNext();
        String outPut = "";
        while (current != null) {
            outPut = outPut + "[ " + current.getData() + " ]";
            current = current.getNext();
        }
        return outPut;
    }

    // to get size of the list
    public int size() {
        return listCount;
    }

    // returns the element at the specified position in this list
    // here we are returning object from the list
    public Object get(int index) {
        // index should be 1 or more
        if (index <= 0) {
            return null;
        }
        Node element = head.getNext();
        for (int i = 1; i < index; i++) {
            if (element.getNext() == null)
                return null;

            element = element.getNext();
        }
        return element.getData();
    }

    // remove the element at specific position in the list\
    public boolean remove(int index) {
        // if index is out of range, exist
        if (index < 1 || index > size())
            return false;
        Node current = head;
        for (int i = 1; i < index; i++) {
            if (current.getNext() == null)
                return false;
            current = current.getNext();
        }
        current.setNext(current.getNext().getNext());
        listCount--;
        return true;
    }

    // insert specified element at specified position in the list
    public void add(String data, int index) {
        // insert to requested index or to last in this list, which ever come
        // first
        Node current = head;
        Node temp = new Node(data);
        for (int i = 1; i < index && current.getNext() != null; i++) {
            current = current.getNext();
        }
        temp.setNext(current.getNext());
        current.setNext(temp);
        listCount++;
    }

    static class Node {
        private Node next;
        private String data;

        Node(String data) {
            this.data = data;
        }

        public String toString() {
            return this.data;
        }

        public Node(String data, Node node) {
            this.data = data;
            this.next = node;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

    }
}