?? orderedbag.cs
字號:
/// <para>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.</para>
/// </remarks>
/// <param name="otherBag">Bag to symmetric difference with.</param>
/// <returns>The symmetric difference of the two bags.</returns>
/// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
/// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
public OrderedBag<T> SymmetricDifference(OrderedBag<T> otherBag)
{
CheckConsistentComparison(otherBag);
OrderedBag<T> result = new OrderedBag<T>(comparer);
IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherBag.GetEnumerator();
bool valid1 = enum1.MoveNext();
bool valid2 = enum2.MoveNext();
int compare;
for (;;) {
// Which item is smaller? The end (!valid) is considered larger than any item.
if (! valid1) {
if (! valid2)
break;
compare = 1;
}
else if (! valid2)
compare = -1;
else
compare = comparer.Compare(enum1.Current, enum2.Current);
// If equal, move through both bags without adding. Otherwise, add the smaller item and advance
// just through that bag.
if (compare == 0) {
valid1 = enum1.MoveNext();
valid2 = enum2.MoveNext();
}
else if (compare < 0) {
result.Add(enum1.Current);
valid1 = enum1.MoveNext();
}
else { // compare > 0
result.Add(enum2.Current);
valid2 = enum2.MoveNext();
}
}
return result;
}
#endregion Set operations
#region Read-only list view
/// <summary>
/// Get a read-only list view of the items in this ordered bag. The
/// items in the list are in sorted order, with the smallest item
/// at index 0. This view does not copy any data, and reflects any
/// changes to the underlying OrderedBag.
/// </summary>
/// <returns>A read-only IList<T> view onto this OrderedBag.</returns>
public IList<T> AsList()
{
return new ListView(this, tree.EntireRangeTester, true, false);
}
/// <summary>
/// The nested class that provides a read-only list view
/// of all or part of the collection.
/// </summary>
[Serializable]
private class ListView : ReadOnlyListBase<T>
{
private OrderedBag<T> myBag;
private RedBlackTree<T>.RangeTester rangeTester; // range tester for the range being used.
private bool entireTree; // is the view the whole tree?
private bool reversed; // is the view reversed?
/// <summary>
/// Create a new list view wrapped the given set.
/// </summary>
/// <param name="myBag">The ordered bag to wrap.</param>
/// <param name="rangeTester">Range tester that defines the range being used.</param>
/// <param name="entireTree">If true, then rangeTester defines the entire tree. Used to optimize some operations.</param>
/// <param name="reversed">Is the view enuemerated in reverse order?</param>
public ListView(OrderedBag<T> myBag, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
{
this.myBag = myBag;
this.rangeTester = rangeTester;
this.entireTree = entireTree;
this.reversed = reversed;
}
public sealed override int Count
{
get
{
if (entireTree)
return myBag.Count;
else {
// Note: we can't cache the result of this call because the underlying
// set can change, which would make the cached value incorrect.
return myBag.tree.CountRange(rangeTester);
}
}
}
public sealed override T this[int index]
{
get
{
if (entireTree) {
if (reversed)
return myBag[myBag.Count - 1 - index];
else
return myBag[index];
}
else {
T dummy;
int firstIndex = myBag.tree.FirstItemInRange(rangeTester, out dummy);
int lastIndex = myBag.tree.LastItemInRange(rangeTester, out dummy);
if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
throw new ArgumentOutOfRangeException("index");
if (reversed)
return myBag[lastIndex - index];
else
return myBag[firstIndex + index];
}
}
}
public sealed override int IndexOf(T item)
{
if (entireTree) {
if (reversed)
return myBag.Count - 1 - myBag.LastIndexOf(item);
else
return myBag.IndexOf(item);
}
else {
T dummy;
if (rangeTester(item) != 0)
return -1;
if (reversed) {
int indexInSet = myBag.tree.FindIndex(item, false);
if (indexInSet < 0)
return -1;
int indexOfEnd = myBag.tree.LastItemInRange(rangeTester, out dummy);
return indexOfEnd - indexInSet;
}
else {
int indexInSet = myBag.tree.FindIndex(item, true);
if (indexInSet < 0)
return -1;
int indexOfStart = myBag.tree.FirstItemInRange(rangeTester, out dummy);
return indexInSet - indexOfStart;
}
}
}
}
#endregion Read-only list view
#region Sub-views
/// <summary>
/// Returns a View collection that can be used for enumerating the items in the bag in
/// reversed order.
/// </summary>
///<remarks>
///<p>Typically, this method is used in conjunction with a foreach statement. For example:
///<code>
/// foreach(T item in bag.Reversed()) {
/// // process item
/// }
///</code></p>
/// <p>If an item is added to or deleted from the bag while the View is being enumerated, then
/// the enumeration will end with an InvalidOperationException.</p>
///<p>Calling Reverse does not copy the data in the tree, and the operation takes constant time.</p>
///</remarks>
/// <returns>An OrderedBag.View of items in reverse order.</returns>
public View Reversed() // A reversed view that can be enumerated
{
return new View(this, tree.EntireRangeTester, true, true);
}
/// <summary>
/// Returns a View collection that can be used for enumerating a range of the items in the bag.
/// Only items that are greater than <paramref name="from"/> and
/// less than <paramref name="to"/> are included. The items are enumerated in sorted order.
/// Items equal to the end points of the range can be included or excluded depending on the
/// <paramref name="fromInclusive"/> and <paramref name="toInclusive"/> parameters.
/// </summary>
///<remarks>
///<p>If <paramref name="from"/> is greater than or equal to <paramref name="to"/>, the returned collection is empty. </p>
///<p>Typically, this method is used in conjunction with a foreach statement. For example:
///<code>
/// foreach(T item in bag.Range(from, true, to, false)) {
/// // process item
/// }
///</code></p>
/// <p>If an item is added to or deleted from the bag while the View is being enumerated, then
/// the enumeration will end with an InvalidOperationException.</p>
///<p>Calling Range does not copy the data in the tree, and the operation takes constant time.</p>
///</remarks>
/// <param name="from">The lower bound of the range.</param>
/// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
/// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
/// be included in the range.</param>
/// <param name="to">The upper bound of the range. </param>
/// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
/// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
/// be included in the range.</param>
/// <returns>An OrderedBag.View of items in the given range.</returns>
public View Range(T from, bool fromInclusive, T to, bool toInclusive) // A partial view that can be enumerated
{
return new View(this, tree.DoubleBoundedRangeTester(from, fromInclusive, to, toInclusive), false, false);
}
/// <summary>
/// Returns a View collection that can be used for enumerating a range of the items in the bag.
/// Only items that are greater than (and optionally, equal to) <paramref name="from"/> are included.
/// The items are enumerated in sorted order. Items equal to <paramref name="from"/> can be included
/// or excluded depending on the <paramref name="fromInclusive"/> parameter.
/// </summary>
///<remarks>
///<p>Typically, this method is used in conjunction with a foreach statement. For example:
///<code>
/// foreach(T item in bag.RangeFrom(from, true)) {
/// // process item
/// }
///</code></p>
/// <p>If an item is added to or deleted from the bag while the View is being enumerated, then
/// the enumeration will end with an InvalidOperationException.</p>
///<p>Calling RangeFrom does not copy the data in the tree, and the operation takes constant time.</p>
///</remarks>
/// <param name="from">The lower bound of the range.</param>
/// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
/// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
/// be included in the range.</param>
/// <returns>An OrderedBag.View of items in the given range.</returns>
public View RangeFrom(T from, bool fromInclusive) // A partial view that can be enumerated
{
return new View(this, tree.LowerBoundedRangeTester(from, fromInclusive), false, false);
}
/// <summary>
/// Returns a View collection that can be used for enumerating a range of the items in the bag.
/// Only items that are less than (and optionally, equal to) <paramref name="to"/> are included.
/// The items are enumerated in sorted order. Items equal to <paramref name="to"/> can be included
/// or excluded depending on the <paramref name="toInclusive"/> parameter.
/// </summary>
///<remarks>
///<p>Typically, this method is used in conjunction with a foreach statement. For example:
///<code>
/// foreach(T item in bag.RangeTo(to, false)) {
/// // process item
/// }
///</code></p>
/// <p>If an item is added to or deleted from the bag while the View is being enumerated, then
/// the enumeration will end with an InvalidOperationException.</p>
///<p>Calling RangeTo does not copy the data in the tree, and the operation takes constant time.</p>
///</remarks>
/// <param name="to">The upper bound of the range. </param>
/// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
/// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
/// be inc?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -