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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="Microsoft FrontPage 2.0">
<title>General Abstractions</title>
</head>
<body bgcolor="#FFFFFF">
<table border="0" width="100%">
<tr>
<td><font size="6"><strong>General Abstractions</strong></font></td>
<td align="right"><a href="terminology.html"><img
src="../image/previous.gif" alt="Previous" border="0"
width="40" height="40"></a><a href="traversal.html"><img
src="../image/next.gif" alt="Next" border="0" width="40"
height="40"></a></td>
</tr>
</table>
<hr size="1">
<p align="center"><!--webbot bot="ImageMap" startspan
rectangle=" (133,253) (220, 286) flatshort/ds_bilinear.html"
rectangle=" (138,180) (216, 208) flatshort/ds_linear.html"
rectangle=" (246,102) (336, 133) flatshort/ds_sortable.html"
rectangle=" (197,14) (282, 44) flatshort/ds_container.html"
rectangle=" (15,103) (107, 134) flatshort/ds_searchable.html"
rectangle=" (245,178) (336, 209) flatshort/ds_indexable.html"
rectangle=" (128,103) (227, 134) flatshort/ds_traversable.html"
rectangle=" (352,104) (440, 134) flatshort/ds_resizable.html"
src="image/container.gif" border="0" width="453" height="300" --><MAP NAME="FrontPageMap0"><AREA SHAPE="RECT" COORDS="133, 253, 220, 286" HREF="flatshort/ds_bilinear.html"><AREA SHAPE="RECT" COORDS="138, 180, 216, 208" HREF="flatshort/ds_linear.html"><AREA SHAPE="RECT" COORDS="246, 102, 336, 133" HREF="flatshort/ds_sortable.html"><AREA SHAPE="RECT" COORDS="197, 14, 282, 44" HREF="flatshort/ds_container.html"><AREA SHAPE="RECT" COORDS="15, 103, 107, 134" HREF="flatshort/ds_searchable.html"><AREA SHAPE="RECT" COORDS="245, 178, 336, 209" HREF="flatshort/ds_indexable.html"><AREA SHAPE="RECT" COORDS="128, 103, 227, 134" HREF="flatshort/ds_traversable.html"><AREA SHAPE="RECT" COORDS="352, 104, 440, 134" HREF="flatshort/ds_resizable.html"></MAP><img src="image/container.gif" border="0" width="453" height="300" usemap="#FrontPageMap0"><!--webbot
bot="ImageMap" i-checksum="51832" endspan --></p>
<p>The <em>Gobo Eiffel Structure Library</em> follows the
classical design pattern whereby deferred classes introduce
abstract properties, which leaves room for expansion by
inheriting from these deferred classes to implement yet
unavailable containers. The <font color="#800000"><em><tt>container</tt></em></font>
cluster contains classes describing general abstract notions such
as traversable, resizable or sortable properties.</p>
<h2><a name="DS_CONTAINER">Class <em><tt>DS_CONTAINER</tt></em></a></h2>
<p>All data structures are descendant of class <a
href="flatshort/ds_container.html"><font color="#008080"><em><tt>DS_CONTAINER</tt></em></font></a>.
The classes are generic, the generic parameter representing the
type of the items being held in the containers. <font
color="#008080"><em><tt>DS_CONTAINER</tt></em></font> provides
expected queries such as <a
href="flatshort/ds_container.html#count"><font color="#008080"><em><tt>count</tt></em></font></a>,
the number of items in the container, and <a
href="flatshort/ds_container.html#is_empty"><font color="#008080"><em><tt>is_empty</tt></em></font></a>,
checking whether there is any item held in the container. Also
available is feature <a
href="flatshort/ds_container.html#wipe_out"><font color="#008080"><em><tt>wipe_out</tt></em></font></a>,
which empty the container putting it back to a state similar to
what it was just after its creation.</p>
<p>The most direct descendant classes of <font color="#008080"><em><tt>DS_CONTAINER
</tt></em></font>introduce some abstract properties of
containers.</p>
<h2><a name="DS_SEARCHABLE">Class <em><tt>DS_SEARCHABLE</tt></em></a></h2>
<p>Some containers can provide facilities to find out whether a
given item is held in this container. The class <a
href="flatshort/ds_searchable.html"><font color="#008080"><em><tt>DS_SEARCHABLE</tt></em></font></a>
introduces two features for this prupose: <a
href="flatshort/ds_searchable.html#has"><font color="#008080"><em><tt>has</tt></em></font></a>
is a boolean query which returns true if the object given as
argument is actually held in the container, and <a
href="flatshort/ds_searchable.html#occurrences"><font
color="#008080"><em><tt>occurrences</tt></em></font></a> is the
number of times an object appears in that container.</p>
<p>Depending on the context, several different criteria might be
used to search items in a container. For example, one may want to
check whether a given object appears in a list (using Eiffel's '<font
color="#008080"><tt>=</tt></font>' comparison criterion) or
whether a similar object is included (using the redefinable
feature <font color="#008080"><em><tt>is_equal</tt></em></font>
from class <font color="#008080"><em><tt>GENERAL</tt></em></font>
as equality criterion). In order to achieve this flexibility, the
class <font color="#008080"><em><tt>DS_SEARCHABLE </tt></em></font>can
be configured with an instance of class <a
href="flatshort/ds_equality_tester.html"><font color="#008080"><em><tt>DS_EQUALITY_TESTER</tt></em></font></a>
which provide a comparison criterion to the container. This
comparison criterion is held in the attribute <a
href="flatshort/ds_searchable.html#equality_tester"><font
color="#008080"><em><tt>equality_tester</tt></em></font></a> and
can be changed with <a
href="flatshort/ds_searchable.html#set_equality_tester"><font
color="#008080"><em><tt>set_equality_tester</tt></em></font></a>.
When no <font color="#008080"><em><tt>equality_tester</tt></em></font>
has been specified, the Eiffel's '<font color="#008080"><tt>=</tt></font>'
comparison criterion is used. By default, <font color="#008080"><em><tt>DS_EQUALITY_TESTER
</tt></em></font>is implemented using feature <font
color="#008080"><em><tt>equal</tt></em></font> from class <font
color="#008080"><em><tt>GENERAL</tt></em></font>, but descendant
classes can be easily written to provide user-defined comparison
criteria.</p>
<p>The comparison criterion of the container is not only taken
into account by the features <font color="#008080"><em><tt>has</tt></em></font><font
color="#008000"><em><tt> </tt></em></font>and<font
color="#008000"><em><tt> </tt></em></font><font color="#008080"><em><tt>occurrences</tt></em></font>
but also by the features <a
href="flatshort/ds_linear_cursor.html#search_forth"><font
color="#008080"><em><tt>search_forth</tt></em></font></a> and <a
href="flatshort/ds_bilinear_cursor.html#search_back"><font
color="#008080"><em><tt>search_back</tt></em></font></a> provided
by the cursor classes of the <a href="traversal.html">traversal
mechanism</a>.</p>
<h2>Class <em><tt>DS_TRAVERSABLE</tt></em></h2>
<p>Some containers can provide facilities in order to inspect
their items one after another. This traversal mechanism is quite
complex since there is different schools of thought for the
design and implementation of such pattern and hence deserves a <a
href="traversal.html">chapter of its own</a> in this
documentation.</p>
<h2>Class <em><tt>DS_SORTABLE</tt></em></h2>
<p>Some containers such as priority queues or binary search trees
keep their items sorted. On the other hand some other containers
do not necessarily keep their items sorted but provide facilities
to sort them on demand according to various comparison criteria
and sorting algorithms. These latter containers inherit from the
class <a href="flatshort/ds_sortable.html"><font color="#008080"><em><tt>DS_SORTABLE</tt></em></font></a>.
As just said, this facility depends on various criteria such as
sorting algorithms and here again deserves a <a href="sort.html">chapter
of its own</a> in this documentation.</p>
<h2><a name="DS_INDEXABLE">Class <em><tt>DS_INDEXABLE</tt></em></a></h2>
<p>Some containers provide an index-based access to their items,
like access to the characters of a <font color="#008080"><em><tt>STRING</tt></em></font>
or to the elements of an <font color="#008080"><em><tt>ARRAY</tt></em></font>.
Such containers inherit from the class <a
href="flatshort/ds_indexable.html"><font color="#008080"><em><tt>DS_INDEXABLE</tt></em></font></a>
whose items are indexed from 1 to <a
href="flatshort/ds_indexable.html#count"><font color="#008080"><em><tt>count</tt></em></font></a>.
The basic feature of this class is of course the access routine <a
href="flatshort/ds_indexable.html#item"><font color="#008080"><em><tt>item</tt></em></font></a><font
color="#008080"><em><tt> </tt></em></font>(for analogy to class <font
color="#008080"><em><tt>ARRAY</tt></em></font> and other classes
from <em>EiffelBase</em>, feature <font color="#008080"><em><strong><tt>infix</tt></strong></em><em><tt>
"@"</tt></em></font> has been added as a synomym of <font
color="#008080"><em><tt>item</tt></em></font>.), but it is also
equipped with commands to add and remove items at given index
positions, such as <a href="flatshort/ds_indexable.html#put"><font
color="#008080"><em><tt>put</tt></em></font></a> or <a
href="flatshort/ds_indexable.html#remove"><font color="#008080"><em><tt>remove</tt></em></font></a>.
There is also convenience features to access the first (at index
1) and last (at index <font color="#008080"><em><tt>count</tt></em></font>)
items of the container, such as <a
href="flatshort/ds_indexable.html#first"><font color="#008080"><em><tt>first</tt></em></font></a>,
<a href="flatshort/ds_indexable.html#put_last"><font
color="#008080"><em><tt>put_last</tt></em></font></a> or <a
href="flatshort/ds_indexable.html#remove_first"><font
color="#008080"><em><tt>remove_first</tt></em></font></a>. Have a
look at the <a href="flatshort/ds_indexable.html">flat-short form</a>
for a complete list of these features.</p>
<h2><a name="DS_RESIZABLE">Class <em><tt>DS_RESIZABLE</tt></em></a></h2>
<p>Some containers allocate chunks of memory to hold their items.
This is for example the case for containers internally
implemented with arrays (typically named <font color="#008080"><em><tt>DS_ARRAYED_*</tt></em></font>).
Such data structures cannot contain more items than initially
planned when allocating the chunk of memory unless they are
resized from time to time. The class <a
href="flatshort/ds_resizable.html"><font color="#008080"><em><tt>DS_RESIZABLE</tt></em></font></a>
provides such facility. Apart from the expected feature <a
href="flatshort/ds_resizable.html#resize"><font color="#008080"><em><tt>resize</tt></em></font></a>,
there are also two queries which are the counterpart of <font
color="#008080"><em><tt>count</tt></em></font> and <font
color="#008080"><em><tt>is_empty</tt></em></font> from <font
color="#008080"><em><tt>DS_CONTAINER</tt></em></font>: <a
href="flatshort/ds_resizable.html#capacity"><font color="#008080"><em><tt>capacity</tt></em></font></a>
is the maximum number of items that the container can currently
hold, and <a href="flatshort/ds_resizable.html#is_full"><font
color="#008080"><em><tt>is_full</tt></em></font></a> checks
whether the number of items in the container has reached this
limit.</p>
<hr size="1">
<table border="0" width="100%">
<tr>
<td><address>
<font size="2"><b>Copyright 1999</b></font><font
size="1"><b>, </b></font><font size="2"><strong>Eric
Bezault</strong></font><strong> </strong><font
size="2"><br>
<strong>mailto:</strong></font><a
href="mailto:ericb@gobosoft.com"><font size="2">ericb@gobosoft.com</font></a><font
size="2"><br>
<strong>http:</strong></font><a
href="http://www.gobosoft.com"><font size="2">//www.gobosoft.com</font></a><font
size="2"><br>
<strong>Last Updated:</strong> 21 August 1999</font><br>
<!--webbot bot="PurpleText"
preview="
$Date: 1999/10/02 11:54:54 $
$Revision: 1.5 $"
-->
</address>
</td>
<td align="right" valign="top"><a
href="http://www.gobosoft.com"><img
src="../image/home.gif" alt="Home" border="0" width="40"
height="40"></a><a href="index.html"><img
src="../image/toc.gif" alt="Toc" border="0" width="40"
height="40"></a><a href="terminology.html"><img
src="../image/previous.gif" alt="Previous" border="0"
width="40" height="40"></a><a href="traversal.html"><img
src="../image/next.gif" alt="Next" border="0" width="40"
height="40"></a></td>
</tr>
</table>
</body>
</html>
|
