Feladat:

Adott egy pályaudvar k darab vágánnyal rendelkezik. A pályaudvarra érkező vonatok napi forgalmi adatait egy szekvenciális fájlban találjuk. A fájl egy eleme tartalmazza a vonat egyedi azonosítóját, továbbá annak érkezési és indulási idejét. Ezek nem negatív egészek, az érkezési idő kisebb, mint az indulási. A fájl érkezési idő szerint monoton növekvően rendezett. A nap kezdetén a pályaudvar összes vágánya üres. Egy érkező vonat tetszőleges szabad vágányra beállhat és azt az indulási idejéig foglalja. Adjuk meg azon vonatok azonosítóit egy szekvenciális fájlban, amelyeket a pályaudvar nem tud fogadni, mert érkezésük idején nem lenne szabad vágány! Ezek a vonatok figyelmen kívül hagyandók.

Megoldás

A pályaudvar egy olyan típussal reprezentálható, mely mindig tudja, melyik eleme az, amelyik kimegy és az, amely pontosan k számosságú adatot tárol le. Ilyen típus a prioritási sor.

Van egy kimenő és egy bemenő fájlunk, az egyik összetett típusokat olvas be, a másik az összetett típus egyik részét írja csak ki. Ezeket iteráltan kell megoldani, tehát lesz egy iterált absztrakt osztályunk is.

Továbbá az összetett típust is meg kell adni.

És kell egy rész, amely magát a feladatot oldja meg, elvégzi a példányosításokat és származtatásokat.

Összetett típus (CTrain.hpp):

struct CTrain

{

unsigned int trainId;

unsigned int arrivalTime;

unsigned int leaveTime;

friend std::ifstream& operator>>(std::ifstream& s, CTrain& myTrain)

{

s >> myTrain.trainId >> myTrain.arrivalTime >> myTrain.leaveTime;

return s;

}

friend std::ofstream& operator<<(std::ofstream& s, const CTrain& myTrain)

{

s << myTrain.trainId;

return s;

}

friend bool operator>(const CTrain& a, const CTrain& b)

{

return (a.arrivalTime > b.leaveTime);

}

CTrain &operator=(const CTrain &b)

{

this->trainId = b.trainId;

this->arrivalTime = b.arrivalTime;

this->leaveTime = b.leaveTime;

}

};

Prioritási sor (CPriorityQue.hpp):

push() egy elemet tesz a sorba

pop() kiveszi az elsőbbséget élvező elemet (azt a vonatot, amely már elment)

isEmpty() megadja, hogy a sor üres-e

first() visszaadja az elsőbbséget élvező elem értékét

template <class Item>

class CPriorityQue

{

private:

Item* myQue;

unsigned int size;

unsigned int max;

int act; // ő lehet -1 is

public:

enum Exceptions {EQueIsFull, EQueIsEmpty};

CPriorityQue(unsigned int k);

~CPriorityQue();

void push(Item e);

void pop(Item &e);

bool isEmpty();

Item first();

};

Magát a megvalósítást nem írtam bele a dokumentációba, az egész az algoritmusok és adatszerkezetek alapján vektoros ábrázolással implementálódott

Iterált típus (CIterated.hpp)

#ifndef CITERATED

#define CITERATED

template <class Item>

class CIterated

{

protected:

CIterated() {}

public:

// virtual methods (abstract class)

virtual ~CIterated() {}

virtual void open() {}

virtual void close() {}

virtual void first() { read(); }

virtual void read() {}

virtual void write(const Item& e) {}

virtual bool end() { return true; }

virtual Item current() { Item e; return e; }

};

#endif

Mivel az osztály absztrakt, így minden metódus szinte virtuális (kivéve a konstrukort), amelyeket később a származtatás során felülbírálunk, ha akarjuk.

Származtatott bemenő fájl típus (CSeqInFile.hpp):

template <class Item>

class CSeqInFile : public CIterated<Item>

{

private:

std::ifstream f;

Item data;

std::string fileName;

public:

CSeqInFile(const std::string& s) : fileName(s) { open(); }

~CSeqInFile() { close(); }

void open() { f.open(fileName.c_str()); }

void read() { f >> data; }

bool end() const { return f.eof(); }

Item current() const { return data; }

void close() { f.close(); }

};

Származtatott kimenő fájl típus (CSeqOutFile.hpp):

template <class Item>

class CSeqOutFile : public CIterated<Item>

{

private:

std::ofstream f;

std::string fileName;

public:

CSeqOutFile(const std::string& s) : fileName(s) { open(); }

~CSeqOutFile() { close(); }

void open() { f.open(fileName.c_str()); }

void write(const Item& data) { f << data << endl; }

void close() { f.close(); }

};

Megoldó rész (CStation.hpp):

#ifndef CSTATION

#define CSTATION

#include "CSeqInFile.hpp"

#include "CSeqOutFile.hpp"

#include "CPriorityQue.hpp"

#include "CTrain.hpp"

class CStation

{

private:

CPriorityQue<CTrain>* station;

CSeqInFile<CTrain>* input;

CSeqOutFile<unsigned int>* output;

public:

CStation(const std::string InFileName, const std::string OutFileName, unsigned int NumberOfPlatforms)

{

station = new CPriorityQue<CTrain> (NumberOfPlatforms);

input = new CSeqInFile<CTrain> (InFileName);

output = new CSeqOutFile<unsigned int> (OutFileName);

} // end of constructor

Fent létrehozzuk a példányokat típusuk szerint.

~CStation()

{

delete station;

delete input;

delete output;

} // end of destructor

void Do()

{

CTrain trainRead;

CTrain dummy;

input->first();

trainRead = input->current();

while ((!station->isEmpty()) && (trainRead > station->first()))

{

station->pop(dummy);

if (station->isEmpty()) continue;

}

try

{

station->push(trainRead);

}

catch (...)

{

output->write(trainRead.trainId);

}

while(!input->end())

{

input->read();

trainRead = input->current();

while ((!station->isEmpty()) && (trainRead > station->first()))

{

station->pop(dummy);

if (station->isEmpty()) continue;

}

try

{

station->push(trainRead);

}

catch (...)

{

output->write(trainRead.trainId);

}

}

} // end of main procedure do

};

#endif

A program olvassa a fájlt (előolvasás fontos!) és ha az aktuális vonat érkezési ideje nagyobb mint a bentlévő vonatok valamelyikének az indulási időpontja, úgy azokat a vonatokat kiveszi a sorból, majd utána elhelyezi a beolvasottat.
Ha nem, úgy megpróbálja beletenni, de ha az állomás már tele van, akkor kiírja.

Főprogram (main.cpp):

#include <stdlib.h>

#include <iostream>

#include "CStation.hpp"

using namespace std;

int main(int argc, char *argv[])

{

CStation* myStation;

myStation = new CStation("vonat.txt", "rossz.txt", 10);

myStation->Do();

char dummy;

cout << " Gombnyomas es <ENTER> a vege... ";

cin >> dummy;

return 0;

}