' Program:  Link List Example Source Code
' Version:  0.01
' Language: FreeBASIC (v0.18.3b)
' Author:   Quinton Roberts (Eclipzer)
' Date:     04-16-08
' Update:   04-17-08
'
' Copyright (c) 2008.

type nodedat
  as string      id      'user-defined id for nodes
  as any     ptr dataptr 'pointer to node data
  as any     ptr listptr 'pointer to list (any pointer allows variable list types)
  as nodedat ptr nextptr 'pointer to next node
  as nodedat ptr prevptr 'pointer to previous node
  declare destructor()
end type

type listdat
  as ulongint     count   'list node count
  as nodedat  ptr nodeptr 'pointer to current node
  as nodedat  ptr front   'pointer to first node
  as nodedat  ptr last    'pointer to last node
  declare sub      append(byref nodeptr as nodedat ptr)
  declare sub      clear()
  declare sub      insert(byref nodeptr as nodedat ptr,index as ulongint=0)
  declare sub      move(byref source as nodedat ptr,target as ulongint)
  declare sub      move(source as ulongint,target as ulongint)
  declare sub      move(id as string,target as ulongint)
  declare function node_idx(nodeptr as nodedat ptr) as ulongint
  declare function node_idx(id as string) as ulongint
  declare function node_ptr(index as ulongint) as nodedat ptr
  declare function node_ptr(id as string) as nodedat ptr
  declare function remove(nodeptr as nodedat ptr) as nodedat ptr
  declare function remove(index as ulongint) as nodedat ptr
  declare function remove(id as string) as nodedat ptr
  declare destructor()
  declare sub print()
end type

declare function node_create(bytes as ulongint=0,id as string="") as nodedat ptr
declare sub      node_delete(byref nodeptr as nodedat ptr)

dim as listdat     myList
dim as nodedat ptr myNode

for i as integer=0 to 3
  myNode=node_create(0,"node"+str$(i+1))
  myList.append(myNode)
next

? "Generating initial list..."
?
? "List node count: "; myList.count
?
myList.print
sleep

dim as integer index1,index2

index1=2
myNode=node_create(0,"nodeX") 'create node X
myList.insert(myNode,index1)  '

?
? "Inserting "; myNode->id; " into list at index"; index1; "..."
?

? "List node count: "; myList.count

?
myList.print
sleep

?
myNode=myList.node_ptr("nodeX")
index1=myList.node_idx(myNode)
index2=4
? "moving "; myNode->id; " from index"; index1; " to index"; index2;"..."

myList.move(myNode,index2)

?
myList.print
sleep

?
? "Clearing list...":  myList.clear
? "List node count: "; myList.count
? "List cleared!!!"

sleep

' node destructor
destructor nodedat: node_delete(@this): end destructor

' =============================================================================
'          Name: node_create (04.16.08)
'       Returns: node pointer
'    Parameters:
'       [bytes]: bytes to allocate to node data pointer [0]
'          [id]: user-defined node ID [""]
' -----------------------------------------------------------------------------
'   Description: Creates a node in memory for subsequent insertion into a
'                linked list. If successful, returns a pointer to the node.
'      Comments: CALLOCATE() will set the node elements to zero (null pointers).
'                Node's data pointer is a null pointer if bytes = 0.
' =============================================================================
function node_create(bytes as ulongint,id as string) as nodedat ptr

  dim nodeptr as nodedat ptr      'create node pointer

  nodeptr=callocate(len(nodedat)) 'create empty node

  nodeptr->id=id     'store node ID
  nodeptr->listptr=0 'null list pointer
  nodeptr->prevptr=0 'null prev pointer
  nodeptr->nextptr=0 'null next pointer

  ' allocate cleared memory to node if requested bytes > 0
  if bytes then nodeptr->dataptr=callocate(bytes)

  return nodeptr

end function

' =============================================================================
'          Name: node_delete (04.16.08)
'       Returns:
'    Parameters:
'       nodeptr: pointer to node to delete from memory
' -----------------------------------------------------------------------------
'   Description: Deletes a node from memory.
'      Comments: Be certain to destroy all references to a node before deleting.
'                Node pointer is set to null after deallocating.
' =============================================================================
sub node_delete(byref nodeptr as nodedat ptr)
  if nodeptr then                  'if valid node pointer...
   if nodeptr->listptr then       'if attached to a list...
    cptr(listdat ptr,nodeptr->listptr)->remove(nodeptr) 'remove it!
   end if
   if nodeptr->dataptr then       'if valid data pointer...
    deallocate(nodeptr->dataptr) 'delete node data from memory
   end if
   deallocate(nodeptr)            'delete node from memory
   nodeptr=0                      'set null pointer
  end if
end sub

' list destructor
destructor listdat: this.clear: end destructor

' =============================================================================
'          Name: .append (04.16.08)
'       Returns:
'    Parameters:
'       nodeptr: pointer to node to append
'          list: list to append node to
' -----------------------------------------------------------------------------
'   Description: Add a node to the end of a linked list.
'      Comments:
' =============================================================================
sub listdat.append(byref nodeptr as nodedat ptr)

  if nodeptr=0 then return 'exit if node is a null pointer

  ' remove node from attached list before modifying it
  if nodeptr->listptr then
   cptr(listdat ptr,nodeptr->listptr)->remove(nodeptr)
  end if

  ' if the list contains nodes, we simply link the new node to the last node.
  ' otherwise we need to make the new node the first node and keep its pointer
  ' as the list pointer.
  if front then           'if nodes present...
   nodeptr->prevptr=last 'link new node to last node
   last->nextptr=nodeptr 'update rear node to point to new node
   last=nodeptr          'update rear pointer
  else                    'if list empty...
   nodeptr->prevptr=0    'front node has no prev node so make it a null pointer
   front=nodeptr         'update front pointer
   last =nodeptr         'update last pointer
  end if

  nodeptr->listptr=@this 'store list pointer with node
  nodeptr->nextptr=0     'end the list by making next pointer a null pointer

  count+=1 'update list node count

end sub

' =============================================================================
'          Name: .clear (04.16.08)
'       Returns:
'    Parameters:
' -----------------------------------------------------------------------------
'   Description: Remove and delete all nodes from a list.
'      Comments: The list is cleared by repeatedely removing the front node
'                until no nodes remain. Be certain to destroy all references to
'                list nodes before clearing the list.
' =============================================================================
sub listdat.clear()
  do while front
   node_delete(remove(front))
  loop
end sub

' =============================================================================
'          Name: .insert (04.16.08)
'       Returns:
'    Parameters:
'       nodeptr: pointer to node to insert
'         [idx]: index to insert into list [0]
' -----------------------------------------------------------------------------
'   Description: Insert node into list at specified index.
'      Comments: Insert front if index <= 0
'                Insert rear if index >= node count
' =============================================================================
sub listdat.insert(byref nodeptr as nodedat ptr,index as ulongint)

  if nodeptr=0 then return 'exit if node is a null pointer

  ' remove node from attached list before modifying it
  if nodeptr->listptr then
   cptr(listdat ptr,nodeptr->listptr)->remove(nodeptr)
  end if

  dim as ulongint nodeCount=1

  if front then 'if nodes present

   dim as nodedat ptr prev=0
   dim as nodedat ptr curr=front

   if index then
    do while curr
     if nodeCount=index then exit do 'index found!
     prev=curr
     curr=curr->nextptr
     nodeCount+=1
    loop
   end if

   if prev=0 then           'if front of list...
    nodeptr->prevptr=0     'point node prev to 0 (front node has no prev node)
    nodeptr->nextptr=front 'point node next to front node
    front->prevptr=nodeptr 'point front prev to node
    front=nodeptr          'make node the front node

   elseif curr=0 then       'if end of list
    nodeptr->nextptr=0     'point node next to 0 (last node has no next node)
    nodeptr->prevptr=last  'point node prev to last node
    last->nextptr=nodeptr  'point last next to node
    last=nodeptr           'make node the last node

   else                     'insert into list...
    nodeptr->prevptr=prev  'point node prev to prev
    nodeptr->nextptr=curr  'point node next to curr
    prev->nextptr=nodeptr  'point prev node to node
    curr->prevptr=nodeptr  'point curr node to node
   end if

  else                 'if no nodes in list...
   front=nodeptr      'point front to node
   last =nodeptr      'point last to node
   nodeptr->prevptr=0 'point node prev to 0 (front node has no prev node)
   nodeptr->nextptr=0 'point node next to 0 (last node has no next node)
  end if

  nodeptr->listptr=@this 'store list pointer with node
  count+=1               'update list count

end sub

' =============================================================================
'          Name: .move (04.16.08)
'       Returns:
'    Parameters: (source,target)
'        source: pointer, index or ID of node to remove
'        target: index to place removed node
' -----------------------------------------------------------------------------
'   Description: Reposition a node within a list, using a source node pointer,
'                index or ID and a target index. The node is first removed and
'                then it is reinserted into the list.
'      Comments: The source index must be within the list range in order for a
'                move to occur. If the target index is out of range, the node
'                will be placed in either the front or rear of the list.
' =============================================================================
sub listdat.move(byref source as nodedat ptr,target as ulongint)
  insert(remove(source),target) 'reinsert node into list
end sub

sub listdat.move(source as ulongint,target as ulongint)
  insert(remove(source),target) 'reinsert node into list
end sub

sub listdat.move(id as string,target as ulongint)
  insert(remove(id),target) 'reinsert node into list
end sub

' =============================================================================
'          Name: .node_idx (04.16.08)
'       Returns: node index
'    Parameters: (nodeptr)
'       nodeptr: node pointer of index to return
'            OR: (id)
'            id: node id of index to return
' -----------------------------------------------------------------------------
'   Description: Return the index of a node in a list using the node's pointer.
'      Comments: Return 0 if pointer is not in the list.
' =============================================================================
function listdat.node_idx(nodeptr as nodedat ptr) as ulongint

  dim as nodedat ptr curr=front 'create list pointer

  for index as ulongint = 1 to count
   if curr=nodeptr then return index
   curr=curr->nextptr
  next

  return 0

end function

function listdat.node_idx(id as string) as ulongint

  dim as nodedat ptr nodeptr=front 'create list pointer

  for index as ulongint = 1 to count
   if nodeptr->id=id then return index
   nodeptr=nodeptr->nextptr
  next

  return 0

end function

' =============================================================================
'          Name: .node_ptr (04.16.08)
'       Returns: node pointer
'    Parameters: (index)
'         index: index of node pointer to return
'            OR: (id)
'            id: ID of node pointer to return
' -----------------------------------------------------------------------------
'   Description: Return the pointer to a node at a specified list index. Return
'                a null pointer (0) if index out of range.
'      Comments: The first node in the list is index=1.
' =============================================================================
function listdat.node_ptr(index as ulongint) as nodedat ptr

  if index>count then return 0     'return null pointer if index out of range

  dim as ulongint    nodeCount=1
  dim as nodedat ptr nodeptr=front 'pointer to front of list

  do while nodeptr               'loop to find list node to remove
   if nodeCount=index then exit do
   nodeptr=nodeptr->nextptr  'traverse next node
   nodeCount+=1              'update node count
  loop

  return nodeptr

end function

function listdat.node_ptr(id as string) as nodedat ptr

  dim as nodedat ptr nodeptr=front 'pointer to front of list

  for i as integer = 0 to count-1
   if nodeptr->id=id then return nodeptr 'exit if ids match
   nodeptr=nodeptr->nextptr              'traverse next node
  next

  return 0

end function

' =============================================================================
'          Name: .remove (04.16.08)
'       Returns: pointer to removed node
'    Parameters:
'       nodeptr: pointer to node to remove
' -----------------------------------------------------------------------------
'   Description: Remove a node from a list using node's pointer.
'      Comments: Since each node contains a list pointer, they can properly
'                remove themselves from their assigned list. This prevents any
'                attempt to remove a node from a list that it does not belong
'                to.
' =============================================================================
function listdat.remove(nodeptr as nodedat ptr) as nodedat ptr

  if nodeptr=0        then return 0 'exit if node invalid

  dim as listdat ptr listptr: listptr=cptr(listdat ptr,nodeptr->listptr)

  if listptr <> @this then return 0 'exit if node not in list

  'first node has a prev pointer is always 0
  'last node next pointer is always 0
  'if a list only has 1 node then its prev and next pointers will both be 0

  if (nodeptr->prevptr=0) and (nodeptr->nextptr=0) then 'if single node...
   this.nodeptr=0
   front=0
   last=0
  elseif (nodeptr->prevptr=0) then 'if first node...
   front=nodeptr->nextptr
   if front then front->prevptr=0 'start list
  elseif (nodeptr->nextptr=0) then 'if last node...
   last=nodeptr->prevptr
   if last then last->nextptr=0   'end list
  else
   nodeptr->prevptr->nextptr = nodeptr->nextptr 'connect prev pointer with next pointer
   nodeptr->nextptr->prevptr = nodeptr->prevptr 'connect next pointer with prev pointer
  end if

  nodeptr->prevptr=0 'assign removed node a null prev pointer
  nodeptr->nextptr=0 'assign removed node a null next pointer
  nodeptr->listptr=0 'assign removed node a null list

  count-=1  'decrement list node count

  return nodeptr 'return node pointer

end function

' =============================================================================
'          Name: .remove (04.17.08)
'       Returns: pointer to removed node
'    Parameters:
'         index: index of node to remove (1=first node)
' -----------------------------------------------------------------------------
'   Description: Remove a node from a list at a specified index position and
'                return a pointer to it. Return a null pointer (0) if index
'                out of range.
'      Comments: The first node in the list is index=1.
' =============================================================================
function listdat.remove(index as ulongint) as nodedat ptr

  if (index=0) or (index>count) then return 0 'return null pointer if index out of range

  dim as ulongint    nodeCount=1
  dim as nodedat ptr nodeptr=front 'pointer to front of list

  do while nodeCount<index    'loop to find list node to remove
   if nodeptr=0 then exit do 'exit at end of list
   nodeptr=nodeptr->nextptr  'traverse next node
   nodeCount+=1              'update node count
  loop

  remove(nodeptr)

  return nodeptr 'return pointer to removed node

end function

function listdat.remove(id as string) as nodedat ptr

  dim as nodedat ptr nodeptr=front 'pointer to front of list

  do while nodeptr                 'loop while valid node
   if nodeptr->id=id then exit do 'exit loop if ID match found
   nodeptr=nodeptr->nextptr       'traverse next node
  loop

  remove(nodeptr) 'remove node

  return nodeptr  'return pointer to removed node

end function

sub listdat.print

  dim as nodedat ptr nodeptr

  nodeptr=front
  for i as integer=1 to count
   ? nodeptr->id
   nodeptr=nodeptr->nextptr
  next

end sub