list.asm

; These affect the name of lists' length constants
def list_length_prefix equs "LENGTH_"
def list_length_suffix equs ""

; __list_length LIST, length
; 	For internal use only!
;
MACRO __list_length
	if def({list_length_prefix}\1{list_length_suffix})
		purge {list_length_prefix}\1{list_length_suffix}
	endc
	def {list_length_prefix}\1{list_length_suffix} equ \2
ENDM

; list LIST, items...
; 	Create a new list.
;
; \1: symbol - The list to create
; \2+: number... - The initial items, if any
;
; 	list SQUARES, 1, 4, 9
; 	assert LENGTH_SQUARES == 3
; 	assert SQUARES#2 == 4
;
; list_item items...
; 	Append items to the previously created list.
;
; \1+: number... - The items to append, if any
;
; 	list SQUARES
; 	list_item 1
; 	list_item 4, 9
; 	assert LENGTH_MONS == 3
; 	assert SQUARES#3 == 9
;
MACRO list
	assert !def({list_length_prefix}\1{list_length_suffix}), \
		"list: list \1 is already defined"
	__list_length \1, 0
	list_append \#
	redef list_item equs "list_append \1,"
ENDM

; list_print LIST
; 	Print a list.
;
; \1: symbol - The list to print
;
; 	list SQUARES, 1, 4, 9
; 	; Prints [$1, $4, $9]
; 	list_print SQUARES
;
MACRO list_print
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_print: list \1 is not defined"
	print "["
	for __i, 1, {list_length_prefix}\1{list_length_suffix} + 1
		if __i > 1
			print ", "
		endc
		print {\1#{d:__i}}
	endr
	purge __i
	print "]"
ENDM

; list_println LIST
; 	Print a list followed by a newline.
;
; \1: symbol - The list to print
;
; 	list SQUARES, 1, 4, 9
; 	; Prints [$1, $4, $9]
; 	list_println SQUARES
;
MACRO list_println
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_println: list \1 is not defined"
	list_print \1
	println
ENDM

; list_append LIST, items...
; 	Append items to a list.
;
; \1: symbol - The list to update
; \2+: number... - The items to append, if any
;
; 	list SQUARES
; 	list_append SQUARES, 1, 4, 9
; 	assert LENGTH_SQUARES == 3
; 	assert SQUARES#1 == 1
;
MACRO list_append
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_append: list \1 is not defined"
	def __n = {list_length_prefix}\1{list_length_suffix}
	for __i, 2, _NARG + 1
		def __j = __n + __i - 1
		def \1#{d:__j} equ \<__i>
		purge __j
	endr
	purge __i
	__list_length \1, __n + {_NARG} - 1
	purge __n
ENDM

; list_extend LIST1, LIST2
; 	Append items to a list from another.
;
; \1: symbol - The list to update
; \2: symbol - The list to append from
;
; 	list SQUARES, 1, 4, 9
; 	list MORESQUARES, 16, 25
; 	list_extend SQUARES, MORESQUARES
; 	assert LENGTH_SQUARES == 5
;
MACRO list_extend
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_extend: list \1 is not defined"
	assert def({list_length_prefix}\2{list_length_suffix}), \
		"list_extend: list \2 is not defined"
	for __i, 1, {list_length_prefix}\2{list_length_suffix} + 1
		list_append \1, {\2#{d:__i}}
	endr
	purge __i
ENDM

; list_copy LIST1, LIST2
; 	Create a new list as a copy of another list.
;
; \1: symbol - The list to create
; \2: symbol - The list to copy
;
; 	list SQUARES, 1, 4, 9
; 	list_copy DIMS, SQUARES
; 	; Prints [$1, $4, $9]
; 	list_print DIMS
;
MACRO list_copy
	assert !def({list_length_prefix}\1{list_length_suffix}), \
		"list_copy: list \1 is already defined"
	assert def({list_length_prefix}\2{list_length_suffix}), \
		"list_copy: list \2 is not defined"
	__list_length \1, {list_length_prefix}\2{list_length_suffix}
	for __i, 1, {list_length_prefix}\2{list_length_suffix} + 1
		def \1#{d:__i} equ {\2#{d:__i}}
	endr
	purge __i
ENDM

; list_clear LIST
; 	Clear a list.
;
; \1: symbol - The list to clear
;
; 	list SQUARES, 1, 4, 9
; 	list_clear SQUARES
; 	assert LENGTH_SQUARES == 0
;
MACRO list_clear
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_clear: list \1 is not defined"
	for __i, 1, {list_length_prefix}\1{list_length_suffix} + 1
		purge \1#{d:__i}
	endr
	purge __i
	__list_length \1, 0
ENDM

; list_purge LIST
; 	Purge a list.
;
; \1: symbol - The list to purge
;
; 	list SQUARES, 1, 4, 9
; 	list_purge SQUARES
; 	assert !DEF(LENGTH_SQUARES)
;
MACRO list_purge
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_purge: list \1 is not defined"
	list_clear \1
	purge {list_length_prefix}\1{list_length_suffix}
ENDM

; list_set LIST, index, item
; 	Set an index of a list to an item.
;
; \1: symbol - The list to update
; \2: number - The index to be set
; \3: number - The item to set
;
; 	list SQUARES, 1, 3, 9
; 	list_set SQUARES, 2, 4
; 	assert SQUARES#2 == 4
;
MACRO list_set
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_set: list \1 is not defined"
	def __idx = \2
	assert 1 <= __idx && __idx <= {list_length_prefix}\1{list_length_suffix}, \
		"list_set: invalid index for list \1: {d:__idx}"
	purge \1#{d:__idx}
	def \1#{d:__idx} equ \3
	purge __idx
ENDM

; list_insert LIST, index, item
; 	Insert an item into a list before an index.
;
; \1: symbol - The list to update
; \2: number - The index to insert before
; \3: number - The item to insert
;
; 	list SQUARES, 1, 9
; 	list_insert SQUARES, 2, 4
; 	assert SQUARES#2 == 4
;
MACRO list_insert
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_insert: list \1 is not defined"
	def __n = {list_length_prefix}\1{list_length_suffix}
	def __idx = \2
	assert 1 <= __idx && __idx <= __n, \
		"list_insert: invalid index for list \1: {d:__idx}"
	for __i, __n + 1, __idx, -1
		def __j = __i - 1
		def \1#{d:__i} equ {\1#{d:__j}}
		purge \1#{d:__j}, __j
	endr
	purge __i
	def \1#{d:__idx} equ \3
	purge __idx
	__list_length \1, __n + 1
	purge __n
ENDM

; list_delete LIST, index
; 	Delete an index from a list.
;
; \1: symbol - The list to update
; \2: number - The index to delete
;
; 	list SQUARES, 1, 4, 9
; 	list_delete SQUARES, 1
; 	assert LENGTH_SQUARES == 2
; 	assert SQUARES#1 == 4
;
MACRO list_delete
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_delete: list \1 is not defined"
	def __n = {list_length_prefix}\1{list_length_suffix}
	def __idx = \2
	assert 1 <= __idx && __idx <= __n, \
		"list_delete: invalid index for list \1: {d:__idx}"
	purge \1#{d:__idx}
	for __i, __idx, __n
		def __j = __i + 1
		def \1#{d:__i} equ {\1#{d:__j}}
		purge \1#{d:__j}, __j
	endr
	purge __i, __idx
	__list_length \1, __n - 1
	purge __n
ENDM

; list_find INDEX, LIST, item
; 	Find the first index of an item in a list.
;
; \1: symbol - The index to define
; \2: symbol - The list to use
; \3: number - The item to search for
;
; 	list SQUARES, 1, 4, 9
; 	list_find N, SQUARES, 4
; 	assert N == 2
; 	list_find N, SQUARES, 100
; 	assert N == 0
;
MACRO list_find
	assert def({list_length_prefix}\2{list_length_suffix}), \
		"list_find: list \2 is not defined"
	def \1 = 0
	for __i, 1, {list_length_prefix}\2{list_length_suffix} + 1
		if (\3) == {\2#{d:__i}}
			def \1 = __i
			break
		endc
	endr
	purge __i
ENDM

; list_rfind INDEX, LIST, item
; 	Find the last index of an item in a list.
;
; \1: symbol - The index to define
; \2: symbol - The list to use
; \3: number - The item to search for
;
; 	list VALUES, 6, 4, 6
; 	list_rfind N, VALUES, 6
; 	assert N == 3
;
MACRO list_rfind
	assert def({list_length_prefix}\2{list_length_suffix}), \
		"list_rfind: list \2 is not defined"
	def \1 = 0
	for __i, {list_length_prefix}\2{list_length_suffix}, 0, -1
		if (\3) == {\2#{d:__i}}
			def \1 = __i
			break
		endc
	endr
	purge __i
ENDM

; list_count NUM, LIST, item
; 	Count the occurrences of an item in a list.
;
; \1: symbol - The quantity to define
; \2: symbol - The list to use
; \3: number - The item to count
;
; 	list ROW, 1, 1, 2, 3, 1
; 	list_count N, ROW, 1
; 	assert N == 3
;
MACRO list_count
	assert def({list_length_prefix}\2{list_length_suffix}), \
		"list_count: list \2 is not defined"
	def \1 = 0
	for __i, 1, {list_length_prefix}\2{list_length_suffix} + 1
		if (\3) == {\2#{d:__i}}
			def \1 = \1 + 1
		endc
	endr
	purge __i
ENDM

; list_replace LIST, old, new
; 	Replace each occurrence of an item in a list.
;
; \1: symbol - The list to update
; \2: number - The old number to be replaced
; \3: number - The new number to replace with
;
; 	list VALUES, 6, 4, 6
; 	list_replace VALUES, 6, 3
; 	; Prints [$3, $4, $3]
; 	list_println VALUES
;
MACRO list_replace
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_replace: list \1 is not defined"
	for __i, 1, {list_length_prefix}\1{list_length_suffix} + 1
		if (\2) == {\1#{d:__i}}
			purge \1#{d:__i}
			def \1#{d:__i} equ \3
		endc
	endr
	purge __i
ENDM

; list_remove LIST, item
; 	Remove the first occurrence of an item in a list.
;
; \1: symbol - The list to update
; \2: number - The number to be removed
;
; 	list VALUES, 1, 2, 3, 1
; 	list_remove VALUES, 1
; 	; Prints [$2, $3, $1]
; 	list_println VALUES
;
MACRO list_remove
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_remove: list \1 is not defined"
	list_find ___idx\@, \1, \2
	if ___idx\@ > 0
		list_delete \1, ___idx\@
	endc
	purge ___idx\@
ENDM

; list_remove_all LIST, item
; 	Remove each occurrence of an item in a list.
;
; \1: symbol - The list to update
; \2: number - The number to be removed
;
; 	list VALUES, 1, 2, 3, 1
; 	list_remove_all VALUES, 1
; 	; Prints [$2, $3]
; 	list_println VALUES
;
MACRO list_remove_all
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_remove_all: list \1 is not defined"
	list_count ___num\@, \1, \2
	rept ___num\@
		list_remove \1, \2
	endr
	purge ___num\@
ENDM

; list_sort LIST
; 	Sort a list.
;
; \1: symbol - The list to sort
;
; 	list SQUARES, 4, 9, 1
; 	list_sort SQUARES
; 	; Prints [$1, $4, $9]
; 	list_println SQUARES
;
MACRO list_sort
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_sort: list \1 is not defined"
	def __n = {list_length_prefix}\1{list_length_suffix}
	for __p, ceil(log(__n << 16, 2.0)) >> 16
		def __w = 2 ** __p
		for __i, 1, __n + 1, 2 * __w
			if __i + __w > __n
				break
			endc
			def __l1 = __i
			def __r1 = __l1 + __w - 1
			def __l2 = __r1 + 1
			def __r2 = __l2 + __w - 1
			if __r2 > __n
				def __r2 = __n
			endc
			for __t, __n
				if __l1 > __r1 || __l2 > __r2
					break
				endc
				if {\1#{d:__l1}} <= {\1#{d:__l2}}
					def __tmp{d:__t} equ {\1#{d:__l1}}
					def __l1 = __l1 + 1
				else
					def __tmp{d:__t} equ {\1#{d:__l2}}
					def __l2 = __l2 + 1
				endc
			endr
			for __j, __l1, __r1 + 1
				def __tmp{d:__t} equ {\1#{d:__j}}
				def __t = __t + 1
			endr
			for __j, __l2, __r2 + 1
				def __tmp{d:__t} equ {\1#{d:__j}}
				def __t = __t + 1
			endr
			purge __l1, __r1, __l2, __r2
			for __j, __t
				def __k = __i + __j
				purge \1#{d:__k}
				def \1#{d:__k} equ {__tmp{d:__j}}
				purge __k, __tmp{d:__j}
			endr
			purge __j, __t
		endr
		purge __i, __w
	endr
	purge __p, __n
ENDM

; list_reverse LIST
; 	Reverse a list.
;
; \1: symbol - The list to reverse
;
; 	list SQUARES, 9, 4, 1
; 	list_reverse SQUARES
; 	; Prints [$1, $4, $9]
; 	list_println SQUARES
;
MACRO list_reverse
	assert def({list_length_prefix}\1{list_length_suffix}), \
		"list_reverse: list \1 is not defined"
	def __n = {list_length_prefix}\1{list_length_suffix}
	for __i, 1, __n / 2 + 1
		def __j = __n - __i + 1
		def __tmp equ {\1#{d:__i}}
		purge \1#{d:__i}
		def \1#{d:__i} equ {\1#{d:__j}}
		purge \1#{d:__j}
		def \1#{d:__j} equ {__tmp}
		purge __tmp, __j
	endr
	purge __i, __n
ENDM

	list SQUARES
	list_item 4
	list_item 9
	list_item 1
	list_sort SQUARES

	list_println SQUARES ; [$1, $4, $9]
	println LENGTH_SQUARES ; $3

	list_copy VALUES, SQUARES
	list_append VALUES, 10, 20

	list_println VALUES ; [$1, $4, $9, $A, $14]
	list_replace VALUES, 10, 11
	println VALUES#4 ; $B

	list SEQUENCE, 16, 25, 36
	list_delete VALUES, 4
	list_remove VALUES, 20
	list_extend VALUES, SEQUENCE
	list_purge SEQUENCE
	list_println VALUES ; [$1, $4, $9, $10, $19, $24]

	list_purge VALUES
	assert !DEF(LENGTH_VALUES)
	list VALUES, 11, 22, 22, 33, 22, 33
	list_find N, VALUES, 22
	println N ; $2
	list_rfind N, VALUES, 22
	println N ; $5
	list_count N, VALUES, 22
	println N ; $3
	list_remove_all VALUES, 22
	list_set VALUES, 2, 44
	list_insert VALUES, 3, 55
	list_reverse VALUES
	list_println VALUES ; [$21, $37, $2C, $B]