472,352 Members | 1,465 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,352 software developers and data experts.

Event Queues

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
Expand|Select|Wrap|Line Numbers
  1. // Store a collection of events.  The operations are to add an event to the
  2. // collection, or to remove the earliest event from the collection.
  3. // Internally, a priority heap is used to provide an efficient implementation.
  5. class EventQueue
  6.     // The fields of an EventQueue are...
  7.     Event[] eventqueue = new Event[100];
  8.     // The capacity() method returns the maximum size that the queue can grow
  9.     // to without resizing.
  10.     public int capicity()
  11.     {
  12.         return eventqueue.length;
  13.     }
  14.     // The size() method returns the number of events currently in the queue.
  15.     public int size(int count)
  16.     {
  17.     for (int i=0; i<eventqueue.length;i++)
  18.         {
  19.             if (eventqueue != null); 
  20.             count = count+1;
  21.         }
  22.         return count;
  23.     }
  24.     // The add(event) method adds an event to the queue.
  25.     public void add(Event event)
  26.     {
  29.     }
  31.     // The take() method returns the earliest event in the queue.
  33.     // Test the queue.
  35.     public static void main(String[] args)
  36.     {
  37.         EventQueue q = new EventQueue();
  38.         Event e1 = new Event("One", 1);
  39.         Event e2 = new Event("Two", 2);
  40.         Event e3 = new Event("Three", 3);
  41.         q.add(e2);
  42.         q.add(e3);
  43.         q.add(e1);
  44.         test(q.size(), 3, "The queue should have size 3.");
  45.         test(q.capacity() >= 3, true, "The capacity should be >= size.");
  46.         test(q.take(), e1, "The earliest event was expected.");
  47.         test(q.take(), e2, "The second event was expected.");
  48.         test(q.take(), e3, "The third event was expected.");
  49.     }
  51.     // Test that an actual value matches an expected value, either of which can
  52.     // be null.  Print the given message and throw an error if not.
  54.     private static void test(Object actual, Object expected, String message)
  55.     {
  56.         if (actual == null && expected == null) return;
  57.         if (actual != null && actual.equals(expected)) return;
  58.         System.err.print(message);
  59.         System.err.print(": " + actual);
  60.         System.err.println(", not " + expected);
  61.         throw new Error("Testing failed.");
  62.     }
  63. }
Feb 15 '08 #1
5 2205
1,216 Expert 1GB
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.

Feb 15 '08 #2
1,216 Expert 1GB
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?
Feb 15 '08 #3
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
Feb 17 '08 #4
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:


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

/ \
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.
Feb 17 '08 #5
1,216 Expert 1GB
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.
Feb 17 '08 #6

Sign in to post your reply or Sign up for a free account.

Similar topics

by: Marcin Kielar | last post by:
hello i'm searching for algorithm able to detect and resolve conflicts during recursive event propagation. I'd like to implement small message...
by: Aki Niimura | last post by:
Hello everyone. I'm trying to control a program from a Python program using IPC. Although using a socket is a common choice for such...
by: badtemper | last post by:
Is there any way to use perl or any other programming language to perform a "qchk -A" from a web page and see the listing? My problem is that I...
by: Mark | last post by:
Hi, I'm looking for some ideas on how to build a very simple Event processing framework in my C++ app. Here is a quick background ... I'm...
by: saleem | last post by:
Dear friends, I am working on the problem which deals with the data management of requests and how should we match the responses for the requests...
by: Iain | last post by:
I've got a (VC++ 6.0) com object which does something asynchronously (writes a DVD image, actually). It rasies COM events to indicate progress,...
by: copx | last post by:
How do you implement an event queue in C? The problem I had is that events needed pointers to the objects they affect and I do not know any way to...
by: Anis | last post by:
hi, i want to know what is event that windows log in "Event Log". i have read that there r some services that log the event, but at the base level...
by: Chuck B | last post by:
I couldn't find the info I was looking for anwhere else so I'll try here. I have a custom control that calls a delegate method when a...
by: teenabhardwaj | last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...
by: Naresh1 | last post by:
What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...
by: jalbright99669 | last post by:
Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made...
by: Matthew3360 | last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ...
by: AndyPSV | last post by:
HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable...
by: Arjunsri | last post by:
I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and...
by: Matthew3360 | last post by:
Hi, I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web...
by: Oralloy | last post by:
Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.