CodeRevisited Keep Learning.. Cheers!

Replace Every Element With Next Greatest

Problem: Replace Every Element With Next Greatest

Given an array of integers, replace every element with next greatest element.Since there is no element next to the last element, replace it with -1.

In an array of a1 to aN, replace ai with \( max (ai+1 …. aN) \) where \( 0 < i < N \) and aN with -1

Solution

  • Consider the array with only positive integers.
  • Initially set maximum element as -1.
  • Start from the N-1th element, move to the left side one by one, and keep track of the maximum element.
  • Replace every element with the maximum element.

What if our array contains negative integers too?

Modified solution

  • Initially set maximum element as Integer.MIN_VALUE.
  • Start from the N-1th element, move to the left side one by one, and keep track of the maximum element.
  • Replace every element with the maximum element. And Finally set the last element to -1.

Sample Code

Check here for complete code.

Beginning with Spring Data JPA

In my previous post, I briefly wrote about JPA, a Java specification for accessing, persisting, and managing data between Java objects / classes and a relational database.

In this post, I will talk about Spring Data JPA with a simple example.

Why Spring Data JPA?

The data access code which uses the Java Persistence API contains a lot of unnecessary boilerplate code. Too much boilerplate code has to be written  If we have to write dynamic queries or implement pagination.

Spring Data JPA is another layer of abstraction for the support of persistence layer in spring context. The goal of Spring Data repository abstraction is to significantly reduce the amount of boilerplate code required to implement data access layers for various persistence stores. We just have to write repository interfaces, including custom finder methods, and Spring will provide the implementation automatically.

Defining repository interfaces

As a first step we define a domain class-specific repository interface. The interface must extend Repository and be typed to the domain class and an ID type. If you want to expose CRUD methods for that domain type, extend CrudRepository instead of Repository. The CrudRepository provides sophisticated CRUD functionality for the entity class that is being managed. We can add additional query methods to this repository interface.

public interface EmployeeRepository extends CrudRepository<Employee, Integer> {
}

Note: Employee entity class is defined in previous post.

XML configuration

Each Spring Data module includes repositories element that allows you to simply define a base package that Spring scans for you. Spring bean configurations are used to configure JPA vendor, data source for creating entity manager.

Querying Repository

We can execute query methods from application class by referring to repository bean.

The above application code when executed would insert 3 rows to Employee table in test database.

The code for this example can be downloaded from here

Beginning with JPA 2.0

The Java Persistence Architecture API (JPA) is a Java specification for accessing, persisting, and managing data between Java objects / classes and a relational database. JPA allows POJO (Plain Old Java Objects) to be easily persisted. JPA allows an object’s object-relational mappings to be defined through standard annotations or XML defining how the Java class maps to a relational database table. JPA also defines a runtime EntityManager API for processing queries and transaction on the objects against the database. JPA defines an object-level query language, JPQL, to allow querying of the objects from the database.

Why JPA

It is a standard for the management of persistence and object/relational mapping with Java EE and Java SE. JPA supports the large data sets, data consistency, concurrent use, and query capabilities of JDBC. Like object-relational software and object databases, JPA allows the use of advanced object-oriented concepts such as inheritance. JPA avoids vendor lock-in by relying on a strict specification. JPA focuses on relational databases. And JPA is extremely easy to use. Currently most of the persistence vendors have released implementations of JPA confirming its adoption by the industry and users. These include Implementations include Hibernate, TopLink, and Kodo JDO, Cocobase and JPOX. Java Persistence consists of four areas

  • The Java Persistence API
  • The query language
  • The Java Persistence Criteria API
  • Object/relational mapping metadata

Entities

In Object oriented paradigm, An entity is a lightweight persistence domain object. Typically, an entity represents a table in a relational database, and each entity instance corresponds to a row in that table. Changing values of entity instance works just like changing values on any other class instance. The difference is that you can persist those changes in database. The primary programming artifact of an entity is the entity class, although entities can use helper classes. The persistent state of an entity is represented through either persistent fields or persistent properties. These fields or properties use object/relational mapping annotations to map the entities and entity relationships to the relational data in the underlying data store.

Characteristics of an Entity

  1. Persistability
    • An Entity is persistable since it can be saved to a persistence store. But this doesn’t happen automatically. It has to be invoked by API. It is important because it leaves control over persistence to application.
  2. Identity
    • Identifier, is the key that uniquely identifies an entity instance and distinguishes it from all the other instances of the same entity type.
  3. Transactionality
    • Changes made to the database either succeed or fail atomically, so the persistent view of an entity should indeed be transactional.
  4. Granularity
    • Entities are meant to be fine-grained objects and they are business domain objects that have specific meaning to the application that accesses them.

Example Entity class with annotations metadata

Managing Entities

Entities are managed by the entity manager. Each EntityManager instance is  associated with a persistence context: a set of managed entity instances that exist in a particular data store. A persistence context defines the scope under which particular entity instances are created, persisted, and removed. The EntityManager interface defines the methods that are used to interact with the persistence context.

EntityManager is to be implemented by a particular persistence provider. It is the provider that supplies the backing implementation engine for the entire Java Persistence API, from the EntityManager through to implementation of the query classes and SQL generation.

Illustration of Entity manager

Project setup

  • Setup mysql and use the following sql code to create “Employee” table in test database
  • Create META-INF/persistence.xml file in resources directory. It specifies JPA provider and it’s properties.
  • Add Employee.java, EmployeeTest.java files to project
  • You should be able to execute EmployeeTest which will insert 3 records to Employee table.

The sample code can be downloaded from here

Infix expression to Postfix expression

This post shows sample implementations for 1. Converting an infix expression to postfix expression (Reverse polish notation) 2. Evaluating postfix expression

Infix to PostFix notation

To convert from infix to postfix notation, I have implemented Dijkstra’s shunting-yard algorithm. For detailed algorithm, please take a look at wiki page.

Evaluating postfix expression

This program evaluates postfix expresions using a stack. The following is sample implementation in java

Sample code for Infix to PostFix

Sample code for PostFix evaluation

Check here for complete code.

For other libraries used in the above program, please refer to GitHub repo here

Arrays of Generic types

This post examines differences between arrays and generics and finds out how we can create arrays of generic types in Java.

Let’s start with Arrays

In Java, Arrays are covariant, which means that if B is a subtype of A, B[] is also subtype of A[].

Is there a problem here

Yes, there is a problem. Suppose, we have array of integers. We can assign these array of integers to array of numbers and put a double value as shown in the following program.

Though this programs compiles successfully, It throws ArrayStoreException at runtime since arrays are reified and enforce their element types at runtime. Though It is illegal that integer container can’t be assigned to Number container, We had to wait till we run this program. It’s hard to find bugs at runtime than compile time.

Invariant generics

The following program perform the same operations as sated above.

This program throws compile error. Generics are invariant which means that if B is a subtype of A, List is not subtype of List.

And also, Generics are implemented by erasure. This means that they enforce their type constraints only at compile time and discard (or erase) their element type information at runtime. Erasure is what allows generic types to interoperate freely with legacy code that does not use generics. It is preferred to use generic list over arrays because any bugs will be surfaced at compile time.

As a consequence of the fact, arrays are covariant but generics are not, we are not allowed to create array of generic types unless the type argument is an unbounded wildcard.

Why arrays of generic types

Suppose, if you want to implement ArrayList as follows,

public class MyArrayList<E> {
    
    private E[] elements;
    	
    public MyArrayList(int size){
    		elements = new E[size];
    }
}

But above code does not work. The compiler doesn’t know what type E really represents, so it cannot instantiate an array of type E.

How can we create arrays of generic types

One workaround is to create an Object[] and then cast it (generating a warning) to E[]:

elements = (E[])new Object[size]; 

Second approach is through reflection by passing a class literal (Foo.class) of element type into the constructor, so that the implementation could know, at runtime, the value of E.

public MyArrayList(Class<E> elementType, int size){
    elements = (E[]) Array.newInstance(elementType, size);
}