Event Queues

[nt5515]

im trying to write a program that store a binary tree of possible events in an array. i need to be able to sort the the Events in the array based on the previous event that caused it by the time which they will occur. After the specific time has passed the event will be removed and all other events will be bumped up, all the while new events will be added to the end and sorted by their time.

Please Help

heres wot i've got so far, i've got some test that will test whe the program is doin wot it should. i just dont know how to implement the add(event) and remove(event) methods

// Store a collection of events.  The operations are to add an event to the
// collection, or to remove the earliest event from the collection.
// Internally, a priority heap is used to provide an efficient implementation.
 
class EventQueue
{ 
    // The fields of an EventQueue are...
    Event[] eventqueue = new Event[100];
    // The capacity() method returns the maximum size that the queue can grow
    // to without resizing.
    public int capicity()
    {
        return eventqueue.length;
    }
    // The size() method returns the number of events currently in the queue.
    public int size(int count)
    {
    for (int i=0; i<eventqueue.length;i++)
        {
            if (eventqueue != null); 
            count = count+1;
        }
        return count;
    }
    // The add(event) method adds an event to the queue.
    public void add(Event event)
    {
 
 
    }
 
    // The take() method returns the earliest event in the queue.
 
    // Test the queue.
 
    public static void main(String[] args)
    {
        EventQueue q = new EventQueue();
        Event e1 = new Event("One", 1);
        Event e2 = new Event("Two", 2);
        Event e3 = new Event("Three", 3);
        q.add(e2);
        q.add(e3);
        q.add(e1);
        test(q.size(), 3, "The queue should have size 3.");
        test(q.capacity() >= 3, true, "The capacity should be >= size.");
        test(q.take(), e1, "The earliest event was expected.");
        test(q.take(), e2, "The second event was expected.");
        test(q.take(), e3, "The third event was expected.");
    }
 
    // Test that an actual value matches an expected value, either of which can
    // be null.  Print the given message and throw an error if not.
 
    private static void test(Object actual, Object expected, String message)
    {
        if (actual == null && expected == null) return;
        if (actual != null && actual.equals(expected)) return;
        System.err.print(message);
        System.err.print(": " + actual);
        System.err.println(", not " + expected);
        throw new Error("Testing failed.");
    }
}

[BigDaddyLH]

Please enclose your posted code in [code] tags (See How to Ask a Question).

This makes it easier for our Experts to read and understand it. Failing to do so creates extra work for the moderators, thus wasting resources, otherwise available to answer the members' questions.

Please use [code] tags in future.

MODERATOR

[BigDaddyLH]

I'm confused. Isn't one of the features of a sorted tree data structure that it can efficiently maintain data in a sorted order yet allow you to insert and remove elements? Why the array, then? Are you sure you read your assignment correctly?

[nt5515]

hey sorry bout not using th [code] tags. im new to this and didnt know how. I had considered using a tree structure but the question does state the use of an array. I think its more an exercise in manipulating the array resizing and sorting etc.

could you tell me how to add a new event to the array? please

[nt5515]

heres the info i recieved about the question:

The purpose of the EventQueue class is to store all the events that "haven't happened yet" (according to the simulated current time). The events are taken out of the queue in order of increasing time. Here's a starting point for your class:

EventQueue.java

The EventQueue class stores events in an array which is bigger than is needed. For now, you can create the array with length 100 and assume there will never be more than 100 events. There is also a separate variable size which records how many events are currently stored in the array (from index 0 to index size-1).

The array represents a tree in which each node has up to two children. No pointers or anything like that are needed, just the array itself, because the tree has a very regular structure. The item at position n in the array has children which are at positions 2*n+1 and 2*n+2 in the tree, and a parent which is at position (n-1)/2. The item at position 0 is the top one in the tree and has no parent, and an item at position n has one child or no children if one or both of the child positions are greater than or equal to size. So, suppose the array contains 10 items in positions 0 to 9 like this:

a b c d e f g h i j

Then the tree which is implicitly represented looks like this. (It is a binary tree which is completely filled in, up to some point in the lowest row of nodes.)

a
/ \
b c
/ \ / \
d e f g
/ \ /
h i j

The trick is then to make sure that each event has an earlier time than either of its children. So, in the tree above, event a is earlier than b or c, but we don't care whether b is earlier than c or not. Then b is earlier than d or e and so on. This is effectively a compromise "partially sorted" array, making both of the necessary operations reasonably quick.

Then there are the two operations on the array to implement: adding another event, and extracting the earliest event.

To add another event, first put it in the next available slot in the array (slot size, after which size is incremented). The new event is then "bubbled up". That means while it has a parent, and it is earlier than its parent, swap it with its parent.

The queue allows events to have equal times, but doesn't guarantee any particular ordering between them (i.e. they will be extracted from the queue one after the other, nut not necessarily in the same order as they were added to the queue). We will discuss the efficiency of this priority queue implementation later in the course.

[BigDaddyLH]

Your instructor is describing a classic data structure called a "priority queue": http://en.wikipedia.org/wiki/Priority_queue .
Certain operations can be implemented efficiently in a PQ, including adding an element to the queue and remove the least element from the queue. The queue itself is not totally sorted, and shouldn't be used in applications that require the data to be totally sorted.