Library Name:
lib_dstr.a
Introduction:
The Dstr classes are generic data structure container classes, including
commonly used data structures such as a linked list, a stack, a tree, and
a graph. They are designed to provide users with a clean and simple
interface to data structure manipulations.
These classes are implemented as templates. Each class and its methods
are defined in the same file. This allows the classes to be instantiated
with any eligible object. For example, a doubly linked list of String
objects can be created as follows:
DoubleLinkedList<String> dstr;
Most data structure classes have two memory
allocation modes - SYSTEM or USER. The most appropriate
mode depends on a user's need to trade-off speed versus code complexity.
An important feature of data structure classes is the hierarchal I/O.
The contents of a data structure in this class can be written to an
Sof file by simply invoking the appropriate I/O method as we do for
any ISIP class. The I/O methods recurse through all objects contained
in the data structure and invoke each object's write method.
Example:
01 // file: $isip/doc/examples/class/dstr/dstr_example_00/example.cc
02 // version: $Id: index.html 10237 2005-09-13 18:52:36Z srinivas $
03 //
04
05 // isip include files
06 //
07 #include <String.h>
08 #include <DoubleLinkedList.h>
09
10 // main program starts here:
11 // this example produces a linked list of randomly generated nonsense strings
12 // note that the linked list has two modes - USER and SYSTEM.
13 // we use the default mode (SYSTEM) here so that we do not have to deal
14 // with memory allocation and deallocation
15 //
16 int main() {
17
18 // declare a DoubleLinkedList in SYSTEM mode
19 //
20 DoubleLinkedList<String> list_string;
21
22 // add 10 randomly generated strings, all with lengths on the range [5,20],
23 // to the linked list
24 //
25 for (long i = 0; i < 10; i++) {
26
27 // generate the random string
28 //
29 String tmp_str;
30 tmp_str.rand(5,20);
31
32 // add the random string to the list. this inserts at the current location
33 // and changes the current location to be this item.
34 //
35 list_string.insert(&tmp_str);
36 }
37
38 // display the contents of the list
39 //
40 list_string.debug(L"list of random strings");
41
42 // exit gracefully
43 //
44 Integral::exit();
45 }
Explanation:
On line 20 of the above example, a dstr object of type
DoubleLinkedList
is created using the default SYSTEM memory management mode. Inside the for
loop, on lines 29 and 30, a String object is created and assigned a
random set of characters. On line 35, it is added to the
DoubleLinkedList<String>. Inside
DoubleLinkedList<String>, a
DoubleLinkedNode<String> will be created to hold each String,
and the appropriate links between these nodes will be made. Since a local
copy of the object is being made by the system in this mode, we refer to this
as SYSTEM mode.
If the executable file name is example.exe, and we execute the following
command:
The output for this code is generated using the debug method
on line 40. On our systems, the output is shown below. Due to the
random function, your output may vary.
<DoubleLinkedList<String>::list of random strings> length_d = 10
<DoubleLinkedList<String>::list of random strings> alloc_d = 0
<DoubleLinkedList<String>::list of random strings> debug_level_d = none
<DoubleLinkedList<String>::list of random strings> node = first
<String::list of random strings> value_d = (7 >= 7) "s:T#-%L"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (17 >= 17) "{>U}\D.FkiGlD2CR:"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (11 >= 11) "~9JYjjQnBD`"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (6 >= 6) "]`@vAv"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (5 >= 5) "g[rG*"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (11 >= 11) "6})NJP9R16P"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (16 >= 16) "+rPE3(*i8Ti1B8]X"
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (14 >= 14) "9TFX,KV]ic"FG""
<DoubleLinkedList<String>::list of random strings> node
<String::list of random strings> value_d = (6 >= 6) "rD0kwg"
<DoubleLinkedList<String>::list of random strings> node = last, current
<String::list of random strings> value_d = (7 >= 7) "\nv7&x-"
We see that the DoubleLinkedList<String> we created consists of
10 elements, each being a string of random length and composition.
Example:
In this second
example,
we implement the same task shown above using
USER mode. In this mode, each dstr object will hold only
a pointer to the object, and the burden of memory management
for the associated objects will be on the user.
01 // file: $isip/doc/examples/class/dstr/dstr_example_01/example.cc
02 // version: $Id: index.html 10237 2005-09-13 18:52:36Z srinivas $
03 //
04
05 // isip include files
06 //
07 #include <String.h>
08 #include <DoubleLinkedList.h>
09
10 // main program starts here:
11 // this example produces a linked list of randomly generated nonsense strings
12 // note that the linked list has two modes - USER and SYSTEM.
13 // we use USER mode here to demonstrate the way that memory can be
14 // controlled by the user while still taking advantage of our dstr
15 // classes
16 //
17 int main() {
18
19 // declare a USER mode DoubleLinkedList
20 //
21 DoubleLinkedList<String> list_string(DoubleLinkedList<String>::USER);
22
23 // add 10 randomly generated strings, all with lengths on the range [5,20],
24 // to the linked list
25 //
26 for (long i = 0; i < 10; i++) {
27
28 // generate the random string
29 //
30 String* tmp_str = new String();
31 tmp_str->rand(5,20);
32
33 // add the random string to the list. this inserts at the current location
34 // and changes the current location to be this item.
35 //
36 list_string.insert(tmp_str);
37 }
38
39 // display the contents of the list
40 //
41 list_string.debug(L"list of random strings");
42
43 // free the memory allocated for the list
44 //
45 String* tmp_str = (String*)NULL;
46 while (list_string.removeFirst(tmp_str)) {
47 delete tmp_str;
48 }
49
50 // exit gracefully
51 //
52 Integral::exit();
53 }
Explanation:
The declaration on line 21 creates a
DoubleLinkedList
using the USER memory management mode. Inside the for loop, on
line 30, each String is initialized by the new operator, which ensures
the String is still valid after going out of the loop. On
line 36, it is added to the DoubleLinkedList<String>. Inside
DoubleLinkedList<String>, a DoubleLinkedNode<String> will
be created and holds a pointer to the String. In USER memory mode,
destructing the DoubleLinkedList<String> object will not automatically
delete the Strings it points to. Users must manage memory associated with
objects put on the list manually. Lines 45 through 48 show one way to do
this. Finally, the output of the above example is the same as the first
example.
Example:
Here is another
example
demonstrating the hierarchical I/O capability
of the dstr classes:
01 // file: $isip/doc/examples/class/dstr/dstr_example_02/example.cc
02 // version: $Id: index.html 10237 2005-09-13 18:52:36Z srinivas $
03 //
04
05 // isip include files
06 //
07 #include <String.h>
08 #include <Vector.h>
09
10 // main program starts here:
11 // this example demonstrates reading and writing data structures to a
12 // text sof file. the output file will not be deleted so that the user
13 // may examine the output upon exiting.
14 //
15 int main () {
16
17 // create a string filename that we will write to
18 //
19 String file(L"dstr_example_02.sof");
20
21 // create a Vector of Strings:
22 // the vector has length 3. note that we are using the indexing operator()
23 // to directly access the objects internal to the vector
24 //
25 String string_0(L"for more information");
26 String string_1(L"please see");
27 String string_2(L"http://www.isip.msstate.edu/");
28 Vector<String> vec_write(3);
29 vec_write(0).assign(string_0);
30 vec_write(1).assign(string_1);
31 vec_write(2).assign(string_2);
32
33 // write the Vector to a text Sof file
34 //
35 Sof text_file;
36 text_file.open(file, File::WRITE_ONLY, File::TEXT);
37 vec_write.write(text_file, 0);
38 text_file.close();
39
40 // read the file back in:
41 // the read vector should be identical to the vector we wrote
42 //
43 text_file.open(file);
44 Vector<String> vec_read;
45 vec_read.read(text_file, 0);
46 text_file.close();
47
48 // print the two vectors
49 //
50 vec_write.debug(L"vector we wrote");
51 Console::put(L"");
52 vec_read.debug(L"vector we read");
53
54 // exit gracefully
55 //
56 Integral::exit();
57 }
Explanation:
In the above program, on line 19 a string containing the name of
the output file is created.
Next, a Vector<String> is declared, which contains three elements.
Each String element is assigned to a different string using the
indexing parentheses operator of the Vector class.
The next portion of the code, from lines 33 to 47, demonstrates how to
write and read the Vector<String> with an Sof
file. The Vector<String> is written into an Sof file with the
tag 0. After closing the file and reopening it in read mode, the
Vector<String> is read back in. The vector being read will contain
identical strings to those that were written.
The makefile defines the executable file to be named example.exe. Executing:
creates an output file, dstr_example_02.sof:
@ Sof v1.0 @
@ Vector<String> 0 @
values = {
"for more information"
}, {
"please see"
}, {
"http://www.isip.msstate.edu/"
};
and will produce the output:
<Vector<String>::vector we wrote> length_d = 3
<Vector<String>::vector we wrote> capacity_d = 3
<Vector<String>::vector we wrote> v_d[0]
<String::> value_d = (20 >= 20) "for more information"
<Vector<String>::vector we wrote> v_d[1]
<String::> value_d = (10 >= 10) "please see"
<Vector<String>::vector we wrote> v_d[2]
<String::> value_d = (28 >= 28) "http://www.isip.msstate.edu/"
<Vector<String>::vector we read> length_d = 3
<Vector<String>::vector we read> capacity_d = 3
<Vector<String>::vector we read> v_d[0]
<String::> value_d = (20 >= 20) "for more information"
<Vector<String>::vector we read> v_d[1]
<String::> value_d = (10 >= 10) "please see"
<Vector<String>::vector we read> v_d[2]
<String::> value_d = (28 >= 28) "http://www.isip.msstate.edu/"
The dstr classes that are currently available include:
The next level in the ISIP class hierarchy is
multimedia
which provides classes that interface with information sources
such as speech signals. The software corresponding to the examples
demonstrated in this document can be found in our
documentation directory
under
class/dstr/.