<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
<TITLE> A Guide to the S-Lang Language: Structures and User-Defined Types</TITLE>
<LINK HREF="slang-14.html" REL=next>
<LINK HREF="slang-12.html" REL=previous>
<LINK HREF="slang.html#toc13" REL=contents>
</HEAD>
<BODY>
<A HREF="slang-14.html">Next</A>
<A HREF="slang-12.html">Previous</A>
<A HREF="slang.html#toc13">Contents</A>
<HR>
<H2><A NAME="s13">13. Structures and User-Defined Types</A></H2>
<P>
<P>A <EM>structure</EM> is a heterogeneous container object, i.e., it is
an object with elements whose values do not have to be of the same
data type. The elements or fields of a structure are named, and
one accesses a particular field of the structure via the field
name. This should be contrasted with an array whose values are of
the same type, and whose elements are accessed via array indices.
<P>A <EM>user-defined</EM> data type is a structure with a fixed set of
fields defined by the user.
<P>
<H2><A NAME="ss13.1">13.1 Defining a Structure</A>
</H2>
<P>
<P>The <CODE>struct</CODE> keyword is used to define a structure. The syntax
for this operation is:
<BLOCKQUOTE><CODE>
struct {<EM>field-name-1</EM>, <EM>field-name-2</EM>, ... <EM>field-name-N</EM>};
</CODE></BLOCKQUOTE>
This creates and returns a structure with <EM>N</EM> fields whose names
are specified by <EM>field-name-1</EM>, <EM>field-name-2</EM>, ...,
<EM>field-name-N</EM>. When a structure is created, all its fields are
initialized to <CODE>NULL</CODE>.
<P>For example,
<BLOCKQUOTE><CODE>
<PRE>
variable t = struct { city_name, population, next };
</PRE>
</CODE></BLOCKQUOTE>
creates a structure with three fields and assigns it to the
variable <CODE>t</CODE>.
<P>Alternatively, a structure may be created by dereferencing
<CODE>Struct_Type</CODE>. For example, the above structure may also be
created using one of the two forms:
<BLOCKQUOTE><CODE>
<PRE>
t = @Struct_Type ("city_name", "population", "next");
t = @Struct_Type (["city_name", "population", "next"]);
</PRE>
</CODE></BLOCKQUOTE>
These are useful when creating structures dynamically where one does
not know the name of the fields until run-time.
<P>Like arrays, structures are passed around via a references. Thus,
in the above example, the value of <CODE>t</CODE> is a reference to the
structure. This means that after execution of
<BLOCKQUOTE><CODE>
<PRE>
variable u = t;
</PRE>
</CODE></BLOCKQUOTE>
<EM>both</EM> <CODE>t</CODE> and <CODE>u</CODE> refer to the <EM>same</EM> structure,
since only the reference was used in the assignment. To actually
create a new copy of the structure, use the <EM>dereference</EM>
operator, e.g.,
<BLOCKQUOTE><CODE>
<PRE>
variable u = @t;
</PRE>
</CODE></BLOCKQUOTE>
<P>
<H2><A NAME="ss13.2">13.2 Accessing the Fields of a Structure</A>
</H2>
<P>
<P>The dot (<CODE>.</CODE>) operator is used to specify the a particular
field of structure. If <CODE>s</CODE> is a structure and <CODE>field_name</CODE>
is a field of the structure, then <CODE>s.field_name</CODE> specifies
that field of <CODE>s</CODE>. This specification can be used in
expressions just like ordinary variables. Again, consider
<BLOCKQUOTE><CODE>
<PRE>
variable t = struct { city_name, population, next };
</PRE>
</CODE></BLOCKQUOTE>
described in the last section. Then,
<BLOCKQUOTE><CODE>
<PRE>
t.city_name = "New York";
t.population = 13000000;
if (t.population > 200) t = t.next;
</PRE>
</CODE></BLOCKQUOTE>
are all valid statements involving the fields of <CODE>t</CODE>.
<P>
<H2><A NAME="ss13.3">13.3 Linked Lists</A>
</H2>
<P>
<P>One of the most important uses of structures is to create a
<EM>dynamic</EM> data structure such as a <EM>linked-list</EM>. A
linked-list is simply a chain of structures that are linked together
such that one structure in the chain is the value of a field of the
previous structure in the chain. To be concrete, consider the
structure discussed earlier:
<BLOCKQUOTE><CODE>
<PRE>
variable t = struct { city_name, population, next };
</PRE>
</CODE></BLOCKQUOTE>
and suppose that we desire to create a list of such structures.
The purpose of the <CODE>next</CODE> field is to provide the link to the
next structure in the chain. Suppose that there exists a function,
<CODE>read_next_city</CODE>, that reads city names and populations from a
file. Then we can create the list via:
<BLOCKQUOTE><CODE>
<PRE>
define create_population_list ()
{
variable city_name, population, list_root, list_tail;
variable next;
list_root = NULL;
while (read_next_city (&city_name, &population))
{
next = struct {city_name, population, next };
next.city_name = city_name;
next.population = population;
next.next = NULL;
if (list_root == NULL)
list_root = next;
else
list_tail.next = next;
list_tail = next;
}
return list_root;
}
</PRE>
</CODE></BLOCKQUOTE>
In this function, the variables <CODE>list_root</CODE> and <CODE>list_tail</CODE>
represent the beginning and end of the list, respectively. As long
as <CODE>read_next_city</CODE> returns a non-zero value, a new structure is
created, initialized, and then appended to the list via the
<CODE>next</CODE> field of the <CODE>list_tail</CODE> structure. On the first
time through the loop, the list is created via the assignment to the
<CODE>list_root</CODE> variable.
<P>This function may be used as follows:
<BLOCKQUOTE><CODE>
<PRE>
variable Population_List = create_population_list ();
if (Population_List == NULL) error ("List is empty");
</PRE>
</CODE></BLOCKQUOTE>
We can create other functions that manipulate the list. An example is
a function that finds the city with the largest population:
<BLOCKQUOTE><CODE>
<PRE>
define get_largest_city (list)
{
variable largest;
largest = list;
while (list != NULL)
{
if (list.population > largest.population)
largest = list;
list = list.next;
}
return largest.city_name;
}
vmessage ("%s is the largest city in the list",
get_largest_city (Population_List)));
</PRE>
</CODE></BLOCKQUOTE>
The <CODE>get_largest_city</CODE> is a typical example of how one traverses
a linear linked-list by starting at the head of the list and
successively moves to the next element of the list via the
<CODE>next</CODE> field.
<P>In the previous example, a <CODE>while</CODE> loop was used to traverse the
linked list. It is faster to use a <CODE>foreach</CODE> loop for this:
<BLOCKQUOTE><CODE>
<PRE>
define get_largest_city (list)
{
variable largest, elem;
largest = list;
foreach (list)
{
elem = ();
if (item.population > largest.population)
largest = item;
}
return largest.city_name;
}
</PRE>
</CODE></BLOCKQUOTE>
Here a <CODE>foreach</CODE> loop has been used to walk the list via its
<CODE>next</CODE> field. If the field name was not <CODE>next</CODE>, then it
would have been necessary to use the <CODE>using</CODE> form of the
<CODE>foreach</CODE> statement. For example, if the field name implementing the
linked list was <CODE>next_item</CODE>, then
<BLOCKQUOTE><CODE>
<PRE>
foreach (list) using ("next_item")
{
elem = ();
.
.
}
</PRE>
</CODE></BLOCKQUOTE>
would have been used. In other words, unless otherwise indicated
via the <CODE>using</CODE> clause, <CODE>foreach</CODE> walks the list using a field
named <CODE>next</CODE>.
<P>Now consider a function that sorts the list according to population.
To illustrate the technique, a <EM>bubble-sort</EM> will be used, not
because it is efficient, it is not, but because it is simple and
intuitive.
<BLOCKQUOTE><CODE>
<PRE>
define sort_population_list (list)
{
variable changed;
variable node, next_node, last_node;
do
{
changed = 0;
node = list;
next_node = node.next;
last_node = NULL;
while (next_node != NULL)
{
if (node.population < next_node.population)
{
% swap node and next_node
node.next = next_node.next;
next_node.next = node;
if (last_node != NULL)
last_node.next = next_node;
if (list == node) list = next_node;
node = next_node;
next_node = node.next;
changed++;
}
last_node = node;
node = next_node;
next_node = next_node.next;
}
}
while (changed);
return list;
}
</PRE>
</CODE></BLOCKQUOTE>
Note the test for equality between <CODE>list</CODE> and <CODE>node</CODE>, i.e.,
<BLOCKQUOTE><CODE>
<PRE>
if (list == node) list = next_node;
</PRE>
</CODE></BLOCKQUOTE>
It is important to appreciate the fact that the values of these
variables are references to structures, and that the
comparison only compares the references and <EM>not</EM> the actual
structures they reference. If it were not for this, the algorithm
would fail.
<P>
<H2><A NAME="ss13.4">13.4 Defining New Types</A>
</H2>
<P>
<P>A user-defined data type may be defined using the <CODE>typedef</CODE>
keyword. In the current implementation, a user-defined data type
is essentially a structure with a user-defined set of fields. For
example, in the previous section a structure was used to represent
a city/population pair. We can define a data type called
<CODE>Population_Type</CODE> to represent the same information:
<BLOCKQUOTE><CODE>
<PRE>
typedef struct
{
city_name,
population
} Population_Type;
</PRE>
</CODE></BLOCKQUOTE>
This data type can be used like all other data types. For example,
an array of Population_Type types can be created,
<BLOCKQUOTE><CODE>
<PRE>
variable a = Population_Type[10];
</PRE>
</CODE></BLOCKQUOTE>
and `populated' via expressions such as
<BLOCKQUOTE><CODE>
<PRE>
a[0].city_name = "Boston";
a[0].population = 2500000;
</PRE>
</CODE></BLOCKQUOTE>
The new type <CODE>Population_Type</CODE> may also be used with the
<CODE>typeof</CODE> function:
<BLOCKQUOTE><CODE>
<PRE>
if (Population_Type = typeof (a)) city = a.city_name;
</PRE>
</CODE></BLOCKQUOTE>
The dereference <CODE>@</CODE> may be used to create an instance of the
new type:
<BLOCKQUOTE><CODE>
<PRE>
a = @Population_Type;
a.city_name = "Calcutta";
a.population = 13000000;
</PRE>
</CODE></BLOCKQUOTE>
<P>
<P>
<P>
<HR>
<A HREF="slang-14.html">Next</A>
<A HREF="slang-12.html">Previous</A>
<A HREF="slang.html#toc13">Contents</A>
</BODY>
</HTML>
