FreeBASIC's Official Forums
|
| View previous topic :: View next topic |
| Author |
Message |
|
|
 Posted: Oct 17, 2006 18:22 Post subject: Just Another Linked List... |
 |
|
i was playing with macros and overloaded functions and made another linked list implementation...
the approach i'we used here alows making lists of any data type (udts or scalar types) but you can't mix different types in one list, anyway here's the code:
jall.bas:
| Code:
|
|
'
' -------------------------------------------------
'
' JALL - Just Another Linked List
'
' by Aleksandar Ruzicic (admin@krcko.net)
'
' Feel free to use this if you like it, just:
' "give credit where credit is due" :)
'
' -------------------------------------------------
'
#ifndef __JALL_BAS__
#define __JALL_BAS__
Option Explicit
Declare Sub ListAdd Overload ()
Declare Sub ListRemove Overload ()
Declare Function ListItem Overload () As Byte
Declare Sub ListSet Overload ()
Declare Sub ListPush Overload ()
Declare Function ListPop Overload () As Byte
Declare Sub ListClear Overload ()
Declare Sub ListResizeItem Overload ()
Sub ListAdd(): End Sub
Sub ListRemove(): End Sub
Function ListItem() As Byte: Return 0: End Function
Sub ListSet(): End Sub
Sub ListPush(): End Sub
Function ListPop() As Byte: Return 0: End Function
Sub ListClear(): End Sub
Sub ListResizeItem(): End Sub
#Macro DefineListType( __TYPE__ )
#ifndef __JALL__LIST__TYPE__##__TYPE__##__DEFINED__
#define __JALL__LIST__TYPE__##__TYPE__##__DEFINED__
Type __TYPE__##ListItem
p_data As __TYPE__ Pointer
p_next As __TYPE__##ListItem Pointer
p_prev As __TYPE__##ListItem Pointer
End Type
Type __TYPE__##List
p_first As __TYPE__##ListItem Pointer
p_last As __TYPE__##ListItem Pointer
Count As Integer
End Type
Declare Sub ListAdd(Byref List As __TYPE__##List, Byref Item As __TYPE__)
Declare Sub ListRemove(ByRef List As __TYPE__##List, ByRef Index As Integer)
Declare Function ListItem(Byref List As __TYPE__##List, Index As Integer) As __TYPE__
Declare Sub ListSet(Byref List As __TYPE__##List, Index As Integer, Byref Item As __TYPE__)
Declare Sub ListPush(Byref List As __TYPE__##List, Byref Item As __TYPE__)
Declare Function ListPop(Byref List As __TYPE__##List) As __TYPE__
Declare Sub ListClear(Byref List As __TYPE__##List)
Declare Sub ListResizeItem(Byref List As __TYPE__##List, Index As Integer, Item As __TYPE__)
Sub ListAdd(Byref List As __TYPE__##List, Byref Item As __TYPE__)
Dim tmp As __TYPE__##ListItem Pointer
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(__TYPE__))
*tmp->p_data = Item
List.Count += 1
If List.p_first = 0 Then
List.p_first = tmp
List.p_last = tmp
Else
tmp->p_prev = List.p_last
List.p_last->p_next = tmp
List.p_last = tmp
End If
End Sub
Sub ListRemove(ByRef List As __TYPE__##List, ByRef Index As Integer)
If Index > 0 And Index <= List.Count Then
Dim As __TYPE__##ListItem Pointer item = List.p_first, nextItem, prevItem
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
nextItem = item->p_next
prevItem = item->p_prev
If nextItem <> 0 Then nextItem->p_prev = prevItem
If prevItem <> 0 Then prevItem->p_next = nextItem
If List.p_first = item Then List.p_first = nextItem
If List.p_last = item Then List.p_last = prevItem
Deallocate(item->p_data)
Deallocate(item)
List.Count -= 1
End If
End Sub
Function ListItem(Byref List As __TYPE__##List, Index As Integer) As __TYPE__
If Index > 0 And Index <= List.Count Then
Dim As __TYPE__##ListItem Pointer item = List.p_first
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
Return *item->p_data
End If
End Function
Sub ListSet(Byref List As __TYPE__##List, Index As Integer, Byref Item As __TYPE__)
If Index > 0 And Index <= List.Count Then
Dim As __TYPE__##ListItem Pointer tmp = List.p_first
Dim i As Integer
For i = 1 To Index - 1
tmp = tmp->p_next
Next
*tmp->p_data = Item
End If
End Sub
Sub ListPush(Byref List As __TYPE__##List, Byref Item As __TYPE__)
Dim As __TYPE__##ListItem Pointer tmp, nextItem
List.Count += 1
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(__TYPE__))
*tmp->p_data = Item
nextItem = List.p_first
List.p_first = tmp
If nextItem <> 0 Then
nextItem->p_prev = tmp
List.p_first->p_next = nextItem
Else
List.p_last = tmp
End If
End Sub
Function ListPop(Byref List As __TYPE__##List) As __TYPE__
If List.Count > 0 Then
Dim As __TYPE__ Result = ListItem(List, List.Count)
ListRemove(List, List.Count)
Return Result
End If
End Function
Sub ListClear(Byref List As __TYPE__##List)
If List.Count > 0 Then
Dim As __TYPE__##ListItem Pointer item1, item2
item1 = List.p_first
While item1 <> 0
item2 = item1
item1 = item1->p_next
Deallocate(item2->p_data)
Deallocate(item2)
Wend
List.Count = 0
End If
End Sub
Sub ListResizeItem(Byref List As __TYPE__##List, Index As Integer, Item As __TYPE__)
If Index > 0 And Index <= List.Count Then
Dim As __TYPE__##ListItem Pointer tmp = List.p_first
Dim i As Integer
For i = 1 To Index - 1
tmp = tmp->p_next
Next
tmp->p_data = Reallocate(tmp->p_data, Len(Item))
*tmp->p_data = Item
End If
End Sub
#endif
#EndMacro
#endif
|
test.bas:
| Code:
|
|
#include "jall.bas"
Type UDT
i As Integer
d As Double
End Type
Dim i As Integer ' counter in loops
Dim u As UDT ' used in debugUDT macro
#Macro debugList(__lst__)
Print #__lst__; " items:"
For i = 1 To __lst__.Count
Print i; ": "; ListItem(__lst__, i)
Next
Print ""
#EndMacro
#Macro debugUDT(__lst__)
Print #__lst__; " items:"
For i = 1 To __lst__.Count
u = ListItem(__lst__, i)
Print i; ": "; u.i; ", "; u.d
Next
Print ""
#EndMacro
DefineListType(Integer) ' define IntegerList
DefineListType(String) ' define StringList
DefineListType(UDT) ' define UDTList
' declare lists
Dim list1 As IntegerList
Dim list2 As StringList
Dim list3 As UDTList
' declare some variables
Dim v1 As Integer
Dim v2 As String
Dim v3 As UDT
''' integer list '''
' adding integers to list1
For i = 0 To 19
ListAdd(list1, i)
Next
debugList(list1)
' clear list1
ListClear(list1)
v1 = 42
' push some data into list1
ListPush(list1, 1)
ListPush(list1, 10)
ListPush(list1, v1)
ListPush(list1, 88)
debugList(list1)
v1 = 18 ' change variable's value
debugList(list1) ' nothing changed!
' change value of list item with index 2
ListSet(list1, 2, 18)
debugList(list1)
' remove item with index 3
ListRemove(list1, 3)
debugList(list1)
' pop value
Print "popped: "; ListPop(list1)
Print
debugList(list1)
''' string list '''
' fill list2 with some values:
v2 = "blah"
ListPush(list2, "foo")
ListPush(list2, v2)
ListPush(list2, "bar")
debugList(list2)
v2 = "this is changed"
debugList(list2)
ListResizeItem(list2, 2, "this is changed") ' safer to use than ListSet (when working with strings), i think
debugList(list2)
For i = 1 To list2.Count
Print "popped: "; ListPop(list2)
Next
Print
ListAdd(list2, "item1")
ListAdd(list2, "item2")
ListAdd(list2, "item3")
debugList(list2)
ListAdd(list2, "added")
ListPush(list2, "pushed")
debugList(list2)
''' udt list '''
ListAdd(list3, Type<UDT>(1, 0.5))
ListAdd(list3, Type<UDT>(0, 3.14))
ListAdd(list3, Type<UDT>(123, 48.58565))
ListAdd(list3, Type<UDT>(448, 45680.5654))
debugUDT(list3)
v3.i = 20
v3.d = 5.6987
ListPush(list3, v3)
debugUDT(list3)
v3.i = 345
debugUDT(list3)
ListSet(list3, 1, Type<UDT>(345, 5.6987))
debugUDT(list3)
Sleep
|
i've tested this with 0.17b testing july/30 version...
p.s. i'm still learning fb... |
| |
|
| Back to top |
|
 |
|
|
| Posted: Oct 18, 2006 12:17 Post subject: |
|
|
| Nice Job. Doubly Linked list, eh? I tried to do a single but couldn't figure out how to safely remove a node. You have done better than I did. May I *barrow* this for learning purposes? |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 18, 2006 13:58 Post subject: |
|
|
| Imortis wrote: | | Nice Job. Doubly Linked list, eh? I tried to do a single but couldn't figure out how to safely remove a node. You have done better than I did. May I *barrow* this for learning purposes? |
wrote this on top of my head, so this may not be sound.
| Code:
|
|
temp = current->next
temp2 = current
current = current->prev
current ->next = temp
deallocate temp2
|
|
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 18, 2006 14:54 Post subject: |
|
|
| Imortis wrote: | | Nice Job. Doubly Linked list, eh? I tried to do a single but couldn't figure out how to safely remove a node. You have done better than I did. May I *barrow* this for learning purposes? |
thanks, offcourse you can *barrow* the code :) that's way i posted it, so others can use it and/or learn something from it (i'm begginer in fb and i've wrote this just to learn some new things like pointers and alloc/dealloc stuff...)
about single linked lists, maybe something like this will do when removing of node is needed (not tested):
| Code:
|
|
Type SLLItem
p_data As Any Pointer
p_next As SLLItem Pointer
End Type
Type SLL
p_root As SLLItem Pointer
Count As Integer
End Type
Sub ListRemove(ByRef List As SLL, Index As Integer)
If Index > 0 And Index <= List.Count Then
Dim i As Integer
Dim As SLLItem Pointer node = List.p_root, prev
For i = 1 To Index - 1
prev = node
node = node->p_next
Next
prev->p_next = node->p_next
' deallocate node->p_data if needed
Deallocate(node)
End If
End Sub
|
|
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 18, 2006 20:37 Post subject: |
|
|
i've downloaded latest version from cvs and played with new features...
and this is what i've made of JALL (it's YALL now :D):
yall.bas:
| Code:
|
|
'
' -------------------------------------------------------------------------
'
' YALL - Yet Another Linked List
'
' by Aleksandar Ruzicic (admin@krcko.net)
'
' Feel free to use this if you like it, just:
' "give credit where credit is due" :)
'
' -------------------------------------------------------------------------
'
' Usage:
'
' #include "yall.bas"
'
'
' defineListType(String) ' StringList data type is now available
'
' Dim list As StringList
'
' list.add("item 1")
' list.add("item 2")
' list.add("item 3")
'
' ...
'
' Properties:
'
' <DataTypeList>.Count As Integer
' - returns length of list (number of items)
'
'
' Methods:
'
' Sub <DataTypeList>.Add(ByRef Item As <DataType>)
' - adds item to the end of list
'
' Sub <DataTypeList>.Remove(Index As Integer)
' - removes item at Index position
'
' Function <DataTypeList>.GetItem(Index As Integer) As <DataType>
' - returns item from Index position
'
' Sub <DataTypeList>.Set(Index As Integer, Item As <DataType>)
' - changes value of item at Index position
'
' Sub <DataTypeList>.Push(ByRef Item As <DataType>)
' - adds item to the top of list
'
' Function <DataTypeList>.Pop() As <DataType>
' - returns value of the item from the top of the list, and removes it
'
' Function <DataTypeList>.PopBack() As <DataType>
' - returns value of the item from the bottom of the list, and removes it
'
' Sub <DataTypeList>.Clear()
' - removes all items from the list
'
' Sub <DataTypeList>.ResizeItem(Index As Integer, Item As <DataType>)
' - changes value of the item as Index position and Reallocates memory
' needed to store item value (recomended to use with dynamic-length
' strings, instead of .Set)
' -------------------------------------------------------------------------
#ifndef __YALL_BAS__
#define __YALL_BAS__
#macro DefineListType( __TYPE__ )
#ifndef __YALL__LIST__TYPE__##__TYPE__##__DEFINED__
#define __YALL__LIST__TYPE__##__TYPE__##__DEFINED__
Type __TYPE__##ListItem
p_data As __TYPE__ Pointer
p_next As __TYPE__##ListItem Pointer
p_prev As __TYPE__##ListItem Pointer
End Type
Type __TYPE__##List
p_first As __TYPE__##ListItem Pointer
p_last As __TYPE__##ListItem Pointer
Count As Integer
Declare Sub Add(Byref Item As __TYPE__)
Declare Sub Remove(ByRef Index As Integer)
Declare Function GetItem(Index As Integer) As __TYPE__
Declare Sub Set(Index As Integer, Byref Item As __TYPE__)
Declare Sub Push(Byref Item As __TYPE__)
Declare Function Pop() As __TYPE__
Declare Function PopBack() As __TYPE__
Declare Sub Clear()
Declare Sub ResizeItem(Index As Integer, Item As __TYPE__)
End Type
Sub __TYPE__##List.Add(Byref newItem As __TYPE__)
Dim tmp As __TYPE__##ListItem Pointer
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(__TYPE__))
*tmp->p_data = newItem
This.Count += 1
If This.p_first = 0 Then
This.p_first = tmp
This.p_last = tmp
Else
tmp->p_prev = This.p_last
This.p_last->p_next = tmp
This.p_last = tmp
End If
End Sub
Sub __TYPE__##List.Remove(ByRef Index As Integer)
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer item = This.p_first, nextItem, prevItem
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
nextItem = item->p_next
prevItem = item->p_prev
If nextItem <> 0 Then nextItem->p_prev = prevItem
If prevItem <> 0 Then prevItem->p_next = nextItem
If This.p_first = item Then This.p_first = nextItem
If This.p_last = item Then This.p_last = prevItem
Deallocate(item->p_data)
Deallocate(item)
This.Count -= 1
End If
End Sub
Function __TYPE__##List.GetItem(Index As Integer) As __TYPE__
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer item = This.p_first
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
Return *item->p_data
End If
End Function
Sub __TYPE__##List.Set(Index As Integer, Byref Item As __TYPE__)
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer tmp = This.p_first
Dim i As Integer
For i = 1 To Index - 1
tmp = tmp->p_next
Next
*tmp->p_data = Item
End If
End Sub
Sub __TYPE__##List.Push(Byref Item As __TYPE__)
Dim As __TYPE__##ListItem Pointer tmp, nextItem
This.Count += 1
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(__TYPE__))
*tmp->p_data = Item
nextItem = This.p_first
This.p_first = tmp
If nextItem <> 0 Then
nextItem->p_prev = tmp
This.p_first->p_next = nextItem
Else
This.p_last = tmp
End If
End Sub
Function __TYPE__##List.Pop() As __TYPE__
If This.Count > 0 Then
Dim As __TYPE__ Result
Dim As __TYPE__##ListItem Pointer nextItem
Result = *This.p_first->p_data
nextItem = This.p_first->p_next
Deallocate(This.p_first->p_data)
Deallocate(This.p_first)
This.p_first = nextItem
This.p_first->p_prev = 0
This.Count -= 1
Return Result
End If
End Function
Function __TYPE__##List.PopBack() As __TYPE__
If This.Count > 0 Then
Dim As __TYPE__ Result
Dim As __TYPE__##ListItem Pointer prev
Result = *This.p_last->p_data
prev = This.p_last->p_prev
Deallocate(This.p_last->p_data)
Deallocate(This.p_last)
This.p_last = prev
This.p_last->p_next = 0
This.Count -= 1
Return Result
End If
End Function
Sub __TYPE__##List.Clear()
If This.Count > 0 Then
Dim As __TYPE__##ListItem Pointer item1, item2
item1 = This.p_first
While item1 <> 0
item2 = item1
item1 = item1->p_next
Deallocate(item2->p_data)
Deallocate(item2)
Wend
This.Count = 0
End If
End Sub
Sub __TYPE__##List.ResizeItem(Index As Integer, Item As __TYPE__)
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer tmp = This.p_first
Dim i As Integer
For i = 1 To Index - 1
tmp = tmp->p_next
Next
tmp->p_data = Reallocate(tmp->p_data, Len(Item))
*tmp->p_data = Item
End If
End Sub
#endif
#endmacro
#endif
|
and simple test:
| Code:
|
|
#include "yall.bas"
Dim i As Integer
#macro debug(__list__)
For i = 1 To __list__.Count
Print i; ": "; __list__.GetItem(i)
Next
Print ""
#endmacro
defineListType(String)
Dim As StringList test
test.push "foo"
test.push "blah blah blah"
test.push "bar"
debug(test)
test.push "pushed"
test.add "added"
debug(test)
Print "popped: "; test.pop
Print
Print "back-popped: "; test.popback
Print
debug(test)
test.Remove 2
debug(test)
test.set 1, "foo"
test.set 2, "bar"
debug(test)
test.clear
Sleep
|
|
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 19, 2006 22:07 Post subject: |
|
|
I get the following errors:
| Code:
|
|
C:\FreeBASIC\FB_17>fbc testyall.bas
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Function'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Function'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Function'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : Error 18: Syntax Error, found: 'Sub'
DefineListType(String)
^
testyall.bas(15) : warning level 0: Implicit variable allocation, This.p_first
testyall.bas(15) : warning level 0: Implicit conversion
testyall.bas(15) : warning level 0: Implicit conversion
testyall.bas(15) : warning level 0: Suspicious Pointer assignment
testyall.bas(15) : Error 30: Expected Pointer, before: '->'
DefineListType(String)
^
testyall.bas(15) : Error 120: Too many errors, exiting
C:\FreeBASIC\FB_17>
|
Last edited by gedumer on Oct 25, 2006 0:24; edited 1 time in total |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 19, 2006 22:13 Post subject: |
|
|
you must have latest version from CVS... if you have it then i dunno why you're getting errors (i'm not)...
what's the code in testyall.bas? |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 19, 2006 22:26 Post subject: |
|
|
| I just copied your code from YALL above. I didn't download the CVS. I used whatever Victor has on the site for Windows (17b I think). |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 19, 2006 22:34 Post subject: |
|
|
| BTW... it works with JALL but not with YALL. |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 20, 2006 1:11 Post subject: |
|
|
| OK... I downloaded Pritchard's latest CVS build and it's works fine. |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 20, 2006 2:12 Post subject: |
|
|
I added the JALL test program to the YALL test program and it works fine.
I'd like to see the following function/sub's added:
GetFirst() - first in list
GetLast() - last in list
Find(value)
GetNext() - from the current record pointer
GetPrior() - from the current record pointer
Insert(index)
PopFirst - instead of Pop
PopLast - instead of PopBack
|
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 20, 2006 21:13 Post subject: |
|
|
ok, i've changed it a bit..
Macros:
DefineListType(Type)
- defines new list type
DefineDynamicListType(Type)
- same as DefineListType but when .Set is called, data pointer is reallocated.
this should be used with dynamic length types (strings)
Properties:
Count As Integer
- returns length of list (number of items)
Position As Integer
- returns current position
Methods:
Add(ByRef Item As <type>)
- adds item to the end of list
Remove(ByRef Index As Integer)
- removes item at Index position
GetItem(Index As Integer) As <type>
- returns item from Index position
Set(Index As Integer, ByRef Item As <type>)
- changes value of item at Index position
Push(ByRef Item As <type>)
- adds item to the top of list
Pop() As <type>
- returns value of the item from the top of the list, and removes it
PopFirst() As <type>
- alias of Pop
PopLast() As <type>
- returns value of the item from the bottom of the list, and removes it
Clear()
- removes all items from the list
Resize(Value As Integer)
- resizes list (expands or truncates list)
Current() As <type>
- returns item at current position
MoveNext()
- moves to the next item in the list (incerments current position)
MovePrevious()
- moves to the previous item in the list (decrements current position)
MoveFirst()
- moves to the first item in the list (sets current position to 1)
MoveLast()
- moves to the last item in the list (sets current position to .Count)
EOF() As Byte
- returns 1 if current position is out of bounds (0 otherwise)
Insert(ByRef Item As <type>, Index As Integer = 0)
- inserts new item at Index position, if Index is not specified, value is inserted at current position
"yall.bas"
| Code:
|
|
'
' -------------------------------------------------------------------------
'
' YALL - Yet Another Linked List
'
' by Aleksandar Ruzicic (admin@krcko.net)
'
' Feel free to use this if you like it, just:
' "give credit where credit is due" :)
'
' -------------------------------------------------------------------------
# ifndef __YALL_BAS__
# Define __YALL_BAS__
# macro DefineListType( __TYPE__ )
# ifndef __YALL__LIST__TYPE__##__TYPE__##__DEFINED__
# Define __YALL__LIST__TYPE__##__TYPE__##__DEFINED__
Type __TYPE__##ListItem
p_data As __TYPE__ Pointer
p_next As __TYPE__##ListItem Pointer
p_prev As __TYPE__##ListItem Pointer
End Type
Type __TYPE__##List
p_first As __TYPE__##ListItem Pointer
p_last As __TYPE__##ListItem Pointer
p_cur As __TYPE__##ListItem Pointer
Count As Integer
Position As Integer
Declare Sub Add(Byref Item As __TYPE__)
Declare Sub Remove(ByRef Index As Integer)
Declare Function GetItem(Index As Integer) As __TYPE__
Declare Sub Set(Index As Integer, Byref Item As __TYPE__)
Declare Sub Push(Byref Item As __TYPE__)
Declare Function Pop() As __TYPE__
Declare Function PopFirst() As __TYPE__
Declare Function PopLast() As __TYPE__
Declare Sub Clear()
Declare Sub Resize(Value As Integer)
Declare Function Current() As __TYPE__
Declare Sub MoveNext()
Declare Sub MovePrevious()
Declare Sub MoveFirst()
Declare Sub MoveLast()
Declare Function Eof() As Byte
Declare Sub Insert(Byref Item As __TYPE__, Index As Integer = 0)
Declare Destructor()
End Type
Sub __TYPE__##List.Add(Byref newItem As __TYPE__)
Dim tmp As __TYPE__##ListItem Pointer
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(newItem))
*tmp->p_data = newItem
This.Count += 1
If This.p_first = 0 Then
This.p_first = tmp
This.p_last = tmp
This.p_cur = tmp
Else
tmp->p_prev = This.p_last
This.p_last->p_next = tmp
This.p_last = tmp
End If
End Sub
Sub __TYPE__##List.Remove(ByRef Index As Integer)
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer item = This.p_first, nextItem, prevItem
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
nextItem = item->p_next
prevItem = item->p_prev
If nextItem <> 0 Then nextItem->p_prev = prevItem
If prevItem <> 0 Then prevItem->p_next = nextItem
If This.p_first = item Then This.p_first = nextItem
If This.p_last = item Then This.p_last = prevItem
Deallocate(item->p_data)
Deallocate(item)
This.Count -= 1
End If
End Sub
Function __TYPE__##List.GetItem(Index As Integer) As __TYPE__
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer item = This.p_first
Dim i As Integer
For i = 1 To Index - 1
item = item->p_next
Next
Return *item->p_data
End If
End Function
Sub __TYPE__##List.Set(Index As Integer, Byref Item As __TYPE__)
If Index > 0 And Index <= This.Count Then
Dim As __TYPE__##ListItem Pointer tmp = This.p_first
Dim i As Integer
For i = 1 To Index - 1
tmp = tmp->p_next
Next
# ifdef __YALL__LIST__TYPE__##__TYPE__##__DYNAMIC__
tmp->p_data = Reallocate(tmp->p_data, Len(Item))
# Endif
*tmp->p_data = Item
End If
End Sub
Sub __TYPE__##List.Push(Byref Item As __TYPE__)
Dim As __TYPE__##ListItem Pointer tmp, nextItem
This.Count += 1
tmp = Callocate(Len(__TYPE__##ListItem))
tmp->p_data = Callocate(Len(__TYPE__))
*tmp->p_data = Item
nextItem = This.p_first
This.p_first = tmp
If nextItem <> 0 Then
nextItem->p_prev = tmp
This.p_first->p_next = nextItem
Else
This.p_last = tmp
End If
End Sub
Function __TYPE__##List.Pop() As __TYPE__
If This.Count > 0 Then
Dim As __TYPE__ Result
Dim As __TYPE__##ListItem Pointer nextItem
Result = *This.p_first->p_data
nextItem = This.p_first->p_next
Deallocate(This.p_first->p_data)
Deallocate(This.p_first)
This.p_first = nextItem
This.p_first->p_prev = 0
This.Count -= 1
Return Result
End If
End Function
Function __TYPE__##List.PopFirst() As __TYPE__
Return This.Pop
End Function
Function __TYPE__##List.PopLast() As __TYPE__
If This.Count > 0 Then
Dim As __TYPE__ Result
Dim As __TYPE__##ListItem Pointer prev
Result = *This.p_last->p_data
prev = This.p_last->p_prev
Deallocate(This.p_last->p_data)
Deallocate(This.p_last)
This.p_last = prev
This.p_last->p_next = 0
This.Count -= 1
Return Result
End If
End Function
Sub __TYPE__##List.Clear()
If This.Count > 0 Then
Dim As __TYPE__##ListItem Pointer item1, item2
item1 = This.p_first
While item1 <> 0
item2 = item1
item1 = item1->p_next
Deallocate(item2->p_data)
Deallocate(item2)
Wend
This.Count = 0
End If
End Sub
Sub __TYPE__##List.Resize(Value As Integer)
If Value < 1 Then
This.Clear
Else
Dim dummy As __TYPE__
Dim i As Integer
If Value < This.Count Then
For i = Value To This.Count - 1
dummy = This.PopLast
Next
Else
Dim As Integer from = This.Count
For i = from To Value - 1
This.Add(dummy)
Next
End If
End If
End Sub
Function __TYPE__##List.Current() As __TYPE__
If This.p_cur <> 0 Then
If This.p_cur->p_data <> 0 Then Return *This.p_cur->p_data
End If
End Function
Sub __TYPE__##List.MoveNext()
If This.p_cur <> 0 Then
This.p_cur = This.p_cur->p_next
This.Position += 1
End If
End Sub
Sub __TYPE__##List.MovePrevious()
If This.p_cur <> 0 Then
This.p_cur = This.p_cur->p_prev
This.Position -= 1
End If
End Sub
Sub __TYPE__##List.MoveFirst()
This.p_cur = This.p_first
This.Position = 1
End Sub
Sub __TYPE__##List.MoveLast()
This.p_cur = This.p_last
This.Position = This.Count
End Sub
Function __TYPE__##List.EOF() As Byte
If This.p_cur <> 0 Then Return 0
Return 1
End Function
Sub __TYPE__##List.Insert(Byref Item As __TYPE__, Index As Integer = 0)
Dim As __TYPE__##ListItem Pointer nextItem, prevItem, newItem
If Index > 0 Then
If Index > This.Count Then Return
Dim i As Integer
nextItem = This.p_first
For i = 1 To Index - 1
nextItem = nextItem->p_next
Next
Elseif This.p_cur <> 0 Then
nextItem = This.p_cur
Index = This.Position
Else
Return
End If
prevItem = nextItem->p_prev
newItem = Allocate(Len(__TYPE__##ListItem))
newItem->p_data = Allocate(Len(Item))
*newItem->p_data = Item
If prevItem <> 0 Then prevItem->p_next = newItem
newItem->p_prev = prevItem
newItem->p_next = nextItem
nextItem->p_prev = newItem
If Index = 1 Then This.p_first = newItem
If Index = This.Count Then This.p_last = nextItem
This.Count += 1
End Sub
Destructor __TYPE__##List()
This.Clear
End Destructor
# Endif
# endmacro
# macro DefineDynamicListType( __TYPE__ )
# Define __YALL__LIST__TYPE__##__TYPE__##__DYNAMIC__
DefineListType(__TYPE__)
# endmacro
# Endif
|
Tip: the .MoveFirst/While/.Current/.MoveNext combination is faster then For/.GetItem
i mean, this:
| Code:
|
|
list.MoveFirst
While list.EOF = 0
Print list.Position; ": "; list.Current
list.MoveNext
Wend
|
is faster then
| Code:
|
|
For i = 1 To list.Count
Print i; ": "; list.GetItem(i)
Next
|
Last edited by krcko on Oct 21, 2006 23:05; edited 1 time in total |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 21, 2006 0:25 Post subject: |
|
|
Wow... I love the new functions... Thanks!
I tried to test the combined JALL/YALL program and it bombs at line 137. Right after the Print "***BOMBS HERE***" statement below:
| Code:
|
|
#include "yall.bi"
Type UDT
i As Integer
d As Double
End Type
Dim i As Integer ' counter in loops
Dim j As Integer ' counter in loops
Dim u As UDT ' used in debugUDT macro
#Macro debugList(__lst__)
Print #__lst__; " items:"
For i = 1 To __lst__.Count
Print i; ": "; __lst__.GetItem(i)
Next
Print ""
#EndMacro
#Macro debugUDT(__lst__)
Print #__lst__; " items:"
For i = 1 To __lst__.Count
u = __lst__.GetItem(i)
Print i; ": "; u.i; ", "; u.d
Next
Print ""
#EndMacro
DefineListType(Integer) ' define IntegerList
DefineListType(String) ' define StringList
' DefineDynamicListType(String) ' define Dynamic StringList
DefineListType(UDT) ' define UDTList
' declare lists
Dim list1 As IntegerList
Dim list2 As StringList
Dim list3 As UDTList
Dim test As StringList
' declare some variables
Dim v1 As Integer
Dim v2 As String
Dim v3 As UDT
''' integer list '''
' adding integers to list1
For i = 0 To 19
List1.Add(i)
Next
debugList(list1)
' clear list1
List1.Clear()
v1 = 42
' push some data into list1
List1.Push(1)
List1.Push(10)
List1.Push(v1)
List1.Push(88)
debugList(list1)
v1 = 18 ' change variable's value
debugList(list1) ' nothing changed!
' change value of list item with index 2
List1.Set(2, 18)
debugList(list1)
' remove item with index 3
List1.Remove(3)
debugList(list1)
' pop value
Print "popped: "; List1.PopFirst()
Print
debugList(list1)
''' string list '''
' fill list2 with some values:
v2 = "blah"
List2.Push("foo")
List2.Push(v2)
List2.Push("bar")
debugList(list2)
v2 = "this is changed"
debugList(list2)
List2.Set(2, v2)
debugList(list2)
While (i <= list2.count)
Print "popped: "; List2.PopFirst()
Wend
Print
List2.Add("item1")
List2.Add("item2")
List2.Add("item3")
debugList(list2)
Print "***BOMBS HERE***"
List2.Add("added")
List2.Push("pushed")
debugList(list2)
''' udt list '''
List3.Add(Type<UDT>(1, 0.5))
List3.Add(Type<UDT>(0, 3.14))
List3.Add(Type<UDT>(123, 48.58565))
List3.Add(Type<UDT>(448, 45680.5654))
debugUDT(list3)
v3.i = 20
v3.d = 5.6987
List3.Push(v3)
debugUDT(list3)
v3.i = 345
debugUDT(list3)
List3.Set(1, Type<UDT>(345, 5.6987))
debugUDT(list3)
''' Test another string '''
test.push "foo"
test.push "blah blah blah"
test.push "bar"
debugList(test)
test.push "pushed"
test.add "added"
debugList(test)
Print "popped: "; test.popfirst
Print
Print "back-popped: "; test.poplast
Print
debugList(test)
test.Remove 2
debugList(test)
test.set 1, "foo"
test.set 2, "bar"
debugList(test)
test.clear
Sleep
|
I tried defining list2 using DefineListType(String) and DefineDynamicListType(String) and got the same results.
BTW... did you consider a Find(value) function?
Last edited by gedumer on Oct 21, 2006 2:08; edited 1 time in total |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 21, 2006 1:51 Post subject: |
|
|
| Position and p_cur need to be updated every time an add or delete action takes place. ADD, PUSH, INSERT, REMOVE, POPFIRST, POPLAST must all set POSITION and P_CUR. I think the only time you set p_cur in the ADD function is when it's the first record. They also must be updated when movement actions take place... I think you're already doing that. |
| |
|
| Back to top |
|
|
|
|
| Posted: Oct 21, 2006 2:05 Post subject: |
|
|
| I just realized something, you can't go to a specific position (ie. Index). I think you need a GotoItem(index) function. Do you agree? |
| |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
