CODEWITHSUNDEEP
javadata-structurespriority-queue
Daniel
Daniel

Reputation: 341

Using an Interface in another interface

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).

Upvotes: 2

Views: 611

Answers (4)

Amol Katdare
Amol Katdare

Reputation: 6760

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 -

  1. 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.

  2. 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)

Upvotes: 0

Amir Raminfar
Amir Raminfar

Reputation: 34169

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.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234847

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.

Upvotes: 0

Perception
Perception

Reputation: 80623

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.

Upvotes: 2

Related Questions