haplo_groups.c

Go to the documentation of this file.

/*
 * This work is licensed under a Creative Commons 
 * Attribution-Noncommercial-Share Alike 3.0 United States License.
 * 
 *    http://creativecommons.org/licenses/by-nc-sa/3.0/us/
 * 
 * You are free:
 * 
 *    to Share - to copy, distribute, display, and perform the work
 *    to Remix - to make derivative works
 * 
 * Under the following conditions:
 * 
 *    Attribution. You must attribute the work in the manner specified by the
 *    author or licensor (but not in any way that suggests that they endorse you
 *    or your use of the work).
 * 
 *    Noncommercial. You may not use this work for commercial purposes.
 * 
 *    Share Alike. If you alter, transform, or build upon this work, you may
 *    distribute the resulting work only under the same or similar license to
 *    this one.
 * 
 * For any reuse or distribution, you must make clear to others the license
 * terms of this work. The best way to do this is by including this header.
 * 
 * Any of the above conditions can be waived if you get permission from the
 * copyright holder.
 * 
 * Apart from the remix rights granted under this license, nothing in this
 * license impairs or restricts the author's moral rights.
 */


#include <config.h>

#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
#include <assert.h>

#include <libxml/tree.h>
#include <libxml/parser.h>

#ifdef HAPLO_HAVE_DMALLOC
#include <dmalloc.h>
#endif

#include <jwsc/base/error.h>
#include <jwsc/vector/vector.h>

#include "options.h"
#include "xml.h"
#include "haplo_groups.h"


static uint32_t num_haplo_groups = 0;


static const xmlNode** haplo_groups = NULL;


static xmlDoc* haplo_groups_xml = NULL;


static int compare_label_and_group_label
(
    const char*     label_1,
    const xmlNode** group_2
)
{
    const char*    label_2;
    const xmlNode* it;

    for (it = (*group_2)->children; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "label"))
        {
            label_2 = (const char*) it->children->content;
            break;
        }
    }

    return strcmp(label_1, label_2);
}


static int compare_label_and_group_altlabels
(
    const char*    label_1,
    const xmlNode** group_2
)
{
    const char*    altlabel_2;
    const xmlNode* it;

    for (it = (*group_2)->children; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "altlabel"))
        {
            altlabel_2 = (const char*) it->children->content;

            if (strcmp(label_1, altlabel_2) == 0)
            {
                return 0;
            }
        }
    }

    return 1;
}


static int compare_group_labels
(
    const xmlNode** group_1,
    const xmlNode** group_2
)
{
    const char*    label_1;
    const xmlNode* it;

    for (it = (*group_1)->children; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "label"))
        {
            label_1 = (const char*) it->children->content;
            break;
        }
    }

    return compare_label_and_group_label(label_1, group_2);
}


static uint32_t count_num_haplo_groups(const xmlNode* group)
{
    const xmlNode* it;
    uint32_t N = 0;

    for (it = group; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "group"))
        {
            N += 1 + count_num_haplo_groups(it->children);
        }
    }

    return N;
}


static void enumerate_haplo_groups
(
    xmlNode*         group, 
    const xmlNode*** groups_in_out
)
{
    xmlNode* it;

    for (it = group; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "group"))
        {
            **groups_in_out = it;
            (*groups_in_out)++;

            enumerate_haplo_groups(it->children, groups_in_out);
        }
    }

    assert((*groups_in_out - haplo_groups) <= num_haplo_groups);
}


static void set_haplo_group_back_pointers()
{
    uint32_t i;
    xmlNode* group;

    for (i = 0; i < num_haplo_groups; i++)
    {
        group = (xmlNode*)(haplo_groups[ i ]);
        group->_private = haplo_groups + i;
    }
}


static void build_haplo_groups_array_from_xml()
{
    const xmlNode*  root;
    const xmlNode** groups;

    root = xmlDocGetRootElement(haplo_groups_xml);

    num_haplo_groups = count_num_haplo_groups(root->children);
    assert((haplo_groups = malloc(num_haplo_groups * sizeof(xmlNode*))));

    groups = haplo_groups;
    enumerate_haplo_groups(root->children, &groups);

    qsort(haplo_groups, num_haplo_groups, sizeof(xmlNode*), 
            (int (*)(const void*, const void*))compare_group_labels);

    set_haplo_group_back_pointers();
}


static const xmlNode* binary_search_for_haplo_group_label
(
    uint32_t*   index_out, 
    const char* label
)
{
    const xmlNode** group;

    if ((group = bsearch(label, haplo_groups, num_haplo_groups, 
                    sizeof(xmlNode*), (int (*)(const void*, const void*))
                    compare_label_and_group_label)))
    {
        *index_out = group - haplo_groups;
        return *group;
    }

    return NULL;
}


static const xmlNode* linear_search_for_haplo_group_altlabel
(
    uint32_t*   index_out, 
    const char* altlabel
)
{
    const xmlNode** group;
    uint32_t i;

    for (i = 0; i < num_haplo_groups; i++)
    {
        group = &(haplo_groups[ i ]);

        if (compare_label_and_group_altlabels(altlabel, group) == 0)
        {
            *index_out = group - haplo_groups;
            return *group;
        }
    }

    return NULL;
}


Error* read_haplo_groups(const char* fname)
{
    xmlParserCtxt* xml_parse_ctxt;
    xmlValidCtxt*  xml_valid_ctxt;
    xmlDtd*        xml_dtd;
    int  slen = 256;
    char s[slen];

    assert(haplo_groups == NULL);
    assert(haplo_groups_xml == NULL);

    if (!fname)
    {
        return JWSC_EARG("No labels file specified");
    }

    assert(xml_parse_ctxt = xmlNewParserCtxt());

    if (!(haplo_groups_xml = xmlCtxtReadFile(xml_parse_ctxt, fname, NULL, 0)))
    {
        snprintf(s, slen, "%s: %s",fname, "Could not parse file");
        return JWSC_EARG(s);
    } 

    xmlFreeParserCtxt(xml_parse_ctxt);

    if (opts.labels_dtd_fname)
    {
        assert(xml_valid_ctxt = xmlNewValidCtxt());

        if (!(xml_dtd = xmlParseDTD(NULL, (xmlChar*)opts.labels_dtd_fname)))
        {
            snprintf(s, slen, "%s: %s", opts.labels_dtd_fname, 
                    "Could not parse file");
            return JWSC_EARG(s);
        }

        if (!xmlValidateDtd(xml_valid_ctxt, haplo_groups_xml, xml_dtd))
        {
            snprintf(s, slen, "%s: %s", fname, "XML file not valid");
            return JWSC_EARG(s);
        }

        xmlFreeValidCtxt(xml_valid_ctxt);
        xmlFreeDtd(xml_dtd);
    }

    build_haplo_groups_array_from_xml();

    return NULL;
}


Error* lookup_haplo_group_index_from_label
(
    uint32_t*   index_out, 
    const char* label
)
{
    int slen = 256;
    char s[slen];

    if (binary_search_for_haplo_group_label(index_out, label))
    {
        return NULL;
    }

    if (linear_search_for_haplo_group_altlabel(index_out, label))
    {
        return NULL;
    }

    snprintf(s, slen, "%s: %s", label, "Could not find haplo label");
    return JWSC_EARG(s);
}


Error* lookup_haplo_group_label_from_index
(
    const char** label_out, 
    uint32_t     index
)
{
    xmlNode* it;
    char s[256];

    if (index >= num_haplo_groups)
    {
        snprintf(s, 256, "Haplo label index '%u' too large", index);
        return JWSC_EARG(s);
    }

    for (it = haplo_groups[ index ]->children; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "label"))
        {
            *label_out = (const char*) it->children->content;
        }
    }

    return NULL;
}

Error* lookup_haplo_group_ancestor_index_from_haplo_group_index
(
    uint32_t*   index_out, 
    uint32_t     index
)
{
    xmlNode* parent;
    int slen = 256;
    char s[slen];
    xmlNode* it;
    const char* label_in;

    if (index >= num_haplo_groups)
    {
        snprintf(s, slen, "Haplo label index '%u' too large", index);
        return JWSC_EARG(s);
    }

    parent = haplo_groups[ index ]->parent;

    if(!parent || XMLStrEqual(parent->name, "haplo-labels"))
    {
        snprintf(s, slen, "Haplo label index '%u' too large", index);
        return JWSC_EARG(s);
    }

    for (it = parent->children; it; it = it->next)
    {
        if (it->type == XML_ELEMENT_NODE && XMLStrEqual(it->name, "label"))
        {
            label_in = (const char*) it->children->content;
            break;
        }
    }

    if(lookup_haplo_group_index_from_label(index_out,label_in))
    {
        snprintf(s, slen, "Label %s from parent not recognized", label_in);
        return JWSC_EARG(s);
    }

    return NULL;
}

uint32_t get_num_haplo_groups()
{
    return num_haplo_groups;
}


static uint8_t has_ancestor(const xmlNode* group_1, const xmlNode* group_2)
{
    if (group_1 == group_2)
    {
        return 1;
    }

    if (group_1->parent)
    {
        return has_ancestor(group_1->parent, group_2);
    }

    return 0;
}


static Haplo_ancestor_type find_ancestor_group_2
(
    const xmlNode** ancestor_out,
    const xmlNode*  group_1, 
    const xmlNode*  group_2
)
{
    if (group_1 == group_2)
    {
        *ancestor_out = group_1;
        return HAPLO_ANCESTOR_INDIRECT;
    }

    if (has_ancestor(group_1, group_2))
    {
        *ancestor_out = group_2;
        return HAPLO_ANCESTOR_INDIRECT;
    }

    assert(group_2->parent);
    return find_ancestor_group_2(ancestor_out, group_1, group_2->parent);
}


static Haplo_ancestor_type find_ancestor_group_1
(
    const xmlNode** ancestor_out,
    const xmlNode*  group_1, 
    const xmlNode*  group_2
)
{
    if (group_1 == group_2)
    {
        *ancestor_out = group_1;
        return HAPLO_ANCESTOR_DIRECT;
    }

    if (has_ancestor(group_1, group_2))
    {
        *ancestor_out = group_2;
        return HAPLO_ANCESTOR_DIRECT;
    }

    if (has_ancestor(group_2, group_1))
    {
        *ancestor_out = group_1;
        return HAPLO_ANCESTOR_DIRECT;
    }

    assert(group_2->parent);
    return find_ancestor_group_2(ancestor_out, group_1, group_2->parent);
}


uint8_t is_ancestor(uint32_t index_1, uint32_t index_2)
{
    return has_ancestor(haplo_groups[ index_1 ], haplo_groups[ index_2 ]);
}


Haplo_ancestor_type find_ancestor_index_of_pair
(
    uint32_t* index_out, 
    uint32_t  index_1, 
    uint32_t  index_2
)
{
    Haplo_ancestor_type ancestor_type;
    const xmlNode* ancestor;

    ancestor_type = find_ancestor_group_1(&ancestor, haplo_groups[ index_1 ], 
            haplo_groups[ index_2 ]);
    if ((xmlDoc*)(ancestor->parent) == haplo_groups_xml)
    {
        assert(XMLStrEqual(ancestor->name, "haplo-labels"));
        return HAPLO_ANCESTOR_NONE;
    }

    *index_out = ((const xmlNode**)(ancestor->_private)) - haplo_groups;
    assert(*index_out < num_haplo_groups);

    return ancestor_type;
}


Haplo_ancestor_type find_ancestor_index_of_set
(
    uint32_t*         index_out, 
    const Vector_u32* indices
)
{
    uint32_t i;
    Haplo_ancestor_type t1, t2;

    t1 = HAPLO_ANCESTOR_DIRECT;
    *index_out = indices->elts[0];

    for (i = 1; i < indices->num_elts; i++)
    {
        if (t1 == HAPLO_ANCESTOR_NONE)
        {
            *index_out = 0;
            break;
        }

        t2 = find_ancestor_index_of_pair(index_out, *index_out, 
                indices->elts[ i ]);
        if (t1 == HAPLO_ANCESTOR_DIRECT && t2 != HAPLO_ANCESTOR_DIRECT)
        {
            t1 = t2;
        }
        else if (t1 == HAPLO_ANCESTOR_INDIRECT && t2 == HAPLO_ANCESTOR_NONE)
        {
            t1 = t2;
        }
    }

    return t1;
}