root/branches/d2/concepts.txt

Ranges:

Dcollections defines a unique range type per container.  The range is
bidirectional, since every container in dcollections can be traversed forwards
and backwards.  Use standard range functions to get values from the ranges.
There are no range classes that are supported by the interfaces.  The reason is
because ranges as interfaces are too slow to be useful (one virtual call per
method, if iterating that's 3 virtual calls per loop), plus the range concept
works best as a value type; classes are reference types.  Therefore, to use the
ranges, you must know the exact type of the container you are using.

Dcollections ranges support these additional features:

- Get the beginning cursor which points to the first element in the range, or
  the end cursor which points past the last element in the range (the end
  cursor always is empty, but points to the correct element).
- Get the key of the front and back element of the range if the range is of a
  map container.  The front key element is accessed through the 'key' property,
  and the back key element is accessed through the 'backKey' property.

Cursors:

Cursors are special 1 or 0 element ranges.  They implement the forward range
interface.  The benefit to using cursors is that they always refer to exactly
one element.  A normal range uses two marker elements, a begin and an end
element.  Therefore, cursors are less susceptible to invalidation on removal of
elements.

Cursors support these additional features:

- Use a cursor as a reference point when dealing with a container.
- Use as an end point when slicing a container.  Note that some containers only
  support slicing with an arbitrary cursor and the beginning or end of the
  container.  Slicing is guaranteed to be a fast operation (lgn or better).

Determining cursor/range ownership:

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).

Slicing:

All dcollections support slicing using two cursors.  Dcollections ensures that
you never can create an invalid range.  For instance, trying to get a range
from a container using container[container.end..container.begin] will not work.
This is true even in release mode.

There are limitations for slicing.  Because slicing is expected to be a fast
operation, and validation of the relationship of slice parameters is required,
some collections only allow slicing when one of the slice parameters is begin
or end.  The LinkList and all the Hash-based containers are of this flavor.
The other containers support slicing of any two elements, because validation of
two arbitrary cursors for these containers is a quick operation.  This means
that even if a slice is logically sound, it might be rejected because it can't
be verified quickly.  This might seem like a bad limitation, but I'd rather
start off safe and add unsafe operations later if needed.  I'm hoping that this
ability is not necessary in real code.

If you wish to create internal slices of such containers, you can do so by
shrinking a range from another operation.

Range/Cursor invalidation:

Some operations will invalidate ranges/curosrs.  Dcollections cannot ensure
that such modifications will not invalidate cursors or ranges.  For example
sorting a linked list will most likely invalidate all ranges on that list
created before sorting.  Removal of either endpoint of a range, or the element
pointed to by a cursor will invalidate that cursor or range.  Checking for
invalidation is not implemented for performance and overhead reasons, so it is
up to you to verify the logic of your code.

Some operations can guarantee they do not invalidate ranges/cursors.
Operations that modify the containers will eventually specifically state how
they affect ranges/cursors.  These notes are not always present in the current
docs, but that will change.

Const/Immutable containers:

These are not currently supported.  There will be support in the future, but I
have not decided how it will work.

Purging:

You may note that distinctly missing from some containers is the ability to
remove elements by value.  This is because finding the element might be an
O(n) operation.  However, all containers support a special type of iteration
loop called a purge.  This loop allows you to remove elements as you loop
through them.  The advantage of this is if you are planning to remove many
elements, and searching for elements is not a fast operation, then you may face
a slow operation to find each element, and then a possibly slow operation to
remove each element.  Via the purge function, you can remove all these elements
in a single pass through the container, reducing your complexity to a maximum
of O(n) for searching and removing any number of elements.  Purging is done via
a ref bool parameter, indicating whether the element you are currently dealing
with should be removed.  An example on an ArrayList!int alist:

foreach(ref bool doRemove, int elem; &alist.purge)
{
  // remove all odd elements
  doRemove = (elem & 1) ? true : false;
}

Note that even though an array list takes O(n) to find an element *and* O(n) to
remove an element, the entire loop above is guaranteed to take only O(n) time.
Also note that the ref is required, even though the foreach loop allows you to
make it not ref.  Having it be not ref is useless, since the container will not
get the message.

Separating interface from implementation:

Many of the collection classes are built from an implementation struct that
defines the characteristics of the class.  The implementation struct is a
template alias that is used to generate the implementation.  Using this
technique, many things are possible.  For instance, if you have some amazing
hash implementation, you can replace the hash implementation for all the hash
types with yours, and the functions you must define are minimal.  Because of
the way the Hash and Tree implementations are defined, the same implementation
is used in all the Hash-based and all the Tree-based classes.  This allows as
much code reuse as possible, and allows a clever implementor to cover Map, Set
and Multiset classes with one implementation.

Chaining:

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:

list.add(1,2,3,4,5).add(someOtherList).sort();

Due to covariance, this works even if you call interface functions.

Determing the length effects of operations:

In many container libraries, a function like add(x) will let you know how many
elements were added (in the case of a set, this can be 1 or 0).  However, due
to chaining, we cannot return that value.

Dcollections provides a standard method to determine such things, implemented
via a wrapper type.  This type is accessed through the trackLength function
(defined in dcollections.util).  You should only use this function if you
intend to track the length changes, as it adds unnecessary overhead if you
don't care.  It's used like this:

auto numAdded = trackLength(list).add(1,2,3,4,5).add(6,7,8).delta;
assert(numAdded == 8);

Note that you can still use chaining.  However, you cannot call functions that
do not support chaining.  This restriction is because doing so would mean you
didn't care about the length to begin with.

If you want to use such functions, then you can keep track of the length by
assigning the result of trackLength to a variable, and calling those functions
directly on the container:

auto ltracker = trackLength(list);
list.add(1,2,3,4,5).remove(somerange);
auto lengthdiff = ltracker.delta;