Retro Weekend Challenge – Histogram in C

Bored with all plug and play JS dev, I thought of going retro this weekend and took out the K&R. In the introduction, there was an exercise which author deemed bit challenging:

Write a program to print a histogram (vertical) of the frequencies of different characters in its input.

Here is my take on it.

First of all, the following are the constraints or limitations of this solution:

  • Shows histogram of only English alphabets and digits
  • Avoid any external helper libraries
  • Limited to only *nix/ Mac platforms
  • bar == ‘-‘

Depth First
The first approach I thought of trying is drawing out all the bars for a given digit/alphabet and then somehow move the cursor back to the initial position and start drawing again for next array element. However, nothing came on top of my head to solve that somehow part. So I went for the next approach. (Apparently, this can be done with terminal control escape sequence. )

Breadth First
In the second approach, I first found the max count among all elements of the digit/alphabet array. Then I ran a loop from s-> 1 to the max, meanwhile scanning each array element. If an array element has a count >= s, we draw a bar or else space. After one complete iteration across all array elements, program moves to the next line and repeat the exercise.

#include <stdio.h>
#include <unistd.h>
#include <sys/ioctl.h>

#define DIGITS 10
#define LETTERS 26

void nullify(int arr[], int size);
void histogram(int arr[], int size, int start, int terminalWidth);
int getTermWidth();

int main()
{
    int digits[DIGITS];
    int letters[LETTERS];
    nullify(digits, DIGITS);
    nullify(letters, LETTERS);

    int c;
    while ((c = getchar()) != EOF)
    {
        if (c >= '0' && c <= '9')
            digits[c - '0']++;
        else if (c >= 'a' && c <= 'z')
            letters[c - 'a']++;
        else if (c >= 'A' && c <= 'Z')
            letters[c - 'A']++;
    }

    int terminalWidth = getTermWidth();
    histogram(digits, DIGITS, '0', terminalWidth);
    histogram(letters, LETTERS, 'a', terminalWidth);
}

void nullify(int arr[], int size)
{
    // alternatively can use memset
    for (int i = 0; i < size; i++)
    {
        arr[i] = 0;
    }
}

/**
 * Print historgram
 * 
 * arr  - data array
 * size - size of data
 * start    - starting character for printing labels e.g. '0' or 'a'
 * terminalWidth    - width of terminal
 * 
 */
void histogram(int arr[], int size, int start, int terminalWidth)
{

    int max = 0;
    for (int i = 0; i < size; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }

    int req = size * 4;
    int batch = 1;
    int perBatch = size;
    int extras = 0;

    //create batches if terminal is smaller than the width of all array elements.
    if (terminalWidth < req)
    {
        batch = req / terminalWidth;
        perBatch = terminalWidth / 4;
        extras = (req % terminalWidth) / 4;
    }

    for (int b = 0; b <= batch; b++)
    {
        int low = b * perBatch;
        int up;

        if (b >= batch)
        {
            if (!extras)
                break;
            up = low + extras;
        }
        else
        {
            up = low + perBatch;
        }

        printf("%d, %d\n", low, up);

        for (int i = low; i < up; i++)
        {
            printf("%-4c", start++);
        }

        printf("\n");

        int s = 0;
        while (++s <= max)
        {
            for (int i = low; i < up; i++)
            {
                printf("%-4c", arr[i] >= s ? '-' : ' ');
            }
            printf("\n");
        }
    }
}

/**
 * Get terminal width from system's APIs
 * 
 * returns  - current terminal width (in columns)
 */
int getTermWidth()
{
    struct winsize w;
    ioctl(STDOUT_FILENO, TIOCGWINSZ, &w);
    return w.ws_col;
}

Moody terminal
The extra complexity crept into solution due to possible variations in the terminal width. To solve this, I use the *nix system APIs to get the current terminal width and deal with the case where it’s lesser than what’s required to display all array elements. Simply put, we create and process batches of the set of array elements as per terminal width (including the possible extra elements in left after the last batch).

stats wide terminal
Screen Width > Required
Screen Width < Required

Hope you enjoyed this as much as I did. Please do let me any you find any cool optimizations or better clever solutions for this.

Possible improvements
Use of ncurses – a terminal-independent library

As a side note, there is this Rust project Notty in progress which aims to take a totally modernistic approach to the terminal, including rich text formatting, inline media contents etc. Interesting 😉