root/branches/d2/concepts.txt

Revision 113, 7.6 kB (checked in by schveiguy, 3 years ago)

Fixed shadow declaration. Compiles/tests with 2.054 beta.

Tweaked the docs a bit.

Line 
1 Ranges:
2
3 Dcollections defines a unique range type per container.  The range is
4 bidirectional, since every container in dcollections can be traversed forwards
5 and backwards.  Use standard range functions to get values from the ranges.
6 There are no range classes that are supported by the interfaces.  The reason is
7 because ranges as interfaces are too slow to be useful (one virtual call per
8 method, if iterating that's 3 virtual calls per loop), plus the range concept
9 works best as a value type; classes are reference types.  Therefore, to use the
10 ranges, you must know the exact type of the container you are using.
11
12 Dcollections ranges support these additional features:
13
14 - Get the beginning cursor which points to the first element in the range, or
15   the end cursor which points past the last element in the range (the end
16   cursor always is empty, but points to the correct element).
17 - Get the key of the front and back element of the range if the range is of a
18   map container.  The front key element is accessed through the 'key' property,
19   and the back key element is accessed through the 'backKey' property.
20
21 Cursors:
22
23 Cursors are special 1 or 0 element ranges.  They implement the forward range
24 interface.  The benefit to using cursors is that they always refer to exactly
25 one element.  A normal range uses two marker elements, a begin and an end
26 element.  Therefore, cursors are less susceptible to invalidation on removal of
27 elements.
28
29 Cursors support these additional features:
30
31 - Use a cursor as a reference point when dealing with a container.
32 - Use as an end point when slicing a container.  Note that some containers only
33   support slicing with an arbitrary cursor and the beginning or end of the
34   container.  Slicing is guaranteed to be a fast operation (lgn or better).
35
36 Determining cursor/range ownership:
37
38 All collections can identify whether a cursor/range belongs to them.  Each collection class has a 'belongs' method to determine ownership.  The ownership check is guaranteed to be a fast operation (O(lgN) or better).
39
40 Slicing:
41
42 All dcollections support slicing using two cursors.  Dcollections ensures that
43 you never can create an invalid range.  For instance, trying to get a range
44 from a container using container[container.end..container.begin] will not work.
45 This is true even in release mode.
46
47 There are limitations for slicing.  Because slicing is expected to be a fast
48 operation, and validation of the relationship of slice parameters is required,
49 some collections only allow slicing when one of the slice parameters is begin
50 or end.  The LinkList and all the Hash-based containers are of this flavor.
51 The other containers support slicing of any two elements, because validation of
52 two arbitrary cursors for these containers is a quick operation.  This means
53 that even if a slice is logically sound, it might be rejected because it can't
54 be verified quickly.  This might seem like a bad limitation, but I'd rather
55 start off safe and add unsafe operations later if needed.  I'm hoping that this
56 ability is not necessary in real code.
57
58 If you wish to create internal slices of such containers, you can do so by
59 shrinking a range from another operation.
60
61 Range/Cursor invalidation:
62
63 Some operations will invalidate ranges/curosrs.  Dcollections cannot ensure
64 that such modifications will not invalidate cursors or ranges.  For example
65 sorting a linked list will most likely invalidate all ranges on that list
66 created before sorting.  Removal of either endpoint of a range, or the element
67 pointed to by a cursor will invalidate that cursor or range.  Checking for
68 invalidation is not implemented for performance and overhead reasons, so it is
69 up to you to verify the logic of your code.
70
71 Some operations can guarantee they do not invalidate ranges/cursors.
72 Operations that modify the containers will eventually specifically state how
73 they affect ranges/cursors.  These notes are not always present in the current
74 docs, but that will change.
75
76 Const/Immutable containers:
77
78 These are not currently supported.  There will be support in the future, but I
79 have not decided how it will work.
80
81 Purging:
82
83 You may note that distinctly missing from some containers is the ability to
84 remove elements by value.  This is because finding the element might be an
85 O(n) operation.  However, all containers support a special type of iteration
86 loop called a purge.  This loop allows you to remove elements as you loop
87 through them.  The advantage of this is if you are planning to remove many
88 elements, and searching for elements is not a fast operation, then you may face
89 a slow operation to find each element, and then a possibly slow operation to
90 remove each element.  Via the purge function, you can remove all these elements
91 in a single pass through the container, reducing your complexity to a maximum
92 of O(n) for searching and removing any number of elements.  Purging is done via
93 a ref bool parameter, indicating whether the element you are currently dealing
94 with should be removed.  An example on an ArrayList!int alist:
95
96 foreach(ref bool doRemove, int elem; &alist.purge)
97 {
98   // remove all odd elements
99   doRemove = (elem & 1) ? true : false;
100 }
101
102 Note that even though an array list takes O(n) to find an element *and* O(n) to
103 remove an element, the entire loop above is guaranteed to take only O(n) time.
104 Also note that the ref is required, even though the foreach loop allows you to
105 make it not ref.  Having it be not ref is useless, since the container will not
106 get the message.
107
108 Separating interface from implementation:
109
110 Many of the collection classes are built from an implementation struct that
111 defines the characteristics of the class.  The implementation struct is a
112 template alias that is used to generate the implementation.  Using this
113 technique, many things are possible.  For instance, if you have some amazing
114 hash implementation, you can replace the hash implementation for all the hash
115 types with yours, and the functions you must define are minimal.  Because of
116 the way the Hash and Tree implementations are defined, the same implementation
117 is used in all the Hash-based and all the Tree-based classes.  This allows as
118 much code reuse as possible, and allows a clever implementor to cover Map, Set
119 and Multiset classes with one implementation.
120
121 Chaining:
122
123 Containers and their respective interfaces all support chaining when possible.  This means you can perform multiple operations on one object in the same expression.  For example:
124
125 list.add(1,2,3,4,5).add(someOtherList).sort();
126
127 Due to covariance, this works even if you call interface functions.
128
129 Determing the length effects of operations:
130
131 In many container libraries, a function like add(x) will let you know how many
132 elements were added (in the case of a set, this can be 1 or 0).  However, due
133 to chaining, we cannot return that value.
134
135 Dcollections provides a standard method to determine such things, implemented
136 via a wrapper type.  This type is accessed through the trackLength function
137 (defined in dcollections.util).  You should only use this function if you
138 intend to track the length changes, as it adds unnecessary overhead if you
139 don't care.  It's used like this:
140
141 auto numAdded = trackLength(list).add(1,2,3,4,5).add(6,7,8).delta;
142 assert(numAdded == 8);
143
144 Note that you can still use chaining.  However, you cannot call functions that
145 do not support chaining.  This restriction is because doing so would mean you
146 didn't care about the length to begin with.
147
148 If you want to use such functions, then you can keep track of the length by
149 assigning the result of trackLength to a variable, and calling those functions
150 directly on the container:
151
152 auto ltracker = trackLength(list);
153 list.add(1,2,3,4,5).remove(somerange);
154 auto lengthdiff = ltracker.delta;
Note: See TracBrowser for help on using the browser.