// OpenTween - Client of Twitter
// Copyright (c) 2015 kim_upsilon (@kim_upsilon)
// All rights reserved.
//
// This file is part of OpenTween.
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3 of the License, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
// or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program. If not, see , or write to
// the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
// Boston, MA 02110-1301, USA.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace OpenTween
{
///
/// インデックスでのアクセスが可能なソートされた重複のないコレクション
///
public class IndexedSortedSet : ISet, IReadOnlyList
{
private readonly List innerList;
private readonly IComparer comparer;
public int Count
=> this.innerList.Count;
public bool IsReadOnly
=> false;
public T this[int index]
=> this.innerList[index];
public IndexedSortedSet()
: this(Enumerable.Empty(), Comparer.Default)
{
}
public IndexedSortedSet(IComparer comparer)
: this(Enumerable.Empty(), comparer)
{
}
public IndexedSortedSet(IEnumerable items)
: this(items, Comparer.Default)
{
}
public IndexedSortedSet(IEnumerable items, IComparer comparer)
{
this.innerList = new List(items.OrderBy(x => x, comparer));
this.comparer = comparer;
}
public bool Add(T item)
{
if (this.innerList.Count == 0)
{
this.innerList.Add(item);
return true;
}
var index = this.innerList.BinarySearch(item, comparer);
if (index >= 0)
return false;
// ~index → item の次に大きい要素のインデックス
this.innerList.Insert(~index, item);
return true;
}
void ICollection.Add(T item)
=> this.Add(item);
public bool Remove(T item)
{
var index = this.IndexOf(item);
if (index == -1)
return false;
this.innerList.RemoveAt(index);
return true;
}
public void Clear()
=> this.innerList.Clear();
public bool Contains(T item)
=> this.IndexOf(item) != -1;
public int IndexOf(T item)
{
var index = this.innerList.BinarySearch(item, this.comparer);
return index < 0 ? -1 : index;
}
public void RemoveAt(int index)
=> this.innerList.RemoveAt(index);
public void CopyTo(T[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException(nameof(array));
if (arrayIndex < 0)
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
if (arrayIndex >= array.Length)
throw new ArgumentException($"{nameof(arrayIndex)} is equal to or greater than {nameof(array)}.Length.", nameof(arrayIndex));
if (array.Length - arrayIndex < this.Count)
throw new ArgumentException("The destination array is too small.", nameof(array));
foreach (var pair in this)
array[arrayIndex++] = pair;
}
public IEnumerator GetEnumerator()
=> this.innerList.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator()
=> this.GetEnumerator();
public void UnionWith(IEnumerable other)
{
foreach (var item in other)
this.Add(item);
}
public void IntersectWith(IEnumerable other)
{
var containsMark = new bool[this.Count];
foreach (var item in other)
{
var index = this.IndexOf(item);
if (index != -1)
containsMark[index] = true;
}
foreach (var index in MyCommon.CountDown(this.Count - 1, 0))
{
if (!containsMark[index])
this.RemoveAt(index);
}
}
public void ExceptWith(IEnumerable other)
{
foreach (var item in other)
this.Remove(item);
}
public void SymmetricExceptWith(IEnumerable other)
{
foreach (var item in other)
{
if (this.Contains(item))
this.Remove(item);
else
this.Add(item);
}
}
public bool IsSubsetOf(IEnumerable other)
{
var containsMark = new bool[this.Count];
foreach (var item in other)
{
var index = this.IndexOf(item);
if (index != -1)
containsMark[index] = true;
}
return containsMark.All(x => x == true);
}
public bool IsSupersetOf(IEnumerable other)
{
foreach (var item in other)
{
if (!this.Contains(item))
return false;
}
return true;
}
public bool IsProperSupersetOf(IEnumerable other)
=> !this.SetEquals(other) && this.IsSupersetOf(other);
public bool IsProperSubsetOf(IEnumerable other)
=> !this.SetEquals(other) && this.IsSubsetOf(other);
public bool Overlaps(IEnumerable other)
{
foreach (var item in other)
{
if (this.Contains(item))
return true;
}
return false;
}
public bool SetEquals(IEnumerable other)
{
var containsMark = new bool[this.Count];
foreach (var item in other)
{
var index = this.IndexOf(item);
if (index == -1)
return false;
containsMark[index] = true;
}
return containsMark.All(x => x == true);
}
}
}