Programexempel från Progmet-föreläsning 13, tisdag 11 oktober 2011
==================================================================

Dagens program:

1. Forts: Sorteringsalgoritmer och deras tidskomplexitet
2. En abstrakt datatyp: mängd av heltal



1. Forts: Sorteringsalgoritmer och deras tidskomplexitet
========================================================

"Hemläxan": Programmet som hittar dubbletter av filer!

1. Två filer som är olika stora kan aldrig vara lika,
   så man behöver bara jämföra filer som är lika stora.

2. Man kan (från OS:et) snabbt få fram filstorleken för en fil,
   utan att öppna filen och läsa innehållet.

3. Sortera alla filerna i storleksordning med quicksort?
   Eller finns det en bättre lösning i det här fallet?




2. En abstrakt datatyp: mängd av heltal
=======================================

Användning:

Bilnummerspelet, "platespotting", men inte i ordning

Ett gränssnitt:

* Namnet IntSet
* Funktionerna init, add, is_member, remove och cleanup
* (De kallas IntSet_init, IntSet_add, IntSet_is_member, IntSet_remove och IntSet_cleanup.)

Flera möjliga implementationer:

Variant 1 - fast array av tal, ett tal per position
Variant 2 - dynamisk allokerad array av tal, ett tal per position
Variant 3 - fast array av flaggor, en per möjligt tal
Variant 4 - fast array av flaggor, en per möjligt tal, men packad
Variant 5 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad
Variant 6 - binärt träd
Variant 7 - hashtabell
Variant 8 - std::set



Variant 1 - fast array av tal, ett tal per position
---------------------------------------------------

/* bilnummer.c */

#include <stdio.h>
#include "IntSet.h"

int main(void) {
    IntSet mina_bilnummer;

    IntSet_init(&mina_bilnummer);

    printf("Mata in heltalsdelen av bilnummer. Avsluta med ett ogiltigt tal.\n");
    int bilnumret;
    while (scanf("%d", &bilnumret) == 1) {
        if (IntSet_is_member(&mina_bilnummer, bilnumret))
            printf("Fanns redan.\n");
        else {
            printf("Nytt!\n");
            IntSet_add(&mina_bilnummer, bilnumret);
        }
    }

    IntSet_cleanup(&mina_bilnummer);

    return 0;
}

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#define INTSET_MAX_MEMBERS 1000

struct IntSet {
    int members[INTSET_MAX_MEMBERS];
    int nr_members;
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

#include <stdlib.h>
#include <stdio.h>
#include "IntSet.h"

void IntSet_init(IntSet* isp) {
    isp->nr_members = 0;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else if (isp->nr_members == INTSET_MAX_MEMBERS) {
        fprintf(stderr, "IntSet: Set full. Sorry.\n");
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[isp->nr_members++] = new_number;
    }
}

/*
void int IntSet_is_member(IntSet* isp, int wanted) {
    for (int i = 0; i < isp->nr_members; ++i)
        if (isp->members[i] == wanted)
            return 1;
    return 0;
}
*/

static int find_position(IntSet* isp, int wanted) {
    for (int i = 0; i < isp->nr_members; ++i)
        if (isp->members[i] == wanted)
            return i;
    return -1;
}

int IntSet_is_member(IntSet* isp, int wanted) {
    return find_position(isp, wanted) != -1;
}

void IntSet_remove(IntSet* isp, int doomed) {
    int position = find_position(isp, doomed);
    if (position == -1) {
        // Not a member, so do nothing
    }
    else {
        for (int i = position; i < isp->nr_members - 1; ++i)
            isp->members[i] = isp->members[i + 1];
        --isp->nr_members;
    }
}

void IntSet_cleanup(IntSet* isp) {
    isp->nr_members = 0;
}



Variant 2 - dynamisk allokerad array av tal, ett tal per position
-----------------------------------------------------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

struct IntSet {
    int* members;
    int allocated_members;
    int nr_members;
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

#include <stdlib.h>
#include <stdio.h>
#include "IntSet.h"

void IntSet_init(IntSet* isp) {
    isp->members = NULL;
    isp->allocated_members = 0;
    isp->nr_members = 0;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else {
        if (isp->nr_members == isp->allocated_members) {
            if (isp->allocated_members == 0)
                isp->allocated_members = 16;
            else
                isp->allocated_members *= 2;
            isp->members = realloc(isp->members, isp->allocated_members * sizeof(isp->members[0]));
            if (isp->members == NULL) {
                fprintf(stderr, "IntSet: Memory full. Couldn't allocate %ld bytes. Sorry.\n",
                        (long int)(isp->allocated_members * sizeof(isp->members[0])));
                exit(EXIT_FAILURE);
            }
        }
        isp->members[isp->nr_members++] = new_number;
    }
}

static int find_position(IntSet* isp, int wanted) {
    for (int i = 0; i < isp->nr_members; ++i)
        if (isp->members[i] == wanted)
            return i;
    return -1;
}

int IntSet_is_member(IntSet* isp, int wanted) {
    return find_position(isp, wanted) != -1;
}

void IntSet_remove(IntSet* isp, int doomed) {
    int position = find_position(isp, doomed);
    if (position == -1) {
        // Not a member, so do nothing
    }
    else {
        for (int i = position; i < isp->nr_members - 1; ++i)
            isp->members[i] = isp->members[i + 1];
        --isp->nr_members;
    }
}

void IntSet_cleanup(IntSet* isp) {
    free(isp->members);
    isp->members = NULL;
    isp->allocated_members = 0;
    isp->nr_members = 0;
}



Variant 3 - fast array av flaggor, en per möjligt tal
-----------------------------------------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#define INTSET_MAX_NUMBER 1000

struct IntSet {
    int members[INTSET_MAX_NUMBER + 1];
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

#include <stdlib.h>
#include <stdio.h>
#include "IntSet.h"

void IntSet_init(IntSet* isp) {
    for (int i = 0; i <= INTSET_MAX_NUMBER; ++i)
        isp->members[i] = 0;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) {
        fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n");
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[new_number] = 1;
    }
}

int IntSet_is_member(IntSet* isp, int wanted) {
    if (wanted < 0 || wanted > INTSET_MAX_NUMBER)
        return 0;
    else
        return isp->members[wanted];
}

void IntSet_remove(IntSet* isp, int doomed) {
    if (doomed < 0 || doomed > INTSET_MAX_NUMBER) {
        // Outside range, so can't be in the set. Do nothing.
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[doomed] = 0;
    }
}

void IntSet_cleanup(IntSet* isp) {
    for (int i = 0; i <= INTSET_MAX_NUMBER; ++i)
        isp->members[i] = 0;
}



Variant 4 - fast array av flaggor, en per möjligt tal, men packad
-----------------------------------------------------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#include <limits.h>

#define INTSET_MAX_NUMBER 1000
#define INTSET_NR_BYTES ((INTSET_MAX_NUMBER + 1) / CHAR_BIT + 1)

struct IntSet {
    char members[INTSET_NR_BYTES];
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

#include <stdlib.h>
#include <stdio.h>
#include "IntSet.h"

void IntSet_init(IntSet* isp) {
    for (int i = 0; i < INTSET_NR_BYTES; ++i)
        isp->members[i] = 0;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) {
        fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n");
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[new_number / CHAR_BIT] |= (1 << new_number % CHAR_BIT);
    }
}

int IntSet_is_member(IntSet* isp, int wanted) {
    if (wanted < 0 || wanted > INTSET_MAX_NUMBER)
        return 0;
    else
        return (isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT)) != 0;
        // return isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT); -- Doesn't work:
}

void IntSet_remove(IntSet* isp, int doomed) {
    if (doomed < 0 || doomed > INTSET_MAX_NUMBER) {
        // Outside range, so can't be in the set. Do nothing.
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[doomed / CHAR_BIT] &= ~(1 << doomed % CHAR_BIT);
    }
}

void IntSet_cleanup(IntSet* isp) {
    for (int i = 0; i <= INTSET_NR_BYTES; ++i)
        isp->members[i] = 0;
}



Variant 5 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad
----------------------------------------------------------------------------

...



Variant 6 - binärt träd
-----------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

struct IntSetNode {
    int member;
    struct IntSetNode* left;
    struct IntSetNode* right;
};

struct IntSet {
    struct IntSetNode* root;
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

....



Variant 7 - hashtabell
----------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#define INTSET_HASH_TABLE_SIZE 4703

struct IntSetHashNode {
    int member;
    struct IntSetHashNode* next_in_bucket;
};

struct IntSet {
    struct IntSetHashNode* hash_table[INTSET_HASH_TABLE_SIZE];
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int new_number);
extern int IntSet_is_member(IntSet* isp, int wanted);
extern void IntSet_remove(IntSet* isp, int wanted);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

#include <stdlib.h>
#include <stdio.h>
#include "IntSet.h"

void IntSet_init(IntSet* isp) {
    for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i)
        isp->hash_table[i] = NULL;
}

static unsigned int hash_function(int n) {
    if (n < 0)
        n = -n;
    return n % INTSET_HASH_TABLE_SIZE;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else {
        struct IntSetHashNode* newnode = malloc(sizeof(struct IntSetHashNode));
        if (newnode == NULL) {
            fprintf(stderr, "IntSet: Minnet är fullt. Vi beklagar. Adjö.\n");
            exit(EXIT_FAILURE);
        }
        newnode->member = new_number;
        unsigned int position = hash_function(new_number);
        newnode->next_in_bucket = isp->hash_table[position];
        isp->hash_table[position] = newnode;
    }
}

int IntSet_is_member(IntSet* isp, int wanted) {
    unsigned int position = hash_function(wanted);
    struct IntSetHashNode* p = isp->hash_table[position];
    while (p != NULL) {
        if (p->member == wanted)
            return 1;
        else
            p = p->next_in_bucket;
    }
    return 0;
}

void IntSet_remove(IntSet* isp, int wanted) {
    unsigned int position = hash_function(wanted);
    struct IntSetHashNode* p = isp->hash_table[position];
    struct IntSetHashNode* previous = NULL;
    while (p != NULL) {
        if (p->member == wanted) {
            struct IntSetHashNode* doomed = p;
            if (previous == NULL)
                isp->hash_table[position] = p->next_in_bucket;
            else
                previous->next_in_bucket = p->next_in_bucket;
            free(doomed);
            return;
        }
        previous = p;
        p = p->next_in_bucket;
    }
}

void IntSet_cleanup(IntSet* isp) {
    for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) {
        struct IntSetHashNode* p = isp->hash_table[i];
        while (p != NULL) {
            struct IntSetHashNode* doomed = p;
            p = p->next_in_bucket;
            free(doomed);
        }
    }
}



(Variant 8 - std::set)
----------------------

Förstås enklare att implementera,
men datastrukturen i botten är ju någon av de här
(eller en annan).

Övning: Vilken?