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 using System;
  23 using System.Collections;
  24 using System.Collections.Generic;
  25 using System.Linq;
  26
  27 namespace OpenTween
  28 {
  29     /// <summary>
  30     /// インデックスでのアクセスが可能なソートされた重複のないコレクション
  31     /// </summary>
  32     public class IndexedSortedSet<T> : ISet<T>, IReadOnlyList<T>
  33     {
  34         private readonly List<T> innerList;
  35         private readonly IComparer<T> comparer;
  36
  37         public int Count
  38             => this.innerList.Count;
  39
  40         public bool IsReadOnly
  41             => false;
  42
  43         public T this[int index]
  44             => this.innerList[index];
  45
  46         public IndexedSortedSet()
  47             : this(Enumerable.Empty<T>(), Comparer<T>.Default)
  48         {
  49         }
  50
  51         public IndexedSortedSet(IComparer<T> comparer)
  52             : this(Enumerable.Empty<T>(), comparer)
  53         {
  54         }
  55
  56         public IndexedSortedSet(IEnumerable<T> items)
  57             : this(items, Comparer<T>.Default)
  58         {
  59         }
  60
  61         public IndexedSortedSet(IEnumerable<T> items, IComparer<T> comparer)
  62         {
  63             this.innerList = new List<T>(items.OrderBy(x => x, comparer));
  64             this.comparer = comparer;
  65         }
  66
  67         public bool Add(T item)
  68         {
  69             if (this.innerList.Count == 0)
  70             {
  71                 this.innerList.Add(item);
  72                 return true;
  73             }
  74
  75             var index = this.innerList.BinarySearch(item, comparer);
  76             if (index >= 0)
  77                 return false;
  78
  79             // ~index → item の次に大きい要素のインデックス
  80             this.innerList.Insert(~index, item);
  81
  82             return true;
  83         }
  84
  85         void ICollection<T>.Add(T item)
  86             => this.Add(item);
  87
  88         public bool Remove(T item)
  89         {
  90             var index = this.IndexOf(item);
  91             if (index == -1)
  92                 return false;
  93
  94             this.innerList.RemoveAt(index);
  95
  96             return true;
  97         }
  98
  99         public void Clear()
 100             => this.innerList.Clear();
 101
 102         public bool Contains(T item)
 103             => this.IndexOf(item) != -1;
 104
 105         public int IndexOf(T item)
 106         {
 107             var index = this.innerList.BinarySearch(item, this.comparer);
 108
 109             return index < 0 ? -1 : index;
 110         }
 111
 112         public void RemoveAt(int index)
 113             => this.innerList.RemoveAt(index);
 114
 115         public void CopyTo(T[] array, int arrayIndex)
 116         {
 117             if (array == null)
 118                 throw new ArgumentNullException(nameof(array));
 119             if (arrayIndex < 0)
 120                 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 121             if (arrayIndex >= array.Length)
 122                 throw new ArgumentException($"{nameof(arrayIndex)} is equal to or greater than {nameof(array)}.Length.", nameof(arrayIndex));
 123             if (array.Length - arrayIndex < this.Count)
 124                 throw new ArgumentException("The destination array is too small.", nameof(array));
 125
 126             foreach (var pair in this)
 127                 array[arrayIndex++] = pair;
 128         }
 129
 130         public IEnumerator<T> GetEnumerator()
 131             => this.innerList.GetEnumerator();
 132
 133         IEnumerator IEnumerable.GetEnumerator()
 134             => this.GetEnumerator();
 135
 136         public void UnionWith(IEnumerable<T> other)
 137         {
 138             foreach (var item in other)
 139                 this.Add(item);
 140         }
 141
 142         public void IntersectWith(IEnumerable<T> other)
 143         {
 144             var containsMark = new bool[this.Count];
 145
 146             foreach (var item in other)
 147             {
 148                 var index = this.IndexOf(item);
 149                 if (index != -1)
 150                     containsMark[index] = true;
 151             }
 152
 153             foreach (var index in MyCommon.CountDown(this.Count - 1, 0))
 154             {
 155                 if (!containsMark[index])
 156                     this.RemoveAt(index);
 157             }
 158         }
 159
 160         public void ExceptWith(IEnumerable<T> other)
 161         {
 162             foreach (var item in other)
 163                 this.Remove(item);
 164         }
 165
 166         public void SymmetricExceptWith(IEnumerable<T> other)
 167         {
 168             foreach (var item in other)
 169             {
 170                 if (this.Contains(item))
 171                     this.Remove(item);
 172                 else
 173                     this.Add(item);
 174             }
 175         }
 176
 177         public bool IsSubsetOf(IEnumerable<T> other)
 178         {
 179             var containsMark = new bool[this.Count];
 180
 181             foreach (var item in other)
 182             {
 183                 var index = this.IndexOf(item);
 184                 if (index != -1)
 185                     containsMark[index] = true;
 186             }
 187
 188             return containsMark.All(x => x == true);
 189         }
 190
 191         public bool IsSupersetOf(IEnumerable<T> other)
 192         {
 193             foreach (var item in other)
 194             {
 195                 if (!this.Contains(item))
 196                     return false;
 197             }
 198
 199             return true;
 200         }
 201
 202         public bool IsProperSupersetOf(IEnumerable<T> other)
 203             => !this.SetEquals(other) && this.IsSupersetOf(other);
 204
 205         public bool IsProperSubsetOf(IEnumerable<T> other)
 206             => !this.SetEquals(other) && this.IsSubsetOf(other);
 207
 208         public bool Overlaps(IEnumerable<T> other)
 209         {
 210             foreach (var item in other)
 211             {
 212                 if (this.Contains(item))
 213                     return true;
 214             }
 215
 216             return false;
 217         }
 218
 219         public bool SetEquals(IEnumerable<T> other)
 220         {
 221             var containsMark = new bool[this.Count];
 222
 223             foreach (var item in other)
 224             {
 225                 var index = this.IndexOf(item);
 226                 if (index == -1)
 227                     return false;
 228
 229                 containsMark[index] = true;
 230             }
 231
 232             return containsMark.All(x => x == true);
 233         }
 234     }
 235 }