Histogram

Napisati program koji formira histogram broja pojavljivanja indeksa. Broj različitih indeksa nije unapred poznat, pa je potrebno po potrebi proširivati histogram.

Ulaz

Sa standardnog ulaza učitavaju se nenegativni celi brojevi do kraja ulaza.

Izlaz

Na standardni izlaz, za svaki indeks koji se pojavio bar jednom, ispisati indeks i broj pojavljivanja u obliku <idx>:<count>.

Primer

Ulaz

0 3 2 3 5 2 2 5 2

Izlaz

0:1
2:4
3:2
5:2

Rešenje

main.c

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

#define INITIAL_CAPACITY 8

typedef struct {
	size_t *count;
	size_t capacity;
} Histogram;

Histogram *histo_init()
{
	Histogram *histo = malloc(sizeof (Histogram));
	if (histo == NULL) {
		exit(EXIT_FAILURE);
	}

	histo->count = malloc(INITIAL_CAPACITY * sizeof (size_t));
	if (histo->count == NULL) {
		free(histo);
		exit(EXIT_FAILURE);
	}
	histo->capacity = INITIAL_CAPACITY;

	return histo;
}

void histo_free(Histogram *histo)
{
	free(histo->count);
	histo->count = NULL;
	histo->capacity = 0;
	free(histo);
}

int histo_inc(Histogram *histo, size_t idx) 
{
	if (idx >= histo->capacity) {
		size_t new_capacity = histo->capacity;
		while (idx >= new_capacity) {
			new_capacity += new_capacity / 2; // x 1.5
		}

		size_t *new_count = realloc(histo->count, new_capacity * sizeof (size_t));
		if (new_count == NULL) {
			return -1;
		}

		// Zero-fill only the newly allocated portion after realloc
		memset(new_count + histo->capacity, 0, (new_capacity - histo->capacity) * sizeof (size_t));

		histo->count = new_count;
		histo->capacity = new_capacity;
	}

	histo->count[idx]++;

	return 0;
}

int shrink_to_fit(Histogram *histo)
{
	size_t top = 0;
	for (size_t i = histo->capacity; i > 0; i--) {
		if (histo->count[i - 1]) {
			top = i;
			break;
		}
	}

	if (top < histo->capacity) {
		size_t *new_count = realloc(histo->count, top * sizeof(size_t));
		if (new_count == NULL) {
			return -1;
		}
		histo->count = new_count;
		histo->capacity = top;
	}

	return 0;
}

int main(void)
{
	Histogram *histo = histo_init();

	size_t idx;

	while (scanf("%zu", &idx) != EOF)  {
		if (histo_inc(histo, idx) != 0) {
			histo_free(histo);
			exit(EXIT_FAILURE);
		}
	}

	if (shrink_to_fit(histo) == -1) {
		histo_free(histo);
		exit(EXIT_FAILURE);
	}

	for (size_t i = 0; i < histo->capacity; i++) {
		if (histo->count[i]) {
			printf("%zu:%zu\n", i, histo->count[i]);
		}
	}

	histo_free(histo);

	exit(EXIT_SUCCESS);
}