Solved

Implementing abstract data types

Posted on 1997-09-22
4
213 Views
Last Modified: 2012-06-27
Hi,

I am trying to figure out how to do this problem and I don't have the faintest idea what to do. I need a few hints or advice on how to implement this reservation system. It suppose to use some sort of array system and if there is an easier way to handle this ... that will be great!

************************************************************
Implement the following abstract datatype reservation system (RS) that provides
the following 7 operations.

create: --> RS
Sem.: starts the reservation system

create-new-event: RSxEVNRxNAT -> RS
Sem.: creates a new event with NAT seats with a given event-number

cancel-event: RSxEVNR -> RS
Sem.: cancels the event with the given number

reserve-seat: RSxEVNRxSSN -> RS
Sem.: reserves a seat for a person with a given ssn for a given event

remove-per-res: RSxSSN -> RS
Sem.: removes the all reservation of a given person

get-ev-res: RSxEVNR -> set-of(SSN)
Sem.: gives the set reservations for a given event,

get-pers-res: RSxSSN -> set-of(EVNR)
Sem.: gives the set of events, a person has reservations for.

get-events: RS -> set-of(EVNR)
Sem.: returns the set of the currently defined events

In the above, the following types have the following meaning:

EVNR are numbers between 1 and 999999999 used to identify events; eventnumbers
are not necessarily consecutive.

NAT represents a positive integer between 1 and 1000 that is used to specify
the number of available seats for the event.

SSN represents social security numbers, which are used to identify persons that
made reservations for a particular event; ssn have to be numbers between
100000000 and 999999999.

0
Comment
Question by:blackbeauty
  • 2
  • 2
4 Comments
 
LVL 5

Accepted Solution

by:
yonat earned 200 total points
ID: 1170252
First, the definition of the ADT:

#include <set>
using namespace std;

class ReservationSystem // RS
{
public:
    typedef unsigned long EVNR;
    typedef unsigned int  NAT;
    typedef unsigned long SSN;

    virtual void create() = 0;
    virtual void create_new_event(EVNR e, NAT n) = 0;
    virtual void reserve_seat(EVNR e, SSN s) = 0;
    virtual void remove_per_res(SSN s) = 0;
    virtual set<SSN> get_ev_res(EVNR e) = 0;
    virtual set<EVNR> get_pers_res(SSN s) = 0;
    virtual set<EVNR> get_events() = 0;
};

And here is a simple implementation:

#include <map>
using namespace std;

class SimpleReservationSystem : public ReservationSystem
{
private:
    struct Seats {
        NAT total;
        set<SSN> reserved;
    };

    map<EVNR, Seats> itsEvents;

    typedef map<EVNR, Seats>::iterator Iter;

public:
    virtual void create() {}

    virtual void create_new_event(EVNR e, NAT n)
    {
        itsEvents[e].total = n;
    }

    virtual void reserve_seat(EVNR e, SSN s)
    {
        Seats& seats = itsEvents[e];
        if (seats.total > seats.reserved.size())
            seats.reserved.insert(s);
    }

    virtual void remove_per_res(SSN s)
    {
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )
            i->second.reserved.erase(s);
    }

    virtual set<SSN> get_ev_res(EVNR e)
    {
        return itsEvents[e].reserved;
    }

    virtual set<EVNR> get_pers_res(SSN s)
    {
        set<EVNR> ret;
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )
            if (itsEvents.end() != (*i).second.reserved.find(s))
                ret.insert((*i).first);
        return ret;
    }

    virtual set<EVNR> get_events()
    {
        set<EVNR> ret;
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )
            ret.insert((*i).first);
        return ret;
    }

};

Since it the indentation sometimes gets mixed up in experts-exchange, I've put the source also at
http://www.kinetica.com/home/yom/rs.h

Please tell me if you're having any problems, since the implementation uses STL, which is problematic for some compilers.
0
 

Author Comment

by:blackbeauty
ID: 1170253
This is a nice answer to my questions but I am not understanding the 'virutal' and 'set.' I am still a beginner of data structures but I need explanation of 'virtal set.' I don't think I am that far ahead in C++.  And #include<set> and #include<map>...are those in C compiler library? What if I created some datas to go with this program such as:
create:
create-new-event:  10001  200
create-new-event:   9999  10001
create-new-event:     23  100
create-new-event:     22  150
create-new-event:     33  20
cancel-event:         23
cancel-event:         16
create-new-event:     44  10
create-new-event:     55  5
reserve-seat:       8888  555555555
reserve-seat:          1  6666666666
reserve-seat:         55  123400000
reserve-seat:         55  223400000
reserve-seat:         55  323400000
reserve-seat:          1  123456780
reserve-seat:         55  423400000
reserve-seat:         55  223400000
reserve-seat:         11  223400000
reserve-seat:         55  523400000
reserve-seat:         55  100000004
reserve-seat:         55  100000002
reserve-seat:         11  200000001
reserve-seat:         11  200000002
reserve-seat:         11  200000003
reserve-seat:         11  200000004
reserve-seat:          1  123400000
reserve-seat:          1  123456781
reserve-seat:         22  123456789
get-pers-res:             123400000
get-pers-res:             223400000
remove-per-res:           523400000
remove-per-res:           123400000
remove-per-res:           200000005
cancel-event:          1
get-pers-res:             123400000
get-pers-res:             200000001
get-ev-res:           11
get-ev-res:           55
get-events:
get-pers-res:         11
get-pers-res:         33

Is there a simpler way to this implementing using some sort of linked arrays or the polynomial system?  
0
 
LVL 5

Expert Comment

by:yonat
ID: 1170254
<set> and <map> are standard headers. They declare the templates set and map, which are a part of the Standard Template Library (STL). STL is a part of the standard library.
It is easier to use standard ready maid containers, then to write your own, and that is why I used them.

The 'virtual' keyword has to do with inheritance and polymorphism. From your comment I gather that you haven't learned that yet, so we can ignore it: Ignore the class ReservationSystem and just use SimpleReservationSystem. Also, remover the
: public ReservationSystem
from the declaration and remove all the 'virtual's.
This will be just as good for your purposes.  have updated the web page to reflect this.

About the data: Are you sure that this is the way you want the ADT to be used? If so, I suggest you write a small parser the will parse the input file into calls to ReservationSystem.

Since this is getting a little long, I suggest we use e-mail for further discussion. You can mail me at yonat@usa.net .
0
 

Author Comment

by:blackbeauty
ID: 1170255
Good job on explaining my program.
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now