Standard Library

Abbreviations

OOM: Out of Memory
OOB: Out of Bounds

Contents

collections/
math.dg
primes.dg
polynomial.dg
matrix.dg
ppm.dg
v2.dg

---

math.dg (extends math.h)

Name	Type	Runtime	Heap Use
sign	(int n) -> int	O(1)	-
ipow	(int base, uint power) -> int	O(power)	-
faculty	(uint n) -> uint	O(n)	-
max	(int a, int b) -> int	O(1)	-
min	(int a, int b) -> int	O(1)	-
gcd	(int a, int b) -> int	?	-
lcm	(int a, int b) -> int	?	-
fib	(uint64 n) -> uint64	O(n)	-
iseven	(int n) -> bool	O(1)	-
isodd	(int n) -> bool	O(1)	-

primes.dg

Name	Type	Runtime	Heap Use
isprime	(uint64 n) -> bool	O(n)	-
nprimes	(uint n) ~> [unit32]	O(n^2)	+O(n)

polynomial.dg

Name	Type	Runtime	Heap Use
poly_ctor	(uint n) -> Poly	O(1)	+O(n)
poly_dtor	(Poly p) ~> bool	O(1)	-O(n)
poly_parse	([char] str) ~> Poly	?	+O(n)
poly_scale_inplace	(Poly a, float f) -> Poly	O(n)	-
poly_add	(Poly a, Poly b) ~> Poly	O(n)	+O(n)
poly_sub	(Poly a, Poly b) ~> Poly	O(n)	+O(n)
poly_mul	(Poly a, Poly b) ~> Poly	O(n^2)	+O(n)
poly_deg	(Poly p) -> uint	O(n)	-
poly_print	(Poly p) ~> bool	O(n)	-
poly_eval	(Poly p, float x) -> float	O(n)	-
poly_derivative	(Poly p) ~> Poly	O(n)	+O(n)
poly_integral	(Poly p) ~> Poly	O(n)	+O(n)

matrix.dg

Name	Type	Runtime	Heap Use
matrix_ctor	(uint nrows, uint ncols) ~> Matrix	O(nrows)	+O(nrows*ncols)
matrix_dtor	(Matrix a) ~> bool	O(nrows)	-O(nrows*ncols)
matrix_add	(Matrix a, Matrix b) ~> Matrix	O(nrows*ncols)	+O(nrows*ncols)
matrix_sub	(Matrix a, Matrix b) ~> Matrix	O(nrows*ncols)	+O(nrows*ncols)
matrix_scale	(Matrix a, float r) ~> Matrix	O(nrows*ncols)	+O(nrows*ncols)
matrix_mul	(Matrix a, Matrix b) ~> Matrix	O(a.nrows*b.ncols*a.ncols)	+O(a.nrows*a.ncols)
matrix_submatrix	(Matrix a, uint row, uint col) ~> Matrix	O(a.nrows*a.ncols)	+O((a.nrows-1)*(a.ncols-1))
matrix_det	(Matrix a) ~> float	TODO	-
matrix_transpose	(Matrix a) ~> Matrix	O(nrows*ncols)	+O(nrows*ncols)
matrix_pow	(Matrix a, uint power) ~> Matrix	O(a.nrows*b.ncols*a.ncols*power)	+O(nrows*ncols)
matrix_identity	(uint n) ~> Matrix	O(n)	+O(n*n)

ppm.dg (simple i/o for PPM Image Format)

The Behavior in Exceptional Cases is different here.
The Subroutines which draw on the image will do bounds checking and simply not draw pixels out of bounds.

This is for convenience, So we can can also draw 'over' the edges, clipping what's outside the Image.

Still TODO:

• ppm_draw_rect_outline
• ppm_draw_circle_outline
• ppm_draw_ngon
• ppm_draw_ngon_outline
• ppm_draw_image (other ImagePPM)

Name	Type	Runtime	Heap Use
ppm_ctor	(uint width, uint height) ~> ImagePPM	O(width*height)	+O(width*height)
ppm_dtor	(ImagePPM image) ~> bool	O(1)	-O(width*height)
ppm_set_color	(ImagePPM image, uint8 red, uint8 green, uint8 blue) ~> bool	O(1)	-
ppm_draw_pixel	(ImagePPM image, uint row, uint col) ~> bool	O(1)	-
ppm_draw_line	(ImagePPM image, uint row1, uint col1, uint row2, uint col2) ~> bool	O(max(abs(row2 - row1), abs(col2 - col1)))	-
ppm_draw_rect	(ImagePPM image, uint row, uint col, uint width, uint height) ~> bool	O(width*height)	-
ppm_draw_circle	(ImagePPM image, uint row, uint col, uint radius) ~> bool	O(radius*radius)	-
ppm_pixel_read_red	(ImagePPM image, uint row, uint col) -> uint8	O(1)	-
ppm_pixel_read_green	(ImagePPM image, uint row, uint col) -> uint8	O(1)	-
ppm_pixel_read_blue	(ImagePPM image, uint row, uint col) -> uint8	O(1)	-
ppm_write	(ImagePPM image, [char] filename) ~> bool	O(width*height)	-
ppm_read	([char] filename) ~> ImagePPM	O(width*height)	+O(width*height)

v2.dg (simple 2-component float vector)

...

Name	Type	Runtime	Heap Use
v2_ctor	(float x1, float x2) ~> V2	O(1)	+O(1)
v2_dtor	(V2 v) ~> bool	O(1)	-O(1)
v2_copy	(V2 v) ~> V2
v2_add	(V2 a, V2 b) ~> bool
v2_sub	(V2 a, V2 b) ~> bool
v2_scale	(V2 a, float r) ~> bool
v2_dist	(V2 a, V2 b) -> float
v2_dist_manhattan	(V2 a, V2 b) -> float
v2_mag	(V2 v) -> float
v2_normalize	(V2 v) ~> bool