Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

230 lines (206 sloc) 12.514 kB
<!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 empties 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 purpose: <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>ANY</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 provides 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>ANY</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 are 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>(by 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>
&quot;@&quot;</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 are 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-2005</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> 12 February 2005</font><br>
<!--webbot bot="PurpleText"
preview="
$Date$
$Revision$"
-->
</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>
Jump to Line
Something went wrong with that request. Please try again.