This repository was archived by the owner on Mar 19, 2018. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathcollections_8.html
More file actions
178 lines (178 loc) · 6.77 KB
/
collections_8.html
File metadata and controls
178 lines (178 loc) · 6.77 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html dir="ltr" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html;charset=UTF-8" />
<meta name="generator" content=
"HTML Tidy for Mac OS X (vers 25 March 2009), see www.w3.org" />
<title>Scala 2.8 コレクション API -- 整列済み集合</title>
<link rel="stylesheet" type="text/css" href="guide.css" />
</head>
<body dir="ltr">
<table width="100%" cellpadding="0" cellspacing="2">
<tr>
<td bgcolor="#99CCFF"><a href="collections_9.html"><img border="0"
alt="ビット集合" src="next.png" /></a></td>
<td bgcolor="#99CCFF"><a href="collections_7.html"><img border="0"
alt="集合" src="up.png" /></a></td>
<td bgcolor="#99CCFF"><img alt="" src="blank.png" /></td>
<td align="center" bgcolor="#99CCFF" width="100%">
<b>整列済み集合</b></td>
<td bgcolor="#99CCFF" align="center" class="tocref"><a href=
"collections_49.html">目次</a></td>
</tr>
</table>
<blockquote style=
"border-left: 1px solid gray; font-family: Century, Times, 'Times New Roman', 'MS Gothic', serif; padding-left: 1em;">
最新版は <a href="http://docs.scala-lang.org/ja/overviews/collections/sets.html">Scala Documentation</a> に移行しました。
</blockquote>
<h2>整列済み集合</h2>
<p>整列済み集合は (<a href=
"http://www.scala-lang.org/api/current/scala/collection/SortedSet.html"><tt>SortedSet</tt></a>)
は (集合の作成時に指定された) 任意の順序で要素を (<tt>iterator</tt> や <tt>foreach</tt>
を使って) 返す事ができる集合だ。<a href=
"http://www.scala-lang.org/api/current/scala/collection/SortedSet.html"><tt>SortedSet</tt></a>
クラスのデフォルトの表現は、左の子ツリー内の全ての要素が右の子ツリーの全ての要素よりも小さいという恒常条件を満たす順序付けされた二分木だ。これにより、通りがけ順
(in-order) で探索するだけで、木の全ての要素を昇順に返すことができる。Scala の <a href=
"http://www.scala-lang.org/api/current/scala/collection/immutable/TreeSet.html">
<tt>immutable.TreeSet</tt></a> クラスは <em>赤黒木</em>
を使ってこの恒常条件を実装している。また、この木構造は、<em>平衡木</em>であり、ルートから全て葉のまでの長さの違いは最大で一要素しかない。</p>
<p>空の <a href=
"http://www.scala-lang.org/api/current/scala/collection/immutable/TreeSet.html">
<tt>TreeSet</tt></a> を作成するには、まず順序付けを指定する:</p>
<div class="quote">
<table cellspacing="1" cellpadding="0">
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt>scala> <font color=
"#0000E5">val</font> myOrdering = Ordering.fromLessThan[<font color="#660099">String</font>](_ > _)</tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000">myOrdering: scala.math.</font></tt><tt><font color=
"#590000">Ordering[String] = ...</font></tt></td>
</tr>
</table>
</div>
<p>次に、その順序付けの空の木集合を作成するには:</p>
<div class="quote">
<table cellspacing="1" cellpadding="0">
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left">
<tt>scala> TreeSet.empty(myOrdering)</tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000"> res1: scala.collection.immutable.</font></tt><tt><font color="#590000">TreeSet[String] = TreeSet()</font></tt></td>
</tr>
</table>
</div>
<p>順序付けの引数を省略して、空集合の要素型を指定することもできる。その場合は、要素型のデフォルトの順序付けが使われる。</p>
<div class="quote">
<table cellspacing="1" cellpadding="0">
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left">
<tt>scala> TreeSet.empty[<font color=
"#660099">String</font>]</tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000">res2: scala.collection.immutable.</font></tt><tt><font color="#590000">TreeSet[String] = TreeSet()</font></tt></td>
</tr>
</table>
</div>
<p>(例えば連結やフィルターによって) 新たな木集合を作成した場合、それは元の集合と同じ順序付けを保つ。たとえば、</p>
<div class="quote">
<table cellspacing="1" cellpadding="0">
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left">
<tt>scala> res2 + (<font color=
"#000000">"one"</font>, <font color=
"#000000">"two"</font>, <font color=
"#000000">"three"</font>, <font color=
"#000000">"four"</font>)</tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000">res3: scala.collection.immutable.</font></tt><tt><font color="#590000">TreeSet[String] = TreeSet(four, one, three, two)</font></tt></td>
</tr>
</table>
</div>
<p>整列済み集合は要素の範囲もサポートする。例えば、<tt>range</tt>
メソッドは開始要素以上、終了要素未満の全ての要素を返す。また、<tt>from</tt>
メソッドは開始要素以上の全ての要素を、集合の順序付けで返す。両方のメソッドの戻り値もまた整列済み集合だ。用例:</p>
<div class="quote">
<table cellspacing="1" cellpadding="0">
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left">
<tt>scala> res3 range (<font color=
"#000000">"one"</font>, <font color=
"#000000">"two"</font>)</tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000">res4: scala.collection.immutable.</font></tt><tt><font color="#590000">TreeSet[String] = TreeSet(one, three)</font></tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left">
<tt>scala> res3 from <font color=
"#000000">"three"</font></tt></td>
</tr>
<tr>
<td></td>
</tr>
<tr>
<td colspan="99" align="left"><tt><font color=
"#590000">res5: scala.collection.immutable.</font></tt><tt><font color="#590000">TreeSet[String] = TreeSet(three, two)</font></tt></td>
</tr>
</table>
</div>
<p>続いては、<a href="collections_9.html">ビット集合</a></p>
<hr />
<table width="100%" cellpadding="0" cellspacing="2">
<tr>
<td bgcolor="#99CCFF"><a href="collections_9.html"><img border="0"
alt="ビット集合" src="next.png" /></a></td>
<td bgcolor="#99CCFF"><a href="collections_7.html"><img border="0"
alt="集合" src="up.png" /></a></td>
<td bgcolor="#99CCFF"><img alt="" src="blank.png" /></td>
<td align="center" bgcolor="#99CCFF" width="100%">
<b>整列済み集合</b></td>
<td bgcolor="#99CCFF" align="center" class="tocref"><a href=
"collections_49.html">目次</a></td>
</tr>
</table>
</body>
</html>