Page 1 of 1
List inside a structure workaround
Posted: Mon Feb 18, 2008 8:48 pm
by LDSang
Hello everyone. I've been using PureBasic for a few years now and just ran into a problem. Suppose I want to do a structure with people who own a number of homes for example. I have no idea how many homes. They could be a family person with 1 home, an investor with 10 homes, or Donald Trump. This is the structure I'd like to use:
Code: Select all
Structure
name.s
phone.s
homes.s()
EndStructure
Of course this doesn't work. The only way I could think to do this is to declare an array bigger than the largest value and waste a LOT of memory on the numerous people with 1 home. Does anyone have a simple work around for this. I've been wracking my brain all weekend and haven't come up with anything. Thanks in advance.
Darryl
Re: List inside a structure workaround
Posted: Mon Feb 18, 2008 8:57 pm
by tinman
LDSang wrote:Does anyone have a simple work around for this. I've been wracking my brain all weekend and haven't come up with anything. Thanks in advance.
There are a lot of home made linked list implementations posted on these forums, mainly for solving this problem.
Posted: Mon Feb 18, 2008 9:05 pm
by hellhound66
Removed.
Posted: Tue Feb 19, 2008 2:57 am
by Demivec
@LDSang: here's a long-winded example using an array to hold dynamic singly- linked-lists. I think it'll give you a few more ideas.
Code: Select all
;Dynamic List-in-an-Array example
; by Demivec
;18 Feb 2008
;-structures
Structure homeList
home.s
notLast.l ;this serves as a pointer to next element in homes(), 0 indicates this is end of list
EndStructure
Structure owner
name.s
phone.s
homes.l
EndStructure
;-init
Global NewList owner.owner()
Global maxHomesArraySize.l = 100 ;this records maximum # of homes record, it may go up or down
Global Dim homes.homeList(maxHomesArraySize) ;this holds all homes and links to next home, it's an array of list elements.
Global freeHomeStart.l = 1 ;this shows the first available home, we don't use the zero'th element
For I = freeHomeStart To maxHomesArraySize - 1 ;this initializes list to point to next available home element
homes(I)\notLast = I + 1
Next
;-procedures
Procedure increaseHomesArray() ;increase size of homes array and initialize
Protected I.l
maxHomesArraySize + 50 ;increase size of homes array
freeHomeStart = maxHomesArraySize + 1 ;free element list will start at the addition to array
Redim homes.homeList(maxHomesArraySize)
For I = freeHomeStart To maxHomesArraySize - 1 ;this initializes list to point to next available home element
homes(I)\notLast = I + 1
Next
EndProcedure
Procedure.l findOwner(name.s) ;points owner() list to desired name
FirstElement(owner())
ForEach owner() ;look for owner
If owner()\name = name
ProcedureReturn 1 ;found
Break
EndIf
Next
ProcedureReturn 0 ;didn't find
EndProcedure
Procedure.q findHome(home.s) ;called after owner() list points to desired owner
Protected homeList.l = owner()\homes,lastIndex.q = homeList
Repeat
If homes(homeList)\home = home
PokeL(@lastIndex+4,homeList)
ProcedureReturn lastIndex ;found homeList index of home (previousIndex is at @,homeIndex is at @+4)
EndIf
lastIndex = homeList
homeList = homes(homeList)\notLast
Until homes(homeList)\notLast = #False
ProcedureReturn 0 ;didn't find
EndProcedure
Procedure addNewHome(home.s,homeIndex.l = 0) ;called after owner() list points to desired owner
If homeIndex = 0 ;start a new list for a new owner
owner()\homes = freeHomeStart
homeIndex = freeHomeStart
Else ;update links to add another home
homes(homeIndex)\notLast = freeHomeStart
homeIndex = freeHomeStart
EndIf
If homes(freeHomeStart)\notLast = #False
increaseHomesArray()
Else
freeHomeStart = homes(freeHomeStart)\notLast ;move pointer to next free element
EndIf
homes(homeIndex)\home = home
homes(homeIndex)\notLast = #False ;signal as last home in list
EndProcedure
Procedure.l AddHomeToOwner(name.s,home.s,phone.s = "NA") ;if owner doesn't exist yet it will be created first
Protected homeList.l
If findOwner(name)
homeList = owner()\homes
While homes(homeList)\notLast <> #False ;find end of list
homeList = homes(homeList)\notLast
Wend
addNewHome(home,homeList)
ProcedureReturn 1 ;added to an existing owner
Else
AddElement(owner())
owner()\name = name
owner()\phone = phone
addNewHome(home)
ProcedureReturn -1 ;added to a new owner
EndIf
EndProcedure
Procedure removeHome(homeIndex.l,lastIndex.l) ;called after owner() list points to desired owner
If lastIndex = homeIndex ;modification to list of owners needed
If homes(lastIndex)\notLast = #False ;this was the only home in list
DeleteElement(owner())
Else ;this was the first home, so update pointer to the new first home
owner()\homes = homes(lastIndex)\notLast
EndIf
Else
homes(homes(lastIndex)\notLast)\notLast = homes(homeIndex)\notLast ;relink home list
EndIf
homes(homeIndex)\home = ""
homes(homeIndex)\notLast = freeHomeStart ;link removed home in list of free homes
freeHomeStart = homeIndex
EndProcedure
Procedure.l removeHomeFromOwner(name.s,home.s) ;if no homes left after removal, owner will be removed also
Protected homeIndex.q
If findOwner(name)
homeIndex = findHome(home)
If homeIndex = 0
ProcedureReturn 0 ;didn't find home
Else
removeHome(PeekL(@homeIndex),PeekL(@homeIndex+4))
EndIf
ProcedureReturn 1 ;added to an existing owner
Else
ProcedureReturn -1 ;didn't find owner
EndIf
EndProcedure
Procedure displayOwnerList() ;debugs owners and homeslist
Protected homeList.l,homecount.l
Debug "---------------"
FirstElement(owner())
ForEach owner()
Debug "Owner: " + owner()\name
homeList = owner()\homes
homecount = 1
While homes(homeList)\notLast ;find end of list
Debug " home #" + Str(homecount) + ": " + homes(homeList)\home
homecount + 1
homeList = homes(homeList)\notLast
Wend
Debug " home #" + Str(homecount) + ": " + homes(homeList)\home
Next
EndProcedure
;-example
AddHomeToOwner("Donald","1 Maple Dr","555-5555") ;creates a new owner
AddHomeToOwner("Trump","4 Baltic Ave") ;creates a new owner
AddHomeToOwner("Trump","28 Pennsylvania Ave")
AddHomeToOwner("Trump","35 Park Place")
AddHomeToOwner("Trump","50 Broadway")
AddHomeToOwner("Trump","18 Illinois Ave")
AddHomeToOwner("tinman","57.1604N, 2.1345W") ;creates a new owner
AddHomeToOwner("hellhound66","16 Freiberg Strasse") ;creates a new owner
AddHomeToOwner("Demivec","2 Sherwood Forest","555-AROW") ;creates a new owner
displayOwnerList()
removeHomeFromOwner("Trump","4 Baltic Ave")
removeHomeFromOwner("Donald","1 Maple Dr")
displayOwnerList()
Posted: Tue Feb 19, 2008 3:41 am
by pdwyer
I tend to look at these problems the same a simple database design issues and then work backward to a coding solution.
In a DB, you wanted to have just one table (like you have one structure) then the "Homes" column would do what? you could have a string and put comma separated values in there which is one solution that may suite some apps but is kind of ugly. OR, you could have a second table with homes in there and join them with an ID. (depends how much data you have and your search requirements I suppose)
In your structure, have a unique ID in a LONG or QUAD or whatever, then have a second structure with ID and HOME and have a list or array of that structure. Then you can go and get all the homes for a single ID. If the list is sorted by ID then you can binary search an array very fast.
If this all goes to disk anyway, just use a DB then query it when you need the info.
Posted: Wed Feb 20, 2008 7:57 am
by LDSang
pdwyer wrote:If this all goes to disk anyway, just use a DB then query it when you need the info.
I thought about doing this but then I thought I may have more than one query at a time, and the db functions (I'm using SQLite) seem to reference the entire database handle as opposed to the last result.
I was finally able to get this going though using a stucture and an array. I know the size right before I need it, so I can resize an array in a structure, and use a list of the structure. Thank you everyone for your help.
Darryl
Posted: Fri Feb 22, 2008 10:28 am
by pdwyer
Fair enough,
On the SQLite thing though, you can have multiple concurrent queries, you can only have one write operation at a time though (update, insert, delete etc) Selects are fine.
Posted: Fri Feb 22, 2008 7:25 pm
by LDSang
pdwyer wrote:Fair enough,
On the SQLite thing though, you can have multiple concurrent queries, you can only have one write operation at a time though (update, insert, delete etc) Selects are fine.
So how do you do the multiple concurrent queries in PureBasic for SQLite? It seems like the commands only reference the entire database used and not the "result set".
Darryl
Posted: Sat Feb 23, 2008 2:56 am
by pdwyer
Use threads, have each open it's own connection to the same DB. If one is doing a write operation the other will get a "busy" error till it completed. Not so good to share the same connection handle across threads, I Think some people had issues there