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

Planering för idag:

Forts. från föreläsning 3:
    * Forts. om modulen ListOfDoubles
    * Generiska behållare och funktioner, på olika sätt och i olika språk

Generisk lista i C (och C++) med void-pekare
C++ och klasser
Generisk lista i C++ med hjälp av en mall ("template")
En färdig listtyp: std::list
Iteratorer
Funktionspekare

Om vi hinner:

Mer om tidskomplexitet


Nu ska vi lära oss C++
----------------------

En generisk lista i C++ - typ 3, med en mall ("template")
-- men då måste vi först lära oss om klasser i C++

C++: Man brukar använda klasser ("class") för att skapa abstrakta datatyper
(personer, komplexa tal, double...)

En abstrakt datatyp i C: en struct + några funktioner som jobbar på den

En abstrakt datatyp i C++: Samma sak! Men lite annorlunda organiserat.



Igen: Den abstrakta datatypen Person...
---------------------------------------

Person version 1 -- samma gamla vanliga C-version som vi sett förut
-------------------------------------------------------------------



Person.h -- deklarationsfil
--------

// Person.h

struct Person {
    int nr;
    char namn[35 + 1];
};

void skriv_person(struct Person *p);
void las_person(struct Person *p);
int mindre_an(struct Person *p1, struct Person *p2);


Person.c -- implementationsfil
--------

// Person.c

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

void skriv_person(struct Person *p) {
    printf("Nr: %d\n", p->nr);
    printf("Namn: %s\n", p->namn);
}

void las_person(struct Person *p) {
    printf("Ange personens nummer: ");
    scanf("%d", &p->nr);
    printf("Ange personens namn (bara ett ord!): ");
    scanf("%s", p->namn);
}

int mindre_an(struct Person *p1, struct Person *p2) {
    return p1->nr < p2->nr;
}



personmain.c
------------

// personmain.c

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

int main(void) {
    printf("Ange två personer...\n");
    struct Person en_person;

    las_person(&en_person);
    struct Person en_annan_person;
    las_person(&en_annan_person);
    printf("Det var de här två personerna:\n");
    skriv_person(&en_person);
    skriv_person(&en_annan_person);

    if (mindre_an(&en_person, &en_annan_person))
        printf("Den första personen har lägre nummer än den andra.\n");
    else
        printf("Den första personen har inte lägre nummer än den andra.\n");

    return 0;
}



Person version 2. Vi har gjort om till C++!
-------------------------------------------



Person.h -- deklarationsfil
--------

// Person.h

struct Person {
    int nr;
    char namn[35 + 1];
    
    void skriv();
    void las();
    int mindre_an(struct Person *p2);
};



Person.cpp
----------

// Person.cpp

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

void Person::skriv() {
    printf("Nr: %d\n", this->nr);
    printf("Namn: %s\n", this->namn);
}

void Person::las() {
    printf("Ange personens nummer: ");
    scanf("%d", &this->nr);
    printf("Ange personens namn (bara ett ord!): ");
    scanf("%s", this->namn);
}

int Person::mindre_an(struct Person *p2) {
    return this->nr < p2->nr;
}



personmain-4.cpp
----------------

// personmain-4.cpp

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

int main(void) {
    printf("Ange två personer...\n");
    struct Person en_person;
    en_person.las();
    struct Person en_annan_person;
    en_annan_person.las();
    printf("Det var de här två personerna:\n");
    en_person.skriv();
    en_annan_person.skriv();

    if (en_person.mindre_an(&en_annan_person))
        printf("Den första personen har lägre nummer än den andra.\n");
    else
        printf("Den första personen har inte lägre nummer än den andra.\n");

    return 0;
}



Person version 3. Vi skriver "class" i stället för "struct", som man brukar i C++
---------------------------------------------------------------------------------

Person.h -- deklarationsfil
--------

// Person.h

class Person {
 private:
    int nr;
    char namn[35 + 1];
 public:    
    void skriv();
    void las();
    int mindre_an(struct Person *p2);
};



Person.cpp -- likadan som förut
personmain-4.cpp -- likadan som förut



En generisk lista i C++ - typ 3, med en mall ("template")
---------------------------------------------------------

GenericList3.h
--------------

// GenericList3.h

#ifndef GENERICLIST_H
#define GENERICLIST_H

template <typename T> class GenericList3 {
 private:

    struct GL_link {
        T data;
        GL_link *previous;
        GL_link *next;
    };

    GL_link *sentinel;
    int length;

 public:

    GenericList3();
    ~GenericList3();
    inline int get_length() const { return this->length; }

    T get(int position);
    inline T get_first() { return get(0); }
    inline T get_last() { return get(get_length() - 1); }

    int find(T wanted);

    void insert(T new_data, int position);
    inline void insert_first(T new_data) { insert(new_data, 0); }
    inline void insert_last(T new_data) { insert(new_data, get_length()); }

    void remove(int position);
    inline void remove_first() { remove(0); }
    inline void remove_last() { remove(get_length() - 1); }

};

#include "GenericList3.cpp"

#endif
// #ifndef GENERICLIST_H



GenericList3.cpp
----------------

// GenericList3.cpp

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

template <typename T> GenericList3<T>::GenericList3() {
    GL_link *sentinel = new GL_link();
    sentinel->data = -4711.4711; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this->sentinel = sentinel;
    this->length = 0;
}

template <typename T> GenericList3<T>::~GenericList3() {
    GL_link *sentinel = this->sentinel;
    GL_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        GL_link *doomed_link = current_link;
        current_link = current_link->next;
        delete doomed_link;
    }
    delete sentinel;
}

template <typename T> T GenericList3<T>::get(int position) {
    int length = get_length();
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList3: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this->sentinel;
    GL_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

template <typename T> int GenericList3<T>::find(T wanted) {
    GL_link *sentinel = this->sentinel;
    GL_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

template <typename T> void GenericList3<T>::insert(T new_data, int position) {
    int length = get_length();
    if (position < 0 || position > length) {
        fprintf(stderr, "GenericList3: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this->sentinel;
    GL_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    GL_link *new_link = new GL_link();
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this->length++;
}

template <typename T> void GenericList3<T>::remove(int position) {
    int length = get_length();
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList3: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this->sentinel;
    GL_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    GL_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    delete doomed_link;

    this->length--;
}



baklanges.cpp
-------------

// baklanges.cpp -- använder GenericList3

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

int main(void) {
    GenericList3<double> *talen = new GenericList3<double>();

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        talen->insert_first(talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (talen->get_length() > 0) {
        talet = talen->get_first();
        talen->remove_first();
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    delete talen;

    return 0;
}



Så vilken är bäst?
------------------

GenericList1: Typedef i C (funkar även i C++)?
GenericList2: void-pekare i C (funkar även i C++)?
GenericList3: Template (bara i C++)?
std::list? Standard! Template!



Till sist med std::list!
------------------------

baklanges.cpp
-------------

// baklanges.cpp -- använder std::list

#include <stdlib.h>
#include <stdio.h>
#include <list>

int main(void) {
    std::list<double> talen;

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        talen.push_front(talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (!talen.empty()) { // Obs! Använd inte "while (talen.size() > 0)"
        talet = talen.front();
        talen.pop_front();
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    return 0;
}



Iteratorer
----------

baklanges-med-iterator.cpp
--------------------------

// baklanges-med-iterator.c -- använder ListOfDoubles

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

int main(void) {
    ListOfDoubles *talen = LOD_create();

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        LOD_insert_first(talen, talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");

    LOD_iterator *current = LOD_begin(talen);
    LOD_iterator *end = LOD_end(talen);
    while (current != end) {
        talet = LOD_data(current);
        current = LOD_next(current);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    LOD_destroy(talen);

    return 0;
}



ListOfDoubles.h -- versionen med iteratorer
---------------

// ListOfDoubles.h

#ifndef LISTOFDOUBLES_H
#define LISTOFDOUBLES_H

struct LOD_link {
    double data;
    struct LOD_link *previous;
    struct LOD_link *next;
};

struct ListOfDoubles {
    struct LOD_link *sentinel;
    int length; // Cached for performance
};

typedef struct LOD_link LOD_link;
typedef struct ListOfDoubles ListOfDoubles;

extern ListOfDoubles *LOD_create(void);
extern void LOD_destroy(ListOfDoubles *this_list);
extern int LOD_length(ListOfDoubles *this_list);

extern double LOD_get(ListOfDoubles *this_list, int position);
extern double LOD_get_first(ListOfDoubles *this_list);
extern double LOD_get_last(ListOfDoubles *this_list);

extern int LOD_find(ListOfDoubles *this_list, double wanted);

extern void LOD_insert(ListOfDoubles *this_list, double new_data, int position);
extern void LOD_insert_first(ListOfDoubles *this_list, double new_data);
extern void LOD_insert_last(ListOfDoubles *this_list, double new_data);

extern void LOD_remove(ListOfDoubles *this_list, int position);
extern void LOD_remove_first(ListOfDoubles *this_list);
extern void LOD_remove_last(ListOfDoubles *this_list);

typedef struct LOD_link LOD_iterator;

extern LOD_iterator *LOD_begin(ListOfDoubles *this_list);
extern LOD_iterator *LOD_end(ListOfDoubles *this_list);
extern LOD_iterator *LOD_next(LOD_iterator *this_iterator);
extern LOD_iterator *LOD_previous(LOD_iterator *this_iterator);

extern double LOD_data(LOD_iterator *this_iterator);

#endif
// #ifndef LISTOFDOUBLES_H



ListOfDoubles.cpp -- versionen med iteratorer
-----------------

// ListOfDoubles.cpp

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

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "ListOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

ListOfDoubles *LOD_create(void) {
    ListOfDoubles *this_list = (ListOfDoubles *) safe_malloc(sizeof(ListOfDoubles));
    LOD_link *sentinel = (LOD_link *) safe_malloc(sizeof(LOD_link));
    sentinel->data = -4711.4711; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void LOD_destroy(ListOfDoubles *this_list) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        LOD_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int LOD_length(ListOfDoubles *this_list) {
    return this_list->length;
}

double LOD_get(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

extern double LOD_get_first(ListOfDoubles *this_list) {
    return LOD_get(this_list, 0);
}

extern double LOD_get_last(ListOfDoubles *this_list) {
    return LOD_get(this_list, LOD_length(this_list) - 1);
}

int LOD_find(ListOfDoubles *this_list, double wanted) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

void LOD_insert(ListOfDoubles *this_list, double new_data, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "ListOfDoubles: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    LOD_link *new_link = (LOD_link *) safe_malloc(sizeof(LOD_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;
}

void LOD_insert_first(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, 0);
}

void LOD_insert_last(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, LOD_length(this_list));
}

void LOD_remove(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    LOD_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;
}

void LOD_remove_first(ListOfDoubles *this_list) {
    LOD_remove(this_list, 0);
}

void LOD_remove_last(ListOfDoubles *this_list) {
    LOD_remove(this_list, LOD_length(this_list) - 1);
}

LOD_iterator *LOD_begin(ListOfDoubles *this_list) {
    return this_list->sentinel->next;
}

LOD_iterator *LOD_end(ListOfDoubles *this_list) {
    return this_list->sentinel;
}

LOD_iterator *LOD_next(LOD_iterator *this_iterator) {
    return this_iterator->next;
}

LOD_iterator *LOD_previous(LOD_iterator *this_iterator)  {
    return this_iterator->previous;
}

double LOD_data(LOD_iterator *this_iterator) {
    return this_iterator->data;
}



Iteratorer i std::list
----------------------

// baklanges.cpp -- använder std::list

#include <stdlib.h>
#include <stdio.h>
#include <list>

int main(void) {
    std::list<double> talen;

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        talen.push_front(talet);
    }
    fclose(tsin);
    
    FILE *tsut = fopen("ny-fil.txt", "w");
    std::list<double>::iterator current = talen.begin();
    std::list<double>::iterator end = talen.end();
    while (current != end) {
        talet = *current;
        current++;
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    return 0;
}



Funktionspekare
---------------



enkel-fp.cpp
------------

// enkel-fp.cpp

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

int addera(int x, int y) {
    return x + y;
}

int subtrahera(int x, int y) {
    return x - y;
}

int main(void) {
    int a, b;
    printf("Ge ett heltal: ");
    scanf("%d", &a);
    printf("Ge ett heltal till: ");
    scanf("%d", &b);

    int (*p)(int, int);
    
    printf("Plus eller minus (1 = plus, 2 = minus)? ");
    int vilken_operator;
    scanf("%d", &vilken_operator);

    if (vilken_operator == 1)
        p = addera;
    else
        p = subtrahera;

    int resultat = p(a, b);

    printf("Resultat: %d\n", resultat);

    return 0;
}



sortera.cpp
-----------

// sortera.cpp -- använder qsort

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

int jfr_tal(const void* p1, const void* p2) {
    return *(double*)p1 - *(double*)p2;
}

int main(void) {
    printf("Ge (högst 10) rella tal. Avsluta med ett negativt.\n");
    double talen[10];
    int antal = 0;
    double talet;
    printf("Ge ett tal: ");
    scanf("%lf", &talet);
    while (talet >= 0) {
        talen[antal++] = talet;
        printf("Ge ett tal: ");
        scanf("%lf", &talet);
    }
    qsort(talen, antal, sizeof(double), jfr_tal);
    printf("Talen sorterade:");
    for (int i = 0; i < antal; ++i)
        printf(" %.2f", talen[i]);
    printf("\n");
    return 0;
}



Lästips
-------

Bilting-boken ("Vägen till C, 2:a uppl"):
  Om qsort avsnitt 10.7.5 (s 247)
  Om Funktionspekare: avsnitt 7.11 (s 184-186)

Weiss-boken ("Data Structures and Algorithm Analysis in C++, 3d Ed"):
  Om C++-klasser avsnitt 1.4 t o m 1.4.3 (s 11-17)
  Om Templates avsnitt 1.6 (s 29-32)
  Om std::list och iteratorer: avsnitt 3.3 (s 74-79)