Class Bag<T>

Bag<T> is a collection that contains items of type T. Unlike a Set, duplicate items (items that compare equal to each other) are allowed in an Bag.

Inheritance

System.Object

CollectionBase<T>

Bag<T>

Implements

System.Collections.Generic.ICollection<T>

System.Collections.Generic.IEnumerable<T>

System.Collections.ICollection

System.Collections.IEnumerable

System.ICloneable

Inherited Members

CollectionBase<T>.ToString()

CollectionBase<T>.CopyTo(T[], Int32)

CollectionBase<T>.ToArray()

CollectionBase<T>.ICollection<T>.IsReadOnly

CollectionBase<T>.AsReadOnly()

CollectionBase<T>.Exists(Predicate<T>)

CollectionBase<T>.TrueForAll(Predicate<T>)

CollectionBase<T>.CountWhere(Predicate<T>)

CollectionBase<T>.FindAll(Predicate<T>)

CollectionBase<T>.RemoveAll(Predicate<T>)

CollectionBase<T>.ForEach(Action<T>)

CollectionBase<T>.ConvertAll<TOutput>(Converter<T, TOutput>)

CollectionBase<T>.ICollection.CopyTo(Array, Int32)

CollectionBase<T>.ICollection.IsSynchronized

CollectionBase<T>.ICollection.SyncRoot

CollectionBase<T>.IEnumerable.GetEnumerator()

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

Namespace: Wintellect.PowerCollections

Assembly: CADability.dll

Syntax

[Serializable]
public class Bag<T> : CollectionBase<T>, ICollection<T>, IEnumerable<T>, ICollection, IEnumerable, ICloneable

Type Parameters

Name	Description
T

Remarks

The items are compared in one of two ways. If T implements IComparable<T> then the Equals method of that interface will be used to compare items, otherwise the Equals method from Object will be used. Alternatively, an instance of IComparer<T> can be passed to the constructor to use to compare items.

Bag is implemented as a hash table. Inserting, deleting, and looking up an an element all are done in approximately constant time, regardless of the number of items in the bag.

When multiple equal items are stored in the bag, they are stored as a representative item and a count. If equal items can be distinguished, this may be noticable. For example, if a case-insensitive comparer is used with a Bag<string>, and both "hello", and "HELLO" are added to the bag, then the bag will appear to contain two copies of "hello" (the representative item).

is similar, but uses comparison instead of hashing, maintain the items in sorted order, and stores distinct copies of items that compare equal.

Constructors

| Improve this Doc View Source

Bag()

Creates a new Bag.

Declaration

public Bag()

Remarks

Items that are null are permitted.

| Improve this Doc View Source

Bag(IEnumerable<T>)

Creates a new Bag. The bag is initialized with all the items in the given collection.

Declaration

public Bag(IEnumerable<T> collection)

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<T>	collection	A collection with items to be placed into the Bag.

Remarks

Items that are null are permitted.

| Improve this Doc View Source

Bag(IEnumerable<T>, IEqualityComparer<T>)

Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object will be used to compare items in this bag. The bag is initialized with all the items in the given collection.

Declaration

public Bag(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<T>	collection	A collection with items to be placed into the Bag.
System.Collections.Generic.IEqualityComparer<T>	equalityComparer	An instance of IEqualityComparer<T> that will be used to compare items.

| Improve this Doc View Source

Bag(IEqualityComparer<T>)

Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object will be used to compare items in this bag for equality.

Declaration

public Bag(IEqualityComparer<T> equalityComparer)

Parameters

Type	Name	Description
System.Collections.Generic.IEqualityComparer<T>	equalityComparer	An instance of IEqualityComparer<T> that will be used to compare items.

Properties

| Improve this Doc View Source

Comparer

Returns the IEqualityComparer<T> used to compare items in this bag.

Declaration

public IEqualityComparer<T> Comparer { get; }

Property Value

Type	Description
System.Collections.Generic.IEqualityComparer<T>	If the bag was created using a comparer, that comparer is returned. Otherwise the default comparer for T (EqualityComparer<T>.Default) is returned.

| Improve this Doc View Source

Count

Returns the number of items in the bag.

Declaration

public override sealed int Count { get; }

Property Value

Type	Description
System.Int32	The number of items in the bag.

Overrides

Wintellect.PowerCollections.CollectionBase<T>.Count

Remarks

The size of the bag is returned in constant time.

Methods

| Improve this Doc View Source

Add(T)

Adds a new item to the bag. Since bags can contain duplicate items, the item is added even if the bag already contains an item equal to item. In this case, the count of items for the representative item is increased by one, but the existing represetative item is unchanged.

Declaration

public override sealed void Add(T item)

Parameters

Type	Name	Description
T	item	The item to add to the bag.

Overrides

Wintellect.PowerCollections.CollectionBase<T>.Add(T)

Remarks

Adding an item takes approximately constant time, regardless of the number of items in the bag.

| Improve this Doc View Source

AddMany(IEnumerable<T>)

Adds all the items in collection to the bag.

Declaration

public void AddMany(IEnumerable<T> collection)

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<T>	collection	A collection of items to add to the bag.

Remarks

Adding the collection takes time O(M log N), where N is the number of items in the bag, and M is the number of items in collection.

| Improve this Doc View Source

AddRepresentative(T)

Adds a new item to the bag. Since bags can contain duplicate items, the item is added even if the bag already contains an item equal to item. In this case (unlike Add), the new item becomes the representative item.

Declaration

public void AddRepresentative(T item)

Parameters

Type	Name	Description
T	item	The item to add to the bag.

Remarks

Adding an item takes approximately constant time, regardless of the number of items in the bag.

| Improve this Doc View Source

ChangeNumberOfCopies(T, Int32)

Changes the number of copies of an existing item in the bag, or adds the indicated number of copies of the item to the bag.

Declaration

public void ChangeNumberOfCopies(T item, int numCopies)

Parameters

Type	Name	Description
T	item	The item to change the number of copies of. This may or may not already be present in the bag.
System.Int32	numCopies	The new number of copies of the item.

Remarks

Changing the number of copies takes approximately constant time, regardless of the number of items in the bag.

| Improve this Doc View Source

Clear()

Removes all items from the bag.

Declaration

public override sealed void Clear()

Overrides

Wintellect.PowerCollections.CollectionBase<T>.Clear()

Remarks

Clearing the bag takes a constant amount of time, regardless of the number of items in it.

| Improve this Doc View Source

Clone()

Makes a shallow clone of this bag; i.e., if items of the bag are reference types, then they are not cloned. If T is a value type, then each element is copied as if by simple assignment.

Declaration

public Bag<T> Clone()

Returns

Type	Description
Bag<T>	The cloned bag.

Remarks

Cloning the bag takes time O(N), where N is the number of unquie items in the bag.

| Improve this Doc View Source

CloneContents()

Makes a deep clone of this bag. A new bag is created with a clone of each element of this bag, by calling ICloneable.Clone on each element. If T is a value type, then each element is copied as if by simple assignment.

Declaration

public Bag<T> CloneContents()

Returns

Type	Description
Bag<T>	The cloned bag.

Remarks

If T is a reference type, it must implement ICloneable. Otherwise, an InvalidOperationException is thrown.

Cloning the bag takes time O(N log N), where N is the number of items in the bag.

Exceptions

Type	Condition
System.InvalidOperationException	T is a reference type that does not implement ICloneable.

| Improve this Doc View Source

Contains(T)

Determines if this bag contains an item equal to item. The bag is not changed.

Declaration

public override sealed bool Contains(T item)

Parameters

Type	Name	Description
T	item	The item to search for.

Returns

Type	Description
System.Boolean	True if the bag contains `item`. False if the bag does not contain `item`.

Overrides

Wintellect.PowerCollections.CollectionBase<T>.Contains(T)

Remarks

Searching the bag for an item takes time O(log N), where N is the number of items in the bag.

| Improve this Doc View Source

Difference(Bag<T>)

Computes the difference of this bag with another bag. The difference of these two bags is all items that appear in this bag, but not in otherBag. If an item appears X times in this bag, and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X). A new bag is created with the difference of the bags and is returned. This bag and the other bag are unchanged.

Declaration

public Bag<T> Difference(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to difference with.

Returns

Type	Description
Bag<T>	The difference of the two bags.

Remarks

The difference of two bags is computed in time O(M + N), where M and N are the size of the two bags.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

DifferenceWith(Bag<T>)

Computes the difference of this bag with another bag. The difference of these two bags is all items that appear in this bag, but not in otherBag. If an item appears X times in this bag, and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X). This bag receives the difference of the two bags; the other bag is unchanged.

Declaration

public void DifferenceWith(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to difference with.

Remarks

The difference of two bags is computed in time O(M), where M is the size of the other bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

DistinctItems()

Enumerates all the items in the bag, but enumerates equal items just once, even if they occur multiple times in the bag.

Declaration

public IEnumerable<T> DistinctItems()

Returns

Type	Description
System.Collections.Generic.IEnumerable<T>	An IEnumerable<T> that enumerates the unique items.

Remarks

If the bag is changed while items are being enumerated, the enumeration will terminate with an InvalidOperationException.

| Improve this Doc View Source

GetEnumerator()

Returns an enumerator that enumerates all the items in the bag. If an item is present multiple times in the bag, the representative item is yielded by the enumerator multiple times. The order of enumeration is haphazard and may change.

Declaration

public override sealed IEnumerator<T> GetEnumerator()

Returns

Type	Description
System.Collections.Generic.IEnumerator<T>	An enumerator for enumerating all the items in the Bag.

Overrides

Wintellect.PowerCollections.CollectionBase<T>.GetEnumerator()

Remarks

Typically, this method is not called directly. Instead the "foreach" statement is used to enumerate the items, which uses this method implicitly.

If an item is added to or deleted from the bag while it is being enumerated, then the enumeration will end with an InvalidOperationException.

Enumeration all the items in the bag takes time O(N), where N is the number of items in the bag.

| Improve this Doc View Source

GetRepresentativeItem(T, out T)

Returns the representative item stored in the bag that is equal to the provided item. Also returns the number of copies of the item in the bag.

Declaration

public int GetRepresentativeItem(T item, out T representative)

Parameters

Type	Name	Description
T	item	Item to find in the bag.
T	representative	If one or more items equal to `item` are present in the bag, returns the representative item. If no items equal to `item` are stored in the bag, returns `item`.

Returns

Type	Description
System.Int32	The number of items equal to `item` stored in the bag.

| Improve this Doc View Source

Intersection(Bag<T>)

Computes the intersection of this bag with another bag. The intersection of two bags is all items that appear in both of the bags. If an item appears X times in one bag, and Y times in the other bag, the intersection contains the item Minimum(X,Y) times. A new bag is created with the intersection of the bags and is returned. This bag and the other bag are unchanged.

Declaration

public Bag<T> Intersection(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to intersection with.

Returns

Type	Description
Bag<T>	The intersection of the two bags.

Remarks

When equal items appear in both bags, the intersection will include an arbitrary choice of one of the two equal items.

The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IntersectionWith(Bag<T>)

Computes the intersection of this bag with another bag. The intersection of two bags is all items that appear in both of the bags. If an item appears X times in one bag, and Y times in the other bag, the sum contains the item Minimum(X,Y) times. This bag receives the intersection of the two bags, the other bag is unchanged.

Declaration

public void IntersectionWith(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to intersection with.

Remarks

When equal items appear in both bags, the intersection will include an arbitrary choice of one of the two equal items.

The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsDisjointFrom(Bag<T>)

Determines if this bag is disjoint from another bag. Two bags are disjoint if no item from one set is equal to any item in the other bag.

Declaration

public bool IsDisjointFrom(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to check disjointness with.

Returns

Type	Description
System.Boolean	True if the two bags are disjoint, false otherwise.

Remarks

The answer is computed in time O(N), where N is the size of the smaller set.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsEqualTo(Bag<T>)

Determines if this bag is equal to another bag. This bag is equal to otherBag if they contain the same number of of copies of equal elements.

Declaration

public bool IsEqualTo(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to compare to

Returns

Type	Description
System.Boolean	True if this bag is equal to `otherBag`, false otherwise.

Remarks

IsSupersetOf is computed in time O(N), where N is the number of unique items in this bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsProperSubsetOf(Bag<T>)

Determines if this bag is a proper subset of another bag. Neither bag is modified. This bag is a subset of otherBag if every element in this bag is also in otherBag, at least the same number of times. Additional, this bag must have strictly fewer items than otherBag.

Declaration

public bool IsProperSubsetOf(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to compare to.

Returns

Type	Description
System.Boolean	True if this is a proper subset of `otherBag`.

Remarks

IsProperSubsetOf is computed in time O(N), where N is the number of unique items in this bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsProperSupersetOf(Bag<T>)

Determines if this bag is a proper superset of another bag. Neither bag is modified. This bag is a proper superset of otherBag if every element in otherBag is also in this bag, at least the same number of times. Additional, this bag must have strictly more items than otherBag.

Declaration

public bool IsProperSupersetOf(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Set to compare to.

Returns

Type	Description
System.Boolean	True if this is a proper superset of `otherBag`.

Remarks

IsProperSupersetOf is computed in time O(M), where M is the number of unique items in otherBag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsSubsetOf(Bag<T>)

Determines if this bag is a subset of another ba11 items in this bag.

Declaration

public bool IsSubsetOf(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to compare to.

Returns

Type	Description
System.Boolean	True if this is a subset of `otherBag`.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

IsSupersetOf(Bag<T>)

Determines if this bag is a superset of another bag. Neither bag is modified. This bag is a superset of otherBag if every element in otherBag is also in this bag, at least the same number of times.

Declaration

public bool IsSupersetOf(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to compare to.

Returns

Type	Description
System.Boolean	True if this is a superset of `otherBag`.

Remarks

IsSupersetOf is computed in time O(M), where M is the number of unique items in otherBag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

NumberOfCopies(T)

Returns the number of copies of item in the bag.

Declaration

public int NumberOfCopies(T item)

Parameters

Type	Name	Description
T	item	The item to search for in the bag.

Returns

Type	Description
System.Int32	The number of items in the bag that compare equal to `item`.

Remarks

NumberOfCopies() takes approximately constant time, no matter how many items are stored in the bag.

| Improve this Doc View Source

Remove(T)

Searches the bag for one item equal to item, and if found, removes it from the bag. If not found, the bag is unchanged.

Declaration

public override sealed bool Remove(T item)

Parameters

Type	Name	Description
T	item	The item to remove.

Returns

Type	Description
System.Boolean	True if `item` was found and removed. False if `item` was not in the bag.

Overrides

Wintellect.PowerCollections.CollectionBase<T>.Remove(T)

Remarks

Equality between items is determined by the comparison instance or delegate used to create the bag.

Removing an item from the bag takes approximated constant time, regardless of the number of items in the bag.

| Improve this Doc View Source

RemoveAllCopies(T)

Searches the bag for all items equal to item, and removes all of them from the bag. If not found, the bag is unchanged.

Declaration

public int RemoveAllCopies(T item)

Parameters

Type	Name	Description
T	item	The item to remove.

Returns

Type	Description
System.Int32	The number of copies of `item` that were found and removed.

Remarks

Equality between items is determined by the comparer instance used to create the bag.

RemoveAllCopies() takes time O(M log N), where N is the total number of items in the bag, and M is the number of items equal to item.

| Improve this Doc View Source

RemoveMany(IEnumerable<T>)

Removes all the items in collection from the bag. Items that are not present in the bag are ignored.

Declaration

public int RemoveMany(IEnumerable<T> collection)

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<T>	collection	A collection of items to remove from the bag.

Returns

Type	Description
System.Int32	The number of items removed from the bag.

Remarks

Equality between items is determined by the comparer instance used to create the bag.

Removing the collection takes time O(M), where M is the number of items in collection.

Exceptions

Type	Condition
System.ArgumentNullException	`collection` is null.

| Improve this Doc View Source

Sum(Bag<T>)

Computes the sum of this bag with another bag. he sum of two bags is all items from both of the bags. If an item appears X times in one bag, and Y times in the other bag, the sum contains the item (X+Y) times. A new bag is created with the sum of the bags and is returned. This bag and the other bag are unchanged.

Declaration

public Bag<T> Sum(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to sum with.

Returns

Type	Description
Bag<T>	The sum of the two bags.

Remarks

The sum of two bags is computed in time O(M + N log M), where M is the size of the larger bag, and N is the size of the smaller bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

SumWith(Bag<T>)

Computes the sum of this bag with another bag. The sum of two bags is all items from both of the bags. If an item appears X times in one bag, and Y times in the other bag, the sum contains the item (X+Y) times. This bag receives the sum of the two bags, the other bag is unchanged.

Declaration

public void SumWith(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to sum with.

Remarks

The sum of two bags is computed in time O(M), where M is the size of the other bag..

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

SymmetricDifference(Bag<T>)

Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags is all items that appear in either of the bags, but not both. If an item appears X times in one bag, and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y) times. A new bag is created with the symmetric difference of the bags and is returned. This bag and the other bag are unchanged.

Declaration

public Bag<T> SymmetricDifference(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to symmetric difference with.

Returns

Type	Description
Bag<T>	The symmetric difference of the two bags.

Remarks

The symmetric difference of two bags is computed in time O(M + N), where M is the size of the larger bag, and N is the size of the smaller bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

SymmetricDifferenceWith(Bag<T>)

Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags is all items that appear in either of the bags, but not both. If an item appears X times in one bag, and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y) times. This bag receives the symmetric difference of the two bags; the other bag is unchanged.

Declaration

public void SymmetricDifferenceWith(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to symmetric difference with.

Remarks

The symmetric difference of two bags is computed in time O(M + N), where M is the size of the larger bag, and N is the size of the smaller bag.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

Union(Bag<T>)

Computes the union of this bag with another bag. The union of two bags is all items from both of the bags. If an item appears X times in one bag, and Y times in the other bag, the union contains the item Maximum(X,Y) times. A new bag is created with the union of the bags and is returned. This bag and the other bag are unchanged.

Declaration

public Bag<T> Union(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to union with.

Returns

Type	Description
Bag<T>	The union of the two bags.

Remarks

The union of two bags is computed in time O(M+N), where M and N are the size of the two bags.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

| Improve this Doc View Source

UnionWith(Bag<T>)

Computes the union of this bag with another bag. The union of two bags is all items from both of the bags. If an item appears X times in one bag, and Y times in the other bag, the union contains the item Maximum(X,Y) times. This bag receives the union of the two bags, the other bag is unchanged.

Declaration

public void UnionWith(Bag<T> otherBag)

Parameters

Type	Name	Description
Bag<T>	otherBag	Bag to union with.

Remarks

The union of two bags is computed in time O(M+N), where M and N are the size of the two bags.

Exceptions

Type	Condition
System.InvalidOperationException	This bag and `otherBag` don't use the same method for comparing items.

Explicit Interface Implementations

| Improve this Doc View Source

ICloneable.Clone()

Makes a shallow clone of this bag; i.e., if items of the bag are reference types, then they are not cloned. If T is a value type, then each element is copied as if by simple assignment.

Declaration

object ICloneable.Clone()

Returns

Type	Description
System.Object	The cloned bag.

Remarks

Cloning the bag takes time O(N), where N is the number of items in the bag.

Implements

System.Collections.Generic.ICollection<T>

System.Collections.Generic.IEnumerable<T>

System.Collections.ICollection

System.Collections.IEnumerable

System.ICloneable