Programexempel från Progmet-föreläsning 4, tisdag 14 september 2010 (och fö 4?)
===============================================================================

Planering för idag:

Dubbellänkade listor
Funktionsbibliotek med generella funktioner,
    generiska datatyper (t ex en generisk lista)
C++ och klasser

(Det här tar nog minst två dagar.)



Dubbellänkade listor
--------------------

Vad?
----

struct talpost {
    double talet;
    struct talpost *previous;
    struct talpost *next;
};



Tips, när vi ändå ritar och definierar structar: "Listhuvud"
------------------------------------------------------------

struct tallista {
    struct talpost *first_in_list;
    struct talpost *last_in_list;
};

....

struct tallista talen; // Bättre abstraktion!
insert_first(&talen, 17.0);



Varför?
-------

Vissa operationer blir enklare!
(stoppa in och ta bort länkar i listan, traversering baklänges...)


Hur?
----

Se exemplet nedan, ListOfDoubles!



Dubbellänkade listor av flyttal: ListOfDoubles
----------------------------------------------

ListOfDoubles -- en dubbellänkad lista med double-flyttal, gjord som en abstrakt datatyp



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

// baklanges.cpp -- 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");
    while (LOD_length(talen) > 0) {
        talet = LOD_get_first(talen);
        LOD_remove_first(talen);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    LOD_destroy(talen);

    return 0;
}



ListOfDoubles.h
---------------

// 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);

#endif
// #ifndef LISTOFDOUBLES_H



ListOfDoubles.cpp
-----------------

// 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);
}



En alternativ implementation av t ex LOD_remove_first och LOD_remove_last
-------------------------------------------------------------------------

Ur ListOfDoubles.h:

#define LOD_remove_first(l)     LOD_remove((l), 0)
#define LOD_remove_last(l)      LOD_remove((l), LOD_length(l) - 1)



Traversering = "gå igenom listan"
------------

Som enkellänkad -- men man kan gå baklänges också!

Men: Om man har en sentinel, så är det inte:

    while (current_link != NULL) { ...

utan:

    while (current_link != sentinel) { ...



En speciell sorts traversering: upprensning (men: skräpsamling!)
-------------------------------------------

Som enkellänkad



En annan sorts traversering: Sökning (ur unique-1.cpp)
------------------------------------

Som enkellänkad

Liten optimering: Om man ska gå till en viss position i listan,
och den är i bakre halvan av listan,
så går det snabbare om man börjar i slutet och går bakåt.



Insättning först, sist och i mitten
-----------------------------------

Med cirkulär lista och sentinel blir alla lika!

    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++;



Borttagning
-----------

    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--;



Sökning i sorterad
------------------

Inte så intressant. Det finns bättre datastrukturer för sorterade data.



Insättning sorterad
-------------------

Inte så intressant. Det finns bättre datastrukturer för sorterade data.



Generella behållare och funktioner, på olika sätt och i olika språk
-------------------------------------------------------------------

Metod 1: typedef i C (eller makron)
Metod 2: void* i C
Metod 3: Templates i C++ (och Java, och C#...)



Metod 1: typedef i C (eller makron)
-----------------------------------

cmax1.cpp
---------

// cmax1.cpp -- max-funktionen i C

#include <stdio.h>

int max_int(int tal1, int tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

double max_double(double tal1, double tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max_int(a, b));

    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max_double(x, y));

    return 0;
}



cmax2a.cpp
----------

// cmax2a.cpp -- max-funktionen i C, som generisk funktion

#include <stdio.h>

typedef int MAX_DATATYP;

MAX_DATATYP max(MAX_DATATYP tal1, MAX_DATATYP tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max(a, b));

    return 0;
}



cmax2b.cpp
----------

// cmax2b.cpp -- max-funktionen i C, som generisk funktion

#include <stdio.h>

typedef double MAX_DATATYP;

MAX_DATATYP max(MAX_DATATYP tal1, MAX_DATATYP tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max(x, y));

    return 0;
}

(och sen ska vi titta på paketet GenericList version 1...)



Metod 2: void* i C
------------------

(vänta till paketet GenericList version 2...)



Metod 3: Templates i C++ (och Java, och C#...)
----------------------------------------------

cppmax.cpp
----------

// cppmax.cpp -- max-funktionen i C++

#include <stdio.h>

template <typename T> T max(T tal1, T tal2) {
    if (tal1 > tal2)
        return tal1;
    else
        return tal2;
}

int main(void) {
    int a, b;
    printf("Ange heltalet a: ");
    scanf("%d", &a);
    printf("Ange heltalet b: ");
    scanf("%d", &b);
    printf("Största heltalet var: %d\n", max(a, b));

    double x, y;
    printf("Ange reella talet x: ");
    scanf("%lf", &x);
    printf("Ange reella talet y: ");
    scanf("%lf", &y);
    printf("Största rellea talet var: %f\n", max(x, y));

    return 0;
}

(och sen ska vi titta på paketet GenericList version 3...)



En generisk lista i C (och C++) - typ 1, med typedef
----------------------------------------------------

Precis som ListOfDoubles, men byt ut alla "double" mot "GL_DATA_TYPE",
och typedef:a den till vad det nu är för sorts data man vill stoppa in i listan...



GenericList1.h
--------------

// GenericList1.h

#ifndef GENERIC_LIST_H
#define GENERIC_LIST_H

typedef double GL_DATA_TYPE;

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

struct GenericList1 {
    struct GL_link *sentinel;
    int length; // Cached for performance
};

typedef struct GL_link GL_link;
typedef struct GenericList1 GenericList1;

extern GenericList1 *GL_create(void);
extern void GL_destroy(GenericList1 *this_list);
extern int GL_length(GenericList1 *this_list);

extern GL_DATA_TYPE GL_get(GenericList1 *this_list, int position);
extern GL_DATA_TYPE GL_get_first(GenericList1 *this_list);
extern GL_DATA_TYPE GL_get_last(GenericList1 *this_list);

extern int GL_find(GenericList1 *this_list, GL_DATA_TYPE wanted);

extern void GL_insert(GenericList1 *this_list, GL_DATA_TYPE new_data, int position);
extern void GL_insert_first(GenericList1 *this_list, GL_DATA_TYPE new_data);
extern void GL_insert_last(GenericList1 *this_list, GL_DATA_TYPE new_data);

extern void GL_remove(GenericList1 *this_list, int position);
extern void GL_remove_first(GenericList1 *this_list);
extern void GL_remove_last(GenericList1 *this_list);

#endif
// #ifndef GENERIC_LIST_H



GenericList1.cpp
----------------

// GenericList1.cpp

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

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

GenericList1 *GL_create(void) {
    GenericList1 *this_list = (GenericList1 *) safe_malloc(sizeof(GenericList1));
    GL_link *sentinel = (GL_link *) safe_malloc(sizeof(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_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void GL_destroy(GenericList1 *this_list) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        GL_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int GL_length(GenericList1 *this_list) {
    return this_list->length;
}

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

extern GL_DATA_TYPE GL_get_first(GenericList1 *this_list) {
    return GL_get(this_list, 0);
}

extern GL_DATA_TYPE GL_get_last(GenericList1 *this_list) {
    return GL_get(this_list, GL_length(this_list) - 1);
}

int GL_find(GenericList1 *this_list, GL_DATA_TYPE wanted) {
    GL_link *sentinel = this_list->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;
}

void GL_insert(GenericList1 *this_list, GL_DATA_TYPE new_data, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "GenericList1: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->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 = (GL_link *) safe_malloc(sizeof(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_list->length++;
}

void GL_insert_first(GenericList1 *this_list, GL_DATA_TYPE new_data) {
    GL_insert(this_list, new_data, 0);
}

void GL_insert_last(GenericList1 *this_list, GL_DATA_TYPE new_data) {
    GL_insert(this_list, new_data, GL_length(this_list));
}

void GL_remove(GenericList1 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList1: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->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;

    free(doomed_link);

    this_list->length--;
}

void GL_remove_first(GenericList1 *this_list) {
    GL_remove(this_list, 0);
}

void GL_remove_last(GenericList1 *this_list) {
    GL_remove(this_list, GL_length(this_list) - 1);
}



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

// baklanges.cpp -- använder GenericList1

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

int main(void) {
    GenericList1 *talen = GL_create();

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

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

    GL_destroy(talen);

    return 0;
}



En generisk lista i C (och C++) - typ 2, med void-pekare
--------------------------------------------------------

En void-pekare (void*) kan peka på vilken sorts data som helst,
så låt listan innehålla void-pekare, som pekar på de riktiga dataelementen!



GenericList2.h
--------------

// GenericList2.h

#ifndef GENERIC_LIST_H
#define GENERIC_LIST_H

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

struct GenericList2 {
    struct GL_link *sentinel;
    int length; // Cached for performance
};

typedef struct GL_link GL_link;
typedef struct GenericList2 GenericList2;

extern GenericList2 *GL_create(void);
extern void GL_destroy(GenericList2 *this_list);
extern int GL_length(GenericList2 *this_list);

extern void *GL_get(GenericList2 *this_list, int position);
extern void *GL_get_first(GenericList2 *this_list);
extern void *GL_get_last(GenericList2 *this_list);

extern int GL_find(GenericList2 *this_list, void *wanted);

extern void GL_insert(GenericList2 *this_list, void *new_data, int position);
extern void GL_insert_first(GenericList2 *this_list, void *new_data);
extern void GL_insert_last(GenericList2 *this_list, void *new_data);

extern void GL_remove(GenericList2 *this_list, int position);
extern void GL_remove_first(GenericList2 *this_list);
extern void GL_remove_last(GenericList2 *this_list);

#endif
// #ifndef GENERIC_LIST_H



GenericList2.cpp
----------------

// GenericList2.cpp

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

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

GenericList2 *GL_create(void) {
    GenericList2 *this_list = (GenericList2 *) safe_malloc(sizeof(GenericList2));
    GL_link *sentinel = (GL_link *) safe_malloc(sizeof(GL_link));
    sentinel->data = (void*)0xdeadbeef; // 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 GL_destroy(GenericList2 *this_list) {
    GL_link *sentinel = this_list->sentinel;
    GL_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        GL_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int GL_length(GenericList2 *this_list) {
    return this_list->length;
}

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

extern void *GL_get_first(GenericList2 *this_list) {
    return GL_get(this_list, 0);
}

extern void *GL_get_last(GenericList2 *this_list) {
    return GL_get(this_list, GL_length(this_list) - 1);
}

int GL_find(GenericList2 *this_list, void *wanted) {
    GL_link *sentinel = this_list->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;
}

void GL_insert(GenericList2 *this_list, void *new_data, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "GenericList2: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->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 = (GL_link *) safe_malloc(sizeof(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_list->length++;
}

void GL_insert_first(GenericList2 *this_list, void *new_data) {
    GL_insert(this_list, new_data, 0);
}

void GL_insert_last(GenericList2 *this_list, void *new_data) {
    GL_insert(this_list, new_data, GL_length(this_list));
}

void GL_remove(GenericList2 *this_list, int position) {
    int length = GL_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "GenericList2: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    GL_link *sentinel = this_list->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;

    free(doomed_link);

    this_list->length--;
}

void GL_remove_first(GenericList2 *this_list) {
    GL_remove(this_list, 0);
}

void GL_remove_last(GenericList2 *this_list) {
    GL_remove(this_list, GL_length(this_list) - 1);
}



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

// baklanges.c -- använder GenericList2

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

int main(void) {
    GenericList2 *talen = GL_create();

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

    FILE *tsut = fopen("ny-fil.txt", "w");
    while (GL_length(talen) > 0) {
        double *talpekare = (double *)GL_get_first(talen);
        double talet = *talpekare;
        free(talpekare);
        GL_remove_first(talen);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    GL_destroy(talen);

    return 0;
}



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
----------

.......