ISet、SortedSet、またはカスタム クラス (不明) にバインドされた 3 つの ListBox 要素を含む WPF アプリケーションを構築しています。以前の Java の経験に基づいて、次の制約が必要なため、この結論に達しました。
- パフォーマンスを念頭に置いて、追加でソートする必要があります
- 重複を含めないでください
MSDN にアクセスして、ObservableCollection が使用するインターフェイスを確認した後、次のようにすることにしました。
public class ObservableSortedSet<T> : SortedSet<T>, INotifyCollectionChanged
{
public event NotifyCollectionChangedEventHandler CollectionChanged;
public override bool Add(T item)
{
bool result = base.Add(item);
OnCollectionChanged(NotifyCollectionChangedAction.Add);
return true;
}
private void OnCollectionChanged(NotifyCollectionChangedAction action)
{
if (CollectionChanged != null)
CollectionChanged(this, new NotifyCollectionChangedEventArgs(action));
}
}
.NET の ObservableCollection クラスに触発されて ObservableSortedSet を作成しましたが、どうやら C# では virtual、override、および new キーワードを使用するため、SortedSet には virtual add メソッドがないため、上記のようにはできません。そこで私の質問は、SortedSet をどのように作成するか、またはどの .NET クラスが必要な機能を提供するかということです。独自の SortedSet クラスを作成できると思いますが、それは .NET フレームワークに組み込まれているように思えます。
更新 上記のようなものが必要な場合は、先に進んで作成しました。私は自分のプロジェクトでしばらく使用してきましたが、かなり安定しているようです。私はずっと前に作成した連結リストの実装を使用して、ソートされたセットとして機能するように調整しました。これにより、並べ替えをすばやく実行できます。
コードは次のとおりです。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
namespace Conquest.Collections {
public class OrderedSet<T> : IEnumerable<T>, INotifyCollectionChanged where T : IComparable<T> {
private Node<T> head;
private Node<T> tail;
public OrderedSet() {
Count = 0;
}
public OrderedSet(IEnumerable<T> enumerable) {
Count = 0;
foreach (T element in enumerable)
Add(element);
}
public T First {
get { return (head == null) ? default(T) : head.Datum; }
}
public T Last {
get { return (tail == null) ? default(T) : tail.Datum; }
}
public int Count { get; private set; }
public IEnumerator<T> GetEnumerator() {
return new OrderedSetEnumerator<T>(this);
}
IEnumerator IEnumerable.GetEnumerator() {
return new OrderedSetEnumerator<T>(this);
}
private void InsertNodeBefore(Node<T> insertingNode, Node<T> here) {
insertingNode.Next = here;
insertingNode.Previous = here.Previous;
if (here == head)
head = insertingNode;
else
here.Previous.Next = insertingNode;
here.Previous = insertingNode;
insertingNode.Index = here.Index;
for (Node<T> n = here; n != null; n = n.Next)
n.Index++;
}
private void InsertNodeAfter(Node<T> insertNode, Node<T> here) {
insertNode.Previous = here;
insertNode.Next = here.Next;
if (here == tail)
tail = insertNode;
else
here.Next.Previous = insertNode;
here.Next = insertNode;
insertNode.Index = here.Index + 1;
for (Node<T> n = insertNode.Next; n != null; n = n.Next)
n.Index++;
}
private bool IsNodeSorted(Node<T> node) {
if (Count == 1)
return true;
return (node == head && node.Next.Datum.CompareTo(node.Datum) > 0) ||
(node == tail && node.Previous.Datum.CompareTo(node.Datum) < 0) ||
(node != tail && node != head && node.Next.Datum.CompareTo(node.Datum) > 0 &&
node.Previous.Datum.CompareTo(node.Datum) < 0);
}
private void RemoveNode(Node<T> node) {
if (node == head)
head = node.Next;
else
node.Previous.Next = node.Next;
if (node == tail)
tail = node.Previous;
else
node.Next.Previous = node.Previous;
for (Node<T> n = node.Next; n != null; n = n.Next)
n.Index--;
Count--;
}
private void SortNodeLeft(Node<T> node) {
// Unlink
RemoveNode(node);
Count++;
for (Node<T> currentNode = node.Previous; currentNode != null; currentNode = currentNode.Previous) {
int compareResult = currentNode.Datum.CompareTo(node.Datum);
if (compareResult < 0) {
// Link
InsertNodeAfter(node, currentNode);
return;
}
}
InsertNodeBefore(node, head);
}
private void SortNodeRight(Node<T> node) {
// Unlink
RemoveNode(node);
Count++;
for (Node<T> currentNode = node.Next; currentNode != null; currentNode = currentNode.Next) {
int compareResult = currentNode.Datum.CompareTo(node.Datum);
if (compareResult > 0) {
// Link
InsertNodeBefore(node, currentNode);
return;
}
}
InsertNodeAfter(node, tail);
}
public bool Add(T item) {
var node = new Node<T>(item);
int index = 0;
if (head == null) {
head = node;
tail = head;
}
else {
for (Node<T> currentNode = head; currentNode != null; currentNode = currentNode.Next, index++) {
int compareResult = currentNode.Datum.CompareTo(item);
if (compareResult == 0)
return false;
else if (compareResult > 0) {
InsertNodeBefore(node, currentNode);
break;
}
// if so, make node the new tail
else if (currentNode == tail) {
InsertNodeAfter(node, tail);
index++;
break;
}
}
}
Count++;
NotifyCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, item, index));
node.Index = index;
node.PropertyChanged += Sort;
return true;
}
/// <summary>
/// If the nodes datum changes state, this function ensures
/// the set remains sorted.
/// </summary>
/// <param name="sender">The node</param>
/// <param name="e">The property that changed</param>
private void Sort(object sender, PropertyChangedEventArgs e) {
var node = (Node<T>) sender;
int index = node.Index;
// Check if node is still in correct spot
if (IsNodeSorted(node))
return;
if (node.Previous == null || (node.Previous.Datum.CompareTo(node.Datum) < 0))
SortNodeRight(node);
else
SortNodeLeft(node);
NotifyCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Move, node.Datum,
node.Index, index));
}
public bool Remove(T item) {
if (head == null)
return false;
for (Node<T> node = head; node != null; node = node.Next) {
if (node.Datum.CompareTo(item) == 0) {
RemoveNode(node);
NotifyCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove,
item, node.Index));
return true;
}
}
return false;
}
#region INotifyCollectionChanged
public event NotifyCollectionChangedEventHandler CollectionChanged;
private void NotifyCollectionChanged(NotifyCollectionChangedEventArgs args) {
if (CollectionChanged != null)
CollectionChanged(this, args);
}
#endregion
#region Enumerator
private class OrderedSetEnumerator<U> : IEnumerator<U> where U : IComparable<U> {
private readonly OrderedSet<U> set;
private OrderedSet<U>.Node<U> current;
public OrderedSetEnumerator(OrderedSet<U> set) {
this.set = set;
current = null;
}
public U Current {
get { return (current == null) ? default(U) : current.Datum; }
}
Object IEnumerator.Current {
get { return (current == null) ? null : (Object) current.Datum; }
}
public bool MoveNext() {
current = current == null ? set.head : current.Next;
return (current != null);
}
public void Reset() {
current = null;
}
public void Dispose() {
current = null;
}
}
#endregion
private class Node<U> : INotifyPropertyChanged {
public Node(U datum) {
Datum = datum;
var flagObserveChanges = datum as INotifyPropertyChanged;
if (flagObserveChanges != null)
flagObserveChanges.PropertyChanged += NotifySet;
}
public Node<U> Next { get; set; }
public Node<U> Previous { get; set; }
public int Index { get; set; }
public U Datum { get; set; }
public event PropertyChangedEventHandler PropertyChanged;
private void NotifySet(object sender, PropertyChangedEventArgs e) {
if (PropertyChanged != null)
PropertyChanged(this, e);
}
}
}
}
そしてもちろん、簡単なテストケースをいくつか作成したので、拡張したいと思うかもしれません:)
using System.Linq;
using Conquest.Collections;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;
using System.ComponentModel;
using System;
namespace Conquest.Test.Collections
{
[TestClass]
public class OrderedSetTest
{
private class Department : INotifyPropertyChanged, IComparable<Department> {
private string name;
public string Name {
get { return name; }
set {
name = value;
if (PropertyChanged != null)
PropertyChanged(this, new PropertyChangedEventArgs("Name"));
}
}
public event PropertyChangedEventHandler PropertyChanged;
public int CompareTo(Department other) {
return String.Compare(this.Name, other.Name, StringComparison.OrdinalIgnoreCase);
}
}
[TestMethod]
public void TestAddSingleItem()
{
var set = new OrderedSet<int> {1};
Assert.AreEqual(set.First, 1, "Head points to correct location");
Assert.AreEqual(set.Count, 1, "Correct Size");
Assert.AreEqual(set.Last, 1, "Tail points to correct location");
}
[TestMethod]
public void TestAddHead()
{
var set = new OrderedSet<int> {2, 1};
Assert.AreEqual(set.First, 1, "Head points to correct value");
}
[TestMethod]
public void TestAddTail()
{
var set = new OrderedSet<int> {1, 2};
Assert.AreEqual(set.Last, 2, "Tail points to correct value");
Assert.AreEqual(set.Count, 2, "Correct Size");
}
[TestMethod]
public void TestAddDuplicationItems()
{
var set = new OrderedSet<int> {1, 1};
Assert.IsTrue(1 == set.Count);
}
[TestMethod]
public void TestAddMultipleItems()
{
var set = new OrderedSet<int> {3, 2, 4, 1, 5};
int expected = 1;
bool worked = true;
foreach (int i in set)
{
if (i != expected)
{
worked = false;
break;
}
expected++;
}
Assert.IsTrue(worked, "Multiple Items");
}
[TestMethod]
public void TestRemoveSingleItem()
{
var set = new OrderedSet<int> {1};
set.Remove(1);
Assert.AreEqual(set.Count, 0, "Removed single item");
Assert.AreEqual(set.First, 0, "Head does not point to anything");
Assert.AreEqual(set.Last, 0, "Tail does not point to anything");
}
[TestMethod]
public void TestRemoveHead()
{
var set = new OrderedSet<int> {1, 2};
set.Remove(1);
Assert.AreEqual(set.Count, 1, "Removed head with more than one item in set");
Assert.AreEqual(set.First, 2, "Head points to the next value in set");
}
[TestMethod]
public void TestRemoveTail()
{
var set = new OrderedSet<int> {1, 2};
set.Remove(2);
Assert.AreEqual(set.Count, 1, "Removed tail with more than one item in set");
Assert.AreEqual(set.Last, 1, "Tail points to the previous value in set");
}
[TestMethod]
public void TestRemoveItem()
{
var set = new OrderedSet<int> {1, 2, 3};
Assert.IsTrue(set.Remove(2), "Remove correct value");
Assert.IsTrue(set.Count == 2, "Removed item");
int sum = set.Sum();
Assert.AreEqual(4, sum, "Remove correctly relinked adjacent nodes");
}
[TestMethod]
public void TestSortOnAdd()
{
var test = new Queue<int>();
for (int i = 0; i < 10; i++)
test.Enqueue(i);
var set = new OrderedSet<int> {5, 4, 3, 7, 2, 8, 1, 9, 0, 6};
var worked = set.All(i => i == test.Dequeue());
Assert.IsTrue(worked, "Sorted on Add");
}
[TestMethod]
public void TestSortOnEdit()
{
var dep1 = new Department
{
Name = "Test"
};
var dep2 = new Department
{
Name = "Test2"
};
var set = new OrderedSet<Department> {dep1, dep2};
dep2.Name = "Hello";
var e = set.GetEnumerator();
e.MoveNext();
Assert.AreEqual("Hello", e.Current.Name, "Swaped tail to head on edit");
dep1.Name = "Abc";
e = set.GetEnumerator();
e.MoveNext();
Assert.AreEqual("Abc", e.Current.Name, "Verified integrity of node linkage");
var dep3 = new Department
{
Name = "Test3"
};
set.Add(dep3);
dep3.Name = "Cat";
e = set.GetEnumerator();
e.MoveNext();
bool correctOrder = e.Current.Name == "Abc";
e.MoveNext();
correctOrder = correctOrder && e.Current.Name == "Cat";
Assert.IsTrue(correctOrder, "Moved item to the left");
dep1.Name = "Dad";
e = set.GetEnumerator();
e.MoveNext();
correctOrder = e.Current.Name == "Cat";
e.MoveNext();
correctOrder = correctOrder && e.Current.Name == "Dad";
Assert.IsTrue(correctOrder, "Moved item to the right");
}
}
}