OpenTween/IndexedSortedSet.cs

   1 // OpenTween - Client of Twitter
   2 // Copyright (c) 2015 kim_upsilon (@kim_upsilon) <https://upsilo.net/~upsilon/>
   3 // All rights reserved.
   4 //
   5 // This file is part of OpenTween.
   6 //
   7 // This program is free software; you can redistribute it and/or modify it
   8 // under the terms of the GNU General Public License as published by the Free
   9 // Software Foundation; either version 3 of the License, or (at your option)
  10 // any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
  15 // for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License along
  18 // with this program. If not, see <http://www.gnu.org/licenses/>, or write to
  19 // the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
  20 // Boston, MA 02110-1301, USA.
  21
  22 #nullable enable
  23
  24 using System;
  25 using System.Collections;
  26 using System.Collections.Generic;
  27 using System.Linq;
  28
  29 namespace OpenTween
  30 {
  31     /// <summary>
  32     /// インデックスでのアクセスが可能なソートされた重複のないコレクション
  33     /// </summary>
  34     public class IndexedSortedSet<T> : ISet<T>, IReadOnlyList<T>
  35     {
  36         private readonly List<T> innerList;
  37         private readonly IComparer<T> comparer;
  38
  39         public int Count
  40             => this.innerList.Count;
  41
  42         public bool IsReadOnly
  43             => false;
  44
  45         public T this[int index]
  46             => this.innerList[index];
  47
  48         public IndexedSortedSet()
  49             : this(Enumerable.Empty<T>(), Comparer<T>.Default)
  50         {
  51         }
  52
  53         public IndexedSortedSet(IComparer<T> comparer)
  54             : this(Enumerable.Empty<T>(), comparer)
  55         {
  56         }
  57
  58         public IndexedSortedSet(IEnumerable<T> items)
  59             : this(items, Comparer<T>.Default)
  60         {
  61         }
  62
  63         public IndexedSortedSet(IEnumerable<T> items, IComparer<T> comparer)
  64         {
  65             this.innerList = new List<T>(items.OrderBy(x => x, comparer));
  66             this.comparer = comparer;
  67         }
  68
  69         public bool Add(T item)
  70         {
  71             if (this.innerList.Count == 0)
  72             {
  73                 this.innerList.Add(item);
  74                 return true;
  75             }
  76
  77             var index = this.innerList.BinarySearch(item, comparer);
  78             if (index >= 0)
  79                 return false;
  80
  81             // ~index → item の次に大きい要素のインデックス
  82             this.innerList.Insert(~index, item);
  83
  84             return true;
  85         }
  86
  87         void ICollection<T>.Add(T item)
  88             => this.Add(item);
  89
  90         public bool Remove(T item)
  91         {
  92             var index = this.IndexOf(item);
  93             if (index == -1)
  94                 return false;
  95
  96             this.innerList.RemoveAt(index);
  97
  98             return true;
  99         }
 100
 101         public void Clear()
 102             => this.innerList.Clear();
 103
 104         public bool Contains(T item)
 105             => this.IndexOf(item) != -1;
 106
 107         public int IndexOf(T item)
 108         {
 109             var index = this.innerList.BinarySearch(item, this.comparer);
 110
 111             return index < 0 ? -1 : index;
 112         }
 113
 114         public void RemoveAt(int index)
 115             => this.innerList.RemoveAt(index);
 116
 117         public void CopyTo(T[] array, int arrayIndex)
 118         {
 119             if (array == null)
 120                 throw new ArgumentNullException(nameof(array));
 121             if (arrayIndex < 0)
 122                 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 123             if (arrayIndex >= array.Length)
 124                 throw new ArgumentException($"{nameof(arrayIndex)} is equal to or greater than {nameof(array)}.Length.", nameof(arrayIndex));
 125             if (array.Length - arrayIndex < this.Count)
 126                 throw new ArgumentException("The destination array is too small.", nameof(array));
 127
 128             foreach (var pair in this)
 129                 array[arrayIndex++] = pair;
 130         }
 131
 132         public IEnumerator<T> GetEnumerator()
 133             => this.innerList.GetEnumerator();
 134
 135         IEnumerator IEnumerable.GetEnumerator()
 136             => this.GetEnumerator();
 137
 138         public void UnionWith(IEnumerable<T> other)
 139         {
 140             foreach (var item in other)
 141                 this.Add(item);
 142         }
 143
 144         public void IntersectWith(IEnumerable<T> other)
 145         {
 146             var containsMark = new bool[this.Count];
 147
 148             foreach (var item in other)
 149             {
 150                 var index = this.IndexOf(item);
 151                 if (index != -1)
 152                     containsMark[index] = true;
 153             }
 154
 155             foreach (var index in MyCommon.CountDown(this.Count - 1, 0))
 156             {
 157                 if (!containsMark[index])
 158                     this.RemoveAt(index);
 159             }
 160         }
 161
 162         public void ExceptWith(IEnumerable<T> other)
 163         {
 164             foreach (var item in other)
 165                 this.Remove(item);
 166         }
 167
 168         public void SymmetricExceptWith(IEnumerable<T> other)
 169         {
 170             foreach (var item in other)
 171             {
 172                 if (this.Contains(item))
 173                     this.Remove(item);
 174                 else
 175                     this.Add(item);
 176             }
 177         }
 178
 179         public bool IsSubsetOf(IEnumerable<T> other)
 180         {
 181             var containsMark = new bool[this.Count];
 182
 183             foreach (var item in other)
 184             {
 185                 var index = this.IndexOf(item);
 186                 if (index != -1)
 187                     containsMark[index] = true;
 188             }
 189
 190             return containsMark.All(x => x == true);
 191         }
 192
 193         public bool IsSupersetOf(IEnumerable<T> other)
 194         {
 195             foreach (var item in other)
 196             {
 197                 if (!this.Contains(item))
 198                     return false;
 199             }
 200
 201             return true;
 202         }
 203
 204         public bool IsProperSupersetOf(IEnumerable<T> other)
 205             => !this.SetEquals(other) && this.IsSupersetOf(other);
 206
 207         public bool IsProperSubsetOf(IEnumerable<T> other)
 208             => !this.SetEquals(other) && this.IsSubsetOf(other);
 209
 210         public bool Overlaps(IEnumerable<T> other)
 211         {
 212             foreach (var item in other)
 213             {
 214                 if (this.Contains(item))
 215                     return true;
 216             }
 217
 218             return false;
 219         }
 220
 221         public bool SetEquals(IEnumerable<T> other)
 222         {
 223             var containsMark = new bool[this.Count];
 224
 225             foreach (var item in other)
 226             {
 227                 var index = this.IndexOf(item);
 228                 if (index == -1)
 229                     return false;
 230
 231                 containsMark[index] = true;
 232             }
 233
 234             return containsMark.All(x => x == true);
 235         }
 236     }
 237 }