§9.16
Patterns for removing duplicates 169
Pattern 78 Compute the difference between sets
s1
and
s2
in
s1
s1.RemoveAll(s2);
Pattern 79 Compute the symmetric difference between sets
s1
and
s2
The symmetric difference is the set of elements in one set but not in the other; it
equals (s1[s2)n(s1\s2) and equals (s1ns2)[(s2ns1). This computes thesymmetric
difference in a new set
su
.
HashSet<T> su = new HashSet<T>();
su.AddAll(s1);
su.AddAll(s2);
HashSet<T> si = new HashSet<T>();
si.AddAll(s1);
si.RetainAll(s2);
su.RemoveAll(si);
For sorted sets thesymmetric differencecan becomputedmoreefciently by travers-
ing the ordered sets in synchrony, in a way similar to a list merge.
9.16 Patterns for removing duplicates
Pattern 80 Keep only the rst occurrence in an enumerable
This method takes an enumerable and returns an array list with the items in the
same order, but keeping only the rst occurrence of each item. Pattern 81 shows
how to keep only the last occurrence of each item.
public static IList<T> RemoveLateDuplicates<T>(SCG.IEnumerable<T> enm) {
IList<T> res = new HashedArrayList<T>();
res.AddAll(enm);
return res;
}
Pattern 81 Keep only the last occurrence in a directed enumerable
This method takes a directed enumerable and returns an array list with the items
in the same order, but keeping only the last occurrence of each item. Pattern 80
shows how to keep only the rst occurrence of each item.
public static IList<T> RemoveEarlyDuplicates<T>(IDirectedEnumerable<T> enm) {
IList<T> res = new HashedArrayList<T>();
res.AddAll(enm.Backwards());
res.Reverse();
return res;
}
If the given enumerable
enm
is not directed, then one can create an ArrayList<T> of
its items and obtain a directed enumerable from that.
Pdf to tiff multipage - SDK software service: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 multipage - SDK software service: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
170 Patterns for collections of collections
§9.17
9.17 Patterns for collections of collections
Here are some patterns for creating a collection whose items are themselves collec-
tions. See also section 8.3.
Pattern 82 Create a hash set of lists with default (sequenced) equality
The default equality comparer created for an outer collection of inner collections
is a sequenced collection equality comparer or an unsequenced collection equality
comparer, depending on the type of the inner collection; see section 2.3. For lists,
the default is a sequenced equality comparer, which takes item order into account.
HashSet<IList<int>> hs1 = new HashSet<IList<int>>();
Hence the default equality comparer
hs1.EqualityComparer
created for the hash set
hs1
above would consider the two lists
coll1
and
coll2
equal because they have
the same items in the same order, whereas
coll3
is not equal to any of the others:
although it contains the same items, they do not appear in the same order. The
result is that
hs1
contains two items (list objects): one of
coll1
and
coll2
,as well as
coll3
:
IList<int> coll1 = new LinkedList<int>(),
coll2 = new LinkedList<int>(),
coll3 = new LinkedList<int>();
coll1.AddAll(new int[] { 7, 9, 13 });
coll2.AddAll(new int[] { 7, 9, 13 });
coll3.AddAll(new int[] { 9, 7, 13 });
hs1.Add(coll1); hs1.Add(coll2); hs1.Add(coll3);
// hs1.Count is 2
Pattern 83 Explicitly create a hash set of lists with sequenced equality
If desired, one can explicitly create a sequenced collection equality comparer
seqc
(section 2.3) and pass it to the constructor when creating the hash set. In fact, this
is exactly what happens implicitly in pattern 82.
SCG.IEqualityComparer<IList<int>> seqc
= new SequencedCollectionEqualityComparer<IList<int>,int>();
HashSet<IList<int>> hs2 = new HashSet<IList<int>>(seqc);
Equalities("Sequenced equality", hs2.EqualityComparer);
hs2.Add(coll1); hs2.Add(coll2); hs2.Add(coll3);
Toavoid taking list item order intoaccount, one couldcreate an UnsequencedCollec-
tionEqualityComparer<IList<
int
>,
int
>object and pass it to the constructor when
creating the hash set. But this is a bad idea, as the equality function will be very
slow except for short lists; see anti-pattern 124.
SDK software service:C# TIFF: C#.NET Code to Split Multipage TIFF File
XDoc.Tiff ›› C# Tiff: Split Tiff. C# TIFF - Split Multi-page TIFF File in C#.NET. C# Guide for How to Use TIFF Processing DLL to Split Multi-page TIFF File.
www.rasteredge.com
SDK software service:.NET Multipage TIFF SDK| Process Multipage TIFF Files
to work with .NET development environments, this Multipage TIFF Processing SDK on the Web, open and view TIFF files on to SharePoint and save to PDF documents.
www.rasteredge.com
§9.17
Patterns for collections of collections 171
Pattern 84 Create a hash set of lists using reference equality
To use reference equality and a corresponding hash function for a collection of col-
lections, one must explicitly create a reference equality comparer (section 2.3) and
pass it to the outer collection when it is created.
SCG.IEqualityComparer<IList<int>> reqc
= new ReferenceEqualityComparer<IList<int>>();
HashSet<IList<int>> hs4 = new HashSet<IList<int>>(reqc);
The equality comparer
hs4.EqualityComparer
usedby thehash set
hs4
created above
would consider the three lists
coll1
,
coll2
and
coll3
below unequal: they are dis-
tinct objects, created by distinct applications of
new
.The result is that
hs4
contains
three items: the three list objects:
hs4.Add(coll1); hs4.Add(coll2); hs4.Add(coll3);
Pattern 85 Check that all inner collections use the same equality comparer
When using a collection of collections it is crucial that the inner collections all
use the same equality comparer. Provided all equality comparers are obtained
from
EqualityComparer<T>.Default
,one can just check that the
EqualityComparer
property for all the inner collections are the same object. The two generic type
parameters and the type parameter constraint permits this method to work on
any collection whose items are extensible collections (and which therefore have the
EqualityComparer
property); it introduces a measure of co-variant subtyping other-
wise not available in C#.
public static bool HasherSanity<T,U>(ICollectionValue<U> colls)
where U : IExtensible<T>
{
SCG.IEqualityComparer<T> hasher = null;
foreach (IExtensible<T> coll in colls) {
if (hasher == null)
hasher = coll.EqualityComparer;
if (hasher != coll.EqualityComparer)
return false;
}
return true;
}
Pattern 86 Adding snapshot of inner collection to an outer collection
An inner collection should never be modied after it has been added to an outer
collection. One way to ensurethis is to createa copy of the inner collection and wrap
it as a guarded collection (to prevent modication of an inner collection retrieved
from an outer collection) before adding it to the outer collection. Snapshots of tree
sets and tree bags are read-only lightweight copies of the tree set and therefore ideal
for this purpose; see sections 4.9 and 8.5.
SDK software service:Process Multipage TIFF Images in Web Image Viewer| Online
Export multi-page TIFF image to a PDF; More image viewing & displaying functions. Multipage TIFF Processing. This page provides detailed
www.rasteredge.com
SDK software service:C# TIFF: C# Code for Multi-page TIFF Processing Using RasterEdge .
instance, adding & deleting Tiff file page, merging and splitting Tiff files, and loading & saving Tiff file to commonly used file formats, like PDF, Bmp, Jpeg
www.rasteredge.com
172 Patterns for collections of collections
§9.17
ICollection<ISequenced<int>> outer = new HashSet<ISequenced<int>>();
IPersistentSorted<int> inner1 = new TreeSet<int>();
inner1.AddAll(new int[] { 2, 3, 5, 7, 11 });
// Take a snapshot and add it to outer:
outer.Add(inner1.Snapshot());
// Modify inner1, but not the snapshot contained in outer:
inner1.Add(13);
Pattern 87 Create a set of sets of integers
After this piece of code, the set bound to
outer
contains ve sets of integers, namely
the sets fg and f
2
gand f
2
;
3
gand f
2
;
3
;
5
gand f
2
;
3
;
5
;
7
g. In cases like this where the
inner sets being added are modications of each other, it is absolutely essential that
only snapshots of the collection bound to
inner
,not that collection itself, are added
to the outer collection.
ICollection<ISequenced<int>> outer = new HashSet<ISequenced<int>>();
int[] ss = { 2, 3, 5, 7 };
TreeSet<int> inner = new TreeSet<int>();
outer.Add(inner.Snapshot());
foreach (int i in ss) {
inner.Add(i);
outer.Add(inner.Snapshot());
}
Pattern 88 Create a set of bags of characters
It is straightforward to create a set of bags of characters as a hash set of hash bags
of characters. As further elaborated in the section 11.4 example, this can be used
to nd anagrams. Note that a new bag object is created for each word added to the
set of bags; hence there is no need to create a copy For defensive programming, one
might wrap each hash bag as a GuardedCollection<
char
>before storing it in the set
of bags.
String text =
@"three sorted streams aligned by leading masters ... algorithm.";
String[] words = text.Split(’ ’, ’\n’, ’\r’, ’;’, ’,’, ’.’);
ICollection<ICollection<char>> anagrams = new HashSet<ICollection<char>>();
int count = 0;
foreach (String word in words) {
if (word != "") {
count++;
HashBag<char> anagram = new HashBag<char>();
anagram.AddAll(word.ToCharArray());
anagrams.Add(anagram);
}
}
Console.WriteLine("Found {0} anagrams", count - anagrams.Count);
SDK software service:Process Multipage TIFF Images in .NET Winforms | Online Tutorials
Swap a Page in a Multipage TIFF Image. Multi-page Tiff Processing; RasterEdge OCR Engine; PDF Reading; Encode & Decode JBIG 2 Files;
www.rasteredge.com
SDK software service:VB.NET Image: Multi-page TIFF Editor SDK; Process TIFF in VB.NET
VB.NET Imaging - Multi-page TIFF Processing in VB. VB.NET TIFF Editor SDK to Process Multi-page TIFF Document Image. Visual C#. VB.NET.
www.rasteredge.com
§9.18
Patterns for creating a random selection 173
9.18 Patterns for creating a random selection
Pattern 89 Create random selection with replacement
Let
coll
be an efciently indexable indexed collection, such as ArrayList<T>, and
let
N
0
be an integer. Then this code obtains
N
random items from
coll
,with
replacement.
public static SCG.IEnumerable<T> RandomWith<T>(IIndexed<T> coll, int N) {
for (int i=N; i>0; i--) {
T x = coll[rnd.Next(coll.Count)];
yield return x;
}
}
Pattern 90 Create a (large) random selection without replacement
Let
list
be a list collection, and let
N
where
0
N <list:Count be an integer. Then
N
random items from
coll
may be selected, without replacement, as shown below.
Note that this modies the given list.
public static SCG.IEnumerable<T> RandomWithout1<T>(IList<T> list, int N) {
list.Shuffle(rnd);
foreach (T x in list.View(0, N))
yield return x;
}
Pattern 91 Create a (small) random selection without replacement
Pattern 90is simpleand quite efcient when
N
and
list.Count
are ofthesameorder
of magnitude. When
N
is much smaller than
list.Count
,the following is faster but
requires the list to be an ArrayList<T> so that it supports fast indexing. Note that
this too modies the given list.
public static SCG.IEnumerable<T> RandomWithout2<T>(ArrayList<T> list, int N) {
for (int i=N; i>0; i--) {
int j = rnd.Next(list.Count);
T x = list[j], replacement = list.RemoveLast();
if (j < list.Count)
list[j] = replacement;
yield return x;
}
}
SDK software service:C# Raster - Image Save Options in C#.NET
VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET PowerPoint, VB.NET Tiff, VB.NET Imaging, VB.NET OCR, VB.NET Twain, VB.NET TIFF(Tiff). MultiPage:
www.rasteredge.com
SDK software service:C# PDF insert image Library: insert images into PDF in C#.net, ASP
Add multiple images to multipage PDF document in .NET WinForms. Jpeg or Jpg, Png, Gif, Bmp, Tiff and other Powerful .NET PDF image edit control, enable users to
www.rasteredge.com
174 Patterns for sorting
§9.19
9.19 Patterns for sorting
9.19.1 Quicksort for array lists
Let
enm
be an SCG.IEnumerable<T> and
cmp
an SCG.IComparer<T>. An array list
containing
enm
’s items sortedaccording to
cmp
can be obtained as follows, preserving
duplicates of items that compare equal:
IList<T> result = new ArrayList<T>();
result.AddAll(enm);
result.Sort(cmp);
9.19.2 Merge sort for linked lists
Let
enm
be an SCG.IEnumerable<T> and
cmp
an SCG.IComparer<T>. A linked list
containing
enm
’s items sorted according to
cmp
can be obtained as follows:
IList<T> result = new LinkedList<T>();
result.AddAll(enm);
result.Sort(cmp);
This operation preserves duplicates of items that compare equal, and preserves the
order of equal items: two items that compare equal will appear in the same order in
the result as in
enm
. This takes time
O
(
nlog n
), but is likely to be somewhat slower
than creating a sorted array list above.
9.19.3 Heap sort using a priority queue
Let
enm
be an SCG.IEnumerable<T>,
cmp
an SCG.IComparer<T> and N an integer.
Asequence ofthe N least items of
enm
(in increasing order)can be createdas follows:
IPriorityQueue<T> queue = new IntervalHeap<T>(enm);
queue.AddAll(enm);
IList<T> result = new ArrayList<T>();
int k = N;
while (!queue.IsEmpty && k-- > 0)
result.Add(queue.DeleteMin());
Using
queue.DeleteMax()
instead of
queue.DeleteMin()
gives a list (in descending
order) of the N greatest items of enm.
When N equals the initial
queue.Count
,this will implement heapsort, but al-
though it will have guaranteed worst-case execution time
O
(
nlog n
)it will be slower
than the introspective quicksort implemented in C5. When N is much smaller than
the initial
queue.Count
,the above procedure may be faster, but it is unlikely.
9.19.4 Sorting arrays
Class Sorting provides several methods for sorting a one-dimensional array or a of
segment of one; see section 8.6.
§9.19
Patterns for sorting 175
9.19.5 Sorting by bulk insertion into a SortedArray<T>
Let
enm
be an SCG.IEnumerable<T> and
cmp
an SCG.IComparer<T>. Asorted-array
list containing
enm
’s items sorted according to
cmp
can be obtained as follows:
IList<T> res = new SortedArray<T>(cmp);
res.AddAll(enm);
After this operation items are stored in increasing order in
res
,but duplicate items
(items that compare equal) have been discarded. The
AddAll
operation on SortedAr-
ray<T> is guaranteed efcient: the above operation takes time
O
(
nlog n
). In partic-
ular,
AddAll()
does not insert the items of
enm
one by one into the sorted array.
9.19.6 Finding a permutation that would sort a list
Sometimes (1) the permutation that would sort a collection is more interesting than
the sorted collection itself; or (2) the items in the collection appear in some order
that should be preserved, while at the same time the must be accessed in sorted
order; or (3) the items to be sorted are very large structs, and it would be good to
avoid the copying of items implied by standard sorting algorithms.
Pattern 92 achieves goals (1), (2) and (3) and applies to collections with fast
indexing, such as array lists, whereas pattern 93 achieves only goals (1) and (2) but
applies also to collections without fast indexing, such as linked lists.
Pattern 92 Finding a permutation that would sort an array list
Given a list
list
ofcomparable items, this method creates and returns an array list
res
of distinct integer indexes such that the functional composition of
list
and
res
is sorted. In other words, whenever
i<=j
it holds that
list[res[i]]<=list[res[j]]
.
It works by sorting the array list
res
of indexes using a comparer that compares
integers
i
and
j
by comparing the items
list[i]
and
list[j]
in the given list. That
is, it rearranges the indexes in
res
but does not move the items in
list
,which may
actually be a read-only list.
This method is fast when
list
is an array list and similar, but not stable. It is
slow for linked lists because it performs random access to list items by index.
public static ArrayList<int> GetPermutation1<T>(IList<T> list)
where T : IComparable<T>
{
ArrayList<int> res = new ArrayList<int>(list.Count);
for (int i = 0; i < list.Count; i++)
res.Add(i);
res.Sort(new DelegateComparer<int>
(delegate(int i, int j) { return list[i].CompareTo(list[j]); }));
return res;
}
176 Patterns for sorting
§9.19
Pattern 93 Find the permutation that would stably sort a linked list
Like the preceding pattern 92 this method creates and returns an array list
res
of distinct integer indexes such that the functional composition of
list
and
res
is
sorted. In other words, whenever
i<=j
it holds that
list[res[i]]<=list[res[j]]
.
It works by creating a new linked list of pairs, each pair consisting of an item
from the given list and the index of that item. Then it sorts the list of pairs, based
on comparison of the items only. Finally it extracts the (now reordered) list of in-
dexes
res
.Note that the given list may be read-only, as only the items of the newly
constructed list of pairs are reordered.
This method performs a stable sort (which means that the indexes ofequal items
will come in increasing order in the result) and is fairly fast both for array lists and
linked lists, but in contrast to pattern 92 it does copy the given list’s items.
public static ArrayList<int> GetPermutation2<T>(IList<T> list)
where T : IComparable<T>
{
int i = 0;
IList<KeyValuePair<T,int>> zipList =
list.Map<KeyValuePair<T,int>>
(delegate(T x) { return new KeyValuePair<T,int>(x, i++); });
zipList.Sort(new KeyValueComparer<T>(list));
ArrayList<int> res = new ArrayList<int>(list.Count);
foreach (KeyValuePair<T, int> p in zipList)
res.Add(p.value);
return res;
}
private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T,int>>
where T : IComparable<T>
{
private readonly IList<T> list;
public KeyValueComparer(IList<T> list) {
this.list = list;
}
public int Compare(KeyValuePair<T,int> p1, KeyValuePair<T,int> p2) {
return p1.key.CompareTo(p2.key);
}
}
These methods to nd the permutation that would sort a list can be used also to
efciently nd the quantile rank of all items in a list; see pattern 106.
§9.20
Patterns using priority queue handles 177
9.20 Patterns using priority queue handles
Apriority queue is a collection that permits efcient retrieval of a minimal or max-
imal item from the collection. In addition, C5’s priority queue implementation per-
mits retrieval, deletion and updating of items using a so-called handle, which is a
unique identication of the item. The comparer of the items cannot be used for this
purpose because the priority queue may contain multiple items that have the same
priority, so they compare equal by the comparer used in the priority queue.
These patterns showtypical uses ofpriority queue handles. Let
pq
be an IPriori-
tyQueue<T>, such as IntervalHeap<T>, and let
h
be an IPriorityQueueHandle<T>.
Pattern 94 Add item
x
into a priority queue, getting a new handle for it in
h
h = null;
pq.Add(ref h, x)
Pattern 95 Add item
x
into a priority queue, reusing handle
h
for it
pq.Add(ref h, x)
Pattern 96 Check whether the item with handle
h
is (still) in the priority queue,
and if so, get it in variable
x
bool isInPq = pq.Find(h, out x)
Pattern 97 Get and delete the item
x
with handle
h
T x = pq.Delete(h)
Pattern 98 Two ways to replace the item having handle
h
with item
x
pq[h] = x
pq.Replace(h, x)
Pattern 99 Get the current least (greatest) item into
min
and its handle into
h
T min = pq.FindMin(out h)
T max = pq.FindMax(out h)
Pattern 100 Get and delete the current least (greatest) item and its handle
T min = pq.DeleteMin(out h)
T max = pq.DeleteMax(out h)
178 Patterns using priority queue handles
§9.21
Pattern 101 Decrease key and increase key
An item in a priority queue often consists of some data of type D and an associated
updatable number representing a priority, an completion time, a weight, or similar.
If we assume that the data type D is a reference type, we may dene a struct type
Prio<D> that holds a Dreference and the priority, and so that implements ICompa-
rable<Prio<D>> by comparing the item priorities:
struct Prio<D> : IComparable<Prio<D>> where D : class
{
public readonly D data;
private int priority;
public Prio(D data, int priority) {
this.data = data; this.priority = priority;
}
public int CompareTo(Prio<D> that) {
return this.priority.CompareTo(that.priority);
}
public bool Equals(Prio<D> that) {
return this.priority == that.priority;
}
... more, see below ...
}
Now one can overload the operators (
+
)and (
-
)in struct Prio<D> to allow expres-
sions such as
prio+7
and
prio-3
where
prio
has type Prio<D>:
public static Prio<D> operator+(Prio<D> prio, int delta) {
return new Prio<D>(prio.data, prio.priority + delta);
}
public static Prio<D> operator-(Prio<D> prio, int delta) {
return new Prio<D>(prio.data, prio.priority - delta);
}
This gives an elegant way of adjusting priorities using priority queue handles:
IPriorityQueue<Prio<String>> pq = new IntervalHeap<Prio<String>>();
IPriorityQueueHandle<Prio<String>> h1 = null, h2 = null;
pq.Add(ref h1, new Prio<String>("surfing", 10));
pq.Add(ref h2, new Prio<String>("cleaning", 6));
pq[h1] += 7;
pq[h2] -= 3;
The last two statements are equivalent to the following more explicit statements:
pq.Replace(h1, pq[h1] + 7);
pq.Replace(h2, pq[h2] - 3);
These operators on priority queues are known as increasekeyanddecrease key. With
the implementation shown above these operations have time complexity
O
(
logn
).
Documents you may be interested
Documents you may be interested