473,698 Members | 1,902 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Event Queues

10 New Member
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 2300
1,216 Recognized Expert Top Contributor
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 Recognized Expert Top Contributor
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
10 New Member
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
10 New Member
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 Recognized Expert Top Contributor
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 passing framework without using message queue - messages would be delivered by simple method calls. This leads to recursive message ordering instead of natural one - and thus sometimes may cause problems. I know there are algorithms that detect this
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 applications, I would like to use SysV message queues because I don't need to parse the stream. I thought Python had a support of SysV message queues (I have found almost anything I need in Python library modules so far).
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 manage the network for a medical facility that is staffed 24/7/365 and when they are replacing the label stock on their barcode printers or the printer is taken offline, the queues are dropping. I would like to have a web page that would like the status of all the queues, along with a start /...
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 building a multithreaded app in C++ (on Linux) that uses message queues to pass pointers to Events between threads. In my app there are simple events that can be defined using an enum (for example an event called NETWORK_TIMEOUT) and more complex events that contain data (for example an event called...
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 to compare the correct Response. my problem is like this, say I am intermediary node between "m" and "n" nodes . n nodes send any of the "p"type of requests to any one of the "m" nodes on the other side. I have to forward the requests to
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, including completion. I've got this running in a c# application, with the events coming up and being caught (The idea is to use this to Set a ManualResetEvent which will alow the rest of the processign to happen). However, when I put an event after the call to start the async process off,
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 check if pointers are actually valid in C. The main issue is that the objects an event data structure points two might be removed before the event is executed. The only solution I came up with was scanning the entire queue each time an object was destroyed to remove all references to it. That was...
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 what exactly event is ? and can we make our own events and can supply that to those services?
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 SelectHandler event is fired. The SelectHandler method adds a ResetHandler method to the control's ResetHandlers. My question is; will multiple instances of the ResetHandler method be added to the event queue or is each method in the queue unique? If I knew how to get at the event handler queue I'd look...
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

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.