[svn] r6163: nemerle/trunk/lib: heap.n set.n tree.n
nazgul
svnadmin at nemerle.org
Sat Mar 25 14:27:29 CET 2006
Log:
Make Heap and Set implement ICollection[T]
Author: nazgul
Date: Sat Mar 25 14:27:27 2006
New Revision: 6163
Modified:
nemerle/trunk/lib/heap.n
nemerle/trunk/lib/set.n
nemerle/trunk/lib/tree.n
Modified: nemerle/trunk/lib/heap.n
==============================================================================
--- nemerle/trunk/lib/heap.n (original)
+++ nemerle/trunk/lib/heap.n Sat Mar 25 14:27:27 2006
@@ -26,6 +26,8 @@
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
+using SCG = System.Collections.Generic;
+
namespace Nemerle.Collections
{
/**
@@ -36,11 +38,10 @@
public this () { base ("Nemerle.Collections.Heap") }
}
-
/**
* General usage heap, can be used as priority queue.
*/
- public class Heap ['a] where 'a : System.IComparable ['a]
+ public class Heap ['a] : SCG.ICollection ['a] where 'a : System.IComparable ['a]
{
/* -- PUBLIC CONSTRUCTORS ----------------------------------------------- */
@@ -58,6 +59,23 @@
build_heap ();
}
+ /**
+ * Creates new heap initially filled with elements from given collection
+ */
+ public this (coll : SCG.IEnumerable ['a])
+ {
+ m_elements_count = 0;
+ m_heap = array (10);
+
+ foreach (x in coll) {
+ when (m_elements_count >= m_heap.Length - 1)
+ grow ();
+ m_elements_count++;
+ m_heap [m_elements_count] = x;
+ }
+
+ build_heap ();
+ }
/**
* Creates a new empty heap with given initial capacity.
@@ -107,9 +125,24 @@
*/
public CurrentCapacity : int
{
- get { m_heap.Length }
+ get { m_heap.Length - 1 }
}
+ /**
+ * Returns false.
+ */
+ public IsReadOnly : bool {
+ get { false }
+ }
+
+ /**
+ * Returns the number of elements that this heap can store
+ * without the need to grow.
+ */
+ public Capacity : int
+ {
+ get { m_heap.Length - 1 }
+ }
/* -- PUBLIC METHODS ---------------------------------------------------- */
@@ -133,6 +166,24 @@
m_heap [i] = x
}
+ /*
+ * Adds element to heap. Alist for Insert method.
+ */
+ public Add (x : 'a) : void
+ {
+ Insert (x)
+ }
+
+ /**
+ * Count is set to 0, and references to other objects from elements of the collection are also released.
+ *
+ * Capacity remains unchanged.
+ */
+ public Clear () : void
+ {
+ System.Array.Clear (m_heap, 1, m_elements_count);
+ m_elements_count = 0;
+ }
/**
* Returns the first (with maximal priority) element from the heap
@@ -166,6 +217,23 @@
}
}
+ /**
+ * Copies elements from heap to given array, starting at specified index in target array
+ */
+ public CopyTo (to : array ['a], mutable startIdx : int) : void
+ {
+ startIdx--; // because i is 1-based
+ for (mutable i = 1; i <= m_elements_count; i++)
+ to [startIdx + i] = m_heap [i];
+ }
+
+ /**
+ * Checks if given value is contained in heap. This is O(n) operation in worst case.
+ */
+ public Contains (x : 'a) : bool
+ {
+ System.Array.IndexOf (m_heap, x, 1) != -1
+ }
/**
* Creates new heap of elements of type 'b. New heap is totally independent, i.e.
@@ -208,6 +276,18 @@
v
}
+ public GetEnumerator () : SCG.IEnumerator ['a]
+ {
+ for (mutable i = 1; i <= m_elements_count; i++)
+ yield m_heap [i];
+ }
+
+ /* HIDDED INTERFACE IMPLEMENTATION */
+
+ private Remove (_ : 'a) : bool implements SCG.ICollection.Remove
+ {
+ throw System.NotSupportedException ("remove operation is not supported by heap class");
+ }
/* -- PRIVATE METHODS --------------------------------------------------- */
Modified: nemerle/trunk/lib/set.n
==============================================================================
--- nemerle/trunk/lib/set.n (original)
+++ nemerle/trunk/lib/set.n Sat Mar 25 14:27:27 2006
@@ -26,23 +26,36 @@
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
+using SCG = System.Collections.Generic;
+
namespace Nemerle.Collections
{
-
- public class Set ['a]
+ public class Set ['a] : SCG.ICollection ['a]
where 'a : System.IComparable ['a]
{
+ root : Tree.Node ['a];
+
public static Singleton (elem : 'a) : Set ['a]
{
Set ().Add (elem)
}
- public static FromList (elems : list ['a]) : Set ['a]
+ public this (coll : SCG.IEnumerable ['a])
{
- Set ().AddList (elems)
+ this (Tree.Node.Leaf (), coll)
}
- root : Tree.Node ['a];
+ this (mutable tree : Tree.Node ['a], coll : SCG.IEnumerable ['a])
+ {
+ foreach (x in coll)
+ tree = Tree.Insert (tree, x, false);
+ root = tree;
+ }
+
+ public static FromList (elems : list ['a]) : Set ['a]
+ {
+ Set (elems)
+ }
public this ()
{
@@ -59,12 +72,14 @@
Set (Tree.Insert (root, elem, false))
}
+ public AddRange (elems : SCG.IEnumerable ['a]) : Set ['a]
+ {
+ Set (root, elems)
+ }
+
public AddList (elems : list ['a]) : Set ['a]
{
- Set (List.FoldLeft (elems, root,
- fun (elem, root) {
- Tree.Insert (root, elem, false)
- }))
+ AddRange (elems)
}
public ReplaceList (elems : list ['a]) : Set ['a]
@@ -172,6 +187,42 @@
{
"Set" + ToList ().ToString ()
}
+
+ public GetEnumerator () : SCG.IEnumerator ['a]
+ {
+ root.GetEnumerator ();
+ }
+
+ public CopyTo (arr : array ['a], mutable arrayIndex : int) : void
+ {
+ _ = Tree.Fold (root, null, fun (x, _) {
+ arr [arrayIndex] = x;
+ arrayIndex++;
+ null
+ });
+ }
+
+ public IsReadOnly : bool {
+ get { true }
+ }
+
+ public Count : int {
+ get { root.Count }
}
+ private Remove_Invalid (_ : 'a) : bool implements SCG.ICollection.Remove
+ {
+ throw System.NotSupportedException ("this is functional set, which is read-only");
+ }
+
+ private Clear_Invalid() : void implements SCG.ICollection.Clear
+ {
+ throw System.NotSupportedException ("this is functional set, which is read-only");
+ }
+
+ private Add_Invalid (_ : 'a) : void implements SCG.ICollection.Add
+ {
+ throw System.NotSupportedException ("this is functional set, which is read-only and returns new instanc upon adding element");
+ }
+ }
}
Modified: nemerle/trunk/lib/tree.n
==============================================================================
--- nemerle/trunk/lib/tree.n (original)
+++ nemerle/trunk/lib/tree.n Sat Mar 25 14:27:27 2006
@@ -26,6 +26,8 @@
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
+using SCG = System.Collections.Generic;
+
namespace Nemerle.Collections
{
/**
@@ -36,7 +38,9 @@
/*
* Definition of the node Node ['a] of tree
*/
- public variant Node ['a] where 'a : System.IComparable ['a] {
+ public variant Node ['a] : SCG.IEnumerable ['a]
+ where 'a : System.IComparable ['a]
+ {
| Red {
key : 'a;
lchild : Node ['a];
@@ -48,6 +52,21 @@
rchild : Node ['a];
}
| Leaf
+
+ public Count : int {
+ get {
+ match (this) {
+ | Red (_, left, right) | Black (_, left, right) =>
+ 1 + left.Count + right.Count
+ | _ => 0
+ }
+ }
+ }
+
+ public GetEnumerator () : SCG.IEnumerator ['a]
+ {
+ NodeEnumerator (this)
+ }
}
/**
@@ -415,8 +434,73 @@
Node.Black (key, ltree, rtree)
}
}
+
+ class NodeEnumerator ['a] : SCG.IEnumerator ['a] where 'a : System.IComparable ['a]
+ {
+ mutable stack : SCG.Stack [Node ['a] * bool] = SCG.Stack ();
+ mutable m_current : 'a;
+
+ public Current : 'a {
+ get { m_current }
+ }
+
+ public this (root : Node ['a]) {
+ enterChild (root, false);
+ }
+
+ private enterChild (childNode : Node ['a], side : bool) : void {
+ match (childNode) {
+ | Node.Red (_, left, _) | Node.Black (_, left, _) =>
+ stack.Push ((childNode, side));
+ enterChild (left, false);
+
+ | Leaf => ()
+ }
+ }
+
+ private ascend () : void
+ {
+ def (_, side) = stack.Pop();
+ if (side) // right
+ ascend ();
+ else // left
+ () // nothing, we are in some fresh node
+ }
+
+ public Reset () : void
+ {
+ if (stack.Count > 0) {
+ repeat (stack.Count - 1) ignore (stack.Pop);
+ def (root, _) = stack.Pop ();
+ enterChild (root, false);
+ }
+ else
+ throw System.InvalidOperationException ();
+ }
+
+ public MoveNext () : bool {
+ if (stack.Count > 0) {
+ match (stack.Peek()) {
+ | (Red (key, _, right), _) | (Black (key, _, right), _) =>
+ m_current = key;
+ match (right) {
+ | Leaf => ascend ();
+ | _ => enterChild (right, true);
}
+ | _ => throw System.InvalidOperationException ();
+ }
+ true
+ }
+ else false
+ }
+
+ public Dispose () : void {
+ stack = null;
+ m_current = Nemerle.Extensions.DefaultValue ('a);
+ }
+ }
+ }
/* ------------------------------------------------------------------------ */
/* -- PUBLIC INTERFACES --------------------------------------------------- */
More information about the svn
mailing list