Provides a mapping between haplo groups and their sequential ordering. More...

#include <config.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
#include <assert.h>
#include <libxml/tree.h>
#include <libxml/parser.h>
#include <jwsc/base/error.h>
#include <jwsc/vector/vector.h>
#include "options.h"
#include "xml.h"
#include "haplo_groups.h"

Functions
static int	compare_label_and_group_label (const char label_1, const xmlNode *group_2)
	Compares a label string against the label of a group xmlNode.
static int	compare_label_and_group_altlabels (const char label_1, const xmlNode *group_2)
	Compares a label string against the altlabels of a group xmlNode.
static int	compare_group_labels (const xmlNode group_1, const xmlNode group_2)
	Compares the label of one group xmlNode against another.
static uint32_t	count_num_haplo_groups (const xmlNode *group)
	Counts the number of groups contained within the haplo_groups_xml document tree.
static void	enumerate_haplo_groups (xmlNode group, const xmlNode **groups_in_out)
	Enumerates the groups in the haplo_groups_xml document tree into the haplo_groups array.
static void	set_haplo_group_back_pointers ()
static void	build_haplo_groups_array_from_xml ()
	Creates and initializes the haplo_groups array from an XML document that was read in from a file.
static const xmlNode *	binary_search_for_haplo_group_label (uint32_t index_out, const char label)
	Searches through the haplo_groups for a group with the specifed label.
static const xmlNode *	linear_search_for_haplo_group_altlabel (uint32_t index_out, const char altlabel)
	Searches through the haplo_groups for a group with the specifed altlabel.
Error *	read_haplo_groups (const char *fname)
	Reads the haplo groups from a file.
Error *	lookup_haplo_group_index_from_label (uint32_t index_out, const char label)
	Looks up the index for a haplo group based on its label.
Error *	lookup_haplo_group_label_from_index (const char **label_out, uint32_t index)
	Looks up a haplo group label from its index.
Error *	lookup_haplo_group_ancestor_index_from_haplo_group_index (uint32_t *index_out, uint32_t index)
	Looks up the index of the immediate ancestor for the haplogroup specified by the index.
uint32_t	get_num_haplo_groups ()
	Returns the number of haplo groups represented.
static uint8_t	has_ancestor (const xmlNode group_1, const xmlNode group_2)
	Tests whether or not a group is an ancestor of another.
static Haplo_ancestor_type	find_ancestor_group_2 (const xmlNode *ancestor_out, const xmlNode group_1, const xmlNode *group_2)
	Finds the lowest common ancestor between two groups.
static Haplo_ancestor_type	find_ancestor_group_1 (const xmlNode *ancestor_out, const xmlNode group_1, const xmlNode *group_2)
	Finds the lowest common ancestor between two groups.
uint8_t	is_ancestor (uint32_t index_1, uint32_t index_2)
	Returns whether a haplo group label is an ancestor of another.
Haplo_ancestor_type	find_ancestor_index_of_pair (uint32_t *index_out, uint32_t index_1, uint32_t index_2)
	Finds the lowest common ancestor between two haplo group labels.
Haplo_ancestor_type	find_ancestor_index_of_set (uint32_t index_out, const Vector_u32 indices)
	Finds the lowest common ancestor between a set of haplo group labels.
Variables
static uint32_t	num_haplo_groups = 0
	Number of haplo groups represented.
static const xmlNode **	haplo_groups = NULL
	Array of xmlNode pointers.
static xmlDoc *	haplo_groups_xml = NULL
	XML document containing the haplo groups.

Detailed Description

Provides a mapping between haplo groups and their sequential ordering.

Author:: Joseph Schlecht

License:: Creative Commons BY-NC-SA 3.0

Definition in file haplo_groups.c.

Function Documentation

static int compare_label_and_group_label	(	const char *	label_1,
		const xmlNode **	group_2
	)		`[static]`

Compares a label string against the label of a group xmlNode.

Returns:: integer less than, equal to or greater than zero, as per strcmp.

Definition at line 90 of file haplo_groups.c.

static int compare_label_and_group_altlabels	(	const char *	label_1,
		const xmlNode **	group_2
	)		`[static]`

Compares a label string against the altlabels of a group xmlNode.

Returns:: Zero if they are equal, and non-zero otherwise.

Definition at line 117 of file haplo_groups.c.

static int compare_group_labels	(	const xmlNode **	group_1,
		const xmlNode **	group_2
	)		`[static]`

Compares the label of one group xmlNode against another.

Returns:: An integer less than, equal to or greater than zero, as per strcmp.

Definition at line 148 of file haplo_groups.c.

static uint32_t count_num_haplo_groups ( const xmlNode * group ) [static]

Counts the number of groups contained within the haplo_groups_xml document tree.

This is a recursive function.

Definition at line 175 of file haplo_groups.c.

static void enumerate_haplo_groups	(	xmlNode *	group,
		const xmlNode ***	groups_in_out
	)		`[static]`

Enumerates the groups in the haplo_groups_xml document tree into the haplo_groups array.

This is a recursive function.

Definition at line 199 of file haplo_groups.c.

static void set_haplo_group_back_pointers ( ) [static]

Definition at line 221 of file haplo_groups.c.

static void build_haplo_groups_array_from_xml ( ) [static]

Creates and initializes the haplo_groups array from an XML document that was read in from a file.

Definition at line 238 of file haplo_groups.c.

static const xmlNode* binary_search_for_haplo_group_label	(	uint32_t *	index_out,
		const char *	label
	)		`[static]`

Searches through the haplo_groups for a group with the specifed label.

Takes time O(nlogn)

Returns:: The group matching the specifed label, or NULL if not found.

Definition at line 266 of file haplo_groups.c.

static const xmlNode* linear_search_for_haplo_group_altlabel	(	uint32_t *	index_out,
		const char *	altlabel
	)		`[static]`

Searches through the haplo_groups for a group with the specifed altlabel.

Takes time O(logn)

Returns:: The group matching the specifed label, or NULL if not found.

Definition at line 294 of file haplo_groups.c.

Error* read_haplo_groups ( const char * fname )

Reads the haplo groups from a file.

The file is expected to be a valid xml document according to haplo.dtd.

Parameters:

fname File to read the haplo groups from.

Returns:: On success, NULL is returned; otherwise an Error is returned.

Definition at line 324 of file haplo_groups.c.

Error* lookup_haplo_group_index_from_label	(	uint32_t *	index_out,
		const char *	label
	)

Looks up the index for a haplo group based on its label.

Parameters:

index_out	Result parameter.
label	Haplo group label to look-up the sequential index for.

Returns:: On success, NULL is returned; otherwise an Error is returned.

Definition at line 384 of file haplo_groups.c.

Error* lookup_haplo_group_label_from_index	(	const char **	label_out,
		uint32_t	index
	)

Looks up a haplo group label from its index.

Parameters:

label_out	Result parameter.
index	Index representing one of the haplo groups.

Returns:: On success, NULL is returned; otherwise an Error is returned.

Definition at line 414 of file haplo_groups.c.

Error* lookup_haplo_group_ancestor_index_from_haplo_group_index	(	uint32_t *	index_out,
		uint32_t	index
	)

Looks up the index of the immediate ancestor for the haplogroup specified by the index.

Definition at line 440 of file haplo_groups.c.

uint32_t get_num_haplo_groups ( )

Returns the number of haplo groups represented.

Returns:: The number of haplo groups represented.

Definition at line 484 of file haplo_groups.c.

static uint8_t has_ancestor	(	const xmlNode *	group_1,
		const xmlNode *	group_2
	)		`[static]`

Tests whether or not a group is an ancestor of another.

This is a recursive function.

Parameters:

group_1	Group whose ancestors are to be searched.
group_2	Group to test if it is an ancestor of group_1.

Returns:: If group_2 is an ancestor of group_1, 1 is returned; otherwise 0.

Definition at line 501 of file haplo_groups.c.

static Haplo_ancestor_type find_ancestor_group_2	(	const xmlNode **	ancestor_out,
		const xmlNode *	group_1,
		const xmlNode *	group_2
	)		`[static]`

Finds the lowest common ancestor between two groups.

Takes time O(log^2(n)) if the xml tree is roughly balanced.

Returns:: Returns the lowest common ancestor between group_1 and group_2.

Definition at line 526 of file haplo_groups.c.

static Haplo_ancestor_type find_ancestor_group_1	(	const xmlNode **	ancestor_out,
		const xmlNode *	group_1,
		const xmlNode *	group_2
	)		`[static]`

Finds the lowest common ancestor between two groups.

Takes time O(log^2(n)) if the xml tree is roughly balanced.

Returns:: Returns the lowest common ancestor between group_1 and group_2.

Definition at line 558 of file haplo_groups.c.

uint8_t is_ancestor	(	uint32_t	index_1,
		uint32_t	index_2
	)

Returns whether a haplo group label is an ancestor of another.

Parameters:

index_1	Index whose ancestors are to be searched.
index_2	Index to test if it is an ancestor of index_1.

Returns:: If index_2 is an ancestor of index_1, 1 is returned; otherwise 0.

Definition at line 594 of file haplo_groups.c.

Haplo_ancestor_type find_ancestor_index_of_pair	(	uint32_t *	index_out,
		uint32_t	index_1,
		uint32_t	index_2
	)

Finds the lowest common ancestor between two haplo group labels.

Parameters:

index_out	Result parameter.
index_1	Index of haplo label to find the common ancestor of.
index_2	Index of haplo label to find the common ancestor of.

Returns:: A value of Haplo_ancestor_type.

Definition at line 608 of file haplo_groups.c.

Haplo_ancestor_type find_ancestor_index_of_set	(	uint32_t *	index_out,
		const Vector_u32 *	indices
	)

Finds the lowest common ancestor between a set of haplo group labels.

Parameters:

index_out	Result parameter.
indices	Set of indices to find the common ancestor of.

Returns:: A value of Haplo_ancestor_type.

Definition at line 639 of file haplo_groups.c.

Variable Documentation

uint32_t num_haplo_groups = 0 [static]

Number of haplo groups represented.

Definition at line 69 of file haplo_groups.c.

const xmlNode** haplo_groups = NULL [static]

Array of xmlNode pointers.

Provides a a sequential index of the haplo groups in an xml parse tree.

Definition at line 77 of file haplo_groups.c.

xmlDoc* haplo_groups_xml = NULL [static]

XML document containing the haplo groups.

Definition at line 81 of file haplo_groups.c.

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation