Solved

Implementing abstract data types

Posted on 1997-09-22
4
235 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

734 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