Implementation of tree-based collections 249
eld and nally update the live child reference. If, nally, we must update
achild reference in a node that has already had made one child reference update,
we copy the node to a new one with whose
will be that of the tree, and
then update the child pointer in the parent node. In the last situation, if the child
reference we are updating is the child that was updated before and the result of the
old update cannot belong to any live snapshots because the tree’s
than or equal to the
of the node, we just update the child reference
instead of copying the node.
It should be clear from this description that the procedure is correct and does not
inuence enumerations and lookups in the tree and snapshots by more than
work per node encountered. Thus a single item operation will still use time
We now explain the crucial fact that the procedure will only produce
new nodes per update operation on the tree. Note that a single update operation on
the tree can result in cascading node copies all the way to the root. But since the
cascade will stop when we use an unlled
slot or reach the root, the number
lled by each update operation is
) . Moreover, a node will only be
copied once: after the copy it will no longer be part of the live tree and no longer
subject to updates. Now, if we have performed
update operations on the tree since
its creation, there can be at most
)nodes with lled
slots. A node with
slot either has been created directly by an insert operation on
the tree or is the single copy of a Node with a lled
slot. In total we have at
)nodes of either kind, which means exactly that we will only produce
amortized new nodes per update operation on the tree.
eld that holds the newest live snapshot is maintained as
follows. When a snapshot is created, it is registered in the
of the original
tree, and its
eld is updated. The storage element in the
is a red-black tree itself. When a snapshot is disposed, either by an explicit call
or by the garbage collector calling the nalizer of the tree class, that
snapshot will be deregistered for the
will be updatedif
relevant. In particular,
may be reset to
if there are no live snapshots.
This means that if we take a single snapshot, keep it alive for some time, and then
dispose it, we may avoid copying the whole tree if we only make a few updates while
the snapshot is alive.
It would be possible, but expensive, to make a more thorough cleanup of nodes
that become unreachable when a snapshot is disposed. We do not consider that
worthwhile, because the typical usage scenarios would be:
Make a snapshot, enumerate it while doing updates, and then dispose the
snapshot, as in section 9.11.
Build a data structure where we need all the snapshots until we just forget
the whole thing, as in the example in section 11.9.
Both scenarios are handled well by the current implementation.
250 Implementation of events and handlers
13.11 Implementation of priority queue handles
In C5 a priority queue is implemented as an interval heap, which permits efcient
access to both least and greatest item. The choice of this data structure over Min-
Max heaps was based upon results  from the Copenhagen STL project . Our
implementation of interval heaps is special in that a handle (at most one) can be
associated with an item in the heap, permitting the item to be efciently retrieved,
updated or deleted.
An interval heap is represented as an array of intervals, where an interval is a
pair ofa rst item
and a last item
.The children (if any) of an interval
at array index
are at array indexes
. The interval heap invariant
stipulates that an interval must contain the intervals of its children. This implies
that the rst and last items of the root interval (at array index 0) are the least and
greatest items in the interval heap. At each item insertion, removal or update, at
)intervals needtobeupdated, where
is thenumber of items in the heap.
for an item is implemented as an object that contains the array index
of the item, thus permitting constant time retrieval of the item. More precisely,
cis the array index of an interval, and the handle points to the interval’s last
is even, otherwise to the interval’s last item.
Each oftherst andlast items ofan interval may contain areference toa handle.
If an item has an associated handle
,then whenever the item is moved (from one
array index to another or from rst to last within an interval or viceversa), then the
is updated accordingly. When the item is removed from the heap,
the handle is invalidated. These operations take constant time.
To prevent a handle
from being used to access a heap with which it is not
associated, we check that the item at
has a handle and that that handle is
13.12 Implementation of events and handlers
Event handlers are implemented using C# delegates and events. There are six dif-
ferent kinds of events in the C5 library; see gure 8.4. However, it is undesirable
to add six event handler elds to every collection object, especially since in the most
frequent case those elds will all be
.Similarly, it is inefcient to test all those
elds for being non-
after operations, such as update, that may raise up to ve
Therefore we have collected all event handlers in a reference type
so that one eld sufces, and so that this eld if
in the frequent case where
there are no event handlers at all. This also helps ensure consistency between the
property (seepage 49)andtheevent handlers actually associated with
Creating new classes
14.1 Implementing derived collection classes
A number of abstract base classes provide common functionality for the various
concrete collection classes. The abstract base classes can be used also to derive new
collection classes. Note: This chapter is currently incomplete.
Abstract base class for implementing sequenced collections that are represented
using an array, such as ArrayList<T>, HashedArrayList<T>, and SortedArray<T>.
The class has elds and methods from CollectionBase<T>, CollectionValueBase<T>,
DirectedCollectionBase<T>, EnumerableBase<T> and SequencedBase<T>.
Further has protected elds to hold underlying array and view offset.
Further methods to manage the underlying array, create an enumerator, insert
and remove items.
Abstract base class for implementing modiable collection classes, such as most
classes in this library except for the read-only wrappers. The class has elds and
methods from CollectionValueBase<T> and EnumerableBase<T>.
Further has protected elds: read-only ag, size, item equality comparers, and
update stamp (for enumerators).
Further has methods for range check against current size, for computing collec-
tion hash codes, checks for modication during enumeration, and for creating an
Class CollectionBase<T> has a public static method:
<U>(ICollection<T> coll1, ICollection<T> coll2,
performs an unsequenced comparison of col-
252 Implementing derived collection classes
,using the given item equality comparer
if the collections contain equal items with equal multiplicity, regardless of
their order; returns
otherwise. This method is efcient on all C5 collec-
tions; in the worst case builds an auxiliary hash set from one of the collections
and then traverses the other. Hence the expected time complexity is
are numbers of items of the two collections.
Abstract base class for implementing modiable and unmodiable collection classes.
The class has elds and methods from EnumerableBase<T>.
Further has events (elds of delegate type), and utilities for event ring.
Further has Count and CountSpeed properties.
Abstract base class for implementing dictionary classes. The class has bases Collec-
tionValueBase<KeyValuePair<K,V>> and EnumerableBase<KeyValuePair<K,V>>.
Abstract base class for implementing directed collections. The class has elds and
methods from CollectionBase<T>, CollectionValueBase<T> and EnumerableBase<T>.
Abstract base class for implementing directed collection values, such as subranges
of indexed and sorted collections. The class has elds and methods from Collection-
ValueBase<T> and EnumerableBase<T>.
Abstract base class for implementing enumerable classes. The class has a public
and protected methods for counting (by enumeration) the
number of items.
Abstract base for implementing sequenced collections. The class has elds, events
and methods inheritedfrom CollectionBase<T>, CollectionValueBase<T>,Directed-
CollectionBase<T> and EnumerableBase<T>. Further has methods for computing
the collection’s hash code and for determining collection equality, respecting the
Implementing derived collection classes 253
Abstract base class for implementing sorted dictionary classes such as SortedDic-
tionaryBase<K,V>. The class has elds and methods from
14.1.10 Read-only wrappers for abstract base classes
The Guarded classes shown in gure 14.1 are mainly useful as base classes for
creating read-only wrappers of derived classes.
Abstract base class
Read-only wrapper class
Figure 14.1: Read-only wrappers for abstract base classes. Read-only wrappers for
non-abstract collection and dictionary classes are shown in gure 8.2.
254 Implementing derived collection classes
 Nunit. Web site. At
 A.M. Andrew. Anotherefcient algorithm forconvex hulls intwo dimensions.
Information Processing Letters,9:216219,1979.
 K. Arnold, J. Gosling,and D. Holmes. TheJava ProgrammingLanguage.
Addison-Wesley, fourth edition, 2005.
 M. Bender etal. Two simplied algorithms for maintaining order ina list. In 10th
Annual European Symposiumon Algorithms (ESA 2002),Rome,Italy, September 2002.
LectureNotesin ComputerScience, vol. 2461, pages 152164. Springer-Verlag, 2002.
 JonBentley, D. E. Knuth,and M.D. McIlroy. Programming pearls: A literate program.
Communications of theACM, 29(6):471483,June 1986.
 Joshua Bloch. Effective Java Programming LanguageGuide. Addison-Wesley,2001.
 W.R. Cook. Interfacesand specications forthe Smalltalk-80 collection classes. In
Conference on Object-Oriented Programming Systems,Languages, and Applications
(OOPSLA1992). SIGPLAN Notices27,10,pages 115, 1992.
 Copenhagen STL. Homepage. Web site. At
 T.H. Cormen, C.E. Leiserson, R.L.Rivest, and C. Stein. Introductionto Algorithms.
The MIT Press, second edition, 2001.
 J. Driscoll, N. Sarnak, D.Sleator, and R. Tarjan. Makingdata structures persistent.
Journal of Computer and Systems Sciences, 38(1):86124, 1989.
 Ecma TC39 TG2. C# Language Specication. StandardECMA-334, 3rd edition. June
 Ecma TC39 TG3. CommonLanguage Infrastructure (CLI).Standard ECMA-335, 3rd
edition. June 2005. At
 M. Evered and G. Menger. Eine Evaluierung des Java JDK 1.2 Collections Framework
aus Sicht derSoftwaretechnik. InC.H. Cap, editor, Java-Informations-Tage1998,
Frankfurt, Germany,November 1998, pages 1112. Springer-Verlag, 1999. At
 A.Goldberg and D. Robson. Smalltalk 80: The Language. Addison-Wesley, 1989.
 P.Golde. PowerCollections for .NET. Web site. At
 R. Graham. An efcient algorithm for determining the convex hull of a nite point set.
Information ProcessingLetters, 1:132133, 1972.
 Anders Hejlsberg, Scott Wiltamuth, and Peter Golde. TheC# Programming Language.
 NielsJłrgen Kokholm. Anextended library of collectionclasses for.NET. Master’s
thesis, IT University of Copenhagen, Denmark, 2004.
 George Marsaglia. Re: New random generator. Posting to newsgroup comp.lang.c,
April 2003. Posted 2003-04-03.
 George Marsaglia. Seeds forrandom number generators. Communications of theACM,
 G. Mengeret al. Collectiontypes and implementations in object-oriented software
libraries. InConferenceon Technology of Object-Oriented Languages and Systems,
Santa Barbara, 1998,pages 97109,1998.
 Microsoft. Microsoft .NET framework developer center. Web site. At
 David R. Musser. Introspective sortingand selection algorithms. Software-Practice and
 Rasmus Paghand Flemming Rodler. Cuckoo hashing. Journal of Algorithms,
 N.Sarnak and R.E. Tarjan. Planarpoint location usingpersistent searchtrees.
Communications of theACM, 29(7):669679, 1986.
 Robert Sedgewick. Algorithms. Addison-Wesley, second edition,1988.
 P. Sestoft and H. I.Hansen. C# Precisely. Cambridge, Massachusetts: The MIT Press,
 Słren Skov and JesperHolm Olsen. A comparative analysis of three different priority
deques. CPH STL Report 2001-14, DIKU, University of Copenhagen,October 2001.
 D. Sleator and P.Dietz. Two algorithms for maintainingorderin a list. In 19th ACM
Symposium on the Theory of Computing (STOC’87), pages 365372.ACMPress, 1987.
 D. Syme. F#. Web site. At
 R.E. Tarjan. Data Structures andNetwork Algorithms. Societyfor Industrial and
Applied Mathematics, 1983.
 VijayV. Vazirani. ApproximationAlgorithms. Springer-Verlag, 2001.
Act<A1> delegate type, 38
source le, 241
Act<A1,A2> delegate type,38
Act<A1,A2,A3>delegate type, 38
Act<A1,A2,A3,A4> delegate type, 38
Action<T> delegate type
corresponds to Act<T>, 38
enum value (EventTypeEnum), 35
method (ICollectionValue<T>), 49
amortized complexity, 233
anagram classes (example), 202203
arraylist as queue, 192
bad hash function, 194
collectionof collections, 195
hashed linked list indexer,192
method onlist, 191,192
linked list, 191
list as set, 193
priority queue insorted array,193
sorted array, 189
sorted arrayas priority queue, 193
array list, 111112
queue (anti-pattern), 192
listenable events, 139
enum value (EventTypeEnum), 35
batchjob queue (example),218
Bentley, Jon, 231
Bond, James, 2
breadth-rst traversal, 182
bucket in hashtable,117
building C5 from source,242
ByteComparer class, 32
ByteEqualityComparer class, 28
C5Random class, 41
cached hashcode, 45, 243
enum value (EventTypeEnum),
CharComparer class, 32
CharEqualityComparer class, 28
circular queue, 111
CircularQueue<T> class, 17, 111
listenable events, 139
enum value (EventTypeEnum),
ClearedEventArgs class, 141
ClearedRangeEventArgs class, 141
cloneable, 12, 142
guarded collection, 142
list view, 142
co-variance, lack of, 133
base classes, 251253
indexed sorted, 16
interface hierarchy, 43
of collections,132, 170172
persistent sorted, 16
CollectionValueBase<T> class, 252
common words (example), 231232
method (IComparer<T>), 31
Comparer<T> class, 32
source le, 241
Comparison<T>delegate (System), 33
and DelegateComparer<T>, 33
Documents you may be interested
Documents you may be interested