Data structures
Hello. I have a new question. So we have a task to simulate elevators in a building. We have 2 elevators, the two of them have different capacity.
When an elevators stops at a certain floor, the people that were waiting for the elevator get in the elevator oe by one if there is the capacity is not full. If there is no place for them, then they wait again.
The speed of the elevator is 0.2 between the floors /the elevator passes a floor for 5 secs/
Every person submits a request from the elevator cabin when the person gets in.
For input we have a text file that has the following info:
4 integer numbers:
G - number of floors in the building
K - the size of the first elevator
D - the size of the second elevator
T - number of requests that were submitted during the day, they are in order of their subimssion
Sequence of T requests (every request is on a new line)
we have 2 types of requests:
the first one: call from a floor: call dir floor time
dir - direction, that has to be sequence of chars - up or down
floor - integer number
time - natural number - time in secs from the start of the simulation
the second type: go floor time
floor - int number
time - natural number - time in secs from the start of the simulation
for output of the program we gotta have:
on a new line we have 4 components:
elevator, time, floor, dir - for every time the elevator stopped on a floor.
elevator - tells us which elevator
time - secs fro the start of the simulation
floor - the floor where the elevator stopped
dir - the direction in which the elevator was going
the elevators performs the request in the order in which they were submitted
in the begging the elevators are on floor 1
so my question, we have to use data structures, do I have to use queue or diff type of data structure, which one is the most suitable, idk where to start with everything and idk what classes i have to implement, how to do the reading from a text file when i use data structures and so on.. thanks in advance, everything will be helpful
When an elevators stops at a certain floor, the people that were waiting for the elevator get in the elevator oe by one if there is the capacity is not full. If there is no place for them, then they wait again.
The speed of the elevator is 0.2 between the floors /the elevator passes a floor for 5 secs/
Every person submits a request from the elevator cabin when the person gets in.
For input we have a text file that has the following info:
4 integer numbers:
G - number of floors in the building
K - the size of the first elevator
D - the size of the second elevator
T - number of requests that were submitted during the day, they are in order of their subimssion
Sequence of T requests (every request is on a new line)
we have 2 types of requests:
the first one: call from a floor: call dir floor time
dir - direction, that has to be sequence of chars - up or down
floor - integer number
time - natural number - time in secs from the start of the simulation
the second type: go floor time
floor - int number
time - natural number - time in secs from the start of the simulation
for output of the program we gotta have:
on a new line we have 4 components:
elevator, time, floor, dir - for every time the elevator stopped on a floor.
elevator - tells us which elevator
time - secs fro the start of the simulation
floor - the floor where the elevator stopped
dir - the direction in which the elevator was going
the elevators performs the request in the order in which they were submitted
in the begging the elevators are on floor 1
so my question, we have to use data structures, do I have to use queue or diff type of data structure, which one is the most suitable, idk where to start with everything and idk what classes i have to implement, how to do the reading from a text file when i use data structures and so on.. thanks in advance, everything will be helpful
Last edited on
read the text file and print out what you got. Do that part first, since you don't know how. There are tutorials here, look at ifstream.
unless I missed it, you need to have people get off the elevator when they get to their floor.
It may help to have a simple person object that says what floor they want to be on, and possibly where they started (debugging purposes), and possibly other info (time, etc). I don't think people object is required, but when you doodle out your design see if you want/need it (again, it may help debug or validate that its working right). For sure you need an elevator object, and a request object. When you do these, see if an STL object does most of the work needed, and if so, use that as the core and add a little to it for anything missing. Eg if the elevator turns out to be just a vector with some fluff... You need to coordinate everything against the simulation timer, too, so you need some way to share a timer object that ticks off a unit of time and the request object sees that and fires up the next request, and the elevator has to actually wait on timer ticks to move after stopping, etc.
as far as representing the elevator activity, a queue sounds correct. But observe this issue:
processing in order will be a mess.
person 1 gets on at floor 1 to go to floor 10.
person 2 gets on floor 1 to go to floor 3
elevator zerks to floor 10 to deliver #1, then back down to floor 3 to deliver #2 ?!
you want to avoid this stupidity, I think. It should drop 2 off on the way.
one way to do this better would be a 'counting sort' storage of the commands.
say you had 10 floors again, so you make a vector of 10 locations (lets make it 11 to simplify the no floor zero thing), and set all those to zero.
those guys get on, and vector[10] is incremented, and vector[3] is incremented.
Then your elevator logic checks as it goes... (you can't check all the items in a queue normally, the idea is only the item that can be removed exists to your knowledge). It starts to move and can see that it needs to deposit on 3, then 10, because there is a guy in bucket 3. When he is let out, you say vector[3]-- and it goes back to zero. This is cute and efficient but you may find yourself in a bind if you needed to track people (eg, who had the longest total service time?) but the problem isnt asking for that.
another idea may be some sort of priority queue, but you would have to roll your own (it can be a VERY thin wrapper for a STL container, probably a list?) and then you can sort the data ascending or decending based on the elevator's direction (I am not sure if you can change the rule used for priority if you don't roll your own logic here). Its similar to above but not as performant -- the sorting lets you stop on each floor in order for all the orders you know about so far (based on sim time!) and it works as above. The sorting is inherent in the above, though, and the direction is easy to reverse when looking at a vector.
pick up logic can be simple I think. if you have a pick-up order, you need to stop at that floor as you pass it processing other orders. If the elevator is currently empty, you need to go to the pick up floor.
do these ideas help?
unless I missed it, you need to have people get off the elevator when they get to their floor.
It may help to have a simple person object that says what floor they want to be on, and possibly where they started (debugging purposes), and possibly other info (time, etc). I don't think people object is required, but when you doodle out your design see if you want/need it (again, it may help debug or validate that its working right). For sure you need an elevator object, and a request object. When you do these, see if an STL object does most of the work needed, and if so, use that as the core and add a little to it for anything missing. Eg if the elevator turns out to be just a vector with some fluff... You need to coordinate everything against the simulation timer, too, so you need some way to share a timer object that ticks off a unit of time and the request object sees that and fires up the next request, and the elevator has to actually wait on timer ticks to move after stopping, etc.
as far as representing the elevator activity, a queue sounds correct. But observe this issue:
processing in order will be a mess.
person 1 gets on at floor 1 to go to floor 10.
person 2 gets on floor 1 to go to floor 3
elevator zerks to floor 10 to deliver #1, then back down to floor 3 to deliver #2 ?!
you want to avoid this stupidity, I think. It should drop 2 off on the way.
one way to do this better would be a 'counting sort' storage of the commands.
say you had 10 floors again, so you make a vector of 10 locations (lets make it 11 to simplify the no floor zero thing), and set all those to zero.
those guys get on, and vector[10] is incremented, and vector[3] is incremented.
Then your elevator logic checks as it goes... (you can't check all the items in a queue normally, the idea is only the item that can be removed exists to your knowledge). It starts to move and can see that it needs to deposit on 3, then 10, because there is a guy in bucket 3. When he is let out, you say vector[3]-- and it goes back to zero. This is cute and efficient but you may find yourself in a bind if you needed to track people (eg, who had the longest total service time?) but the problem isnt asking for that.
another idea may be some sort of priority queue, but you would have to roll your own (it can be a VERY thin wrapper for a STL container, probably a list?) and then you can sort the data ascending or decending based on the elevator's direction (I am not sure if you can change the rule used for priority if you don't roll your own logic here). Its similar to above but not as performant -- the sorting lets you stop on each floor in order for all the orders you know about so far (based on sim time!) and it works as above. The sorting is inherent in the above, though, and the direction is easy to reverse when looking at a vector.
pick up logic can be simple I think. if you have a pick-up order, you need to stop at that floor as you pass it processing other orders. If the elevator is currently empty, you need to go to the pick up floor.
do these ideas help?
Last edited on
Topic archived. No new replies allowed.