数学集合的Java实现

除了老师说的3条外，有一点需要注意，即集合可以包含集合，例如{{1},2,3}。我定义可以放进集合里的东西叫Element。Element有两种，一是1、2、3之类的数字——Number，一是{4}、{8,9}之类的集合——Set。然后按老师讲的，Set分为EmptySet、 SingletonSet和UnionSet。

Set有两种主要操作：

contains(Element e)，看看e是不是在集合里面。如{1,2,3}.contains(3)=>true；{1,2,3}.contains({3})=>false。

union(Set s)，把两个集合并起来。如{1,3,4}.union({5,7})=>{1,3,4,5,7}。

public abstract class Element { @Override public abstract String toString(); @Override public abstract boolean equals(Object other); }

public class Number extends Element { private final int n; public Number(int n) { this.n = n; } public int getNumber() { return n; } @Override public String toString() { return String.valueOf(n); } @Override public boolean equals(Object other) { if (other instanceof Number) return ((Number) other).n == n; else return false; } }

import java.util.Iterator; public abstract class Set extends Element implements Iterable<Element> { public abstract boolean contains(Element e); public abstract Set union(Set e) throws Exception; @Override public abstract Iterator<Element> iterator(); public abstract int length(); @Override public boolean equals(Object other) { if (other instanceof Set) { Set s = (Set) other; for (Element e : s) { if (contains(e) == false) return false; } for (Element e : this) { if (s.contains(e) == false) return false; } return true; } else return false; } }

import java.util.Iterator; import java.util.NoSuchElementException; public class EmptySet extends Set { @Override public boolean contains(Element e) { return false; } @Override public String toString() { return "{}"; } @Override public Iterator<Element> iterator() { return new Iterator<Element>() { @Override public boolean hasNext() { return false; } @Override public Element next() { throw new NoSuchElementException(); } @Override public void remove() { throw new UnsupportedOperationException(); } }; } @Override public Set union(Set e) { return e; } @Override public int length() { return 0; } }

import java.util.Iterator; public class SingletonSet extends Set { Element element; public SingletonSet(Element element) { this.element = element; } @Override public boolean contains(Element e) { return element.equals(e); } @Override public String toString() { return "{" + element.toString() + "}"; } @Override public Iterator<Element> iterator() { return new Iterator<Element>() { boolean first = true; @Override public boolean hasNext() { return first; } @Override public Element next() { first = false; return element; } @Override public void remove() { throw new UnsupportedOperationException(); } }; } @Override public Set union(Set e) throws Exception { return new UnionSet(this, e); } @Override public int length() { return 1; } }

import java.util.Iterator; public class UnionSet extends Set { private final Set s1; private final Set s2; public UnionSet(Set s1, Set s2) throws Exception { for (Element element : s1) { if (s2.contains(element)) throw new Exception(); } for (Element element : s2) { if (s1.contains(element)) throw new Exception(); } this.s1 = s1; this.s2 = s2; } @Override public boolean contains(Element e) { return s1.contains(e) || s2.contains(e); } @Override public String toString() { String s = "{"; for (Element e : s1) { s += e.toString() + ", "; } for (Element e : s2) { s += e.toString() + ", "; } s = s.substring(0, s.length() - 2); return s + "}"; } @Override public Iterator<Element> iterator() { return new Iterator<Element>() { Iterator<Element> inner = s1.iterator(); boolean changed = false; @Override public boolean hasNext() { boolean b = inner.hasNext(); if (b) return true; else if (changed == false) { inner = s2.iterator(); changed = true; return hasNext(); } else return false; } @Override public Element next() { return inner.next(); } @Override public void remove() { throw new UnsupportedOperationException(); } }; } @Override public Set union(Set e) throws Exception { return new UnionSet(this, e); } @Override public int length() { return s1.length() + s2.length(); } }

以下是测试

public class TestSet { public static void main(String[] args) throws Exception { Number e1 = new Number(1); Number e2 = new Number(2); Number e22 = new Number(2); Number e3 = new Number(3); Number e4 = new Number(4); Number e5 = new Number(5); System.out.println(e1 + ", " + e2.toString() + ", " + e3 + ", " + e4 + ", " + e5); Set emptySet = new EmptySet(); Set s1 = new SingletonSet(e1); Set s2 = new SingletonSet(e2); Set s3 = new SingletonSet(e3); Set s4 = new SingletonSet(e4); Set s5 = new SingletonSet(e5); containTest(s1, e22); Set us12 = s1.union(s2); containTest(s2, e5); containTest(us12, e1); equalsTest(us12, s5); lengthTest(us12); Set us4 = emptySet.union(s4); containTest(us4, e4); Set us124 = us12.union(us4); containTest(us124, us4); Set us35 = us4.union(s5); containTest(us35, e5); equalsTest(us124, us35); lengthTest(us124); Set us312 = us4.union(us12).union(s3); containTest(us312, e1); equalsTest(us124, us312); } static void containTest(Set set, Element element) { System.out.println(set + " contains " + element + ": " + set.contains(element)); } static void equalsTest(Set s1, Set s2) { System.out.print(" " + s1 + "==" + s2 + " =>" + s1.equals(s2) + "; "); System.out.println(s2 + "==" + s1 + " =>" + s2.equals(s1)); } static void lengthTest(Set set) { System.out.println(" " + set + ".Length=" + set.length()); } }

输出：

1, 2, 3, 4, 5

{1} contains 2: false

{2} contains 5: false

{1, 2} contains 1: true

{1, 2}=={5} =>false; {5}=={1, 2} =>false

{1, 2}.Length=2

{4} contains 4: true

{1, 2, 4} contains {4}: false

{4, 5} contains 5: true

{1, 2, 4}=={4, 5} =>false; {4, 5}=={1, 2, 4} =>false

{1, 2, 4}.Length=3

{4, 1, 2, 3} contains 1: true

{1, 2, 4}=={4, 1, 2, 3} =>false; {4, 1, 2, 3}=={1, 2, 4} =>false