/****************************************************************************
 * forest.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * Implements a forest for Huffman trees.
 ***************************************************************************/

#include <stdlib.h>

#include "forest.h"
#include "tree.h"


/*
 * Forest *
 * mkforest()
 *
 * Makes a forest, initially barren, returning pointer thereto
 * or NULL on error.
 */

Forest *
mkforest()
{
    // allocate space for forest
    Forest *f = malloc(sizeof(Forest));
    if (f == NULL)
        return NULL;

    // initialize forest as barren
    f->first = NULL;

    // return forest
    return f;
}


/*
 * Tree *
 * pick(Forest *f)
 *
 * Removes a tree with lowest weight from the forest, returning
 * pointer thereto or NULL if forest is barren.
 */

Tree * 
pick(Forest *f)
{
    // ensure source is not NULL
    if (f == NULL)
        return NULL;

    // check whether forest is barren
    if (f->first == NULL)
        return NULL;

    // pick tree with lowest weight
    Tree *tree = f->first->tree;

    // clear tree's plot
    Plot *plot = f->first;
    f->first = f->first->next;
    free(plot);

    // return tree
    return tree;
}


/*
 * bool
 * plant(Forest *f, Tree *t)
 *
 * Plants a tree in the forest, provided that tree's frequency is non-0.
 *
 * Returns TRUE on success and FALSE on error.
 */

bool 
plant(Forest *f, Tree *t)
{
    // ensure destination and source are not NULL
    if (f == NULL || t == NULL)
        return FALSE;

    // reject useless trees
    if (t->frequency == 0)
        return FALSE;

    // prepare tree for forest
    Plot *plot = malloc(sizeof(Plot));
    if (plot == NULL)
        return FALSE;
    plot->tree = t;

    // find tree's position in forest
    Plot *trailer = NULL;
    Plot *leader = f->first;
    while (leader != NULL)
    {
        // keep trees sorted first by frequency then by symbol
        if (t->frequency < leader->tree->frequency)
            break;
        else if (t->frequency == leader->tree->frequency
                 && t->symbol < leader->tree->symbol)
            break;
        else
        {
            trailer = leader;
            leader = leader->next;
        }
    }

    // either insert plot at start of forest
    if (trailer == NULL)
    {
        plot->next = f->first;
        f->first = plot;
    }

    // or insert plot in middle or at end of forest
    else
    {
        plot->next = trailer->next;
        trailer->next = plot;
    }

    // success!
    return TRUE;
}


/*
 * bool
 * rmforest(Forest *f)
 *
 * Deletes a forest (and all of its trees).
 *
 * Returns TRUE on success and FALSE on error.
 */

bool 
rmforest(Forest *f)
{
    // ensure source is not NULL
    if (f == NULL)
        return FALSE;

    // clear forest's trees
    while (f->first != NULL)
    {
        Plot *plot = f->first;
        f->first = f->first->next;
        rmtree(plot->tree);
        free(plot);
    }

    // free forest
    free(f);

    // success!
    return TRUE;
}