Class TreeSet<T>
An implementation of Red-Black trees as an indexed, sorted collection with set semantics, cf. CLRS. C5.TreeBag`1 for a version with bag semantics. C5.TreeDictionary`2 for a sorted dictionary based on this tree implementation. The comparer (sorting order) may be either natural, because the item type is comparable (generic: C5.IComparable`1 or non-generic: System.IComparable) or it can be external and supplied by the user in the constructor.
TODO: describe performance here TODO: discuss persistence and its useful usage modes. Warn about the space leak possible with other usage modes.
Inheritance
Inherited Members
Assembly: DistributedLucene.Net.dll
Syntax
public class TreeSet<T> : SequencedBase<T>, IIndexedSorted<T>, IIndexed<T>, IReadOnlyList<T>, IReadOnlyCollection<T>, Collections.IEnumerable, IPersistentSorted<T>, ISorted<T>, ISequenced<T>, ICollection<T>, IExtensible<T>, Collections.Generic.ICollection<T>, IDirectedCollectionValue<T>, ICollectionValue<T>, IShowable, IFormattable, IDirectedEnumerable<T>, Collections.Generic.IEnumerable<T>, IDisposable, Collections.Generic.ISet<T>Type Parameters
| Name | Description |
|---|---|
| T |
Constructors
| Name | Description |
|---|---|
| TreeSet(MemoryType) | Create a red-black tree collection with natural comparer and item equalityComparer. We assume that if |
| TreeSet(Collections.Generic.IComparer<T>, MemoryType) | Create a red-black tree collection with an external comparer. The itemequalityComparer will be a compatible C5.ComparerZeroHashCodeEqualityComparer`1 since the default equalityComparer for T (C5.EqualityComparer`1.Default) is unlikely to be compatible with the external comparer. This makes the tree inadequate for use as item in a collection of unsequenced or sequenced sets or bags (C5.ICollection`1 and C5.ISequenced`1) |
| TreeSet(Collections.Generic.IComparer<T>, Collections.Generic.IEqualityComparer<T>, MemoryType) | Create a red-black tree collection with an external comparer and an external item equalityComparer, assumed consistent. |
Properties
| Name | Description |
|---|---|
| AllowsDuplicates | |
| Comparer | The comparer object supplied at creation time for this collection |
| ContainsSpeed | The value is symbolic indicating the type of asymptotic complexity in terms of the size of this collection (worst-case or amortized as relevant). |
| DuplicatesByCounting | By convention this is true for any collection with set semantics. |
| IndexingSpeed | |
| Item[Int32] |
|
| Item[Int32, Int32] | |
| ListenableEvents |
Methods
| Name | Description |
|---|---|
| Add(T) | Add an item to this collection if possible. If this collection has set semantics, the item will be added if not already in the collection. If bag semantics, the item will always be added. |
| AddAll(Collections.Generic.IEnumerable<T>) | Add the elements from another collection with a more specialized item type to this collection. If this collection has set semantics, only items not already in the collection will be added. |
| AddSorted(Collections.Generic.IEnumerable<T>) | Add all the items from another collection with an enumeration order that is increasing in the items. The idea is that the implementation may use a faster algorithm to merge the two collections. |
| Backwards() | Create a collection containing the same items as this collection, but whose enumerator will enumerate the items backwards. The new collection will become invalid if the original is modified. Method typically used as in |
| Check() | Checks red-black invariant. Dumps tree to console if bad |
| Check(String) | Checks red-black invariant. Dumps tree to console if bad |
| Choose() | |
| Clear() | Remove all items from this collection. |
| Contains(T) | Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value. |
| ContainsAll(Collections.Generic.IEnumerable<T>) | Check if this collection contains all the values in another collection. If this collection has bag semantics ( |
| ContainsCount(T) | Count the number of items of the collection equal to a particular value. Returns 0 if and only if the value is not in the collection. |
| CountFrom(T) | Determine the number of items at or above a supplied threshold. |
| CountFromTo(T, T) | Determine the number of items between two supplied thresholds. |
| CountTo(T) | Determine the number of items below a supplied threshold. |
| Cut(IComparable<T>, out T, out Boolean, out T, out Boolean) | Perform a search in the sorted collection for the ranges in which a non-increasing (i.e. weakly decreasing) function from the item type to negative, zero respectively positive. If the supplied cut function is not non-increasing, the result of this call is undefined. |
| DeleteMax() | Remove the largest item from this priority queue. |
| DeleteMin() | Remove the least item from this priority queue. |
| Dispose() | If this tree is a snapshot, remove registration in base tree |
| dump() | Print the tree structure to the console stdout. |
| dump(String) | Print the tree structure to the console stdout. |
| ExceptWith(Collections.Generic.IEnumerable<T>) | Not implemented |
| Find(ref T) | Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found. |
| FindAll(Func<T, Boolean>) | Create a new indexed sorted collection consisting of the items of this indexed sorted collection satisfying a certain predicate. |
| FindMax() | Find the current largest item of this priority queue. |
| FindMin() | Find the current least item of this priority queue. |
| FindOrAdd(ref T) | Find or add the item to the tree. If the tree does not contain an item equivalent to this item add it, else return the existing one in the ref argument. |
| GetEnumerator() | Create an enumerator for this tree |
| IndexOf(T) | Searches for an item in this indexed collection going forwards from the start. |
| IntersectWith(Collections.Generic.IEnumerable<T>) | Not implemented |
| IsProperSubsetOf(Collections.Generic.IEnumerable<T>) | Determines whether a TreeSet<T> object is a proper subset of the specified collection. |
| IsProperSupersetOf(Collections.Generic.IEnumerable<T>) | Determines whether a TreeSet<T> object is a proper superset of the specified collection. |
| IsSubsetOf(Collections.Generic.IEnumerable<T>) | Determines whether a TreeSet<T> object is a subset of the specified collection. |
| IsSupersetOf(Collections.Generic.IEnumerable<T>) | Determines whether a TreeSet<T> object is a superset of the specified collection. |
| ItemMultiplicities() | |
| LastIndexOf(T) | Searches for an item in the tree going backwards from the end. |
| Map<V>(Func<T, V>, Collections.Generic.IComparer<V>) | Create a new indexed sorted collection consisting of the results of
mapping all items of this list.
|
| Overlaps(Collections.Generic.IEnumerable<T>) | Determines whether the current TreeSet<T> object and a specified collection share common elements. |
| Predecessor(T) | Find the strict predecessor in the sorted collection of a particular value, i.e. the largest item in the collection less than the supplied value. |
| RangeAll() | Create a directed collection with the same items as this collection. |
| RangeFrom(T) | Query this sorted collection for items greater than or equal to a supplied value. |
| RangeFromTo(T, T) | Query this sorted collection for items between two supplied values. |
| RangeTo(T) | Query this sorted collection for items less than a supplied value. |
| Remove(T) | Remove a particular item from this collection. If the collection has bag semantics only one copy equivalent to the supplied item is removed. |
| Remove(T, out T) | Remove a particular item from this collection if found. If the collection has bag semantics only one copy equivalent to the supplied item is removed, which one is implementation dependent. If an item was removed, report a binary copy of the actual item removed in the argument. |
| RemoveAll(Collections.Generic.IEnumerable<T>) | Remove all items in another collection from this one. If this collection has bag semantics, take multiplicities into account. |
| RemoveAllCopies(T) | Remove all items equivalent to a given value. |
| RemoveAt(Int32) | Remove the item at a specific position of the list.
|
| RemoveInterval(Int32, Int32) | Remove all items in an index interval.
|
| RemoveRangeFrom(T) | Remove all items of this collection above or at a supplied threshold. |
| RemoveRangeFromTo(T, T) | Remove all items of this collection between two supplied thresholds. |
| RemoveRangeTo(T) | Remove all items of this collection below a supplied threshold. |
| RetainAll(Collections.Generic.IEnumerable<T>) | Remove all items not in some other collection from this one. If this collection has bag semantics, take multiplicities into account. |
| SetEquals(Collections.Generic.IEnumerable<T>) | Determines whether the current TreeSet<T> and the specified collection contain the same elements. |
| Snapshot() | Make a (read-only) snapshot of this collection. |
| Successor(T) | Find the strict successor in the sorted collection of a particular value, i.e. the least item in the collection greater than the supplied value. |
| SymmetricExceptWith(Collections.Generic.IEnumerable<T>) | Not implemented |
| TryPredecessor(T, out T) | Find the strict predecessor of item in the sorted collection, that is, the greatest item in the collection smaller than the item. |
| TrySuccessor(T, out T) | Find the strict successor of item in the sorted collection, that is, the least item in the collection greater than the supplied value. |
| TryWeakPredecessor(T, out T) | Find the weak predecessor of item in the sorted collection, that is, the greatest item in the collection smaller than or equal to the item. |
| TryWeakSuccessor(T, out T) | Find the weak successor of item in the sorted collection, that is, the least item in the collection greater than or equal to the supplied value. |
| UnionWith(Collections.Generic.IEnumerable<T>) | Modifies the current TreeSet<T> object to contain all elements that are present in itself, the specified collection, or both. |
| UniqueItems() | |
| Update(T) | Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection. |
| Update(T, out T) | Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection. |
| UpdateOrAdd(T) | Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection with a binary copy of the supplied value; else add the value to the collection. NOTE: the bag implementation is currently wrong! ????? |
| UpdateOrAdd(T, out T) | |
| WeakPredecessor(T) | Find the weak predecessor in the sorted collection of a particular value, i.e. the largest item in the collection less than or equal to the supplied value. |
| WeakSuccessor(T) | Find the weak successor in the sorted collection of a particular value, i.e. the least item in the collection greater than or equal to the supplied value. NoSuchItemException |
Explicit Interface Implementations
| Name | Description |
|---|---|
| IDirectedEnumerable<T>.Backwards() | |
| ISorted<T>.RangeFrom(T) | |
| ISorted<T>.RangeFromTo(T, T) | |
| ISorted<T>.RangeTo(T) |
