|
| From: | Rhys Weatherley <address@hidden> |
| Subject: | [Dotgnu-pnet-commits] CVS: pnetlib/Generics TreeBase.cs,NONE,1.1 TreeDictionary.cs,NONE,1.1 TreeSet.cs,NONE,1.1Generics.html,1.2,1.3 |
| Date: | Sat, 01 Mar 2003 01:22:32 -0500 |
Update of /cvsroot/dotgnu-pnet/pnetlib/Generics
In directory subversions:/tmp/cvs-serv10595/Generics
Modified Files:
Generics.html
Added Files:
TreeBase.cs TreeDictionary.cs TreeSet.cs
Log Message:
Add tree-based collections to the generics library.
--- NEW FILE ---
/*
* TreeBase.cs - Base class for generic tree implementations.
*
* Copyright (c) 2003 Southern Storm Software, Pty Ltd
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
namespace Generics
{
using System;
// The algorithm used here is based on the red-black tree implementation
// in the C++ Standard Template Library.
//
// Normally, programmers should use "TreeSet" or "TreeDictionary"
// instead of inheriting from this class.
public abstract class TreeBase<KeyT, ValueT>
{
// Structure of a tree node.
private sealed class TreeNode<KeyT, ValueT>
{
public TreeNode<KeyT, ValueT> parent; // Parent of this node.
public TreeNode<KeyT, ValueT> left; // Left child.
public TreeNode<KeyT, ValueT> right; // Right child.
public KeyT key;
// Key stored in the node.
public ValueT value; //
Value stored in the node.
public bool red;
// True if the node is "red".
}; // class TreeNode<KeyT, ValueT>
// Internal state.
protected IComparer<KeyT> cmp;
private TreeNode<KeyT, ValueT> root;
private TreeNode<KeyT, ValueT> leftMost;
protected int count;
// Constructors.
protected TreeBase() : this(null) {}
protected TreeBase(IComparer<KeyT> cmp)
{
if(cmp == null)
{
this.cmp = new Comparer<KeyT>();
}
else
{
this.cmp = cmp;
}
root = null;
leftMost = null;
count = 0;
}
// Rotate the tree left around a node.
private void RotateLeft(TreeNode<KeyT, ValueT> x)
{
TreeNode<KeyT, ValueT> y = x.right;
x.right = y.left;
if(y.left != null)
{
y.left.parent = x;
}
y.parent = x.parent;
if(x == root)
{
root = y;
}
else if(x == x.parent.left)
{
x.parent.left = y;
}
else
{
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// Rotate the tree right around a node.
private void RotateRight(TreeNode<KeyT, ValueT> y)
{
TreeNode<KeyT, ValueT> y = x.left;
x.left = y.right;
if(y.right != null)
{
y.right.parent = x;
}
if(x == root)
{
root = y;
}
else if(x == x.parent.right)
{
x.parent.right = y;
}
else
{
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
// Rebalance the tree around a particular inserted node.
private void Rebalance(TreeNode<KeyT, ValueT> x)
{
TreeNode<KeyT, ValueT> y;
// Set the inserted node's color initially to
"red".
x.red = true;
// Split and rotate sub-trees as necessary to
rebalance.
while(x != root && x.parent.red)
{
if(x.parent == x.parent.parent.left)
{
y = x.parent.parent.right;
if(y != null && y.red)
{
x.parent.red = false;
y.red = false;
x.parent.parent.red =
true;
x = x.parent.parent;
}
else
{
if(x == x.parent.right)
{
x = x.parent;
RotateLeft(x);
}
x.parent.red = false;
x.parent.parent.red =
true;
RotateRight(x.parent.parent);
}
}
else
{
y = x.parent.parent.left;
if(y != null && y.red)
{
x.parent.red = false;
y.red = false;
x.parent.parent.red =
true;
x = x.parent.parent;
}
else
{
if(x == x.parent.left)
{
x = x.parent;
RotateRight(x);
}
x.parent.red = false;
x.parent.parent.red =
true;
RotateLeft(x.parent.parent);
}
}
}
// Set the root color to black.
root.red = false;
}
// Remove a specific node and rebalance the tree afterwards.
private void RemoveNode(TreeNode<KeyT, ValueT> z)
{
TreeNode<KeyT, ValueT> y = z;
TreeNode<KeyT, ValueT> x = null;
TreeNode<KeyT, ValueT> x_parent = null;
TreeNode<KeyT, ValueT> w;
bool tempRed;
// There will be one less item once we are
finished.
--count;
// Determine the starting position for the
rebalance.
if(y.left == null)
{
x = y.right;
}
else if(y.right == null)
{
x = y.left;
}
else
{
y = y.right;
while(y.left != null)
{
y = y.left;
}
x = y.right;
}
// Re-link the nodes to remove z from the tree.
if(y != z)
{
z.left.parent = y;
y.left = z.left;
if(y != z.right)
{
x_parent = y.parent;
if(x != null)
{
x.parent = y.parent;
}
y.parent.left = x;
y.right = z.right;
z.right.parent = y;
}
else
{
x_parent = y;
}
if(root == z)
{
root = y;
}
else if(z.parent.left == z)
{
z.parent.left = y;
}
else
{
z.parent.right = y;
}
y.parent = z.parent;
tempRed = y.red;
y.red = z.red;
z.red = tempRed;
y = z;
}
else
{
x_parent = y.parent;
if(x != null)
{
x.parent = y.parent;
}
if(root == z)
{
root = x;
}
else if(z.parent.left = z)
{
z.parent.left = x;
}
else
{
z.parent.right = y;
}
if(leftMost == z)
{
if(z.right == null)
{
leftMost = z.parent;
}
else
{
leftMost = x;
while(leftMost != null
&& leftMost.left != null)
{
leftMost =
leftMost.left;
}
}
}
}
// If the y node is "red", then the tree is
still balanced.
if(y.red)
{
return;
}
// Rotate nodes within the tree to bring it
back into balance.
while(x != root && (x == null || !(x.red)))
{
if(x == x_parent.left)
{
w = x_parent.right;
if(w.red)
{
w.red = false;
x_parent.color = red;
RotateLeft(x_parent);
w = x_parent.right;
}
if((w.left == null ||
!(w.left.red)) &&
(w.right == null ||
!(w.right.red)))
{
w.red = true;
x = x_parent;
x_parent =
x_parent.parent;
}
else
{
if(w.right == null ||
!(w.right.red))
{
if(w.left !=
null)
{
w.left.red = false;
}
w.red = true;
RotateRight(w);
w =
x_parent.right;
}
w.red = x_parent.red;
x_parent.red = false;
if(w.right != null)
{
w.right.red =
false;
}
RotateLeft(x_parent);
break;
}
}
else
{
w = x_parent.left;
if(w.red)
{
w.red = false;
x_parent.red = true;
RotateRight(x_parent);
x = x_parent.left;
}
if((w.right == null ||
!(w.right.red)) &&
(w.left == null ||
!(w.left.red)))
{
w.red = true;
x = x_parent;
x_parent =
x_parent.parent;
}
else
{
if(w.left == null ||
!(w.left.red))
{
if(w.right !=
null)
{
w.right.red = false;
}
w.red = true;
RotateLeft(w);
w =
x_parent.left;
}
w.red = x_parent.red;
x_parent.red = false;
if(w.left != null)
{
w.left.red =
false;
}
RotateRight(x_parent);
break;
}
}
if(x != null)
{
x.red = false;
}
}
}
// Add an item to this tree.
protected void AddItem(KeyT key, ValueT value, bool throwIfExists)
{
TreeNode<KeyT, ValueT> y;
TreeNode<KeyT, ValueT> x;
TreeNode<KeyT, ValueT> z;
int cmpValue;
// Find the insert position.
y = null;
x = root;
while(x != null)
{
y = x;
if((cmpValue = cmp.Compare(key, x.key))
< 0)
{
x = x.left;
}
else if(cmpValue > 0)
{
x = x.right;
}
else if(throwIfExists)
{
throw new
ArgumentException(S._("Arg_ExistingEntry"));
}
else
{
x.value = value;
return;
}
}
// Create a new node to insert.
z = new TreeNode<KeyT, ValueT>();
z.key = key;
z.value = value;
// Determine how to insert the node.
if(y == null)
{
// The tree is empty, so add the
initial node.
root = z;
leftMost = z;
}
else if(x != null || cmp.Compare(key, y.key) <
0)
{
// Insert on the left.
y.left = z;
if(y == leftMost)
{
leftMost = z;
}
}
else
{
// Insert on the right.
y.right = z;
}
z.parent = y;
// Rebalance the tree around the inserted node.
Rebalance(z);
// We have one more element in the tree.
++count;
}
// Clear the contents of this tree.
protected void ClearAllItems()
{
root = null;
leftMost = null;
count = 0;
}
// Determine if this tree contains a specific key.
protected bool ContainsItem(KeyT key)
{
TreeNode<KeyT, ValueT> current = root;
int cmpValue;
while(current != null)
{
if((cmpValue = cmp.Compare(key,
current.key)) < 0)
{
current = current.left;
}
else if(cmpValue > 0)
{
current = current.right;
}
else
{
return true;
}
}
return false;
}
// Look up the value associated with a specific key.
protected T LookupItem(KeyT key)
{
TreeNode<KeyT, ValueT> current = root;
int cmpValue;
while(current != null)
{
if((cmpValue = cmp.Compare(key,
current.key)) < 0)
{
current = current.left;
}
else if(cmpValue > 0)
{
current = current.right;
}
else
{
return current.value;
}
}
throw new
ArgumentException(S._("Arg_NotInDictionary"));
}
// Remove the node for a specific key.
protected void RemoveItem(KeyT key)
{
TreeNode<KeyT, ValueT> current = root;
int cmpValue;
while(current != null)
{
if((cmpValue = cmp.Compare(key,
current.key)) < 0)
{
current = current.left;
}
else if(cmpValue > 0)
{
current = current.right;
}
else
{
RemoveNode(current);
return;
}
}
}
// Get an iterator for this tree.
protected TreeBaseIterator<KeyT, ValueT> GetInOrderIterator()
{
return new TreeBaseIterator<KeyT, ValueT>(this);
}
// Iterator class that implements in-order traversal of a tree.
protected sealed class TreeBaseIterator<KeyT, ValueT>
{
// Internal state.
private Tree<KeyT, ValueT> tree;
private TreeNode<KeyT, ValueT> current;
private bool reset;
private bool removed;
// Constructor.
public TreeBaseIterator(Tree<KeyT, ValueT> tree)
{
this.tree = tree;
this.current = null;
this.reset = true;
this.removed = false;
}
// Move to the next item in the iteration order.
public bool MoveNext()
{
if(removed)
{
// The last node was removed,
so we are already
// positioned on the next node
to be visited.
removed = false;
}
else if(reset)
{
// Start with the left-most
node in the tree.
current = tree.leftMost;
reset = false;
}
else if(current == null)
{
// We already reached the end
of the tree.
return false;
}
else if(current.right != null)
{
// Move to the left-most node
in the right sub-tree.
current = current.right;
while(current.left != null)
{
current = current.left;
}
}
else
{
// Move up ancestors until we
are no longer
// the right-most child of our
parent.
TreeNode<T> parent =
current.parent;
while(parent != null &&
parent.right == current)
{
current = parent;
parent = current.parent;
}
current = parent;
}
return (current != null);
}
// Reset the iterator to the start.
public void Reset()
{
current = null;
reset = true;
removed = false;
}
// Remove the current item in the iteration order.
public void Remove()
{
// Bail out if we are not currently
positioned on a node.
if(current == null || removed)
{
throw new
InvalidOperationException
(S._("Invalid_BadIteratorPosition"));
}
// Save the current node.
TreeNode<T> node = current;
// Move on to the next node in the
traversal order.
MoveNext();
// Remove the node from the tree.
tree.RemoveNode(node);
// Record that we have removed "node".
removed = true;
}
// Get the key from the current item.
public KeyT Key
{
get
{
if(current != null && !removed)
{
return current.key;
}
throw new
InvalidOperationException
(S._("Invalid_BadIteratorPosition"));
}
}
// Get the value from the current item.
public ValueT Value
{
get
{
if(current != null && !removed)
{
return current.value;
}
throw new
InvalidOperationException
(S._("Invalid_BadIteratorPosition"));
}
set
{
if(current != null && !removed)
{
current.value = value;
}
else
{
throw new
InvalidOperationException
(S._("Invalid_BadIteratorPosition"));
}
}
}
}; // class TreeBaseIterator<KeyT, ValueT>
}; // class TreeBase<KeyT, ValueT>
}; // namespace Generics
--- NEW FILE ---
/*
* TreeDictionary.cs - Generic dictionary class, implemented as a tree.
*
* Copyright (c) 2003 Southern Storm Software, Pty Ltd
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
namespace Generics
{
using System;
public sealed class TreeDictionary<KeyT, ValueT>
: TreeBase<KeyT, ValueT>, IDictionary<KeyT, ValueT>, ICloneable
{
// Constructor.
public TreeDictionary() : base(null) {}
public TreeDictionary(IComparer<KeyT> cmp) : base(cmp) {}
// Implement the IDictionary<KeyT, ValueT> interface.
public void Add(KeyT key, ValueT value)
{
AddItem(key, value, true);
}
public void Clear()
{
ClearAllItems();
}
public bool Contains(KeyT key)
{
return ContainsItem(key);
}
public IDictionaryIterator<KeyT, ValueT> GetIterator()
{
return new TreeDictionaryIterator<KeyT, ValueT>
(GetInOrderIterator());
}
public void Remove(KeyT key)
{
RemoveItem(key);
}
public ValueT this[KeyT key]
{
get
{
return LookupItem(key);
}
set
{
AddItem(key, value, false);
}
}
public ICollection<KeyT> Keys
{
get
{
return new TreeKeyCollection<KeyT,
ValueT>(this);
}
}
public ICollection<ValueT> Values
{
get
{
return new TreeValueCollection<KeyT,
ValueT>(this);
}
}
// Implement the ICollection<DictionaryEntry<KeyT, ValueT>> interface.
public void CopyTo(DictionaryEntry<KeyT, ValueT>[] array, int index)
{
TreeBase.TreeIterator<KeyT, ValueT> iterator;
iterator = GetInOrderIterator();
while(iterator.MoveNext())
{
array[index++] = new
DictionaryEntry<KeyT, ValueT>
(iterator.Key,
iterator.Value);
}
}
public int Count
{
get
{
return count;
}
}
public bool IsFixedSize
{
get
{
return false;
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public bool IsSynchronized
{
get
{
return false;
}
}
public Object SyncRoot
{
get
{
return this;
}
}
// Implement the IIterable<DictionaryEntry<KeyT, ValueT>> interface.
IIterator< DictionaryEntry<KeyT, ValueT> >
IIterable< DictionaryEntry<KeyT, ValueT>
>.GetIterator()
{
return GetIterator();
}
// Get the in-order dictionary iterator for the key and value
collections.
// Needed to get around the "protected" permissions in "TreeBase".
private TreeBase.TreeBaseIterator<KeyT, ValueT> GetDictIterator()
{
return GetInOrderIterator();
}
// Iterator class for tree dictionaries.
private sealed class TreeDictionaryIterator<KeyT, ValueT>
: IDictionaryIterator<KeyT, ValueT>
{
// Internal state.
private TreeBase.TreeBaseIterator<KeyT, ValueT> iterator;
// Constructor.
public TreeDictionaryIterator
(TreeBase.TreeBaseIterator<KeyT,
ValueT> iterator)
{
this.iterator = iterator;
}
// Implement the IIterator<DictionaryEntry<KeyT, ValueT>>
interface.
public bool MoveNext()
{
return iterator.MoveNext();
}
public void Reset()
{
iterator.Reset();
}
public void Remove()
{
iterator.Remove();
}
public DictionaryEntry<KeyT, ValueT> Current
{
get
{
return new
DictionaryEntry<KeyT, ValueT>
(iterator.Key,
iterator.Value);
}
}
// Implement the IDictionaryIterator<KeyT, ValueT> interface.
public KeyT Key
{
get
{
return iterator.Key;
}
}
public ValueT Value
{
get
{
return iterator.Value;
}
set
{
iterator.Value = value;
}
}
}; // class TreeDictionaryIterator<KeyT, ValueT>
// Key iterator class for tree dictionaries.
private sealed class TreeKeyIterator<KeyT, ValueT> : IIterator<KeyT>
{
// Internal state.
private TreeBase.TreeBaseIterator<KeyT, ValueT> iterator;
// Constructor.
public TreeKeyIterator
(TreeBase.TreeBaseIterator<KeyT,
ValueT> iterator)
{
this.iterator = iterator;
}
// Implement the IIterator<KeyT> interface.
public bool MoveNext()
{
return iterator.MoveNext();
}
public void Reset()
{
iterator.Reset();
}
public void Remove()
{
iterator.Remove();
}
public KeyT Current
{
get
{
return iterator.Key;
}
}
}; // class TreeKeyIterator<KeyT, ValueT>
// Value iterator class for tree dictionaries.
private sealed class TreeValueIterator<KeyT, ValueT> : IIterator<ValueT>
{
// Internal state.
private TreeBase.TreeBaseIterator<KeyT, ValueT> iterator;
// Constructor.
public TreeValueIterator
(TreeBase.TreeBaseIterator<KeyT,
ValueT> iterator)
{
this.iterator = iterator;
}
// Implement the IIterator<ValueT> interface.
public bool MoveNext()
{
return iterator.MoveNext();
}
public void Reset()
{
iterator.Reset();
}
public void Remove()
{
iterator.Remove();
}
public ValueT Current
{
get
{
return iterator.Value;
}
}
}; // class TreeValueIterator<KeyT, ValueT>
// Collection of keys in a tree dictionary.
private sealed class TreeKeyCollection<KeyT, ValueT> : ICollection<KeyT>
{
// Internal state.
private TreeDictionary<KeyT, ValueT> dict;
// Constructor.
public TreeKeyCollection(TreeDictionary<KeyT, ValueT> dict)
{
this.dict = dict;
}
// Implement the ICollection interface.
public void CopyTo(KeyT[] array, int index)
{
IIterator<KeyT> iterator =
GetIterator();
while(iterator.MoveNext())
{
array[index++] =
iterator.Current;
}
}
public int Count
{
get
{
return dict.Count;
}
}
public bool IsFixedSize
{
get
{
return dict.IsFixedSize;
}
}
public bool IsReadOnly
{
get
{
return dict.IsReadOnly;
}
}
public bool IsSynchronized
{
get
{
return dict.IsSynchronized;
}
}
public Object SyncRoot
{
get
{
return dict.SyncRoot;
}
}
// Implement the IIterable<KeyT> interface.
public IIterator<KeyT> GetIterator()
{
return new TreeKeyIterator<KeyT, ValueT>
(dict.GetDictIterator());
}
}; // class TreeKeyCollection<KeyT, ValueT>
// Collection of values in a tree dictionary.
private sealed class TreeValueCollection<KeyT, ValueT>
: ICollection<ValueT>
{
// Internal state.
private TreeDictionary<KeyT, ValueT> dict;
// Constructor.
public TreeValueCollection(TreeDictionary<KeyT, ValueT> dict)
{
this.dict = dict;
}
// Implement the ICollection interface.
public void CopyTo(ValueT[] array, int index)
{
IIterator<ValueT> iterator =
GetIterator();
while(iterator.MoveNext())
{
array[index++] =
iterator.Current;
}
}
public int Count
{
get
{
return dict.Count;
}
}
public bool IsFixedSize
{
get
{
return dict.IsFixedSize;
}
}
public bool IsReadOnly
{
get
{
return dict.IsReadOnly;
}
}
public bool IsSynchronized
{
get
{
return dict.IsSynchronized;
}
}
public Object SyncRoot
{
get
{
return dict.SyncRoot;
}
}
// Implement the IIterable<ValueT> interface.
public IIterator<ValueT> GetIterator()
{
return new TreeValueIterator<KeyT,
ValueT>
(dict.GetDictIterator());
}
}; // class TreeValueCollection<KeyT, ValueT>
}; // class TreeDictionary<T>
}; // namespace Generics
--- NEW FILE ---
/*
* TreeSet.cs - Generic tree class, implementing a set.
*
* Copyright (c) 2003 Southern Storm Software, Pty Ltd
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
namespace Generics
{
using System;
public sealed class TreeSet<T> : TreeBase<T, bool>, ISet<T>, ICloneable
{
// Constructors.
public TreeSet() : base(null) {}
public TreeSet(IComparer<T> cmp) : base(cmp) {}
// Implement the ISet<T> interface.
public void Add(T value)
{
AddItem(value, true, true);
}
public void Clear()
{
ClearAllItems();
}
public bool Contains(T value)
{
return tree.ContainsItem(value);
}
public void Remove(T value)
{
tree.RemoveItem(value);
}
// Implement the ICollection<T> interface.
public void CopyTo(T[] array, int index)
{
IIterator<T> iterator = GetIterator();
while(iterator.MoveNext())
{
array[index++] = iterator.Current;
}
}
public int Count
{
get
{
return count;
}
}
public bool IsFixedSize
{
get
{
return false;
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public bool IsSynchronized
{
get
{
return false;
}
}
public Object SyncRoot
{
get
{
return this;
}
}
// Implement the IEnumerable<T> interface.
public IIterator<T> GetIterator()
{
return new
TreeSetIterator<T>(GetInOrderIterator());
}
// Implement the ICloneable interface.
public Object Clone()
{
TreeSet<T> tree = new TreeSet<T>(cmp);
TreeBaseIterator<T, bool> iterator =
GetInOrderIterator();
while(iterator.MoveNext())
{
tree.AddItem(iterator.Key,
iterator.Value);
}
return tree;
}
// Iterator class that implements in-order traversal of a tree set.
private sealed class TreeSetIterator<T> : IIterator<T>
{
// Internal state.
private TreeBase.TreeBaseIterator<T, bool> iterator;
// Constructor.
public TreeSetIterator(TreeBase.TreeBaseIterator<KeyT, bool>
iterator)
{
this.iterator = iterator;
}
// Implement the IIterator<T> interface.
public bool MoveNext()
{
return iterator.MoveNext();
}
public void Reset()
{
iterator.Reset();
}
public void Remove()
{
iterator.Remove();
}
public T Current
{
get
{
return iterator.Key;
}
}
}; // class TreeSetIterator<T>
}; // class TreeSet<T>
}; // namespace Generics
Index: Generics.html
===================================================================
RCS file: /cvsroot/dotgnu-pnet/pnetlib/Generics/Generics.html,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -r1.2 -r1.3
*** Generics.html 25 Feb 2003 04:45:18 -0000 1.2
--- Generics.html 1 Mar 2003 06:22:29 -0000 1.3
***************
*** 219,222 ****
--- 219,230 ----
an underlying <code>IList<T></code> object. By default,
a <code>LinkedList<T></code> object is used.</dd>
+
+ <dt><code>TreeSet<T></code></dt>
+ <dd>Implementation of an <code>ISet<T></code> as a
+ balanced binary tree.</dd>
+
+ <dt><code>TreeDictionary<KeyT, ValueT></code></dt>
+ <dd>Implementation of an <code>IDictionary<KeyT, ValueT></code>
+ as a balanced binary tree.</dd>
</dl>
***************
*** 372,375 ****
--- 380,388 ----
<dd>Wraps up an <code>IListIterator<T></code> to reverse
the direction of traversal.</dd>
+
+ <dt><code>TreeBase<KeyT, ValueT></code></dt>
+ <dd>Utility base class for <code>TreeSet<KeyT></code> and
+ <code>TreeDictionary<KeyT, ValueT></code>. Not
recommended
+ for direct use by programmers.</dd>
</dl>
| [Prev in Thread] | Current Thread | [Next in Thread] |