barlib.h File Reference

Data Structures
struct	_BARdesc
	The BARdesc object: a BAR (Beamed Array) descriptor. More...

Typedefs
typedef struct _BARdesc *	BARdesc
	The BARdesc object: a BAR (Beamed Array) descriptor. More...

Functions
BARdesc	BAR_new (int N, int M, int W)
	Creates a BAR whose matrix size is N-by-M, with beam width W. More...
void	BAR_reinit (BARdesc BAR, int N, int M, int W)
	Changes the size of a BAR (erasing the contents of the BAR). More...
void	BAR_delete (BARdesc BAR)
	Destroys a BARdesc object. More...
void	BAR_write (BARdesc BAR, int x, int y, int i)
	Sets an element of a BAR. More...
int	BAR_read (BARdesc BAR, int x, int y)
	Reads a single integer value from the specified cell of the matrix in a BAR. More...

Typedef Documentation

typedef struct _BARdesc * BARdesc

The BARdesc object: a BAR (Beamed Array) descriptor.

The Beamed Array Library implements storage for the kind of sparse matrix required by beam search methods in dynamic programming. A Beamed Array is a N-by-M matrix

 A(x,y) ;  x = 0 ... N-1, y = 0 ... M-1

of integer values, where each right/down diagonal

 d_k := { (x,y) | x + y = k }

contains a single contiguous block of at most W (potentially) nonzero elements. The position of this block on a given diagonal is determined by the first write access to that diagonal. It is assumed that the first element written is the leftmost one, i.e. setting A(x,y) = 1 will define the block on d_(x+y) to be

 {(x,y), (x+1,y-1), ... , (x+W-1, y+W-1)}

Well done if you understand that......

Function Documentation

void BAR_delete

(

BARdesc

BAR

)

Destroys a BARdesc object.

Parameters

BAR	Descriptor of the BAR to destroy.

References _BARdesc::d_block_data, _BARdesc::d_block_start_x, and _BARdesc::data.

Referenced by best_path().

BARdesc BAR_new	(	int	N,
		int	M,
		int	W
	)

Creates a BAR whose matrix size is N-by-M, with beam width W.

Parameters

N	First dimension size for the new matrix (see BARdesc).
M	Second dimension size for the new matrix (see BARdesc).
W	Beam width size for the new matrix (see BARdesc).

Returns

The new BARdesc object.

References _BARdesc::beam_width, _BARdesc::d_block_data, _BARdesc::d_block_start_x, _BARdesc::d_size, _BARdesc::data, _BARdesc::data_size, _BARdesc::vector_size, _BARdesc::x_size, and _BARdesc::y_size.

Referenced by best_path().

int BAR_read	(	BARdesc	BAR,
		int	x,
		int	y
	)

Reads a single integer value from the specified cell of the matrix in a BAR.

Usage:

i = A(x,y)

is expressed as

i = BAR_read(BAR, x, y);

Parameters

BAR	BAR descriptor: the matrix we want to read from.
x	matrix x coordinate of the value we want.
y	matrix y coordinate of the value we want.

Returns

the value of A(x,y); if (x,y) is outside the matrix or beam range, the function returns 0.

References _BARdesc::beam_width, _BARdesc::d_block_data, and _BARdesc::d_block_start_x.

Referenced by best_path().

void BAR_reinit	(	BARdesc	BAR,
		int	N,
		int	M,
		int	W
	)

Changes the size of a BAR (erasing the contents of the BAR).

This function must never be passed a NULL object.

See also

BARdesc

Parameters

BAR	The BAR to resize.
N	First dimension of the new size of matrix (see BARdesc).
M	Second dimension of the new size of matrix (see BARdesc).
W	Beam width of the new size of matrix (see BARdesc).

References _BARdesc::beam_width, _BARdesc::d_block_data, _BARdesc::d_block_start_x, _BARdesc::d_size, _BARdesc::data, _BARdesc::data_size, _BARdesc::vector_size, _BARdesc::x_size, and _BARdesc::y_size.

void BAR_write	(	BARdesc	BAR,
		int	x,
		int	y,
		int	i
	)

Sets an element of a BAR.

Usage:

BAR_write(BAR, x, y, i);

sets A(x,y) = i.

• if (x,y) is outside matrix or beam range, the function call is ignored.
• if d_(x+y) hasn't been accessed before, the block_start_x value is set to x.

Parameters

BAR	BAR descriptor: the matrix we want to write to.
x	matrix x coordinate of the cell we want to write in.
y	matrix y coordinate of the cell we want to write in.
i	value to set it to

References _BARdesc::beam_width, beam_width, _BARdesc::d_block_data, and _BARdesc::d_block_start_x.

Referenced by best_path().