another linked list implementation

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
Mindless
Posts: 110
Joined: Jun 25, 2005 14:50
Location: USA

another linked list implementation

Post by Mindless »

Let me know what you think...

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
Last edited by Mindless on Oct 17, 2006 1:03, edited 5 times in total.
stylin
Posts: 1253
Joined: Nov 06, 2005 5:19

Post by stylin »

cool.
cha0s
Site Admin
Posts: 5319
Joined: May 27, 2005 6:42
Location: USA
Contact:

Post by cha0s »

i dunno, i don't want to discourage you, but something about this implementation... very hard for me to read. don't know why.
Mindless
Posts: 110
Joined: Jun 25, 2005 14:50
Location: USA

Post by Mindless »

cha0s wrote:i dunno, i don't want to discourage you, but something about this implementation... very hard for me to read. don't know why.
I replaced all instances of 'linked_list' with 'll' ... does that make it easier to read?
Sisophon2001
Posts: 1706
Joined: May 27, 2005 6:34
Location: Cambodia, Thailand, Lao, Ireland etc.
Contact:

Post by Sisophon2001 »

For me this is a big improvement. The variable names were so long the code was difficult to follow, I would look at even shortening the names a bit more.

Another thing I don't like is passing pointers by reference (the default in FB), but I don't know if it is just me, with by knowledge of C style codeing, or if other users feel the same.

But these are all style issues, and every programmer must adapt a little when reading others code.

Garvan
cha0s
Site Admin
Posts: 5319
Joined: May 27, 2005 6:42
Location: USA
Contact:

Post by cha0s »

yes, that does help a lot =)

personally, I love the ByRef default in fb. I think it makes things potentially much clearer.

To each, his own=)
stylin
Posts: 1253
Joined: Nov 06, 2005 5:19

Post by stylin »

Sisophon2001: I had a little difficulty reading the code as well. The use of namespaces typically improves readability of scoped code, which I would recommend here.

cha0s: I use 'option byval', only because I'm used to C++. I find that it's safer for me to assume I'm passing by value by default, since that's typically the situation, and I can see at a glance those args I pass by reference - so I can make sure to be careful about accidentally modifying them. If I'm making public code for a library, I'll specify both byval/byref in the param list, but I'll still use 'option byval' for safety. If/when FB supports constant reference params and classes, I think I might still use 'option byval', if not just because I'm used to it. :)
Mindless
Posts: 110
Joined: Jun 25, 2005 14:50
Location: USA

Post by Mindless »

namespaced, pointers now passed byval, shortened variable names, more comments
Mindless
Posts: 110
Joined: Jun 25, 2005 14:50
Location: USA

Post by Mindless »

yup, cha0s probably 1-up'ed me with his linked list, but I'm still working on mine... :D

anyway, i got rid of node_flags, so it's insignificantly faster now
Mindless
Posts: 110
Joined: Jun 25, 2005 14:50
Location: USA

a much simpler, less featured linked list

Post by Mindless »

linkedlist.bi

Code: Select all

namespace ll
  type node_t
    prev_node  as node_t ptr
    next_node  as node_t ptr
    foo        as any ptr
  end type
  
  declare function destroy( byval node_given as node_t ptr ) as node_t ptr
  declare function insert_after( byval node_given as node_t ptr ) as node_t ptr
  declare function remove( byval node_given as node_t ptr ) as node_t ptr
  declare function seek_first( byval node_given as node_t ptr ) as node_t ptr
  declare function count( byval node_given as node_t ptr ) as uinteger
  declare function dump( byval node_given as node_t ptr ) as uinteger
end namespace
linkedlist.bas

Code: Select all

#include "linkedlist.bi"

namespace ll
	
	function destroy( byval node_given as node_t ptr ) as node_t ptr
		dim as node_t ptr node_current = node_given
		
		if (node_given = 0) then return 0
		
		node_current = seek_first(node_current)
		
		do while (node_current->next_node)
			node_current = node_current->next_node
			deallocate(node_current->prev_node)
		loop
		
		deallocate(node_current)
		
		return 0
	end function
	
	function insert_after( byval node_given as node_t ptr ) as node_t ptr
		dim as node_t ptr node_new = callocate(sizeof(node_t))
		
		if (node_given = 0) then return node_new
		
		if (node_given->next_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
		
		return node_new
	end function
	
	function remove( byval node_given as node_t ptr ) as node_t ptr
		if (node_given = 0) then return 0
		
		dim as node_t ptr node_current
		
		if (node_given->prev_node = 0) and (node_given->next_node = 0) then
			node_current = 0
		elseif (node_given->prev_node = 0) then
			node_current = node_given->next_node
			node_given->next_node->prev_node = 0
		elseif (node_given->next_node = 0) then
			node_current = node_given->prev_node
			node_given->prev_node->next_node = 0
		else
			node_current = node_given->prev_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
	
	function seek_first( byval node_given as node_t ptr ) as node_t ptr
		if (node_given = 0) then return 0
		
		dim as node_t ptr node_current = node_given
		do while (node_current->prev_node)
			node_current = node_current->prev_node
		loop
		return node_current
	end function
	
	function count( byval node_given as node_t ptr ) as uinteger
		if node_given = 0 then return 0
		
		dim as node_t ptr node_current = node_given
		dim as uinteger ncount = 1
		
		node_current = seek_first(node_current)
		
		do while (node_current->next_node)
			node_current = node_current->next_node
			ncount += 1
		loop
		
		return ncount
	end function
	
	function dump ( byval node_given as node_t ptr ) as uinteger
		dim as node_t ptr node_current = node_given
		
		node_current = seek_first(node_current)
		
		print "node", "foo", "previous", "next"
		do while (node_current)
			print hex(node_current, 8), hex(node_current->foo, 8),
			if (node_current->prev_node) then
				print hex(node_current->prev_node, 8),;
			else
				print " -",;
			end If
			if (node_current->next_node) then
				print hex(node_current->next_node, 8)
			else
				print " -"
				exit do
			end if
			node_current = node_current->next_node
		loop
		
		return 0
	end function
	
end namespace

dim as ll.node_t ptr myll

for i as integer = 0 to 19
	myll = ll.insert_after(myll)
	myll->foo = i
	if i = 9 then myll = myll->prev_node
next
? ll.count(myll)

myll = ll.seek_first(myll)
myll = ll.remove(myll)
if myll then
	do
		print myll->foo
		if myll->next_node then
			myll = myll->next_node
		else
			exit do
		end if
	loop
end if

myll = ll.destroy( myll )

sleep
Post Reply