- Joined
- Jul 10, 2007
- Messages
- 6,306
So, originally I defined this huge key for collections.
It was here
http://www.hiveworkshop.com/forums/graveyard-418/collections-index-239205/
I'm reworking collections to add all of the missing ones plus improve allocation to use the latest techniques.
With these new definitions, I've come up with the following
Here is a list of all Stack variants
01. StackN
02. StackNt
03. StackHN -> debug shared
04. StackHtN
05. StackHNt
06. StackHtNt -> debug shared
07. StackHxN
08. StackHxtN
09. StackHxNt
10. StackHxtNt
11. StackHNx
12. StackHtNx
13. StackHNxt
14. StackHtNxt
15. StackHxNx
16. StackHxtNx
17. StackHxNxt
18. StackHxtNxt
19. StackNx
20. StackNxt
21. StackArrayHtNt
22. StackArrayN
23. StackArrayNt
24. StackCircularHN -> debug shared
25. StackCircularHtN
26. StackCircularHNt
27. StackCircularHtNt -> debug shared
28. StackCircularHxN
29. StackCircularHxtN
30. StackCircularHxNt
31. StackCircularHxtNt
32. StackCircularN
33. StackCircularNt
34. StackCircularNx
35. StackCircularNxt
36. StackCircularHNx
37. StackCircularHtNx
38. StackCircularHNxt
39. StackCircularHtNxt
40. StackCircularHxNx
41. StackCircularHxtNx
42. StackCircularHxNxt
43. StackCircularHxtNxt
So there are a few questions.
1. How is the readability? Given the key, does everything make sense and does it make it easy to implement arbitrary collections without looking up their names? The new categories are also not backwards compatible with the old categories. Nx in the old categories is Hx in the new categories. Unique in the old categories is Nx in the new. I find these new names to be more logical.
2. How should it be released? How should collections in general be released? I'm planning on releasing Indexed Array, Stack, Queue, and List. Should all stacks be released in a big Stack pack, each as their own trigger/library? Should all stacks be released under 1 all-powerful stack library? Should all collections be released in one super collection pack? I personally think that each set should be released in a pack: Stack Pack, Queue Pack, List Pack. I also think that each collection should be its own library in its own trigger.
3. Default structure for a collection, as defined by the categories, is that the collection is linked. Should Linked be a category instead of Array? Should both be categories?
There is one final point that, instead of posing as a question, argue for. It actually makes sense to make everything HxNx or HxtNxt and so on. That is, the collection itself should not deal with allocation at all, but instead should just provide the code for how to work with the data structure. This would allow users to handle it however they like. They can do dedicated allocation or pass in things that already exist. The problem is that when allocation is defined within the collection, it uses variables like next, prev, first, and last for two purposes: what they were intended for and as the recycler. This means that when the collection itself defines allocation, it saves 2 variables. If the user were to do it, they could not reuse the collection's fields for a recycler, meaning a user would have to use something like Alloc. This also has another benefit besides just saving two variables. It provides O(1) deallocation. If a collection's recycler for nodes uses the next field, then deallocating an entire collection would be about just appending that collection to thistype(0).next. This is 2 lines.
last.next = thistype(0).next
thistype(0).next = first
Without doing this, each node would have to be deallocated separately, which would involve a loop and be O(n). This adds many extra categories, but I think that the benefits are worth it. A language like Wurst also can't do this because Wurst doesn't let you merge fields like this.
It was here
http://www.hiveworkshop.com/forums/graveyard-418/collections-index-239205/
I'm reworking collections to add all of the missing ones plus improve allocation to use the latest techniques.
With these new definitions, I've come up with the following
Code:
Base
Debug -> Shared
The standard collection
H (head)
There is instancing for the collection
Ht
Instancing of the head is done with a hashtable
first and last are table fields
N (node)
There is instancing for nodes of the collection
Nt
Instancing for the nodes is done with a hashtable
next and previous are table fields
Hx
The collection has no instancing. Instead, an instance is passed into the collection from a user.
0 is not legal
Hxt
Can accept instances beyond 8191
first and last are table fields
Nx
The collection has no instancing for nodes. Instead, the user passes in their own nodes.
0 is not legal
Nxt
Can accept instances beyond 8191
next and previous are table fields
No H (static)
There is no instancing for the collection. Instead the struct is the collection itself.
Circular
Debug -> Shared
The collection has no endpoints. Iterating over the collection would result in an infinite loop.
Array
The collection is not linked, but is instead an array. Used with stacks.
Examples:
CollectionN - static with instancing for nodes
CollectionHN - instancing for both head and nodes
CollectionArrayHtNt - head is allocated via Table and nodes are indices in that table
Why are some combinations not included?
CollectionArrayHxNt
In this collection, the head is provided by the user and the collection uses an array
for the nodes. If the array is not a Table, then the array must be of a fixed size or
a heap must be used for array allocation. In either case, some sort of array must be allocated.
Either the user needs to pass in an array that was already allocated, like a Table, which would
corrupt the user's collection, or the system must always allocate itself every time. This means
that Hx does not make sense as a filter because the allocation is still being done for the head
regardless. N is also always with t because a table is always used. Also, Table itself uses a
Table for allocation, not an array. This means that anything that any array variant that uses tables
automatically have to be Ht.
Shared
There is an old type called Shared. Here, the allocation space for nodes and the head were the same.
This was only ever used for debugging. Thus, in debug mode, collections that can be shared are shared.
Outside of debug mode, nothing is shared.
Every collection that hasn't been included is not included for reasons just as good as the above.
Here is a list of all Stack variants
01. StackN
02. StackNt
03. StackHN -> debug shared
04. StackHtN
05. StackHNt
06. StackHtNt -> debug shared
07. StackHxN
08. StackHxtN
09. StackHxNt
10. StackHxtNt
11. StackHNx
12. StackHtNx
13. StackHNxt
14. StackHtNxt
15. StackHxNx
16. StackHxtNx
17. StackHxNxt
18. StackHxtNxt
19. StackNx
20. StackNxt
21. StackArrayHtNt
22. StackArrayN
23. StackArrayNt
24. StackCircularHN -> debug shared
25. StackCircularHtN
26. StackCircularHNt
27. StackCircularHtNt -> debug shared
28. StackCircularHxN
29. StackCircularHxtN
30. StackCircularHxNt
31. StackCircularHxtNt
32. StackCircularN
33. StackCircularNt
34. StackCircularNx
35. StackCircularNxt
36. StackCircularHNx
37. StackCircularHtNx
38. StackCircularHNxt
39. StackCircularHtNxt
40. StackCircularHxNx
41. StackCircularHxtNx
42. StackCircularHxNxt
43. StackCircularHxtNxt
So there are a few questions.
1. How is the readability? Given the key, does everything make sense and does it make it easy to implement arbitrary collections without looking up their names? The new categories are also not backwards compatible with the old categories. Nx in the old categories is Hx in the new categories. Unique in the old categories is Nx in the new. I find these new names to be more logical.
2. How should it be released? How should collections in general be released? I'm planning on releasing Indexed Array, Stack, Queue, and List. Should all stacks be released in a big Stack pack, each as their own trigger/library? Should all stacks be released under 1 all-powerful stack library? Should all collections be released in one super collection pack? I personally think that each set should be released in a pack: Stack Pack, Queue Pack, List Pack. I also think that each collection should be its own library in its own trigger.
3. Default structure for a collection, as defined by the categories, is that the collection is linked. Should Linked be a category instead of Array? Should both be categories?
There is one final point that, instead of posing as a question, argue for. It actually makes sense to make everything HxNx or HxtNxt and so on. That is, the collection itself should not deal with allocation at all, but instead should just provide the code for how to work with the data structure. This would allow users to handle it however they like. They can do dedicated allocation or pass in things that already exist. The problem is that when allocation is defined within the collection, it uses variables like next, prev, first, and last for two purposes: what they were intended for and as the recycler. This means that when the collection itself defines allocation, it saves 2 variables. If the user were to do it, they could not reuse the collection's fields for a recycler, meaning a user would have to use something like Alloc. This also has another benefit besides just saving two variables. It provides O(1) deallocation. If a collection's recycler for nodes uses the next field, then deallocating an entire collection would be about just appending that collection to thistype(0).next. This is 2 lines.
last.next = thistype(0).next
thistype(0).next = first
Without doing this, each node would have to be deallocated separately, which would involve a loop and be O(n). This adds many extra categories, but I think that the benefits are worth it. A language like Wurst also can't do this because Wurst doesn't let you merge fields like this.