/*
* Soubor: proj4.c
* Datum: 15.12.2004
* Autor: Kamil Dudka, xdudka00@stud.fit.vutbr.cz
* Projekt: IZP c. 4 - Ceske razeni
* Popis: Hlavni modul
*
* Prosím, neodevzdávejte zdrojové kódy, které jsou zde k dispozici,
* jako Vaše školní projekty. Děkuji :-)
*/
#include "proj4_io.h"
/*
* Hlavickovi soubor stdio.h se ve finalni verzi vkladat nebude
*/
#ifndef NDEBUG
// Slouzi pro vypis ladicich informaci na stdout
#include <stdio.h>
#endif
/*
* Pocet klicu a tudiz i priorit ktere mohou nabyvat
*/
#define MAX_KEY_COUNT 4
/*
* Chybove hlasky
*/
const char ErrBadArgs[] = "Neplatne nebo chybejici parametry! Zadejte: proj4 -h";
const char ErrBadKey[] = "Chybny klic! Prectete si manual pokud je k dispozici.";
const char ErrFilesOpen[] = "Overte nazev souboru, cestu a pristupova prava.";
const char ErrReadData[] = "Nelze nacist vstupni data.";
const char ErrWriteData[] = "Vystupni data byla ztracena.";
/*
* Hodnoty, ktere muze nabyvat klic
*/
typedef enum {
KEY_NULL, // klic je neplatny
KEY_SURNAME,
KEY_NAME,
KEY_SEX,
KEY_BIRTH
} EKey, *PEKey;
/*
* Prototypy funkci - popis jednotlivich funkci je dole
*/
int readKey (PEKey, const char *);
int sortByMultiKey (PTData, PEKey);
int sortBySingleKey (PTData, EKey);
int strCmpCz (void *, void *);
int intCmp (void *, void *);
inline void xchLink (PTData pData, unsigned a, unsigned b);
/*
* Nacte parametry z prikazove radky
* Nacte priority jednotlivych klicu - readKey()
* Nacte data ze vstupniho souboru, inicializuje mapovaci tabulku - readData()
* Seradi data podle tabulky klicu BEZ PRESUNU POLOZEK - sortByMultiKey()
* Zapise data do vystupniho souboru pomoci mapovaci tabulky - writeData()
*/
int main (int argc, char *argv[])
{
/*
* Tabulka klicu serazenych od nejvyssi priority k nejnizsi
*/
EKey keyTable[MAX_KEY_COUNT];
/*
* Strunktura obsahujici informace o datech
*/
TData data;
if (argc<2)
// Nebyly zadany zadne parametry
errorHandle (NULL, ErrBadArgs);
// Pouzitim nasledujici funkce uvrhnu v zapomneni knihovnu <string.h>
if (strCmpCz (argv[1], "-h")==0)
// Vypis napovedy
printHelpExit ();
if (argc<4)
// Zadano malo parametru
errorHandle (NULL, ErrBadArgs);
if (EXIT_SUCCESS!= readKey (keyTable, argv[1]))
// Zadan chybny klic
errorHandle (NULL, ErrBadKey);
if (EXIT_SUCCESS!= fileIO (FIO_INIT, argv) )
// Nelze otevrit soubory (nebo jeden z nich)
errorHandle (NULL, ErrFilesOpen);
#ifndef NDEBUG
// Ladici informace
printf ("Nacitam vstupni data\n");
#endif
if (EXIT_SUCCESS!= readData (&data))
// Chyba behem nacitani vstupnich dat
errorHandle (&data, ErrReadData);
#ifndef NDEBUG
// Ladici informace
printf ("Nacteno osob: %u\n", data.count);
printf ("Alokovana pamet pro data: %u KB\n",
data.count * sizeof(TPerson)/1024);
printf ("Velikost mapovaci tabulky: %u KB\n",
data.count * sizeof(unsigned)/1024);
#endif
// Zavreni zdrojoveho souboru
fileIO (FIO_CLOSESRC, NULL);
// Valstni razeni podle slozeneho klice
sortByMultiKey (&data, keyTable);
#ifndef NDEBUG
// Ladici informace
printf ("Zapisuji serazena data\n");
#endif
if (EXIT_SUCCESS!= writeData (&data))
// Chyba zapisu - data byla ztracena
errorHandle (&data, ErrWriteData);
// Zavreni vystupniho souboru
fileIO (FIO_CLOSEDEST, NULL);
return EXIT_SUCCESS;
}
/*
* Funkce nacte priority klicu z retezce keyStr
* Vraci EXIT_SUCCESS je-li slozeny klic dany retezcem platny
* Pocet klicu a tudiz i priorit je dan makrem MAX_KEY_COUNT
* @param keyTable - ukazatel na tabulku priorit klicu
* @param keyStr - retezec, ze ktereho jsou klice nacitany
*/
int readKey (PEKey keyTable, const char *keyStr)
{
register int i;
int keyNumber;
// Bitove pole rikajici ktere prvky jsou vyuzity slozenym klicem
int keyUsed [MAX_KEY_COUNT];
// Inicializace poli
for (i=0; i<MAX_KEY_COUNT; i++)
{
keyUsed[i] = 0;
keyTable[i] = KEY_NULL;
}
// Vytvoreni tabulky
for (i=0; keyStr[i]; i++)
{
if (i >= MAX_KEY_COUNT)
// Retezec klice je prilis dlouhy
return EXIT_FAILURE;
if (keyStr[i] < '1')
// Neznamy klic
return EXIT_FAILURE;
keyNumber = keyStr[i] - '1';
if (keyNumber >= MAX_KEY_COUNT)
// Neznamy klic
return EXIT_FAILURE;
if ( keyUsed[keyNumber] )
// Duplicitni klic
return EXIT_FAILURE;
keyUsed[keyNumber] = 1; // Hodnota klice vyuzita
keyTable [i] = keyNumber + 1; // Nastaveni priority klice
}
if (i==0)
// Retezec s klicem je prazdny
return EXIT_FAILURE;
else
return EXIT_SUCCESS;
}
/*
* Seradi data podle slozeneho klice.
* Zacne od klice s nejnizsi prioritou a
* postupne radi data podle elementarnich klicu.
* Predpoklada se stabilni radici metoda funkce sortBySingleKey()
* Vraci EXIT_SUCCESS, pokud je razeni vsech klicu uspesne.
* @param pData - ukazatel na serazovana data
* @param keyTable - ukazatel na tabulku klicu
*/
int sortByMultiKey (PTData pData, PEKey keyTable)
{
for (register int i= MAX_KEY_COUNT-1; i>=0; i--)
{
if (keyTable[i] == KEY_NULL)
// Klic nevyuzit
continue;
#ifndef NDEBUG
printf ("Radim podle klice %i\n", keyTable[i]);
#endif
if (EXIT_SUCCESS!= sortBySingleKey (pData, keyTable[i]))
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
/*
* Setridi data podle zvoleneho jednoducheho klice
* Pouziva se radici metoda Ripple-sort (pamatuje si misto prvni vymneny)
* Pouziva se RAZENI BEZ PRESUNU POLOZEK (meni se pouze mapovaci tabulka)
* Pokud je zadany klic neplatny vrati EXIT_FAILURE jinak EXIT_SUCCESS
* @param pData - ukazatel na serazovana data
* @param key - zvoleny jednoduchy klic
*/
int sortBySingleKey (PTData pData, EKey key)
{
/*
* Promenne cyklu trideni Ripple-sort
*/
int change; // 1 probehla-li vymena dvou prvku
unsigned int firstChg=0; // Prvni vymena v poslednim pruchodu
/*
* Typ ukazatele na porovnavaci funkci
* Typ odpovida funkcim strCmpCz() a intCmp()
*/
typedef int (*PCmpFce)(void *, void *);
/*
* Nasledujici dva ukazatele determinuje zvoleny klic
*/
PCmpFce pCmpFce; // Ukazatel na porovnavaci funkci
PTPerson pTag; // Ukazatel na polozku struktury (pretypovany)
/*
* Nastaveni ukazatelu podle zvoleneho klice
*/
switch (key)
{
case KEY_SURNAME:
pTag = (PTPerson) &pData->pData->surname;
pCmpFce = strCmpCz;
break;
case KEY_NAME:
pTag = (PTPerson) &pData->pData->name;
pCmpFce = strCmpCz;
break;
case KEY_SEX:
pTag = (PTPerson) &pData->pData->sex;
pCmpFce = intCmp;
break;
case KEY_BIRTH:
pTag = (PTPerson) &pData->pData->birth;
pCmpFce = intCmp;
break;
default:// Neplatny klic
return EXIT_FAILURE;
}
/*
* Cyklus trideni Ripple-sort (vylepsene Bubble-sort)
* Pouziva se neprimy pristup k prvkum databaze
* pres mapovaci tabulku (razeni bez presunu polozek)
*/
do
{
change = 0;
for (unsigned int i=firstChg; i< pData->count-1; i++)
if (0<pCmpFce (
pTag + pData->mapTable[i],
pTag + pData->mapTable[i+1] ))
{
// Vymena dvou prvku v mapovaci tabulce
xchLink (pData, i, i+1);
// Tato podminka v klasickem Bubble-sortu neni
if (!change && i)
// Polozka s prvni vymnenou
firstChg = i-1;
change = 1;
}
}
while (change); // Pokud nedoslo k vymnene cyklus se ukonci
return EXIT_SUCCESS;
}
/*
* Funkce lexikograficky porovna dva ceske retezce
* Pro znaky anglicke abecedy vraci hodnoty ekvivalentni ze strcmp()
* Pouziva dvoupruchodovy algoritmus
* Nejvetsi casova slozitost je pro ekvivalentni retezce
* Nepouziva funkce ze string.h
* @param arg1 - retezec 1
* @param arg2 - retezec 2
*/
int strCmpCz (void *arg1, void *arg2)
{
// Typova konverze zadanych parametru
const char *s1 = (const char*) arg1;
const char *s2 = (const char*) arg2;
/*
* Tabulka pro primarni razeni
*/
static const unsigned char priTable[256] = {
[(unsigned char)'A'] = 1, [(unsigned char)'a'] = 1, [(unsigned char)'Á'] = 1, [(unsigned char)'á'] = 1,
[(unsigned char)'B'] = 3, [(unsigned char)'b'] = 3,
[(unsigned char)'C'] = 4, [(unsigned char)'c'] = 4,
[(unsigned char)'Č'] = 5, [(unsigned char)'č'] = 5,
[(unsigned char)'D'] = 6, [(unsigned char)'d'] = 6, [(unsigned char)'Ď'] = 6, [(unsigned char)'ď'] = 6,
[(unsigned char)'E'] = 8, [(unsigned char)'e'] = 8, [(unsigned char)'É'] = 8, [(unsigned char)'é'] = 8, [(unsigned char)'Ě'] = 8, [(unsigned char)'ě'] = 8,
[(unsigned char)'F'] = 11, [(unsigned char)'f'] = 11,
[(unsigned char)'G'] = 12, [(unsigned char)'g'] = 12,
[(unsigned char)'H'] = 13, [(unsigned char)'h'] = 13,
// Číslo 14 je rezerováno pro CH, ktere nema svuj index
[(unsigned char)'I'] = 15, [(unsigned char)'i'] = 15, [(unsigned char)'Í'] = 15, [(unsigned char)'í'] = 15,
[(unsigned char)'J'] = 17, [(unsigned char)'j'] = 17,
[(unsigned char)'K'] = 18, [(unsigned char)'k'] = 18,
[(unsigned char)'L'] = 19, [(unsigned char)'l'] = 19,
[(unsigned char)'M'] = 20, [(unsigned char)'m'] = 20,
[(unsigned char)'N'] = 21, [(unsigned char)'n'] = 21, [(unsigned char)'Ň'] = 21, [(unsigned char)'ň'] = 21,
[(unsigned char)'O'] = 23, [(unsigned char)'o'] = 23, [(unsigned char)'Ó'] = 23, [(unsigned char)'ó'] = 23,
[(unsigned char)'P'] = 25, [(unsigned char)'p'] = 25,
[(unsigned char)'Q'] = 26, [(unsigned char)'q'] = 26,
[(unsigned char)'R'] = 27, [(unsigned char)'r'] = 27,
[(unsigned char)'Ř'] = 28, [(unsigned char)'ř'] = 28,
[(unsigned char)'S'] = 29, [(unsigned char)'s'] = 29,
[(unsigned char)'Š'] = 30, [(unsigned char)'š'] = 30,
[(unsigned char)'T'] = 31, [(unsigned char)'t'] = 31, [(unsigned char)'Ť'] = 31, [(unsigned char)'ť'] = 31,
[(unsigned char)'U'] = 33, [(unsigned char)'u'] = 33, [(unsigned char)'Ú'] = 33, [(unsigned char)'ú'] = 33, [(unsigned char)'Ů'] = 33, [(unsigned char)'ů'] = 33,
[(unsigned char)'V'] = 36, [(unsigned char)'v'] = 36,
[(unsigned char)'W'] = 37, [(unsigned char)'w'] = 37,
[(unsigned char)'X'] = 38, [(unsigned char)'x'] = 38,
[(unsigned char)'Y'] = 39, [(unsigned char)'y'] = 39, [(unsigned char)'Ý'] = 39, [(unsigned char)'ý'] = 39,
[(unsigned char)'Z'] = 41, [(unsigned char)'z'] = 41,
[(unsigned char)'Ž'] = 42, [(unsigned char)'ž'] = 42
};
/*
* Tabulka pro sekundarni razeni
*/
static const unsigned char secTable[256] = {
[(unsigned char)'A'] = 1, [(unsigned char)'a'] = 1,
[(unsigned char)'Á'] = 2, [(unsigned char)'á'] = 2,
[(unsigned char)'B'] = 3, [(unsigned char)'b'] = 3,
[(unsigned char)'C'] = 4, [(unsigned char)'c'] = 4,
[(unsigned char)'Č'] = 5, [(unsigned char)'č'] = 5,
[(unsigned char)'D'] = 6, [(unsigned char)'d'] = 6,
[(unsigned char)'Ď'] = 7, [(unsigned char)'ď'] = 7,
[(unsigned char)'E'] = 8, [(unsigned char)'e'] = 8,
[(unsigned char)'É'] = 9, [(unsigned char)'é'] = 9,
[(unsigned char)'Ě'] = 10, [(unsigned char)'ě'] = 10,
[(unsigned char)'F'] = 11, [(unsigned char)'f'] = 11,
[(unsigned char)'G'] = 12, [(unsigned char)'g'] = 12,
[(unsigned char)'H'] = 13, [(unsigned char)'h'] = 13,
// Číslo 14 je rezerováno pro CH, ktere nema svuj index
[(unsigned char)'I'] = 15, [(unsigned char)'i'] = 15,
[(unsigned char)'Í'] = 16, [(unsigned char)'í'] = 16,
[(unsigned char)'J'] = 17, [(unsigned char)'j'] = 17,
[(unsigned char)'K'] = 18, [(unsigned char)'k'] = 18,
[(unsigned char)'L'] = 19, [(unsigned char)'l'] = 19,
[(unsigned char)'M'] = 20, [(unsigned char)'m'] = 20,
[(unsigned char)'N'] = 21, [(unsigned char)'n'] = 21,
[(unsigned char)'Ň'] = 22, [(unsigned char)'ň'] = 22,
[(unsigned char)'O'] = 23, [(unsigned char)'o'] = 23,
[(unsigned char)'Ó'] = 24, [(unsigned char)'ó'] = 24,
[(unsigned char)'P'] = 25, [(unsigned char)'p'] = 25,
[(unsigned char)'Q'] = 26, [(unsigned char)'q'] = 26,
[(unsigned char)'R'] = 27, [(unsigned char)'r'] = 27,
[(unsigned char)'Ř'] = 28, [(unsigned char)'ř'] = 28,
[(unsigned char)'S'] = 29, [(unsigned char)'s'] = 29,
[(unsigned char)'Š'] = 30, [(unsigned char)'š'] = 30,
[(unsigned char)'T'] = 31, [(unsigned char)'t'] = 31,
[(unsigned char)'Ť'] = 32, [(unsigned char)'ť'] = 32,
[(unsigned char)'U'] = 33, [(unsigned char)'u'] = 33,
[(unsigned char)'Ú'] = 34, [(unsigned char)'ú'] = 34,
[(unsigned char)'Ů'] = 35, [(unsigned char)'ů'] = 33,
[(unsigned char)'V'] = 36, [(unsigned char)'v'] = 36,
[(unsigned char)'W'] = 37, [(unsigned char)'w'] = 37,
[(unsigned char)'X'] = 38, [(unsigned char)'x'] = 38,
[(unsigned char)'Y'] = 39, [(unsigned char)'y'] = 39,
[(unsigned char)'Ý'] = 40, [(unsigned char)'ý'] = 40,
[(unsigned char)'Z'] = 41, [(unsigned char)'z'] = 41,
[(unsigned char)'Ž'] = 42, [(unsigned char)'ž'] = 42
};
/*
* Tabulka tabulek - vyuzivam v hlavnim cyklu
* table[0] je tabulka pro primarni razeni
* table[1] je tabulka pro sekundarni razeni
*/
static const unsigned char *table[] = { priTable, secTable };
/*
* Uzitecne konstanty
*/
static const int S1 = 1; // S1 je vetsi
static const int S2 = -1; // S2 je vetsi
static const int EQ = 0; // S1 a S2 jsou shodne
static const unsigned char CZCH = 14; // Ceske pismeno 'ch'
/*
* Promenne cyklu
*/
unsigned int pos1, pos2;
unsigned char z1, z2;
/*
* Cyklus provede dva pruchody retezcem (pokud je potreba)
*/
for (int step=0; step<=1; step++)
{
// Vlastni pruchod retezcem
for (pos1=pos2=0; s1[pos1] && s2[pos2]; pos1++, pos2++)
{
// Konverze znaku prvniho retezce
z1 = table[step] [(unsigned char) s1[pos1] ];
if ((z1==4) && (s1[pos1+1]=='h'))
{ // aktualni znak je ceske 'ch'
z1 = CZCH;
pos1 ++;
}
// Konverze znaku druheho retezce
z2 = table[step] [(unsigned char) s2[pos2] ];
if ((z2==4) && (s2[pos2+1]=='h'))
{ // aktualni znak je ceske 'ch'
z2 = CZCH;
pos2 ++;
}
// Podminky ukonceni aktualniho pruchodu
if (z1>z2)
return S1;
if (z2>z1)
return S2;
}
// Rozhodovani podle delky retezce
if ((unsigned char)s1[pos1] > (unsigned char)s2[pos2])
return S1;
if ((unsigned char)s2[pos2] > (unsigned char)s1[pos1])
return S2;
}
// Oba retezce jsou stejne
return EQ;
}
/*
* Porovna dve cisla typu int predane odkazem
* Navratova hodnota je stejna jako u strCmpCz, ale porovnavaji se cisla
* @param arg1 - ukazatel na prvni cislo typu int
* @param arg2 - ukazatel na druhe cislo typu int
*/
int intCmp (void *arg1, void *arg2)
{
const int i1 = *((const int*) arg1);
const int i2 = *((const int*) arg2);
static const int I1 = 1; // i1 je vetsi
static const int I2 = -1; // i2 je vetsi
static const int EQ = 0; // Cisla jsou stejna
if (i1 > i2)
return I1;
if (i2 > i1)
return I2;
else
return EQ;
}
/*
* Vymeni dve polozky mapovaci tabulky
* @param pData - ukazatel na nactena data
* @param a - polozka tabulky
* @param b - polozka tabulky
*/
inline void xchLink (PTData pData, unsigned a, unsigned b)
{
assert(NULL!= pData);
assert(NULL!= pData->mapTable);
assert(a < pData->count);
assert(b < pData->count);
pData->mapTable[a] ^= pData->mapTable[b];
pData->mapTable[b] ^= pData->mapTable[a];
pData->mapTable[a] ^= pData->mapTable[b];
}
Back to main page
proj4.c [Download]