§13.11
Implementation of tree-based collections 249
oldref
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
generation
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
maxsnapid
is less
than or equal to the
lastgeneration
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
inuence enumerations and lookups in the tree and snapshots by more than
O
(
1
)
work per node encountered. Thus a single item operation will still use time
O
(
logn
).
We now explain the crucial fact that the procedure will only produce
O
(
1
)amortized
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 unlled
oldref
slot or reach the root, the number
of
oldref
lled by each update operation is
O
(
1
) . 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
m
update operations on the tree since
its creation, there can be at most
O
(
m
)nodes with lled
oldref
slots. A node with
an unlled
oldref
slot either has been created directly by an insert operation on
the tree or is the single copy of a Node with a lled
oldref
slot. In total we have at
most
O
(
m
)nodes of either kind, which means exactly that we will only produce
O
(
1
)
amortized new nodes per update operation on the tree.
The tree’s
maxsnapid
eld that holds the newest live snapshot is maintained as
follows. When a snapshot is created, it is registered in the
snapList
of the original
tree, and its
maxsnapid
eld is updated. The storage element in the
SnapRef
class
is a red-black tree itself. When a snapshot is disposed, either by an explicit call
to
Dispose()
or by the garbage collector calling the nalizer of the tree class, that
snapshot will be deregistered for the
SnapRef
object and
maxsnapid
will be updatedif
relevant. In particular,
maxsnapid
may be reset to  
1
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.
Pdf to tiff online - software control cloud:C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net, ASP.NET MVC, Ajax, WinForms, WPF
Online C# Tutorial for How to Convert PDF File to Tiff Image File
www.rasteredge.com
Pdf to tiff online - software control cloud:VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.net, ASP.NET MVC, Ajax, WinForms, WPF
Free VB.NET Guide to Render and Convert PDF Document to TIFF
www.rasteredge.com
250 Implementation of events and handlers
§13.12
13.11 Implementation of priority queue handles
In C5 a priority queue is implemented as an interval heap, which permits efcient
access to both least and greatest item. The choice of this data structure over Min-
Max heaps was based upon results [28] from the Copenhagen STL project [8]. 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 efciently retrieved,
updated or deleted.
An interval heap is represented as an array of intervals, where an interval is a
pair ofa rst item
a
and a last item
b
,with
a
b
.The children (if any) of an interval
at array index
i
are at array indexes
2i
and
2i
+
1
. 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
most
log
(
n
)intervals needtobeupdated, where
n
is thenumber of items in the heap.
Ahandle
h
for an item is implemented as an object that contains the array index
i
of the item, thus permitting constant time retrieval of the item. More precisely,
b
i
=
2
cis the array index of an interval, and the handle points to the interval’s last
item if
i
is even, otherwise to the interval’s last item.
Each oftherst andlast items ofan interval may contain areference toa handle.
If an item has an associated handle
h
,then whenever the item is moved (from one
array index to another or from rst to last within an interval or viceversa), then the
item index
i
in
h
is updated accordingly. When the item is removed from the heap,
the handle is invalidated. These operations take constant time.
To prevent a handle
h
from being used to access a heap with which it is not
associated, we check that the item at
h
:
i
has a handle and that that handle is
h
.
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
null
.Similarly, it is inefcient to test all those
elds for being non-
null
after operations, such as update, that may raise up to ve
events.
Therefore we have collected all event handlers in a reference type
EventBlock
,
so that one eld sufces, and so that this eld if
null
in the frequent case where
there are no event handlers at all. This also helps ensure consistency between the
ActiveEvents
property (seepage 49)andtheevent handlers actually associated with
acollection.
software control cloud:Online Convert PDF file to Tiff. Best free online PDF Tif
Online PDF to Tiff Converter. Download Free Trial. Convert a PDF File to Tiff. Just upload your file by clicking on the blue button
www.rasteredge.com
software control cloud:Online Convert PDF file to Word. Best free online PDF Conversion
Online Tiff to PDF Converter. Download Free Trial. Convert a Tiff/Tif File to PDF. Just upload your file by clicking on the blue button
www.rasteredge.com
Chapter 14
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.
14.1.1 ArrayBase<T>
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.
14.1.2 CollectionBase<T>
Abstract base class for implementing modiable 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 modication during enumeration, and for creating an
enumerator.
Class CollectionBase<T> has a public static method:
static bool
StaticEquals
<U>(ICollection<T> coll1, ICollection<T> coll2,
SCG.IEqualityComparer<T> eqc)
performs an unsequenced comparison of col-
251
software control cloud:Online Convert Excel to PDF file. Best free online export xlsx
Online Excel to PDF Converter. Download Free Trial. Convert a Excel File to PDF. Download and try RasterEdge.XDoc.PDF for .NET with online support. See pricing.
www.rasteredge.com
software control cloud:C# Create PDF from Tiff Library to convert tif images to PDF in C#
Selection of turning tiff into searchable PDF or scanned PDF. Online demo allows converting tiff to PDF online. C# source codes are provided to use in .NET class
www.rasteredge.com
252 Implementing derived collection classes
§14.1
lections
coll1
and
coll2
,using the given item equality comparer
eqc
.Returns
true
if the collections contain equal items with equal multiplicity, regardless of
their order; returns
false
otherwise. This method is efcient 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
O
(
m
+
n
)
where
m
and
n
are numbers of items of the two collections.
14.1.3 CollectionValueBase<T>
Abstract base class for implementing modiable and unmodiable 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.
Public methods
All
,
Apply
,
Exists
,
Filter
;
CopyTo
,
ToArray
.
14.1.4 DictionaryBase<K,V>
Abstract base class for implementing dictionary classes. The class has bases Collec-
tionValueBase<KeyValuePair<K,V>> and EnumerableBase<KeyValuePair<K,V>>.
14.1.5 DirectedCollectionBase<T>
Abstract base class for implementing directed collections. The class has elds and
methods from CollectionBase<T>, CollectionValueBase<T> and EnumerableBase<T>.
14.1.6 DirectedCollectionValueBase<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>.
14.1.7 EnumerableBase<T>
Abstract base class for implementing enumerable classes. The class has a public
method
GetEnumerator()
and protected methods for counting (by enumeration) the
number of items.
14.1.8 SequencedBase<T>
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
item sequence.
software control cloud:C# HTML5 PDF Viewer SDK to view PDF document online in C#.NET
Word, C# extract text from PDF, C# convert PDF to Jpeg, C# compress PDF, C# print PDF, C# merge PDF files, C# view PDF online, C# convert PDF to tiff, C# read
www.rasteredge.com
software control cloud:VB.NET PDF- View PDF Online with VB.NET HTML5 PDF Viewer
RasterEdge. PRODUCTS: ONLINE DEMOS: Online HTML5 Document Viewer; Online XDoc.PDF Demo▶: Convert PDF to Word; Convert PDF to Tiff; Convert PDF to HTML;
www.rasteredge.com
§14.1
Implementing derived collection classes 253
14.1.9 SortedDictionaryBase<K,V>
Abstract base class for implementing sorted dictionary classes such as SortedDic-
tionaryBase<K,V>. The class has elds and methods from
CollectionValueBase<KeyValuePair<K,V>>,DictionaryBase<K,V>,andEnumerable-
Base<KeyValuePair<K,V>>.
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
CollectionValueBase<T>
GuardedCollectionValue<T>
DirectedCollectionBase<T>
GuardedDirectedCollectionValue<T>
GuardedDirectedEnumerable<T>
EnumerableBase<T>
GuardedEnumerable<T>
GuardedEnumerator<T>
SequencedBase<T>
GuardedSequenced<T>
GuardedSorted<T>
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.
software control cloud:VB.NET PDF - Convert PDF Online with VB.NET HTML5 PDF Viewer
Word, C# extract text from PDF, C# convert PDF to Jpeg, C# compress PDF, C# print PDF, C# merge PDF files, C# view PDF online, C# convert PDF to tiff, C# read
www.rasteredge.com
software control cloud:RasterEdge XDoc.Tiff for .NET - SDK for Tiff Document Imaging
VB.NET developers and end-users have quick evaluation on our product, we provide comprehensive .NET sample codings online for reference. Convert Tiff to PDF.
www.rasteredge.com
254 Implementing derived collection classes
Bibliography
[1] Nunit. Web site. At
http://www.nunit.org/
.
[2] A.M. Andrew. Anotherefcient algorithm forconvex hulls intwo dimensions.
Information Processing Letters,9:216219,1979.
[3] K. Arnold, J. Gosling,and D. Holmes. TheJava ProgrammingLanguage.
Addison-Wesley, fourth edition, 2005.
[4] M. Bender etal. Two simplied algorithms for maintaining order ina list. In 10th
Annual European Symposiumon Algorithms (ESA 2002),Rome,Italy, September 2002.
LectureNotesin ComputerScience, vol. 2461, pages 152164. Springer-Verlag, 2002.
[5] JonBentley, D. E. Knuth,and M.D. McIlroy. Programming pearls: A literate program.
Communications of theACM, 29(6):471483,June 1986.
[6] Joshua Bloch. Effective Java Programming LanguageGuide. Addison-Wesley,2001.
[7] W.R. Cook. Interfacesand specications forthe Smalltalk-80 collection classes. In
Conference on Object-Oriented Programming Systems,Languages, and Applications
(OOPSLA1992). SIGPLAN Notices27,10,pages 115, 1992.
[8] Copenhagen STL. Homepage. Web site. At
http://www.cphstl.dk/
.
[9] T.H. Cormen, C.E. Leiserson, R.L.Rivest, and C. Stein. Introductionto Algorithms.
The MIT Press, second edition, 2001.
[10] J. Driscoll, N. Sarnak, D.Sleator, and R. Tarjan. Makingdata structures persistent.
Journal of Computer and Systems Sciences, 38(1):86124, 1989.
[11] Ecma TC39 TG2. C# Language Specication. StandardECMA-334, 3rd edition. June
2005. At
http://www.ecma-international.org/publications/standards/Ecma-334.htm
.
[12] Ecma TC39 TG3. CommonLanguage Infrastructure (CLI).Standard ECMA-335, 3rd
edition. June 2005. At
http://www.ecma-international.org/publications/standards/Ecma-335.htm
.
[13] 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 1112. Springer-Verlag, 1999. At
http://www.informatik.uni-ulm.de/rs/projekte/proglang/jdk.ps
.
[14] A.Goldberg and D. Robson. Smalltalk 80: The Language. Addison-Wesley, 1989.
[15] P.Golde. PowerCollections for .NET. Web site. At
http://www.wintellect.com/MemberOnly/PowerCollections.aspx
.
255
256 Bibliography
[16] R. Graham. An efcient algorithm for determining the convex hull of a nite point set.
Information ProcessingLetters, 1:132133, 1972.
[17] Anders Hejlsberg, Scott Wiltamuth, and Peter Golde. TheC# Programming Language.
Addison-Wesley, 2003.
[18] NielsJłrgen Kokholm. Anextended library of collectionclasses for.NET. Master’s
thesis, IT University of Copenhagen, Denmark, 2004.
[19] George Marsaglia. Re: New random generator. Posting to newsgroup comp.lang.c,
April 2003. Posted 2003-04-03.
[20] George Marsaglia. Seeds forrandom number generators. Communications of theACM,
46(5):9093, 2003.
[21] G. Mengeret al. Collectiontypes and implementations in object-oriented software
libraries. InConferenceon Technology of Object-Oriented Languages and Systems,
Santa Barbara, 1998,pages 97109,1998.
[22] Microsoft. Microsoft .NET framework developer center. Web site. At
http://msdn.microsoft.com/netframework/
.
[23] David R. Musser. Introspective sortingand selection algorithms. Software-Practice and
Experience,27(8):983993, 1997.
[24] Rasmus Paghand Flemming Rodler. Cuckoo hashing. Journal of Algorithms,
51(2):122144, 2004.
[25] N.Sarnak and R.E. Tarjan. Planarpoint location usingpersistent searchtrees.
Communications of theACM, 29(7):669679, 1986.
[26] Robert Sedgewick. Algorithms. Addison-Wesley, second edition,1988.
[27] P. Sestoft and H. I.Hansen. C# Precisely. Cambridge, Massachusetts: The MIT Press,
October 2004.
[28] 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.
[29] D. Sleator and P.Dietz. Two algorithms for maintainingorderin a list. In 19th ACM
Symposium on the Theory of Computing (STOC’87), pages 365372.ACMPress, 1987.
[30] D. Syme. F#. Web site. At
http://research.microsoft.com/projects/ilx/fsharp.aspx
.
[31] R.E. Tarjan. Data Structures andNetwork Algorithms. Societyfor Industrial and
Applied Mathematics, 1983.
[32] VijayV. Vazirani. ApproximationAlgorithms. Springer-Verlag, 2001.
Index 257
Index
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
actiondelegate, 38
Action<T> delegate type
corresponds to Act<T>, 38
ActiveEvents
property
ICollectionValue<T>,49
Add
method
IDictionary<K,V>, 99
IExtensible<T>, 55
IPriorityQueue<T>, 80
SC.IList,68
SCG.ICollection<T>,44,68
AddAll
method
IDictionary<K,V>, 99
IExtensible<T>, 56
Added
enum value (EventTypeEnum), 35
AddSorted
method
ISorted<T>,88
ISortedDictionary<K,V>, 102
All
enumvalue (EventTypeEnum),35
All
method (ICollectionValue<T>), 49
AllowsDuplicates
property
ArrayList<T>,111
HashBag<T>, 117
HashedArrayList<T>,112
HashedLinkedList<T>,113
HashSet<T>, 116
IExtensible<T>, 55
IntervalHeap<T>,118
IQueue<T>, 83
IStack<T>, 94
LinkedList<T>, 112
overview,109
SortedArrayList<T>,114
TreeBag<T>, 116
TreeSet<T>,115
WrappedArray<T>,114
amortized complexity, 233
anagram classes (example), 202203
anti-pattern
arraylist as queue, 192
bad hash function, 194
collectionof collections, 195
hashed linked list indexer,192
IndexOf
method onlist, 191,192
linked list, 191
list
IndexOf
,191
list
RemoveAll
,
RetainAll
,190
list as set, 193
priority queue insorted array,193
sorted array, 189
sorted arrayas priority queue, 193
anti-symmetricrelation,30,31
Apply
method (ICollectionValue<T>),49
arbitrary item,167
ArgumentException,39
ArgumentOutOfRangeException, 39
array
sorted, 114115
sorting, 134
wrapped, 113114
array list, 111112
hashed,112113
queue (anti-pattern), 192
ArrayBase<T>class,251
ArrayList<T>class,111
constructor, 111
listenable events, 139
source le,241
associative array,19
Backwards
enum value
EnumerationDirection, 36
Backwards
method
IDirectedCollectionValue<T>, 52
IDirectedEnumerable<T>,54
bag
hash-based,117118
semantics, 55
tree-based,116
base classes
collection, 251253
Basic
enum value (EventTypeEnum), 35
batchjob queue (example),218
Bentley, Jon, 231
BinaryFormatterclass,143
Bond, James, 2
breadth-rst traversal, 182
258 Index
bucket in hashtable,117
BucketCostDistribution
method
HashDictionary<K,V>, 120
HashSet<T>, 117,194
building C5 from source,242
ByteComparer class, 32
ByteEqualityComparer class, 28
C5Random class, 41
source le,241
cached hashcode, 45, 243
Changed
enum value (EventTypeEnum),
35
CharComparer class, 32
CharEqualityComparer class, 28
Check
method
IDictionary<K,V>, 99
IExtensible<T>, 56
Choose
method (ICollectionValue<T>),50
circular queue, 111
CircularQueue<T> class, 17, 111
constructor, 111
listenable events, 139
source le,241
Clear
method
ICollection<T>,45
IDictionary<K,V>, 99
view, 128
Cleared
enum value (EventTypeEnum),
35
ClearedEventArgs class, 141
constructor, 141
ClearedRangeEventArgs class, 141
constructor, 141
Clone
method
ICloneable, 142
IDictionary<K,V>, 99
IExtensible<T>, 56
IList<T>, 68
ISortedDictionary<K,V>, 103
cloneable, 12, 142
cloning, 142
guarded collection, 142
list view, 142
co-variance, lack of, 133
collection, 14
base classes, 251253
class hierarchy,110
directed,14
extensible, 14
guarded,130
indexed,15
indexed sorted, 16
inner,132
interface hierarchy, 43
of collections,132, 170172
anti-pattern, 195
outer, 132
persistent sorted, 16
sequenced, 15
sorted,16
CollectionBase<T>class,251
CollectionChanged event
(ICollectionValue<T>),51, 137
CollectionChangedHandler<T> delegate
type,139
CollectionCleared event
(ICollectionValue<T>),51, 137
CollectionClearedHandler<T> delegate
type,139
CollectionModiedException,39
CollectionValueBase<T> class, 252
common words (example), 231232
Compare
method (IComparer<T>), 31
comparer
classes, 3133
item, 25
lexicographic, 187
natural, 32
patterns, 187188
reverse,187
Comparer
property
IComparer<T>, 88
IPriorityQueue<T>,80
ISortedDictionary<K,V>,102
Comparer<T> class, 32
source le, 241
CompareTo
method
IComparable, 31
IComparable<T>,30
comparisondelegate, 33
example, 232
Comparison<T>delegate (System), 33
and DelegateComparer<T>, 33
example, 232
complexity
amortized, 233
concordance (example),199
Documents you may be interested
Documents you may be interested