Implementing abstract data types

Posted on 1997-09-22
Last Modified: 2012-06-27

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.

Question by:blackbeauty
  • 2
  • 2

Accepted Solution

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

#include <set>
using namespace std;

class ReservationSystem // RS
    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
    struct Seats {
        NAT total;
        set<SSN> reserved;

    map<EVNR, Seats> itsEvents;

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

    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.reserved.size())

    virtual void remove_per_res(SSN s)
        for( Iter i = itsEvents.begin();
             i != itsEvents.end();
             ++i )

    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))
        return ret;

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


Since it the indentation sometimes gets mixed up in experts-exchange, I've put the source also at

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

Author Comment

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-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-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?  

Expert Comment

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 .

Author Comment

ID: 1170255
Good job on explaining my program.

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

831 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