Developing a custom list gadget

[Mistrel]

I have been developing a custom list gadget for a couple of weeks now and would like to ask some general questions regarding the structure of my implementation. Because this is part of a project for a client, as much as I would like to, I can't post any code for this.

I'll be interested to answer any questions regarding development for anyone else who may want to build something similar.

So far I've build it to be a completely transparent PB gadget by returning a container gadget ID. This ID can be passed to the list view functions which know how to work with all of the other gadgets contained inside, specifically an image gadget and two scrollbars.

The gadget supports an infinite number of instances by using a doubly-linked global structure. Each new ID is a copy of the same structure in the list. All of the instanced structures use a similar method of linking data. Each column is a list which points to a list of rows.

An example of this can be found here:
http://www.purebasic.fr/english/viewtopic.php?t=34139

So, after implementing scrollbars I needed to know the exact width and height of the visible content in pixels. I know when the scrollbars should be visible by whether the columns or rows are 'overdrawn' past the visible area. But since I don't want to continue drawing I don't know what the limit is beyond the visible area and therefore can't provide the scrollbars with an upper limit.

I can do this vertically by finding the sum of the height of each cell but this would require me to scan each column individually. To find the width I would them need to scan the entire table n*n times because I only link each cell vertically. This is a poor solution.

I've been re-working the code and cell structures to support stepping through each cell vertically as well horizontally. Each column and row will also cache the width and height of the table in pixels on-insert. This should solve this problem and lead into being able to identify which cell the mouse cursor is in vertically (I can already do it horizontally) for the column resizing code.

The way I handle updating the horizontal cell pointers is by walking the cells horizontally three cells (one left and one right of the new row) and then vertically until all of the cells relevant cells are updated.

I am using linked lists for everything, because it makes sense to me. Can anyone provide guidance on optimizations and things to be aware of during development? I can easily say that I was not expecting this one gadget to be so complicated to write. It's been a real trip.

To be specific about why I am even creating a custom list gadget: the list view provided through the Win32 API is not flexible enough to satisfy the needs of this project and has several limitations when it comes to customizability (the client wants a specific look) and it has several caveats when it comes to displaying text with images.

Since I studied the Win32 list view prior to this, as my first solution, I've found a few of the concepts to be very attractive which I am implementing in my own gadget, like various callbacks and image lists. There are a lot of good things about Win32's list view but there is also a lot of baggage.

[Demivec]

For the width why not keep the length of the widest cell as part of the list structure? When ever the list would be modified the element being modified would be checked against this value to see if the new element is the widest.

[Mistrel]

For the width why not keep the length of the widest cell as part of the list structure? When ever the list would be modified the element being modified would be checked against this value to see if the new element is the widest.

I'm not sure I follow. Each column can be of variable width so I need to know the width of each of them to find the sum. Also, because no two cells in a column can have different widths I'll only need to check against the pixel width of the title cells plus the pixel width of the visible area in the last cells.

It's the height that's more difficult.

[Xombie]

Hello, Mistrel.

For my xList project here: http://www.purebasic.fr/english/viewtopic.php?t=33522 I store rows for a column within the memory block for the column itself. I have a single block of memory allocated that stores the height of each row. It's a long value per row so it's nothing more than allocating 40 bytes of memory if I have 10 rows. Each cell in a row must have the same height so only height value per row.

Retrieving or setting the height of the row is nothing more than peek/poke'ing a long value at [base address] + ((row index - 1) * 4). I scan across all rows (within the columns) at the index and get the maximum height of the row. The maximum value is then stored and gets used. Column width can change based on the column but row height must be the same for all columns at the specified index.

Does that help and/or make sense? I just woke up from a nap and my brain is still fuzzy so ...

[Mistrel]

I see how your method of allocating a block of memory for each column would work but each time you add a new cell to the column you have to redim or release/allocate/copy/free that entire block of memory.

If you instead used a block that represented each cell and linked each one together with a pointer then you would only need to allocate/free memory for each individual cell instead of the entire column. This way you can link each cell both vertically and horizontally to easily transfers the grid.

The downside is that you have to transverse the entire list to find the row you want. But you could easily cache the pointers to an array or block of memory for that.

[Xombie]

Yes - xList primarily works (great) as a database list control where I preallocate a large block and dump everything in it.

Adding rows line by line is slower but I went by this logic: You either know how many rows you have ahead of time (databases, file lists or something that can be predetermined) or you're allowing the user to add rows intermittently. Option 2 should only happen in tasks like the user adding their own rows for whatever information their storing.

Now, think of all the times you would use or want to use a list. I think the majority of data you can determine the amount of information to add ahead of time and plan on that. Any lines that are added beyond that are not extremely time sensitive.

When you cannot determine the amount of data to be inserted (possibly users adding rows for some app) then that should also not be speed sensitive and can work well with allocating/freeing memory blocks. The plus side of my code is that if that ever became an issue with my code, I can allocate a large block and leave it empty - only filling it as needed. Possibly in some buffer scenario.

I would be interested in hearing from someone like freak or fred whether constantly freeing/allocating blocks of memory is bad but I haven't run into a problem yet in the tests I did with adding single lines. Also, the speed was not a problem either in my tests. You might give the demo a shot to see if the preload and single row loads work well so you can see how these ideas work out.

Going the linked list route seems overly complex and slow to me - no offence intended. I started to write some reasons why I thought so and then realized it's probably just my bad habit of trying to optimize everything. Sorry - I guess we aren't living in the days of limited memory and space. My solution works well for me and hopefully yours works well for you.

Now, let's see....

For xList I store the desired width and height and automatically subtract out space for the scrollbars. I store the PB IDs and Handles for both scrollbars in the main memory block for the list and then set ... err... I'm not at the computer with the code right now... and I can't remember if I use SetProp_() or what... I think so... I use an ImageGadget() for the list itself. I handle resize calls to xList and take out the width/height needed for the scrollbars every time.

Width changes are nothing as beyond an initial width setting, it's up to the user to resize if they want to do it. The code doesn't not automatically resize the columns by itself.

Scrollbars become tricky when you're working with variable height rows. The horizontal scrollbar should present you no problems. You should be storing the visible width of your list and you should quickly/easily know the width of each column. So if your list is 100 pixels wide but the total column width is 150 pixels then your scrollbar should have a minimum of 1 and maximum of 55. This is assuming you allow partially visible columns.

I haven't taken the time to handle vertical scrollbars very well but it works on a similar concept. If you allow partially visible rows then you're all set and you can follow a method like I suggested earlier - a block of memory just for row heights. It's not entirely clear to me how all your data is linked so I can't think of other ways for you. Can you store the row height in one of the cells for the row? Or you could calculate the maximum height of the whole list (adding up each row's height as rows are added) and then use a simple calculation similar to the width one. Any time you add/remove/change a cell value you recalculate the height for that row and take out/add in the difference to your maximum list height and recalculate/reset your scrollbar. However, this only works if you allow partially visible rows. If you make it so that each scroll makes the next row the first visible then it's more complex. Not sure which route you picked. I picked the second choice because it seemed more clean to me. I feel like there was another reason but I can't remember at the moment.

Do you have a feature list? Maybe I could help with advice based on what you're putting into it. And what size of data do you think you'll mostly be dealing with on this list?

[Mistrel]

I would be interested in hearing from someone like freak or fred whether constantly freeing/allocating blocks of memory is bad but I haven't run into a problem yet in the tests I did with adding single lines. Also, the speed was not a problem either in my tests. You might give the demo a shot to see if the preload and single row loads work well so you can see how these ideas work out.

This method would not work well for my needs since I want to keep the amount of memory my gadget uses at a minimum. The method you've outlined would require twice the size of the memory block in order to copy it. Depending on the size of the column (or if you use a single block for the whole table) then you would be limiting the amount of allocatable memory for each operation that requires resizing the memory block by half. The actual amount of available memory space available for this type of operation may be significantly less if the remaining system memory is fragmented.

Can you store the row height in one of the cells for the row? Or you could calculate the maximum height of the whole list (adding up each row's height as rows are added) and then use a simple calculation similar to the width one.

I haven't gotten to that part yet. But the theory is that on each row insert/remove I would recalculate the pixel height by transversing the entire column and storing the value in the column structure. Working with horizontal width is simpler. I would only have to add/subtract the new/old width of the row to find a new value.

There are fundamental differences between our lists worth recognizing. My list view is a 'list view' where columns and rows only exist when you insert them and must be inserted in-order to exist. Correct me if I'm wrong but your list view appears to be more similar to a data grid. This would explain why some of the design choices each of us have appear radical to the other: the goal of our gadgets are different.

For example, you cannot arbitrarily add a column or a row to my list view. They must be added in the correct order (0, 1, 2, 3) or automatically by passing -1 as the new column/row index. I don't allocate memory for any more data than necessary and data is expected to change often in my gadget and may be inserted at random. This is why designing its structures as doubly-linked lists was ideal.

I can image that something like a data grid would benefit from allocating large blocks of data instead since it is designed to have a large number of cells immediately accessible.

A direct comparison would be that my solution is more dependent on a cpu speed and less on storage whereas your solution is more dependant on an abundance of storage and less cpu.

[srod]

With my nxTreeField gadget I hold cell data in a hash-table indexed on (column, row) indexes etc. Seems to work quite well.

Just thought I'd throw that in!

[Mistrel]

With my nxTreeField gadget I hold cell data in a hash-table indexed on (column, row) indexes etc. Seems to work quite well.

Can you describe your method of using hashes to store cell data? How do you walk adjacent cells? How do you know what cell is at the beginning/end of a column/row?

Is your gadget custom drawn or does it use the API list view?

[srod]

Sorry, my previous post wasn't very clear.

Each column / row is assigned an index corresponding to the order in which they are added and NOT the position they occupy within the grid. For example, if I add 3 columns these will have column indexes 1, 2, 3 respectively. If I add a 4th column to sit at the left-most position within the grid then it will still be given index 4 (not 0). If I then delete a column and add a new one, the new one will be given index 5 regardless of which position in the grid it occupies.

I then have a simple array to record the column order and another one for the row order.

To grab a cell I first pull out the column index from the column array then the row index from the row array. I then create the hash-table key from something like :

Code: Select all

hashKey$ = Str(*column\hash)+"."+Str(*row\hash)

and voila I have the cell data I require.

The thing about this is that inserting/deleting columns/rows is a breeze. E.g. inserting a column requires that I simply insert a single new index into the column array and that's essentially it. I don't have to examine individual cells (or the hash table) at all! (When deleting a row or column I have to remove individual cells from the hash table but that's just a simple loop etc.)

This is a somewhat simplified version of what nxTreeField does but it should give you an idea of how it all works.