-
Notifications
You must be signed in to change notification settings - Fork 0
/
fqGetIdsAVLTree.h
119 lines (103 loc) · 5.35 KB
/
fqGetIdsAVLTree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*##############################################################################
# Name: fastqGrepAVLTree
# Use: Header file for clustGraphReadTree.c
# Has functions to build a self blancing tree with read info nodes
##############################################################################*/
#ifndef FQGREPAVLTREE_C
#define FQGREPAVLTREE_C
#include <string.h> /*strcmp*/
#include "fqGetIdsStructs.h"
/*
Includes: <stdlib.h>
<stdio.h>
*/
/*##############################################################################
# Output:
# Returns: pointer to found or new readInfo node (with readnameCStr)
# 0: If the read name was not in the tree
# Modifes: readTree to have a new node with readNameCStr in it
##############################################################################*/
struct readInfo * findAddNodeToReadTree(
char * readIdCStr, /*c-string with name of read to find*/
const unsigned int *lenIdUInt, /*Length of read id*/
struct readInfo **readTree, /*tree to search for readNameCStr*/
struct readNodeStack *readStackAry /*Stack, (as array) for searching*/
); /*Finds or creates node with input read name in a read info tree*/
/*##############################################################################
# Output:
# Modifies: readInfo tree by inserting node, if not duplicate
# Returns: 0 if found duplicate, 1 if no duplicates
##############################################################################*/
uint8_t insertNodeIntoReadTree(
struct readInfo *idToInsert, /*node with read to insert in tree*/
struct readInfo **readTree, /*readInfo tree to insert read into*/
struct readNodeStack *readStackAry /*Stack, (as array) for searching*/
); /*Inserts read node in tree, if it is not a duplicate*/
/*##############################################################################
# Output:
# Returns:
# Pointer: to node with read
# 0: If the read name was not in the tree
##############################################################################*/
struct readInfo * searchTree(
struct bigNum *queryIdBigNum, /*Read id to search for (as big number)*/
struct readInfo *readTree /*readInfo tree to search for readNameCStr*/
); /*Find a particler read name in the avl tree*/
/*##############################################################################
# Output:
# Modifies: balanceChar in readNode to be the depth of its deepest child + 1
##############################################################################*/
void updateDepth(
struct readInfo *readNode /*node in tree of read id's to update*/
); /*Updates the depth of a single node by using its child nodes*/
/*##############################################################################
# Output:
# Returns: long with balance, - means left imbalanced, + right imbalenced
##############################################################################*/
int64_t getBalance(
struct readInfo *readNode /*node to get balance from*/
); /*Gets the balance of a single node in a tree*/
/*##############################################################################
# Output: Modifies: tree to be rebalanced when nodes unbalanced
##############################################################################*/
void rebalanceTree(
struct readNodeStack *readStackAry, /*stack of nodes to check*/
struct readInfo **readTree /*Root node of tree.
Changed when root swaped*/
); /*Uses readInfo nodes in readStack to reblance the tree*/
struct readInfo * readTreeRightLeftRebalance(
struct readInfo *parNode
); /*Does a right left rebalance on an avl readInfo tree*/
struct readInfo * readTreeRightRightRebalance(
struct readInfo *parNode
); /*Does a right left rebalance on an avl readInfo tree*/
struct readInfo * readTreeLeftRightRebalance(
struct readInfo *parNode
); /*Does a right left rebalance on an avl readInfo tree*/
struct readInfo * readTreeLeftLeftRebalance(
struct readInfo *parNode
); /*Does a left left rebalance on an avl readInfo tree*/
void readTreeAdjustParPtrAfterSwap(
struct readInfo *readOn, /*Parent node before a rebalance*/
struct readInfo *newPar, /*Parent node after rebalance*/
struct readNodeStack **readStackAry, /*Stack to get the parent node from*/
struct readInfo **readTree /*root node to make sure not swaped*/
); /*Addjusts parent poniter after rebalancing a readInfo tree*/
/*##############################################################################
# Output:
# Frees: every node in readTree & sets readTreeRoot to 0
# Returns: 1: if suceeded
# 0: If malloc failed to allocate stack memory
##############################################################################*/
uint8_t freeReadTree(
struct readInfo **readTree, /*Root of readInfo tree to free*/
struct readNodeStack *readStackAry /*Stack to use in freeing*/
); /*Frees a tree of readInfoNodes*/
/*##############################################################################
# Output:
# int: with max depth of the input readInfo tree
##############################################################################*/
int32_t getTreeDepth(
struct readInfo *readTree
); /*Gets depth of a readInfo tree (just here for testing)*/
#endif