Shantibhushan Naik

Tag: queue

  • Jawbone – Data structures in Javascript

    I have just posted a project for essential data structures using Javascript. These data structures form the backbone (hence the name jawbone) of many advanced formats to store, retrieve data

    The project is hosted on GitHub as well as Google Code

    Happy learning!

  • Merging pre-sorted lists

    A while ago, I came across an interesting problem. We have 3 different sorted queues (entries were sorted by time), out of which we had to pickup the smallest time, and send the first arrived entry out of those 3 queues in sequence.

    Q1 Q2 Q3
    2 3 1
    5 4 6
    7 6 9
    8 10 11

    As you can see, all queues (Q1, Q2, Q3) are already sorted, but on application side we have to pickup entries across all queues in sorted order and process them. So the entries should be processed in 1, 2, 3, 4, 5, … 11 sequence. Frankly this is merging of already sorted lists, and a person from computer science background should already know this. But I don’t come from such background, and the solution one of my friends gave was plain amazing.

    The solution was pickup first entry from each queue, compare them, choose the smallest and process it first.

    Q1 Q2 Q3 Smallest
    2 3 1 1

    Thus, here 1 is processed first. Now pickup next entry from queue where smallest was found (Q3 in this example), so now the next comparison becomes like this

    Q1 Q2 Q3 Smallest
    2 3 6 2

    The smallest is 2, so this is processed and next entry from Q1 was picked-up

    Q1 Q2 Q3 Smallest
    5 3 6 3

    And so on… giving us

    Q1 Q2 Q3 Smallest
    2 3 1 1
    2 3 6 2
    5 3 6 3
    5 4 6 4
    5 6 6 5
    7 6 6 6
    7 10 6 6
    7 10 9 7
    8 10 9 8
    10 9 9
    10 11 10
    11 11

    A simple, and elegant solution, isn’t it? Is there any other better alternative?

  • Spring IoC, DI quick tutorial

    There has been an (evident) craze amongst Java community with contrived terms such as IoC (Inversion of Control), DI (Dependency Injection) mainly through Spring. I initially found the connotation “Don’t call me, I’ll call you” a bit difficult (yeah, it’s bending your head upside down) to understand, but after spending few hours around Spring documentation, I get the gist.

    To a layman (Java layman, of course) it is helpful to picture that each Java program is a set of one or more classes, which act together. Essentially, this means classes are “dependent” on some classes in order to be fully functional. Usually, the class requiring functionality of another class instantiates the class, and uses it. This is called coupling because class instantiates the object of required class. What if we always got an “instantiated” instance of required class, and our class did not have to worry of instantiation? – This is called IoC (Inversion of Control) principle in Spring, and it achieves this by providing ready-to-use instance (injecting dependency) to your class. This has some important uses, since now you don’t worry of creating connections to databases, loggers to log4j, or sessions for JMS queues. Spring will create these for you, and your class can focus on the actual purpose – using the pre-instantiated ready-to-use object.

    Get it? OK, to simplify it further, let us assume you have a class A having one field – log. You want to use log to log information, but your class nowhere has the logic to instantiate or initialize log. You accept a pre-instantiated log through constructor, or getter/setter methods, and you will have a ready-to-use log instance passed to your class via Spring!

    I won’t go into details of Spring further, since Spring’s own documentation on http://static.springsource.org/spring/docs/2.5.x/reference/index.html is the definitive source to look into.