Code: Select all
option explicit
namespace ll
type node_t
index as integer
prev_node as node_t ptr
next_node as node_t ptr
foo as any ptr
end type
const as uinteger no_node = 0
declare function create (index as integer = 0) as node_t ptr
declare function destroy (byval node_given as node_t ptr) as node_t ptr
declare function insert_before (byval node_given as node_t ptr, index as integer = 0, avoid_duplicates as ubyte = 1) as node_t ptr
declare function insert_after (byval node_given as node_t ptr, index as integer = 0, avoid_duplicates as ubyte = 1) as node_t ptr
declare function delete (byval node_given as node_t ptr) as node_t ptr
declare function nswap (byval node_given1 as node_t ptr, byval node_given2 as node_t ptr) as ubyte
declare function seek_first (byval node_given as node_t ptr) as node_t ptr
declare function seek_last (byval node_given as node_t ptr) as node_t ptr
declare function seek_index (byval node_given as node_t ptr, index as integer = 0, nseek_first as ubyte = 1) as node_t ptr
declare function sort_index (byval node_given as node_t ptr) as ubyte
declare function rebuild_index (byval node_given as node_t ptr, start as integer = 0) as ubyte
declare function count (byval node_given as node_t ptr) as uinteger
declare function dump (byval node_given as node_t ptr) as ubyte
'' creates a linked list with one node with specified index
'' returns pointer to created node
function create (index as integer = 0) as node_t ptr
dim as node_t ptr node_new = callocate(sizeof(node_t))
node_new->index = index
return node_new
end function
'' destroys a linked list by deallocating all nodes
'' returns 0
function destroy (byval node_given as node_t ptr) as node_t ptr
dim as node_t ptr node_current = node_given
node_current = seek_first(node_current)
do until (node_current->next_node = no_node)
node_current = node_current->next_node
deallocate(node_current->prev_node)
loop
deallocate(node_current)
return no_node
end function
'' inserts a node before node_given with specified index
'' returns pointer to created node
function insert_before (byval node_given as node_t ptr, index as integer = 0, avoid_duplicates as ubyte = 1) as node_t ptr
if avoid_duplicates then
if seek_index(node_given, index) <> node_given or node_given->index = index then return node_given
end if
dim as node_t ptr node_new = callocate(sizeof(node_t))
if not(node_given->prev_node = no_node) then
node_new->prev_node = node_given->prev_node
node_given->prev_node->next_node = node_new
end if
node_given->prev_node = node_new
node_new->next_node = node_given
node_new->index = index
return node_new
end function
'' inserts a node after node_given with specified index
'' returns pointer to created node
function insert_after (byval node_given as node_t ptr, index as integer = 0, avoid_duplicates as ubyte = 1) as node_t ptr
if avoid_duplicates then
if (seek_index(node_given, index) <> node_given) or (node_given->index = index) then return node_given
end if
dim as node_t ptr node_new = callocate(sizeof(node_t))
if not(node_given->next_node = no_node) then
node_new->next_node = node_given->next_node
node_given->next_node->prev_node = node_new
end if
node_given->next_node = node_new
node_new->prev_node = node_given
node_new->index = index
return node_new
end function
'' removes node node_given
'' returns pointer to next node (or previous node if there is no next node)
function delete (byval node_given as node_t ptr) as node_t ptr
dim as node_t ptr node_current
if (node_given->prev_node = no_node) and (node_given->next_node = no_node) then
node_current = no_node
elseif (node_given->prev_node = no_node) then
node_current = node_given->next_node
node_given->next_node->prev_node = no_node
elseif (node_given->next_node = no_node) then
node_current = node_given->prev_node
node_given->prev_node->next_node = no_node
else
node_current = node_given->next_node
node_given->prev_node->next_node = node_given->next_node
node_given->next_node->prev_node = node_given->prev_node
end if
deallocate(node_given)
return node_current
end function
'' swaps the index and value of two node
'' returns 0
function nswap (byval node_given1 as node_t ptr, byval node_given2 as node_t ptr) as ubyte
swap node_given1->index, node_given2->index
swap node_given1->foo, node_given2->foo
return 0
end function
'' seeks to first node
'' returns pointer to first node
function seek_first (byval node_given as node_t ptr) as node_t ptr
dim as node_t ptr node_current = node_given
do until (node_current->prev_node = no_node)
node_current = node_current->prev_node
loop
return node_current
end function
'' seeks to last node
'' returns pointer to last node
function seek_last (byval node_given as node_t ptr) as node_t ptr
dim as node_t ptr node_current = node_given
do until (node_current->next_node = no_node)
node_current = node_current->next_node
loop
return node_current
end function
'' seeks node with specified index
'' returns pointer to node with index (or node_given if not found)
function seek_index (byval node_given as node_t ptr, index as integer = 0, nseek_first as ubyte = 1) as node_t ptr
dim as node_t ptr node_current = node_given
if nseek_first then node_current = seek_first(node_current)
do until node_current->index = index
if (node_current->next_node = no_node) then return node_given
node_current = node_current->next_node
loop
return node_current
end function
'' sorts nodes by index
'' returns 0
function sort_index (byval node_given as node_t ptr) as ubyte
dim as node_t ptr node_current = node_given
dim as node_t ptr node_grab, node_match
node_current = seek_first(node_current)
node_grab = node_current
do until (node_grab->next_node = no_node)
node_match = node_grab
node_current = node_grab
do until (node_current->next_node = no_node)
node_current = node_current->next_node
if (node_current->index < node_match->index) then node_match = node_current
loop
if (node_match <> node_grab) then nswap(node_match, node_grab)
node_grab = node_grab->next_node
loop
return 0
end function
'' renumbers the nodes based on order
'' returns 0
function rebuild_index (byval node_given as node_t ptr, start as integer = 0) as ubyte
dim as node_t ptr node_current = node_given
node_current = seek_first(node_current)
node_current->index = start
do until (node_current->next_node = no_node)
node_current = node_current->next_node
node_current->index = node_current->prev_node->index + 1
loop
return 0
end function
'' counts number of nodes in list
'' returns number of nodes counted
function count (byval node_given as node_t ptr) as uinteger
dim as node_t ptr node_current = node_given
dim as uinteger ncount = 1
node_current = seek_first(node_current)
do until (node_current->next_node = no_node)
node_current = node_current->next_node
ncount += 1
loop
return ncount
end function
'' lists nodes on screen
'' returns 0
function dump (byval node_given as node_t ptr) as ubyte
dim as node_t ptr node_current = node_given
node_current = seek_first(node_current)
print "index", "foo", "previous", "next"
do
print hex(node_current->index, 8), hex(node_current->foo, 8),;
if not(node_current->prev_node = no_node) then
print hex(node_current->prev_node->index, 8),;
else
print " -",;
end if
if not(node_current->next_node = no_node) then
print hex(node_current->next_node->index, 8)
else
print " -"
exit do
end if
node_current = node_current->next_node
loop
return 0
end function
end namespace
dim as integer i, j = 64
'' create linked list with one node (index 0 by default)
dim as ll.node_t ptr test_ll = ll.create()
'' create j nodes before current node
for i = 1 to j
test_ll = ll.insert_before(test_ll, -i)
next
'' create j nodes after current node
for i = 1 to j
test_ll = ll.insert_after(test_ll, i)
next
'' count nodes
print ll.count(test_ll)
'' swap j nodes
for i = 1 to j
ll.nswap(ll.seek_index(test_ll, -i), ll.seek_index(test_ll, i))
next
'' list nodes
ll.dump(test_ll)
'' sort nodes
ll.sort_index(test_ll)
'' list nodes
ll.dump(test_ll)
'' renumber nodes
ll.rebuild_index(test_ll)
'' seek to node with index j \ 2
test_ll = ll.seek_index(test_ll, j \ 2)
'' delete j nodes
for i = 1 to j
test_ll = ll.delete(test_ll)
next
'' destroy linked list
test_ll = ll.destroy(test_ll)
sleep