Permalink
Fetching contributors…
Cannot retrieve contributors at this time
361 lines (288 sloc) 9.48 KB
/*
* Copyright (c) 2009-2009 rampelstinskin@gmail.com
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. The name of rampelstinskin may not be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
* NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
using System;
using System.Diagnostics;
using SCG = System.Collections.Generic;
using Nemerle.Utility;
namespace Nemerle.Collections
{
[DebuggerDisplay("Count = {Count}: {ToString()}")]
[DebuggerNonUserCode]
public class Map[TKey, TValue] : SCG.IEnumerable[TKey * TValue]
{
private struct Node
{
public Key : TKey;
public Value : TValue;
public this (k : TKey, v : TValue)
{
this.Key = k;
this.Value = v;
}
public this (k : TKey)
{
this.Key = k;
}
public override ToString() : string
{
$"($Key, $Value)"
}
}
#region State
private _tree : TwoThreeTree.Node[Node];
private _cmp : Node * Node -> int;
private _size : int;
#endregion
#region Constructors
private static MakeNodeComparer(cmp : TKey * TKey -> int) : Node * Node -> int
{
(x, y) => cmp(x.Key, y.Key)
}
private static DefaultComparer() : Node * Node -> int
{
MakeNodeComparer(NemerleCollectionsComparer.Comparer[TKey].Default);
}
public this()
{
this(0, TwoThreeTree.Node.Leaf(), DefaultComparer());
}
public this(cmp : TKey * TKey -> int)
{
this(0, TwoThreeTree.Node.Leaf(), MakeNodeComparer(cmp));
}
public this(coll : SCG.IEnumerable [TKey * TValue])
{
this(0, TwoThreeTree.Node.Leaf(), DefaultComparer(), coll)
}
public this(coll : SCG.IEnumerable [TKey * TValue], cmp : TKey * TKey -> int)
{
this(0, TwoThreeTree.Node.Leaf(), MakeNodeComparer(cmp), coll)
}
private this(mutable size : int, tree : TwoThreeTree.Node[Node], cmp : Node * Node -> int, coll : SCG.IEnumerable[TKey * TValue])
{
_cmp = cmp;
_tree = coll.Fold(tree, fun((key, value), tree) { tree.Insert(Node(key, value), _cmp, TwoThreeTree.InsertOptions.ThrowIfDuplicate, ref size) });
_size = size;
}
private this(size : int, tree : TwoThreeTree.Node[Node], cmp : Node * Node -> int)
{
_tree = tree;
_cmp = cmp;
_size = size;
}
#endregion
#region Contains
public Contains(key : TKey) : bool
{
mutable outNode;
_tree.TryGet(Node(key), _cmp, out outNode);
}
#endregion
public Clear() : Map[TKey, TValue]
{
Map(0, TwoThreeTree.Node.Leaf(), _cmp);
}
#region Add
public Add(key : TKey, value : TValue) : Map[TKey, TValue]
{
mutable size = _size;
def tree = _tree.Insert(Node(key, value), _cmp, TwoThreeTree.InsertOptions.ThrowIfDuplicate, ref size);
Map(size, tree, _cmp);
}
public AddRange(elems : SCG.IEnumerable[TKey * TValue]) : Map[TKey, TValue]
{
Map(_size, _tree, _cmp, elems)
}
public AddList(elems : list[TKey * TValue]) : Map[TKey, TValue]
{
AddRange(elems)
}
#endregion
#region Remove
public Remove(key : TKey) : Map[TKey, TValue]
{
mutable size = _size;
def tree = _tree.Delete(Node(key), _cmp, TwoThreeTree.DeleteOptions.IgnoreMissed, ref size);
Map(size, tree, _cmp);
}
public RemoveRange(elems : SCG.IEnumerable[TKey]) : Map[TKey, TValue]
{
mutable size = _size;
def tree = elems.Fold(_tree, fun(key : TKey, tree) { tree.Delete(Node(key), _cmp, TwoThreeTree.DeleteOptions.IgnoreMissed, ref size) });
Map(size, tree, _cmp);
}
public RemoveList(elems : list[TKey]) : Map[TKey, TValue]
{
mutable size = _size;
def tree = elems.Fold(_tree, fun(key : TKey, tree) { tree.Delete(Node(key), _cmp, TwoThreeTree.DeleteOptions.IgnoreMissed, ref size) });
Map(size, tree, _cmp);
}
#endregion
#region Replace
public Replace(key : TKey, value : TValue) : Map[TKey, TValue]
{
mutable size = _size;
def tree = _tree.Insert(Node(key, value), _cmp, TwoThreeTree.InsertOptions.Replace, ref size);
Map(size, tree, _cmp);
}
public ReplaceRange(elems : SCG.IEnumerable[TKey * TValue]) : Map[TKey, TValue]
{
mutable size = _size;
def tree = elems.Fold(_tree, fun((key, value), tree) { tree.Insert(Node(key, value), _cmp, TwoThreeTree.InsertOptions.Replace, ref size) });
Map(size, tree, _cmp);
}
public ReplaceList(elems : list[TKey * TValue]) : Map[TKey, TValue]
{
mutable size = _size;
def tree = elems.Fold(_tree, fun((key, value), tree) { tree.Insert(Node(key, value), _cmp, TwoThreeTree.InsertOptions.Replace, ref size) });
Map(size, tree, _cmp);
}
#endregion
#region Fold
public Fold[TAccumulator](acc : TAccumulator, fn : TKey * TValue * TAccumulator -> TAccumulator) : TAccumulator
{
_tree.FoldLeft(acc, fun(node, acc) { fn(node.Key, node.Value, acc) });
}
public FoldLeft[TAccumulator](acc : TAccumulator, fn : TKey * TValue * TAccumulator -> TAccumulator) : TAccumulator
{
_tree.FoldLeft(acc, fun(node, acc) { fn(node.Key, node.Value, acc) });
}
public FoldRight[TAccumulator](acc : TAccumulator, fn : TKey * TValue * TAccumulator -> TAccumulator) : TAccumulator
{
_tree.FoldRight(acc, fun(node, acc) { fn(node.Key, node.Value, acc) });
}
#endregion
#region Iter
public Iter(fn : TKey * TValue -> void) : void
{
_ = _tree.FoldLeft(null, (node, _) => { fn(node.Key, node.Value); null; })
}
public IterLeft(fn : TKey * TValue -> void) : void
{
_ = _tree.FoldLeft(null, (node, _) => { fn(node.Key, node.Value); null; })
}
public IterRight(fn : TKey * TValue -> void) : void
{
_ = _tree.FoldRight(null, (node, _) => { fn(node.Key, node.Value); null; })
}
#endregion
#region Filter
public Filter(fn : TKey * TValue -> bool) : Map[TKey, TValue]
{
def (size, tree) = _tree.Filter(_cmp, node => fn(node.Key, node.Value));
Map(size, tree, _cmp);
}
#endregion
#region Partition
public Partition(fn : TKey * TValue -> bool) : Map[TKey, TValue] * Map[TKey, TValue]
{
def (ysize, ytree, nsize, ntree) = _tree.Partition(_cmp, node => fn(node.Key, node.Value));
(Map(ysize, ytree, _cmp), Map(nsize, ntree, _cmp));
}
#endregion
#region ForAll
public ForAll(fn : TKey * TValue -> bool) : bool
{
_tree.ForAll(node => fn(node.Key, node.Value));
}
#endregion
#region Exists
public Exists(fn : TKey * TValue -> bool) : bool
{
_tree.Exists(node => fn(node.Key, node.Value));
}
#endregion
public Find(key : TKey) : option[TValue]
{
mutable value;
if (_tree.TryGet(Node(key), _cmp, out value))
Some(value.Value);
else
None();
}
public Get(key : TKey) : TValue
{
mutable value;
if (_tree.TryGet(Node(key), _cmp, out value))
value.Value;
else
{
assert2(false);
throw System.ArgumentException("key not found");
}
}
public ToList() : list[TKey * TValue]
{
_tree.MapToList(node => (node.Key, node.Value));
}
public ToArray() : array[TKey * TValue]
{
_tree.MapToArray(node => (node.Key, node.Value));
}
public MapToList[U](fn : TKey * TValue -> U) : list[U]
{
_tree.MapToList(node => (fn(node.Key, node.Value)));
}
public MapToArray[U](fn : TKey * TValue -> U) : array[U]
{
_tree.MapToArray(node => (fn(node.Key, node.Value)));
}
public IsEmpty : bool
{
get { _size == 0 }
}
#region ICollection
public GetEnumerator() : SCG.IEnumerator[TKey * TValue]
{
foreach (elem in _tree.Enumerate())
yield (elem.Key, elem.Value)
}
public CopyTo(arr : array[TKey * TValue], mutable arrayIndex : int) : void
{
def copyOne(value, arrayIndex)
{
arr[arrayIndex] = (value.Key, value.Value);
arrayIndex + 1;
}
_ = _tree.Fold(arrayIndex, copyOne);
}
public IsReadOnly : bool
{
get { true }
}
public Count : int
{
get { _size }
}
#endregion
public override ToString() : string
{
_tree.ToString("Map[", ", ", "]");
}
}
}