Redefining Collection Categories

[Nestharus]

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

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.

 

[Almia]

Wow. That is a lot of stacks. I can't wait to see how many Trees, Queues, Lists you are planning to do.

 

[Waffle]

I really don't thins saving 2 variables should be a very big goal.. (tho +1 for caring )

However i think of something like a Stack or an Array or a List as a utility.
Such basic utilities should be (relatively) noob friendly. having to define your allocator would be rather a pain .

JASS2 seems to be the only language where its ok to make libraries where the user has to write half of it before he can use it.