|
クラスIntSet では、要素の並びは不定であるため、要素の探索を線形探索によって行っている。 配列内の要素を常に昇順にソートしておくように変更したクラスIntSortedSet を作成せよ。 そうすると、要素の探索は２分探索によって行えるし、要素の追加や削除も２分探索によって得られた位置に対して行える。また、他の配列と等しいかどうかの判断も効率よく行えることになる。 |
// 演習7-6 // int型の集合 class IntSortedSet { int max; // 集合の容量 int num; // 集合の要素数 int[] set; // 集合本体 //--- コンストラクタ ---// IntSortedSet(int capacity) { num = 0; max = capacity; try { set = new int[max]; // 集合本体用の配列を生成 } catch (OutOfMemoryError e) { // 配列の生成に失敗 max = 0; } } //--- 集合からnを探索してインデックスを返す ---// //--- 見つからない場合は-挿入ポイント-1を返す ---// int indexOf(int n) { int pl = 0; // 探索範囲先頭のインデックス int pr = n - 1; // 〃 末尾のインデックス do { int pc = (pl + pr) / 2; // 中央要素のインデックス if (set[pc] == n) return pc; // 探索成功 else if (set[pc] < n) pl = pc + 1; // 探索範囲を前半に絞り込む else pr = pc - 1; // 探索範囲を後半に絞り込む } while (pl <= pr); return -pl - 1; // 探索失敗 } //--- 集合にnが入っているか ---// boolean contains(int n) { return (indexOf(n) >= 0) ? true : false; } //--- 集合にnを追加 ---// boolean add(int n) { int idx; if (num >= max || (idx = indexOf(n)) >= 0) // 満杯 or 含まれている return false; else { idx = -(idx + 1); num++; for (int i = num - 1; i > idx; i--) set[i] = set[i - 1]; set[idx] = n; return true; } } //--- 集合からnを削除 ---// boolean remove(int n) { int idx; // nが格納されている要素のインデックス if (num <= 0 || (idx = indexOf(n)) == -1) // 空 or 含まれていない return false; else { num--; for (int i = idx; i < num; i++) // set[idx]を削除して set[i] = set[i + 1]; // それ以降の要素をずらす return true; } } //--- 集合の容量 ---// int capacity() { return max; } //--- 集合の要素数 ---// int size() { return num; } //--- 集合sにコピー（s ← this）---// void copyTo(IntSet s) { int n = (s.max < num) ? s.max : num; // コピーする要素数 for (int i = 0; i < n; i++) s.set[i] = set[i]; s.num = n; } //--- 集合sをコピー（this ← s）---// void copyFrom(IntSet s) { int n = (max < s.num) ? max : s.num; // コピーする要素数 for (int i = 0; i < n; i++) set[i] = s.set[i]; num = n; } //--- 集合sと等しいか ---// boolean equals(IntSet s) { if (num != s.num) // 要素数が等しくなければ return false; // 集合も等しくない for (int i = 0; i < num; i++) if (set[i] == s.set[i]) return false; return true; } //--- 集合s1とs2の和集合をコピー ---// void unionOf(IntSet s1, IntSet s2) { copyFrom(s1); // 集合s1をコピー for (int i = 0; i < s2.num; i++) // 集合s2の要素を追加 add(s2.set[i]); } //--- "{ a b c }"形式の文字列表現に変換 ---// public String toString() { StringBuffer temp = new StringBuffer("{ "); for (int i = 0; i < num; i++) temp.append(set[i] + " "); temp.append("}"); return temp.toString(); } //------------------------------ 演習7-2 ------------------------------// // 集合は空であるか boolean isEmpty() { return num == 0; } // 集合は満杯か boolean isFull() { return num >= max; } // 集合を空にする（全要素を削除） void clear() { num = 0; } //------------------------------ 演習7-3 ------------------------------// // 集合sとの和集合にする boolean addAll(IntSet s) { boolean flag = false; for (int i = 0; i < s.num; i++) if (add(s.set[i]) == true) flag = true; return flag; } // 集合sとの積集合にする boolean retainAll(IntSet s) { boolean flag = false; for (int i = 0; i < num; i++) if (s.contains(set[i]) == false) { remove(set[i]); flag = true; } return flag; } // 集合sとの差集合にする boolean removeAll(IntSet s) { boolean flag = false; for (int i = 0; i < num; i++) if (s.contains(set[i]) == true) { remove(set[i]); flag = true; } return flag; } //------------------------------ 演習7-4 ------------------------------// // 集合sの部分集合か boolean isSubsetOf(IntSet s) { for (int i = 0; i < num; i++) { int j = 0; for ( ; j < s.num; j++) if (set[i] == s.set[j]) break; if (j == s.num) // set[i]はsに含まれない return false; } return true; } // 集合sの真部分集合か boolean isProperSubsetOf(IntSet s) { if (num >= s.num) // 要素数がs以上であれば return false; // sの真部分集合ではない return s.isSubsetOf(s); } //------------------------------ 演習7-5 ------------------------------// // 集合s1とs2の積集合をコピー void intersectionOf(IntSet s1, IntSet s2) { clear(); for (int i = 0; i < s1.num; i++) if (s2.contains(s1.set[i])) add(s1.set[i]); } // 集合s1とs2の差集合をコピー void differenceOf(IntSet s1, IntSet s2) { clear(); for (int i = 0; i < s1.num; i++) if (!s2.contains(s1.set[i])) add(s1.set[i]); } }
