Using an Interface in another interface

Question

I am not sure how to proceed with adding element to the Priority Queue. I don't want code to be spoon feed to me, can someone just explain to me how to use interface passed to another interface as parameter and a class implementing one of its method. Please give me pointers, I will look it up and learn how to implement this code.

QueueItem class

 public interface QueueItem 

     {

     /** 
    * Returns the priority of this item. The priority is guaranteed to be 
    * between 0 - 100, where 0 is lowest and 100 is highest priority.
    */

    public int priority();

    }

PriorityQueue class

 public interface PriorityQueue 

     {

    /**
    * Inserts a queue item into the priority queue.
    */
    public void insert(QueueItem q);

    /**
    * Returns the item with the highest priority.
    */
    public QueueItem next();

 }

QuickInsertQueue class

public class QuickInsertQueue implements  PriorityQueue  {

    @Override
    public void insert(QueueItem q) {
        // TODO Auto-generated method stub

    }

    @Override
    public QueueItem next() {
        // TODO Auto-generated method stub
        return null;
    }

}

I have to Write a QuickInsertQueue class that implements the PriorityQueue interface having insert() method O(1).

No this is online test your skills and I want to do this to improve my skills, spent a day couldn't figure out. — Daniel, Jun 30 '11 at 18:27
it is unclear what you need help with here - is it how to implement a O(1) algorithm? Is it how to write a class that implements the PriorityQueue interface in general? The statement "how to use interface passed to another interface as parameter and a class implementing one of its method" is hard to parse. — matt b, Jun 30 '11 at 18:42
Matt b, I a unable to write " Is it how to write a class that implements the PriorityQueue interface in general?" — Daniel, Jun 30 '11 at 19:34
Get some clarification about interfaces here http://stackoverflow.com/q/8531292/1055241 — gprathour, Jan 27 '12 at 07:22

score 2 · Answer 1 · answered Jun 30 '11 at 18:28

2

You are already on the right track. Your interfaces are defined and your class definition has the correct implementation attached. Since you say you dont want code spoon fed to you which I applaud - the next step you want to implement is actually adding the HashMap instance variable to your class, since that is your underlying storage. And in your method implementation for insert, you will be adding your variable to the map.

Eventually you are going to need to read about Generics.

answered Jun 30 '11 at 18:28

Perception

79,279
19
185
195

I don't see how generics are relevant to this particular problem. – Ted Hopp Jun 30 '11 at 18:30
It will be when he tries to define that Hashmap variable. – Perception Jun 30 '11 at 18:33
I don't see how how HashMaps are relative. :) but I guess that's why he the author removed that from the question. – Amir Raminfar Jun 30 '11 at 18:40
Well they aren't 'relevant' anymore! Haha, but really he pretty much answered his own question with the core *originally* posted. – Perception Jun 30 '11 at 18:43

score 1 · Answer 2 · answered Jun 30 '11 at 18:40

1

Ted and Perception have you told you what you need. One more suggestion I have is you need to find the right data structure to use so that insertion would be O(1). I suggest you look at heaps. Specifically looking at min-heaps allows you to insert in contant time. Look here. I hope this helps.

answered Jun 30 '11 at 18:40

Amir Raminfar

33,777
7
93
123

How can I implement public void insert(QueueItem q) { // TODO Auto-generated method stub } – Daniel Jun 30 '11 at 19:51

score 0 · Answer 3 · answered Jun 30 '11 at 18:32

You use an interface to guarantee that any object you receive will behave according to the interface. That's why your QuickInsertQueue needs to implement the methods of PriorityQueue. The only information it can use about the inserted objects, though, is that they behave according to the QueueItem interface—that is, they have a priority() method that returns an int. Your implementation can rely on that, but nothing else, about the objects it will be managing.

score 0 · Answer 4 · answered Jun 30 '11 at 18:56

You are on the right track. So, without getting into code level details that you are right you should figure out on your own, how it (is supposed to) work in an ideal world is -

All interaction in your system between different kind of objects is defined by using interfaces. i.e. if you need to find out "how do things interact in my application" you should need to look no further than all the interfaces. (Everything else is implementation detail.) In other words, all the real work is done by classes (that implement interfaces) but the interaction is defined by the interfaces.
One implementation class e.g. QuickInsertQueue, should not need to know anything about other implementations. (e.g. implementation of QueueItem) i.e. QueueItem does not need to know about what class is implementing PriorityQueue nor does PriorityQueue need to know about the class that implements QueueItem. (For this to work, make sure an in interface has all the methods necessary to allow others to interact with it. Also note that classes can implement multiple interfaces)

Practically,

Unless you are make use of things like factory method pattern and/or IoC containers like Spring or Guice, you will have at the least, an implementation instance (i.e. an object of a class) instantiating other implementations (objects of other classes) in your system.

(In this case, data structure to use so that insertion should be O(1) is an implementation detail quuestion/discussion)

Using an Interface in another interface

4 Answers4