Tag Archives: java

Swapping Values of Two Integer Variables

Posted on by

The simplest way to swap the values of two variables is to have a third variable that can temporarily hold the value of one variable while the other is being copied. This is very easy code, but a small problem is that we have to allocate extra memory. In these days of gigabytes of data, that is not a huge concern. But still it is useful to know a technique where you can achieve that.

So here are a couple of ways to do that I saw in a few places. I don’t have the name of the original author, I am assuming that it became common knowledge early. The first method uses addition, but if you have large values, then there is the chance of arithmetic overflow based on the result. The second method uses bitwise operations that avoid the “over-flaw” (sorry!)

public class Swap extends Object
{
    public static void main(String args[])
    {
        int a = 123;
        int b = 345;
        System.out.println(a + " : " + b);

        //Swapping using temporary variable : straight-forward method
        int temp = a;
        a = b;
        b = temp;
        System.out.println(a + " : " + b);

        //Swapping using arithmetic operations : saves memory
        a = a + b;  //You can use a += b;
        b = a - b;
        a = a - b;  //You can use a -= b;
        System.out.println(a + " : " + b);

        //Swapping using bitwise operations : avoids arithmetic overflow
        a = a ^ b;  //You can use a ^= b;
        b = a ^ b;  //You can use b ^= a;
        a = a ^ b;  //You can use a ^= b;
        System.out.println(a + " : " + b);
    }
}

Implementation of Kruskal’s algorithm in Java

Posted on by

I will be posting some code from time to time. Some of these posts are from way back. I could probably rewrite them if I wanted to and perhaps in a different language, but there are bigger fish to fry. But maybe someone may find this useful.

So this is the Kruskal’s algorithm which finds a minimum spanning tree for a connected weighted graph. The program below uses a hard-coded example. You may want to write a unit test or something, changing it to match your problem by changing the edges in the graph. The Kruskal class contains the main method. The Edge class represents an edge (!). The KruskalEdges class contains the edges determined by the Kruskal algorithm.

The meat of the algorithm is in the InsertEdge method of KruskalEdges class. Let us assume that the edge to be inserted has 2 vertices, namely A and B. We maintain a vector that contains groups of vertices. We first check if either A or B exists in any group

  • If neither A nor B exists in any group, we create a new group containing both the vertices.
  • If one of the vertices exists in a group and the other does not, we add the vertex that does not exist to the group of the other vertex.
  • If both vertices exist in different groups, we merge the two groups into one.

All of the above scenarios mean that the edge is a valid Kruskal edge. So we will add the edge to the Kruskal edges.

However one final scenario remains where both vertices exist in the same group (note the missing empty else statement). In that case, we will not consider the edge as a valid Kruskal edge.

import java.util.TreeSet;
import java.util.Vector;
import java.util.HashSet;

class Edge implements Comparable<Edge>
{
    String vertexA, vertexB;
    int weight;

    public Edge(String vertexA, String vertexB, int weight)
    {
        this.vertexA = vertexA;
        this.vertexB = vertexB;
        this.weight = weight;
    }
    public String getVertexA()
    {
        return vertexA;
    }
    public String getVertexB()
    {
        return vertexB;
    }
    public int getWeight()
    {
        return weight;
    }
    @Override
    public String toString()
    {
        return "(" + vertexA + ", " + vertexB + ") : Weight = " + weight;
    }
    public int compareTo(Edge edge)
    {
        //== is not compared so that duplicate values are not eliminated.
        return (this.weight < edge.weight) ? -1: 1;
    }
}
class KruskalEdges
{
    Vector<HashSet<String>> vertexGroups = new Vector<HashSet<String>>();
    TreeSet<Edge> kruskalEdges = new TreeSet<Edge>();

    public TreeSet<Edge> getEdges()
    {
        return kruskalEdges;
    }
    HashSet<String> getVertexGroup(String vertex)
    {
        for (HashSet<String> vertexGroup : vertexGroups) {
            if (vertexGroup.contains(vertex)) {
                return vertexGroup;
            }
        }
        return null;
    }
    public void insertEdge(Edge edge)
    {
        String vertexA = edge.getVertexA();
        String vertexB = edge.getVertexB();

        HashSet<String> vertexGroupA = getVertexGroup(vertexA);
        HashSet<String> vertexGroupB = getVertexGroup(vertexB);

        if (vertexGroupA == null) {
            kruskalEdges.add(edge);
            if (vertexGroupB == null) {
                HashSet<String> htNewVertexGroup = new HashSet<String>();
                htNewVertexGroup.add(vertexA);
                htNewVertexGroup.add(vertexB);
                vertexGroups.add(htNewVertexGroup);
            }
            else {
                vertexGroupB.add(vertexA);           
            }
        }
        else {
            if (vertexGroupB == null) {
                vertexGroupA.add(vertexB);
                kruskalEdges.add(edge);
            }
            else if (vertexGroupA != vertexGroupB) {
                vertexGroupA.addAll(vertexGroupB);
                vertexGroups.remove(vertexGroupB);
                kruskalEdges.add(edge);
            }
        }
    }
}

public class Kruskal
{
    public static void main(String[] args)
    {
        //TreeSet is used to sort the edges before passing to the algorithm
        TreeSet<Edge> edges = new TreeSet<Edge>();

        //Sample problem - replace these values with your problem set
        edges.add(new Edge("0", "1", 2));
        edges.add(new Edge("0", "3", 1));
        edges.add(new Edge("1", "2", 3));
        edges.add(new Edge("2", "3", 5));
        edges.add(new Edge("2", "4", 7));
        edges.add(new Edge("3", "4", 6));
        edges.add(new Edge("4", "5", 4));

        System.out.println("Graph");
        KruskalEdges vv = new KruskalEdges();

        for (Edge edge : edges) {
            System.out.println(edge);
            vv.insertEdge(edge);
        }

        System.out.println("Kruskal algorithm");
        int total = 0;
        for (Edge edge : vv.getEdges()) {
            System.out.println(edge);
            total += edge.getWeight();
        }
        System.out.println("Total weight is " + total);
    }
}

Java — The Platform

Posted on by

(This article appeared in “IT Glimpse 2000″, a magazine published by the School of Computer Science, M.G. University, Kottayam, Kerala. Current technology advancements have made some of the statements below obsolete.)

One of the most common mistakes that people make about Java is to regard it as just another programming language and then get involved in futile arguments over whether it is better than C or C++ or other languages. They miss the whole point.

Java provides many more benefits than simply a new programming language. It is a complete platform for development and deployment of software solutions ranging from hand-held products to enterprise-wide applications. The actual language specification provides a base for addressing real-life concerns like performance, security and cost.

Java is general-purpose. Although initially marketed as a Web technology and used for creating jazzy Web applets, Java is now being used in a wide variety of other applications. Java Servlets and JSP are being used in place of CGI and ASP. Enterprise Java Beans are being used to build n-tier applications. Java is being used for network programming, game programming, database programming — what not!

One of the most touted benefits of Java is “write-once run-anywhere”, an old programmer mirage. A developer can create his product, implement all the business needs, round it off with an intuitive user interface and never worry about which software or hardware platform it is going to run on. The days of painstakingly re-writing code, especially GUI frameworks, is over. Barring minor areas, a Java program will run the same on any platform that has a Java Runtime Environment.

The portability of Java frees the developer and end-user from the tyranny of being tied down to a specific vendor or product. One can change the platform on which the program is running to a cheaper, better or more convenient one. Makes better sense. Makes better markets and products too as software makers have to get involved in actually bettering their products instead of the old scenario of “once-a-customer, always-a-customer” where a change for the customer was prohibitively expensive.

The development time for Java is considerably less than other languages. One factor is the well-thought-out design of the language itself. Compilation and run-time checks allow a lot of bugs to be trapped early enough. The language prevents a lot of errors by various means such as array bounds checking, type checking and exception handling. The object-oriented nature forces the programmer to invest more in the design process, leading to a smoother coding and testing phase.

One of the great advantages of using an object-oriented language is the ability to reuse components. The JavaBeans API specification provides a framework for defining reusable, embeddable, modular software components. More importantly, they can be visually manipulated in a builder tool, even if they don´t have a visual representation. This has created a whole industry of GUI development tools for Java.

With JavaBeans, one can create complex objects to function as a collection of co-operating intelligent beans. A Java program can dynamically extend or change its behaviour by loading or replacing different objects at runtime from resources in its accessible network path. Thus Java has changed programs from monolithic entities to interacting collections of intelligent software components.

The amazing array of reusable classes that Sun provides the developer for implementing various features adds to the ease of development. Java 1.2 at the last count had around 1500 classes in more than 50 packages. In addition, one can purchase objects from different software vendors or download free Java classes from the Net. The bottom line reads thus: High quality at inexpensive development costs.

RMI (Remote Method Invocation) allows Java objects on one machine to invoke methods on other machines. Unlike socket programming, this ensures type safety of the communicated values and also enables event and exception handling. The Java IDL (Interface Definition Language) specifies the way in which Java objects acquire the capability to communicate in a broader environment that includes programs written in other languages.

Java has been designed with networking in mind. From a programmer perspective, Java makes it easy to work with resources across the network, be it a LAN or the Internet. In fact, interaction with different resources such as system accessories, local and remote files hardly changes as far as coding is concerned. From simple file access to socket programming to communicating using different protocols, Java is right there at the top.

Java applets have spawned a new line of thinking in the business world. Everywhere businesses are moving from a client-server paradigm to a Web-centric online world. Users are asking, “Why do I have to pay for something I seldom or never use? Why should I have to perform an upgrade every so often? Give me something basic to work with and I will pay for the extra software fittings when I need them.” This is something that the dynamic nature of Java programs is very comfortable with and adept in handling.

Java Servlets and JSP, at the other end of the pipe as applets, are the hottest technology in town today. Offering the same functionality as CGI with additional advantages such as robustness, security, speed and all the other advantages of Java technology, they are virtually taking over the market for server-side programming.

Security has always been a major concern of software clients. This goes way beyond stopping freak hacker attacks. It involves maintaining confidential information, maybe involving complex encryption. It needs safe, secure electronic communication with authentication, policy-based access control and non-repudiation. These are all areas where Java is good and we are seeing such real systems being built with Java.

Database programming has been made child’s play by Java. Through allowing different mechanisms of access through its various classes with easy-to-use methods, the programmer can concentrate on the high-level functionality instead of the petty details of coding. For hard-core developers, the latest version of JDBC (Java Database Connectivity) offers pooled database connections, scrollable resultsets, batch updates and even storing Java objects in databases.

Multi-threading allows programmers to build applications that more accurately reflect the way the world works. Although users and developers alike have long known the advantages of multi-threaded programs, creation of such programs had long been a big pain with languages providing little or no support. Programmers usually ended up making and using specialised libraries. Sun has incorporated threads into the language, building into them some of the same safeguards as “heavy-weight” threads with little of the overhead.

Java really shines when it comes to programming for other natural languages and cultures. While the initial design of Java had features that supported internationalisation such as support for Unicode, more enhancements to the platform have come to prevent the programmer in falling for the trap of coding to a particular region. These improvements have been made throughout the platform such as database programming.

When it comes to GUI systems, even programs written in languages with a compile-everywhere tag are rewritten at heavy expense for different platforms. With its powerful AWT and Swing classes, Java has eliminated all that drudgery without sacrificing the ability to build sophisticated user interfaces. Swing also allows a developer to either maintain a consistent platform-independent look or acquire the look-and-feel of the underlying operating system.

Swing also provides several accessibility features to visually impaired end-users, such as the ability to work with screen readers, screen magnifiers and speech recognition systems. Through its support for windowing systems, drag-and-drop data transfer capabilities and 2D and 3D graphics, Java programs can be made very user-friendly. After all, users more readily identify themselves with metaphorical symbols and actions than cryptic command-line statements.

For more elegant applications, Sun has included several application services for use by Java Foundation Classes. These include keyboard navigation, multi-threaded event queue, undo capability, bounded range model, custom cursors, graphics debugging, screen repaint batching and event target manager. And that´s not all – Java now offers splendid sound and graphics support for its applications.

One limitation of Java programs is their speed when compared to natively compiled programs. This situation has been improved by Just-in-Time technology that compiles Java byte code on the fly into native code, thus increasing efficiency multi-fold. Direct compilation of programs into executables for different platforms is also possible. Improved performance is also expected through techniques such as memory compression, faster memory allocation and garbage collection, monitor speedups and native library JNI port. JNI (Java Native Interface) allows a Java application to link to platform-specific code written in other languages.

Several metaphors come to the mind like “Java is a vast ocean” or “You have only seen the tip of the Java iceberg”, but I guess you get the idea. Important things like JNDI, JTA, JMA, JavaDoc, Java Help and JAR have hardly found a mention. But that is not even the idea. What is important to know is that if you want to do something, just pull out that Java reference book you will be buying after reading this article. What you want will be there somewhere in it.

The range and power of Java is simply amazing. It provides a complete environment for building software solutions, down to the last wire. For the developer, Java makes it easy to build, maintain and extend. For the software maker, this means faster development, less costs and more profit. For the end user, it means a robust, secure and supported product. In short,

Java is it.