using System; using System.Collections.Generic; using System.Collections; public class Set { /* Invariant: At most one occurrence of an element in the array store Consequtive storing from low end. */ private int capacity; private static int DefaultCapacity = 3; private T[] store; private int next; public Set(int capacity){ this.capacity = capacity; store = new T[capacity]; next = 0; } public Set(): this(DefaultCapacity){ } public Set(T[] elements): this(elements.Length){ foreach(T el in elements) this.Insert(el); } // Copy constructor public Set(Set s): this(s.capacity){ foreach(T el in s) this.Insert(el); } public bool Member(T element){ for(int idx = 0; idx < next; idx++) if (element.Equals(store[idx])) return true; return false; } public void Insert(T element){ if (!this.Member(element)){ if (this.Full){ Console.WriteLine("[Resize to {0}]", capacity * 2); Array.Resize(ref store, capacity * 2); capacity = capacity * 2; } store[next] = element; next++; } } public void Delete(T element){ bool found = false; int foundIdx = 0; for(int idx = 0; !found && (idx < next); idx++){ if (element.Equals(store[idx])){ found = true; foundIdx = idx; } } if (found){ // shift remaining elements left for(int idx = foundIdx+1; idx < next; idx++) store[idx-1] = store[idx]; store[next-1] = default(T); next--; } } public int Count{ get{ return next; } } // Is this set a subset of other public bool Subset(Set other){ foreach(T e in this) if (!other.Member(e)) return false; return true; } public Set Intersection(Set other){ Set res = new Set(this.Count); foreach(T e in this) if (other.Member(e)) res.Insert(e); return res; } public Set Union(Set other){ Set res = new Set(this.Count + other.Count); foreach(T e in this) res.Insert(e); foreach(T e in other) res.Insert(e); return res; } // Subtract other elements from this set. public Set Diff(Set other){ Set res = new Set(this); foreach(T e in other) res.Delete(e); return res; } public override string ToString(){ string elRes = ""; for(int idx = 0; idx < next; idx++) if (store[idx] != null) elRes += " " + store[idx]; return "{" + elRes + " "+ "}" + this.Count; } private class SetEnumerator: IEnumerator{ private readonly Set set; private int idx; public SetEnumerator (Set s){ this.set = s; idx = -1; // position enumerator outside range } public T Current{ get { return set.store[idx]; } } Object IEnumerator.Current{ get { return set.store[idx]; } } public bool MoveNext(){ if (idx < set.next - 1){ idx++; return true; } else return false; } public void Reset(){ idx = -1; } public void Dispose(){ } } public IEnumerator GetEnumerator (){ return new SetEnumerator(this); } private bool Full{ get{ return next == capacity; } } }