CSharp C# LinkedHashMap / LRU Cache
using System;
using System.Collections.Generic;
class LinkedHashMap
{
Dictionary>> D = new Dictionary>>();
LinkedList> LL = new LinkedList>();
public U this[T c]
{
get
{
return D[c].Value.Item1;
}
set
{
if(D.ContainsKey(c))
{
LL.Remove(D[c]);
}
D[c] = new LinkedListNode>(Tuple.Create(value, c));
LL.AddLast(D[c]);
}
}
public bool ContainsKey(T k)
{
return D.ContainsKey(k);
}
public U PopFirst()
{
var node = LL.First;
LL.Remove(node);
D.Remove(node.Value.Item2);
return node.Value.Item1;
}
public int Count
{
get
{
return D.Count;
}
}
}
class LinkedHashMapTest
{
public static void Test()
{
var lhm = new LinkedHashMap();
lhm['a'] = 1;
lhm['b'] = 2;
lhm['c'] = 3;
Console.WriteLine(lhm['a']);
Console.WriteLine(lhm['b']);
Console.WriteLine(lhm['c']);
Console.WriteLine(lhm.PopFirst());
Console.WriteLine(lhm.PopFirst());
Console.WriteLine(lhm.PopFirst());
}
}
CSharp C# SortedMultiset
CSharp does not have a SortedMultiSet out of the box.
This should work, but it's not extensively battle-tested and could have edge cases.
using System;
using System.Collections;
using System.Collections.Generic;
// Duck-taped SortedMultiSet by using a SortedSet and custom comparer function.
public class SortedMultiSet : IEnumerable
{
SortedSet data;
public SortedMultiSet(Comparer fn)
{
bool refType = default(T) == null;
if (!refType)
throw new Exception ("Will not work for value types.");
var fnd = Comparer.Create(
(a, b) =>
{
int r = fn.Compare(a,b);
if(r == 0)
{
// If same object (no matter values), is the same.
// Be careful because struct or objects that compare by value will not work.
if(a.Equals(b)) return 0;
// If not (same values according to compare function, but a
// distinct object), we give a consistent but arbitrary order.
if(a.GetHashCode() < b.GetHashCode()) return -1;
return 1;
}
return r;
});
this.data = new SortedSet(fnd);
}
public int Count
{
get
{
return this.data.Count;
}
}
public void Add(T v)
{
this.data.Add(v);
}
public void Remove(T v)
{
this.data.Remove(v);
}
public T Min()
{
return this.data.Min;
}
public T Max()
{
return this.data.Max;
}
public IEnumerator GetEnumerator()
{
return this.data.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
public class Run
{
class Node
{
public int i;
public int v;
public Node(int i, int v)
{
this.i = i;
this.v = v;
}
public override string ToString()
{
return string.Format("i: {0}, v: {1}", this.i, this.v);
}
}
public static void UnitTest(IEnumerable set, List vec, Func equal)
{
int i = 0;
foreach(var v in set)
{
Console.WriteLine(string.Format("{0}, {1}", v, vec[i]));
if(!equal(v, vec[i])) throw new Exception();
++i;
}
}
public static void UnitTestInts()
{
var smset = new SortedMultiSet(
Comparer.Create( (a, b) => a.CompareTo(b) )
);
var vec = new List();
var random = new Random(Environment.TickCount);
const int n = 100000;
for(int i = 0; i < n; ++i)
{
int v = random.Next(0, n/10);
vec.Add(v);
smset.Add(v);
}
vec.Sort();
UnitTest(smset, vec, (a,b) => a == b);
}
public static void UnitTestCustomClass()
{
var cmpFn = Comparer.Create( (a, b) => a.v.CompareTo(b.v) );
var smset = new SortedMultiSet( cmpFn );
var vec = new List();
var random = new Random(Environment.TickCount);
const int n = 100000;
for(int i = 0; i < n; ++i)
{
int v = random.Next(0, n/10);
var node = new Node(i, v);
vec.Add(node);
smset.Add(node);
}
vec.Sort( cmpFn );
UnitTest(smset, vec, (a,b) => a.v == b.v);
}
public static void UnitTestRemoveCustom()
{
var cmpFn = Comparer.Create( (a, b) => a.v.CompareTo(b.v) );
var smset = new SortedMultiSet( cmpFn );
// Should be able to remove self.
var node = new Node(0, 0);
if(smset.Count != 0) throw new Exception();
smset.Add(node);
if(smset.Count != 1) throw new Exception();
smset.Remove(node);
if(smset.Count != 0) throw new Exception();
smset.Add(node);
if(smset.Count != 1) throw new Exception();
// Different node with same value, should be independent.
var node2 = new Node(0, 0);
smset.Add(node2);
if(smset.Count != 2) throw new Exception();
smset.Add(node2);
if(smset.Count != 2) throw new Exception();
smset.Add(node);
if(smset.Count != 2) throw new Exception();
smset.Remove(node);
if(smset.Count != 1) throw new Exception();
smset.Remove(node);
if(smset.Count != 1) throw new Exception();
smset.Remove(node2);
if(smset.Count != 0) throw new Exception();
}
public static void UnitTestRemoveValueType()
{
var cmpFn = Comparer.Create( (a, b) => a.CompareTo(b) );
var smset = new SortedMultiSet( cmpFn );
// Should be able to remove same.
if(smset.Count != 0) throw new Exception();
smset.Add(1);
if(smset.Count != 1) throw new Exception();
smset.Remove(1);
if(smset.Count != 0) throw new Exception();
smset.Add(1);
if(smset.Count != 1) throw new Exception();
// Different node with same value, should be independent.
smset.Add(2);
if(smset.Count != 2) throw new Exception();
smset.Add(2);
if(smset.Count != 3) throw new Exception();
smset.Add(1);
if(smset.Count != 4) throw new Exception();
smset.Remove(1);
if(smset.Count != 3) throw new Exception();
smset.Remove(1);
if(smset.Count != 2) throw new Exception();
smset.Remove(2);
if(smset.Count != 1) throw new Exception();
smset.Remove(1);
if(smset.Count != 0) throw new Exception();
smset.Remove(1);
if(smset.Count != 0) throw new Exception();
}
public static void Main()
{
// UnitTestInts();
UnitTestCustomClass();
UnitTestRemoveCustom();
// UnitTestRemoveValueType();
}
}
If you do not care at all about performance (you just want to have something that will respect the SortedMultiset behavior), here is a silly version that justs uses a vector underneath and re-sorts for every insert.
using System;
using System.Collections;
using System.Collections.Generic;
// C# does not have a SortedMultiSet, use this class if you need the interface for verifications,
// but do not care about performance.
//
// This does NOT use a red-black tree as storage (it justs re-sorts a basic linear DS),
// so the performance will be horrible.
public class FakeSortedMultiSet : IEnumerable
{
List data;
Comparer compareFn;
public FakeSortedMultiSet()
: this(null)
{
this.data = new List();
}
public FakeSortedMultiSet(Comparer fn)
{
this.data = new List();
this.compareFn = fn;
}
public int Count
{
get
{
return this.data.Count;
}
}
public void Add(T v)
{
this.data.Add(v);
// Obviously, this is really silly performance-wise.
this.data.Sort(this.compareFn);
}
public void Remove(T v)
{
this.data.Remove(v);
}
public T Min()
{
return this.data[0];
}
public T Max()
{
return this.data[this.data.Count-1];
}
public IEnumerator GetEnumerator()
{
return this.data.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
public class Run
{
class Node
{
public int i;
public int v;
public Node(int i, int v)
{
this.i = i;
this.v = v;
}
public override string ToString()
{
return string.Format("i: {0}, v: {1}", this.i, this.v);
}
}
public static void Main()
{
var sortedVector = new FakeSortedMultiSet();
var vector = new List();
vector.Add( 10 );
vector.Add( 3 );
vector.Add( 5 );
vector.Add( 5 );
vector.Add( 5 );
vector.Add( 100 );
vector.Add( 1 );
foreach(var v in vector)
{
sortedVector.Add(v);
}
vector.Sort();
int i = 0;
foreach(var v in sortedVector)
{
if( v != vector[i] ) throw new Exception();
++i;
}
var nodes = new List();
nodes.Add( new Node(7, 10) );
nodes.Add( new Node(10, 1) );
nodes.Add( new Node(1, -234) );
nodes.Add( new Node(3, 100) );
var sortedNodes = new FakeSortedMultiSet(
Comparer.Create( (a, b) => a.v.CompareTo(b.v) )
);
foreach(var v in nodes)
{
sortedNodes.Add(v);
}
nodes.Sort( (a,b) => a.v.CompareTo(b.v) );
i = 0;
foreach(var v in sortedNodes)
{
Console.WriteLine(v);
if( v != nodes[i] ) throw new Exception();
++i;
}
}
}
