Jednostavni inventar II

Napraviti verziju 2 funkcionalnosti jednostavnog inventara iz prve verzije zadatka. Inventar sada mora da koristi dinamički alocirane strukture i rad sa pokazivačima. Niz predmeta se više ne čuva u statičkom nizu, već se memorija realocira po potrebi (početni kapacitet 4, pri popunjavanju kapacitet se duplira).

Rešiti zadatak u više fajlova: main.c, item.h, item.c, inventory.h, inventory.c.

Predmet (Item) treba da podržava sledeće funkcionalnosti:

Item struktura (sadrži naziv, težinu i vrednost);
Item item_make(const char name[], int w, int v) kreira novi predmet;
void item_print(const Item *it) ispisuje predmet na standardni izlaz;
int item_cmp_by_weight(const void *a, const void *b) i int item_cmp_by_value(const void *a, const void *b) komparatori za upotrebu sa qsort/bsearch; i
int item_cmp_by_name(const void *a, const void *b) komparator po imenu (koristi se pri pretraživanju).

Inventar (Inventory) treba da podržava sledeće funkcionalnosti i sve funkcije rade sa pokazivačima:

Inventory struktura (sadrži dinamički niz predmeta, veličinu, kapacitet, i indikator da li su predmeti sortirani po imenu)
void inv_init(Inventory *inv) inicijalizuje prazan inventar sa dinamičkim nizom;
void inv_free(Inventory *inv) oslobađa zauzetu memoriju;
int inv_add(Inventory *inv, Item it) dodaje predmet u inventar (po potrebi proširuje niz);
void inv_print(const Inventory *inv) ispisuje inventar;
int inv_total_weight(const Inventory *inv) vraća ukupnu težinu inventara;
int inv_total_value(const Inventory *inv) vraća ukupnu vrednost inventara;
const Item *inv_max_weight(const Inventory *inv) vraća najteži predmet inventara;
const Item *inv_max_value(const Inventory *inv) vraća najvredniji predmet inventara;
void inv_sort_by_name(Inventory *inv) sortira inventar po imenu koristeći qsort; i
const Item *inv_find_by_name(Inventory *inv, const char *name) pronalazi predmet po nazivu koristeći bsearch (pre pretrage, ukoliko inventar nije sortiran po nazivu, mora se pozvati inv_sort_by_name).

Ulaz

Sa standardnog ulaza se unosi broj upita $q$ ($1 \leq q \leq 100$). Zatim se unosi $q$ upita oblika:

a <name> <w> <v> - dodaje ili ažurira u inventaru predmet sa datim nazivom, težinom i vrednošću; ako postoji predmet sa istim nazivom, ažurirati mu težinu i vrednost;
p - ispisuje predmete inventara redosledom kojim su trenutno u nizu;
w - ispisuje ukupnu težinu inventara;
v - ispisuje ukupnu vrednost inventara;
W - ispisuje najteži predmet inventara;
V - ispisuje najvredniji predmet inventara; i
s <name> - pronalazi predmet sa datim nazivom (inventar se po potrebi sortira po nazivu i traženje se vrši binarnom pretragom), ispisati predmet ako je pronađen, inače ispisati not found.

Pretpostaviti da naziv predmeta nije duži od $30$, kao i da će u inventar biti smešteno najviše $10^9$ predmeta.

Izlaz

Na standardni izlaz ispisati rezultate upita redom:

za w i v ispisuje se odgovarajuća celobrojna vrednost;
za W i V ispisuje se predmet u formatu <name>{w=<w>,v=<v>} (ako inventar nije prazan);
za s ispisati predmet ili poruku not found; i
za p ispisati listu predmeta u formatu [ <it1>, <it2>, ..., <itn> ].

Primer

Ulaz

8
a sword 10 100
a shield 15 80
a potion 1 10
s shield
s bow
p
W
s potion

Izlaz

shield{w=15,v=80}
not found
[ potion{w=1,v=10}, shield{w=15,v=80}, sword{w=10,v=100} ]
shield{w=15,v=80}
potion{w=1,v=10}

Rešenje

`item.h`

#ifndef ITEM_H
#define ITEM_H

#define MAX_NAME_LENGTH 30

typedef struct Item {
    char name[MAX_NAME_LENGTH + 1];
    int weight;
    int value;
} Item;

Item item_make(const char name[MAX_NAME_LENGTH + 1], int w, int v);
void item_print(const Item *it);

int item_cmp_by_weight(const void *lhs, const void *rhs);
int item_cmp_by_value(const void *lhs, const void *rhs);
int item_cmp_by_name(const void *lhs, const void *rhs);

#endif // ITEM_H

`inventory.h`

#ifndef INVENTORY_H
#define INVENTORY_H

#include <stdbool.h>
#include <stddef.h>

#include "item.h"

#define INITIAL_CAPACITY 4

typedef struct Inventory {
    Item *items;
    size_t size;
    size_t capacity;
    bool sorted_by_name;
} Inventory;

void inv_init(Inventory *inv);
void inv_free(Inventory *inv);

int inv_add(Inventory *inv, Item it);
void inv_print(const Inventory *inv);

int inv_total_weight(const Inventory *inv);
int inv_total_value(const Inventory *inv);

const Item *inv_max_weight(const Inventory *inv);
const Item *inv_max_value(const Inventory *inv);

void inv_sort_by_name(Inventory *inv);
const Item *inv_find_by_name(Inventory *inv, const char *name);

#endif // INVENTORY_H

`item.c`

#include "item.h"

#include <stdio.h>
#include <string.h>

static const Item *as_item(const void *ptr)
{
    return (const Item *)ptr;
}

Item item_make(const char name[MAX_NAME_LENGTH + 1], int w, int v)
{
    Item it;

    strncpy(it.name, name, MAX_NAME_LENGTH);
    it.name[MAX_NAME_LENGTH] = '\0';

    it.weight = w;
    it.value = v;

    return it;
}

void item_print(const Item *it)
{
    printf("%s{w=%d,v=%d}", it->name, it->weight, it->value);
}

int item_cmp_by_weight(const void *lhs, const void *rhs)
{
    const Item *a = as_item(lhs);
    const Item *b = as_item(rhs);

    return a->weight - b->weight;
}

int item_cmp_by_value(const void *lhs, const void *rhs)
{
    const Item *a = as_item(lhs);
    const Item *b = as_item(rhs);

    return a->value - b->value;
}

int item_cmp_by_name(const void *lhs, const void *rhs)
{
    const Item *a = as_item(lhs);
    const Item *b = as_item(rhs);

    return strcmp(a->name, b->name);
}

`inventory.c`

#include "inventory.h"

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

static int inv_reserve(Inventory *inv, size_t new_capacity)
{
    Item *tmp = realloc(inv->items, new_capacity * sizeof (Item));
    if (tmp == NULL) {
        return 0;
    }

    inv->items = tmp;
    inv->capacity = new_capacity;

    return 1;
}

static Item *inv_find_linear(Inventory *inv, const char *name)
{
    if (!inv) {
        return NULL;
    }
    for (size_t i = 0; i < inv->size; i++) {
        if (strcmp(inv->items[i].name, name) == 0) {
            return &inv->items[i];
        }
    }
    return NULL;
}

void inv_init(Inventory *inv)
{
    if (inv == NULL) {
        return;
    }

    // realloc will only work for NULL or malloced/realloced pointers
    inv->items = NULL;
    inv->size = 0;
    inv->capacity = 0;
    inv->sorted_by_name = true;
}

void inv_free(Inventory *inv)
{
    if (inv == NULL) {
        return;
    }

    free(inv->items);
    inv->items = NULL;
    inv->size = 0;
    inv->capacity = 0;
    inv->sorted_by_name = true;
}

int inv_add(Inventory *inv, Item it)
{
    if (inv == NULL) {
        return 0;
    }

    Item *existing = inv_find_linear(inv, it.name);
    if (existing != NULL) {
        *existing = it;
        return 1;
    }

    if (inv->size == inv->capacity) {
        size_t new_capacity = inv->capacity ? 2 * inv->capacity : INITIAL_CAPACITY;
        if (!inv_reserve(inv, new_capacity)) {
            return 0;
        }
    }

    inv->items[inv->size++] = it;
    inv->sorted_by_name = false;

    return 1;
}

void inv_print(const Inventory *inv)
{
    if (inv == NULL) {
        printf("[ ]\n");
        return;
    }

    printf("[ ");
    for (size_t i = 0; i < inv->size; i++) {
        item_print(&inv->items[i]);
        if (i < inv->size - 1) {
            printf(", ");
        }
    }
    printf(" ]\n");
}

int inv_total_weight(const Inventory *inv)
{
    if (inv == NULL) {
        return 0;
    }

    int total_weight = 0;
    for (size_t i = 0; i < inv->size; i++) {
        total_weight += inv->items[i].weight;
    }
    return total_weight;
}

int inv_total_value(const Inventory *inv)
{
    if (inv == NULL) {
        return 0;
    }

    int total_value = 0;
    for (size_t i = 0; i < inv->size; i++) {
        total_value += inv->items[i].value;
    }
    return total_value;
}

const Item *inv_max_weight(const Inventory *inv)
{
    if (inv == NULL || inv->size == 0) {
        return NULL;
    }

    const Item *heaviest = &inv->items[0];
    for (size_t i = 1; i < inv->size; i++) {
        if (item_cmp_by_weight(&inv->items[i], heaviest) > 0) {
            heaviest = &inv->items[i];
        }
    }
    return heaviest;
}

const Item *inv_max_value(const Inventory *inv)
{
    if (inv  == NULL|| inv->size == 0) {
        return NULL;
    }

    const Item *best = &inv->items[0];
    for (size_t i = 1; i < inv->size; i++) {
        if (item_cmp_by_value(&inv->items[i], best) > 0) {
            best = &inv->items[i];
        }
    }
    return best;
}

void inv_sort_by_name(Inventory *inv)
{
    if (inv == NULL || inv->sorted_by_name) {
        return;
    }

    if (inv->size < 2) {
        inv->sorted_by_name = true;
        return;
    }

    qsort(inv->items, inv->size, sizeof (Item), item_cmp_by_name);
    inv->sorted_by_name = true;
}

const Item *inv_find_by_name(Inventory *inv, const char *name)
{
    if (inv == NULL || inv->size == 0 || name == NULL) {
        return NULL;
    }

    if (!inv->sorted_by_name) {
        inv_sort_by_name(inv);
    }

    Item key = item_make(name, 0, 0);
    return (const Item *) bsearch(&key, inv->items, inv->size, sizeof (Item), item_cmp_by_name);
}

`main.c`

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

#include "inventory.h"
#include "item.h"

int main(void)
{
    Inventory inv;

    inv_init(&inv);

    int q;
    scanf("%d", &q);

    while (q--) {
        char op;
        scanf(" %c", &op);

        if (op == 'a') {
            char name[MAX_NAME_LENGTH + 1];
            int w, v;
            scanf("%s %d %d", name, &w, &v);
            inv_add(&inv, item_make(name, w, v));
        } else if (op == 'p') {
            inv_print(&inv);
        } else if (op == 'w') {
            printf("%d\n", inv_total_weight(&inv));
        } else if (op == 'v') {
            printf("%d\n", inv_total_value(&inv));
        } else if (op == 'W') {
            const Item *it = inv_max_weight(&inv);
            if (it != NULL) {
                item_print(it);
                printf("\n");
            }
        } else if (op == 'V') {
            const Item *it = inv_max_value(&inv);
            if (it != NULL) {
                item_print(it);
                printf("\n");
            }
        } else if (op == 's') {
            char query[MAX_NAME_LENGTH + 1];
            scanf("%30s", query);
            const Item *it = inv_find_by_name(&inv, query);
            if (it == NULL) {
                printf("not found\n");
            } else {
                item_print(it);
                printf("\n");
            }
        }
    }

    inv_free(&inv);

    exit(EXIT_SUCCESS);
}

`Makefile`

CC = gcc
CFLAGS = -Wall -Wextra -pedantic -std=c11

.PHONY: all clean

all: main

main: main.o item.o inventory.o
	$(CC) $(CFLAGS) -o main main.o item.o inventory.o

main.o: main.c item.h inventory.h
	$(CC) $(CFLAGS) -c main.c -o main.o

item.o: item.c item.h
	$(CC) $(CFLAGS) -c item.c -o item.o

inventory.o: inventory.c inventory.h item.h
	$(CC) $(CFLAGS) -c inventory.c -o inventory.o

clean:
	rm -f main main.o item.o inventory.o