Back Matter

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Appendix: Fundamental data structures

In several algorithms we have used fundamental data structures such as vectors and queues. I trust the reader to be familiar with these data structures, and rather than describing their implementation in the middle of the description of an algorithm, I have moved them to this appendix and made references to them when we encountered them the first time. We have needed some of the data structures for more than one type of elements, for example, a vector of strings and indices and a queue of pointers and indices. To avoid duplicated code, I have used a combination of functions and macros. Most of the smaller functions are most appropriately implemented as inline functions, so the compiler can optimize them. I have done this where I found for all short functions but not for longer functions. Without further ado, here are their implementations.

Vectors

#define vector_init(vec, init_size) {

(vec)->data = malloc((init_size) * sizeof(*(vec)->data));

(vec)->size = init_size;

(vec)->used = 0;

}

#define dealloc_vector(vec) {

free((vec)->data);

}

#define vector_append(vec, val) {

if ((vec)->used == vec->size) {

(vec)->data =

realloc((vec)->data, 2 * (vec)->size

* sizeof(*(vec)->data));

(vec)->size = 2 * (vec)->size;

}

(vec)->data[(vec)->used++] = (val);

}

#define vector_get(vec,idx) (vec)->data[(idx)]

#define vector_set(vec,idx,val) (vec)->data[(idx)] = (val)

struct index_vector {

uint32_t *data;

uint32_t size;

uint32_t used;

};

static inline void init_index_vector(

struct index_vector *vec,

uint32_t init_size

) {

vector_init(vec, init_size);

}

static inline void dealloc_index_vector(

struct index_vector *vec

) {

dealloc_vector(vec);

}

static inline struct index_vector *

alloc_index_vector(

uint32_t init_size

) {

struct index_vector *vec =

malloc(sizeof(struct index_vector));

init_index_vector(vec, init_size);

return vec;

}

static inline void free_index_vector(

struct index_vector *vec

) {

dealloc_index_vector(vec);

free(vec);

}

static inline void index_vector_append(

struct index_vector *vec,

uint32_t index

) {

vector_append(vec, index);

}

static inline uint32_t

index_vector_get(

struct index_vector *vec,

uint32_t i

) {

return vector_get(vec, i);

}

static inline void

index_vector_set(

struct index_vector *vec,

uint32_t i,

uint32_t val

) {

vector_set(vec, i, val);

}

void sort_index_vector(

struct index_vector *vec

);

bool index_vector_equal(

struct index_vector *v1,

struct index_vector *v2

);

void print_index_vector(

struct index_vector *vec

);

struct string_vector {

uint8_t **data;

uint32_t size;

uint32_t used;

};

static inline void init_string_vector(

struct string_vector *vec,

uint32_t init_size

) {

vector_init(vec, init_size);

}

static inline void dealloc_string_vector(

struct string_vector *vec

) {

dealloc_vector(vec);

}

static inline struct string_vector *

alloc_string_vector(

uint32_t init_size

) {

struct string_vector *vec =

malloc(sizeof(struct string_vector));

init_string_vector(vec, init_size);

return vec;

}

static inline void free_string_vector(

struct string_vector *vec

) {

dealloc_string_vector(vec);

free(vec);

}

static inline uint8_t *string_vector_get(

struct string_vector *vec,

uint32_t idx

) {

return vector_get(vec, idx);

}

static inline void string_vector_set(

struct string_vector *vec,

uint32_t idx,

uint8_t *string

) {

vector_set(vec, idx, string);

}

static inline void string_vector_append(

struct string_vector *vec,

uint8_t *string

) {

vector_append(vec, string);

}

struct pointer_vector {

void **data;

uint32_t size;

uint32_t used;

};

static inline void init_pointer_vector(

struct pointer_vector *vec,

uint32_t init_size

) {

vector_init(vec, init_size);

}

static inline void dealloc_pointer_vector(

struct pointer_vector *vec

) {

dealloc_vector(vec);

}

static inline struct pointer_vector *

alloc_pointer_vector(

uint32_t init_size

) {

struct pointer_vector *vec =

malloc(sizeof(struct pointer_vector));

init_pointer_vector(vec, init_size);

return vec;

}

static inline void free_pointer_vector(

struct pointer_vector *vec

) {

dealloc_pointer_vector(vec);

free(vec);

}

static inline void *pointer_vector_get(

struct pointer_vector *vec,

uint32_t idx

) {

return vector_get(vec, idx);

}

static inline void pointer_vector_set(

struct pointer_vector *vec,

uint32_t idx,

void *pointer

) {

vector_set(vec, idx, pointer);

}

static inline void pointer_vector_append(

struct pointer_vector *vec,

uint8_t *pointer

) {

vector_append(vec, pointer);

}

Lists

struct index_linked_list {

struct index_linked_list *next;

uint32_t data;

};

static inline struct index_linked_list *

new_index_link(

uint32_t val,

struct index_linked_list *tail

) {

struct index_linked_list *link =

malloc(sizeof(struct index_linked_list));

link->data = val; link->next = tail;

return link;

}

void free_index_list(

struct index_linked_list *list

) {

while (list) {

struct index_linked_list *next = list->next;

free(list);

list = next;

}

struct pointer_linked_list {

struct pointer_linked_list *next;

void *data;

};

static inline struct pointer_linked_list *

new_pointer_link(

void *val,

struct pointer_linked_list *tail

) {

struct pointer_linked_list *link =

malloc(sizeof(struct pointer_linked_list));

link->data = val; link->next = tail;

return link;

}

void free_pointer_list(

struct pointer_linked_list *list

) {

while (list) {

struct pointer_linked_list *next = list->next;

free(list);

list = next;

}

Queues

#define init_queue(queue) {

(queue)->front = 0;

(queue)->back = 0;

}

#define alloc_queue(queue_type) {

queue_type *queue = malloc(sizeof(queue_type));

init_queue(queue);

return queue;

}

#define enqueue(list_type, link_constructor, queue, val) {

list_type *link = link_constructor(val, 0);

if (queue->front == 0) {

queue->front = queue->back = link;

} else {

queue->back->next = link;

queue->back = link;

}

#define dequeue(list_type, queue) {

assert(queue->front != 0);

list_type *link = queue->front;

if (queue->front == queue->back) {

queue->front = queue->back = 0;

} else {

queue->front = queue->front->next;

}

free(link);

}

#define dealloc_queue(list_type, queue) {

while (!is_queue_empty(queue))

dequeue(list_type, queue);

}

#define free_queue(list_type, queue) {

dealloc_queue(list_type, queue);

free(queue);

}

#define is_queue_empty(queue)

((queue)->front == 0 && (queue)->back == 0)

#define queue_length(list_type, queue) {

uint32_t i = 0;

for (list_type *link = queue->front;

link;

link = link->next) {

i++;

}

return i;

}

struct index_queue {

struct index_linked_list *front;

struct index_linked_list *back;

};

static inline void init_index_queue(

struct index_queue *queue

) {

init_queue(queue);

}

static inline void dealloc_index_queue(

struct index_queue *queue

) {

dealloc_queue(struct index_linked_list, queue);

}

static inline struct index_queue *

alloc_index_queue(void) {

alloc_queue(struct index_queue);

}

static inline void free_index_queue(

struct index_queue *queue

) {

free_queue(struct index_linked_list, queue);

}

static inline bool is_index_queue_empty(

const struct index_queue *queue

) {

return is_queue_empty(queue);

}

static inline uint32_t

index_queue_front(

const struct index_queue *queue

) {

assert(queue->front != 0);

return queue->front->data;

}

static inline void enqueue_index(

struct index_queue *queue,

uint32_t index

) {

enqueue(struct index_linked_list,

new_index_link, queue, index);

}

static inline void dequeue_index(

struct index_queue *queue

) {

dequeue(struct index_linked_list, queue);

}

static inline uint32_t

index_queue_length(

struct index_queue *queue

) {

queue_length(struct index_linked_list, queue);

}

struct pointer_queue {

struct pointer_linked_list *front;

struct pointer_linked_list *back;

};

static inline void init_pointer_queue(

struct pointer_queue *queue

) {

init_queue(queue);

}

static inline void dealloc_pointer_queue(

struct pointer_queue *queue

) {

dealloc_queue(struct pointer_linked_list, queue);

}

static inline struct pointer_queue *

alloc_pointer_queue(void)

{

alloc_queue(struct pointer_queue);

}

static inline void free_pointer_queue(

struct pointer_queue *queue

) {

free_queue(struct pointer_linked_list, queue);

}

static inline bool is_pointer_queue_empty(

const struct pointer_queue *queue

) {

return is_queue_empty(queue);

}

static inline void *pointer_queue_front(

const struct pointer_queue *queue

) {

assert(queue->front != 0);

return queue->front->data;

}

static inline void enqueue_pointer(

struct pointer_queue *queue, void *pointer

) {

enqueue(struct pointer_linked_list,

new_pointer_link, queue, pointer);

}

static inline void dequeue_pointer(

struct pointer_queue *queue

) {

dequeue(struct pointer_linked_list, queue);

}

static inline uint32_t pointer_queue_length(

struct pointer_queue *queue

) {

queue_length(struct pointer_linked_list, queue);

}

Index

Aho-Corasick (AC) algorithm

failure links

iterators

matching and mismatching

missing matches problem

outlists and matches

output lists

preprocessing

trie structure

Alignment

alloc_suffix_tree()

alph_size

append_child()

Approximate search

comparison

Li-Durbin algorithm

SeeLi-Durbin algorithm

local alignment and CIGAR notation

suffix trees

Array-based algorithms

Array-based children

Backward border array

Binary search

Bit array macros

bool array

Border array construction algorithm

Border array jump table

Border arrays

Border of string

Boyer-Moore (BM) algorithm

border array

combining jump tables

jump rule one

backward border array

border array jump table

computing Z array

jump table based on reverse borders

matching suffix

point to border endpoints

prefix and suffix

restricted reversed border array

reverse border array

reverse-compute-reverse strategy

uniqueness of endpoints

Z array

Z-based jump table

jump rule two

border array

jump ranges

restricted reversed border array

reversed border array

Boyer-Moore-Horspool (BMH) algorithm

Brute force approach

edit cloud, building

at_beginning variable

CIGAR representation

deletion and match operations

pattern

pattern_front and edits_front

pushing information

push operations

recursion

recursive version

stack frames

Buckets

Burrows-Wheeler transform (BWT)

C and O tables

construction

construction time

running time

search algorithm

searching

string transformation

CHECK_INDEX()

CIGAR format

CIGAR string

Code conventions

compute_failure_link_for_node()

compute_failure_link_node()

const strings

Constructing SA3

Construction function

construct_u()

Conventions

C’s qsort() function

Data structures

lists

queues

vectors

Depth-first traversal

dequeue_pointer()

Divide-and-conquer algorithm

Divide-and-conquer approach

edge_length() function

Edit cloud

edits_to_cigar() function

enqueue_pointer()

enqueue_siblings()

equal3() function

Exact search

Aho-Corasick algorithm

borders

Boyer-Moore

SeeBoyer-Moore (BM) algorithm

BMH algorithm

extended rightmost table

KMP algorithm

Naïve algorithm

trie

SeeTries

fast_scan() function

find_buckets_beginnings()

find_buckets_ends()

find_outgoing_edge() function

find_rightmost() function

Global alignment

Graphical notation

Graphical string notation

Heap-allocating arrays

I, J

Input string

insert_child() function

Inverse suffix array (ISA)

is_trie_root()

Iterator initialization function

Iterator structure

Knuth-Morris-Pratt (KMP) algorithm

lcp_insert()

lcp_traverse()

Leaf iterators

Leftmost S (LMS) index

LEX3 alphabet

Li-Durbin algorithm

approximative matching iterator

BWT search

bwt_table data struct

CIGAR

D table

D_table variable

edit operations, build

edits_buf variable

increment iterator

L, R, and next_interval variables

O table, build

recursive search

reversed string

ro_table suffix array

suffix array

Linear algorithms

Lists

LMS strings

LMS substrings

Local alignment

Longest common prefix (LCP) array

array computations

branch lengths

constructing

traversal

lower_bound_search() function

malloc()

map_lex3() function

map_s_s12() function

map_u_s()

Match structure

McCreight’s algorithm

construct suffix trees

edge splitting

fast_scan()

general case of suffix search

head and suffix links

jumping

jump pointers

main function

mismatches

naive_insert()

path of suffix links

prefix matching

running time

slow scan (scan 2) time usage

suffix i

suffix links

suffix_search()

terminology and notation

uniqueness of suffix links

McCreight’s suffix tree construction algorithm

Memory-efficient algorithm

Memory reduction

allocating and deallocating buckets

bit array

bit array macros

bool array

buckets’ beginnings and ends

find_buckets_beginnings()

input string

reduced string

reduce_SA() function

sort_SA()

suffix array

UNDEFINED

merge_suffix_arrays() function

Merging arrays

m12 variable

N, O

Naïve algorithm, exact search

Naïve construction algorithm

edge splitting

find_outgoing_edge() function

insert_child()

naive_insert()

naive_suffix_tree() function

out_letter()

remove child

scanning

single-symbol strings

split_edge()

traverse tree

naive_insert() function

naïve sorting algorithm

naive_suffix_tree()

new_node() function

next_ac_match()

next_bmh_match()

next_bm_match()

next_st_leaf()

Notation

Parent pointer

Pattern

pattern_front pointer

Pattern-matching algorithm

Pivot element

pointer_queue data structure

pointer_queue_front()

pool variable

Prefix tree

Proper prefix

qsort() function

Queues

radix_sort() function

radix_sort_3()

range_length()

RAWKEY()

Reduced suffix array

reduce_SA() function

Remap function

remap_lex3() function

remap_LMS()

Remapping

REPORT() function

report_function

report_function_data

Restricted backward border arrays

Restricted border array

Restricted reversed border array

Reversed border array

Reversed pattern prefix

Reversed restricted border array

Reversed string

searching

Reversed Z array

reverse_push() function

Sorting sa12

sa_is_construction()

Sampling-induced sorting (SA-IS) algorithm.

Table of Contents for Back Matter

Create new playlist

Sign In

Sign Up

Table of Contents for
Back Matter