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
|
COMMENT(
class
Let's assume that a database is created in which information about persons
is stored. Name, street names, city names, house numbers, birthdays, etc. are
collected in objects of the class tt(Person), which are, in turn, stored
in a class tt(PersonDbase). Partial interfaces of these classes could be
designed as follows:
verb(
class Date;
class Person()
{
public:
...
char const *get_name() const;
Date const &birthdate() const;
private:
...
};
class Person_dbase
{
public:
enum Listtype
{
list_by_name,
list_by_birthday,
};
void list(Listtype type);
private:
Person
*pp; // pointer to the info
size_t
n; // number of persons stored.
};
)
The organization of tt(Person) and tt(Person_dbase) is pictured in
fig(PersonFig): Within a tt(Person_dbase) object the tt(Person) objects
are stored. They can be reached via the pointer variable tt(Person *pp).
figure(ptrmembers/personfig)
(Person_dbase objects: Persons reached via Person *pp)
(PersonFig)
We would like to develop the function tt(Person_dbase::list()) in such a
way that it lists the contents of the database sorted according to a selected
field of a tt(Person) object.
So, when tt(list()) is called to list the
database sorted by em(names), the database of tt(Person) objects is first
sorted by names, and is then listed.
Alternatively, when tt(list()) is called to list the
database sorted by em(birthdates), the database of tt(Person) objects
is first sorted by birthdates, and is then listed.
In this situation, the function tt(qsort()) is most likely called to do
the actual sorting of the tt(Person) objects+footnote(
In the current implementation tt(pp) points to an array of tt(Person)
objects. In this implementation, the function tt(qsort()) will have to
copy the actual tt(Person) objects again and again, which may be rather
inefficient when the tt(Person) objects become large. Under an alternative
implementation, in which the tt(Person) objects are reached through
pointers, the efficiency of the tt(qsort()) function will be improved. In that
case, the datamember tt(pp) will have to be declared as
tt(Person **pp).).
This function requires a pointer to a compare function, comparing
two elements of the array to be sorted. The prototype of this compare function
is
center(tt(int (*)(void const *, void const *)))
However, when used with
tt(Person) objects, the prototype of the tt(compare()) function should be
center(tt(int (*)(Person const *, Person const *)))
Somewhere a typecast
will be required: either when calling tt(qsort()), or within the tt(
compare()) functions themselves. We will use the typecast when calling
tt(qsort()), using the following typedef to reduce the verbosity of the
typecasts
(a em(pointer to an integer function requiring two void pointers)):
center(tt(typedef int (*pif2vp)(void const *, void const *)))
Next, the function tt(list()) could be developed according to the following
setup:
verb(
void Person_dbase::list(Listtype type)
{
switch (type)
{
case list_by_name:
qsort(pp, n, sizeof(Person), (pif2vp)cmpname);
break;
case list_by_birthday:
qsort(pp, n, sizeof(Person), (pif2vp)cmpdate);
break;
}
// list the sorted Person-database
}
)
There are several reasons why this setup is not particularly desirable:
startit()
it() Although the example only shows two list-alternatives (sort by name
and sort by birthday), a real-life implementation will have many more
ways to list the information. This will soon result in a very long
function tt(list()) which will be hard to maintain and will
look inaccessible due to its length.
it() Every time a new way to list the data in the database, the function
tt(list()) will have to be expanded, by offering an extra
tt(case) label for every new way to list the data.
it() Much of the code in the function tt(list()) will be repeated
within the function, showing only some small differences.
endit()
Much of the complexity of tt(list()) function could be reduced by
defining em(pointers) to the compare-functions, storing these pointers in an
array. Since this array will be common to all tt(Person_dbase) objects,
it should be defined as a static array, containing the pointers to the
compare-functions.
Before actually constructing this array, note that this approach requires the
definition of as many compare functions as there are elements in the
tt(Listtype) enum. So, to list the information sorted by name a function
tt(cmpname()) is used, comparing the names stored in two
tt(Person) objects, while a function tt(cmpcity()), is used to compare
cities. Somehow this seems to be redundant as well: we would like to use
one function to compare strings, whatever their meanings. Comparable
considerations hold true for other fields of information.
The compare functions, however, receive pointers to tt(Person)
objects. Therefore, the data-members of the tt(Person) objects to which
these pointers point can be accessed using the access-member functions
of the tt(Person) class. So, the compare functions can access these
data-members as well, using the pointers to the tt(Person) objects.
Now note that the access member functions that are used within a particular
compare function can be em(hard-coded), by plainly mentioning the accessors
to be used, and they can be selected indirectly, by using em(pointers)
to the accessors to be used.
This latter solution allows us to em(merge) compare functions that
use the same implementations, but use different accessors: By setting a pointer
to the appropriate accessor function just before the compare function is
called, one single compare function can be used to compare many different
kinds of data stored inside tt(Person) objects.
The compare functions themselves are used within the context of the
tt(Person_dbase) class, where they are passed to the tt(qsort()) function. The
tt(qsort()) function, however, is a global function. Consequently, the compare
functions can't be ordinary member functions of the class tt(Person_dbase),
but they must be static members of that class, so they can be passed to the
tt(qsort()) function.
Summarizing what we've got so far, we see that the problem has been
broken down as follows:
startit()
it() The tt(switch) construction in the tt(list()) function
should be replaced by a call to a function using a pointer to
a function.
it() The actual function to be used is determined by the
value of the selector, which is given to tt(list()) when it's
called.
it() The tt(compare()) functions may be further
abstracted by combining those comparing the same types.
it() When tt(compare()) functions are combined, the access
member function of the tt(Person) objects to be used will also
be found via an array containing pointers to the access member
functions of tt(Person) objects.
it() The tt(compare()) functions are part of the tt(
Person_dbase) class, but it must also be possible to
give their addresses as arguments to tt(qsort()). Hence, these
functions must be defined as static functions of the class
tt(Person_dbase).
endit()
From this analysis the essential characteristics of the proposed implementation
emerge.
For every type of listing, as produced by the function tt(list()), the
following is required:
startit()
it() The access member function of the tt(Person) class to be
used.
it() The tt(compare()) function to be used. The tt(compare()) functions
will be em(static functions) of the class tt(Person_dbase), so that
they can be passed over to tt(qsort())
endit()
This information does not depend on a particular tt(Person_dbase) object,
but is common to all of these objects. Hence it will be stored compile-time
in a tt(static Person_dbase) kind of array.
How will the tt(compare()) functions know which element of this array to
use? The requested index is passed to the tt(list()) member function
as a tt(Listtype) value. The tt(list()) function can then save this
information in a tt(static Person_dbase::Listtype) variable for the
tt(compare()) functions to use.
We've analyzed enough. Let's build it this way.
COMMENT ENDS)
|
