8. Parameterized Classes

1. Introduction

I will explain the parameterized classes in this chapter. The class needs a parameter (or parameters) to declare the data type. For example, ARRAY{INT} declares an array of integers. Flexible data types can be made by using an abstract class as a parameter. For instance, ARRAY{$OB} is an array for any kind of objects.

2. Quick look at the parameterized classes

The parameterized classes are mainly used as containers like ARRAY{INT} and MAP{INT, STR}. Thus you should declare following two things to use a parameterized class:

Objects to be stored
How to store these

Most of parameterized classes are the subclass of $ELT, $ELT{ETP}, and $CONTAINER{ETP} and have methods defined in these abstract classes (Table 1).

Table 1: Methods defined in $ELT, $ELT{ETP}, and $CONTAINER{ETP}.

Method	Explanation
`elt!`	It is an iterator defined in `$ELT` and `$ELT{ETP}`. It returns an element stored in a container one by one.
`copy`	It returns a copy of `self`, which is defined in the `$CONTAINER` class.
`has(e: ETP)`	It returns true if `self` contains `e`.
`size`	It returns the number of elements.

2.1. The typecase operator

You need the operator typecase when you want to branch the operation according to the data type as the parameterized classes can contain almost everything if you use $OB or $STR as a parameter.

01:     -- a simple typecase program
02:     
03:     class MAIN is
04:     
05:        main is
06:           a:ARRAY{$STR}:=#(|1, 2.12, 3.14159d, "Hello", #INTI(1000000), 'c'|);  -- defining an array that contains six objects which have $STR method
07:           s:STR;                                                                -- Any object having .str method can be stored in the array.
08:           loop
09:     	 i:$STR:=a.elt!;                         -- picking up an object from the array
10:     	 typecase i                              -- and change the procedure according to the data type
11:     	 when INT then
12:     	    s:="INT: "; 
13:     	 when FLT then
14:     	    s:="FLT: ";
15:     	 when FLTD then
16:     	    s:="FLTD: ";
17:     	 when INTI then
18:     	    s:="INTI: ";
19:     	 when STR then
20:     	    s:="STR: ";
21:     	 else
22:     	    s:="Other: ";
23:     	 end;
24:     	 #OUT + "a[" + a.ind! +"] = " + s + i.str + "\n";
25:           end;
26:        end;
27:     end;

$ sacomp typecase.sa -o typecase
$ ./typecase
a[0] = INT: 1
a[1] = FLT: 2.12
a[2] = FLTD: 3.14159
a[3] = STR: Hello
a[4] = INTI: 100000000
a[5] = Other: c

3. The Array{T} classes

I will explain first about the Array{T} classes which is used most frequently.

3.1. Constructing the instances (create, create_from)

The ARRAY{T} class has three creates (the constructors) taking no argument, one nonnegative integer, and the array of literals as an argument.

a0:ARRAY{INT}=#(|1,2,3|);  -- a0[0]=1, a0[1]=2, a0[2]=3
a1:ARRAY{INT}=#(3);        -- making an array for three INT's
a2::=#ARRAY{INT};          -- making an array for zero INT's

The create_from(e: $ELT{T}):SAME constructor is also defined to create an instance of ARRAY{T} from that of other $ELT{T} classes.

3.2. Frequently used methods

Table 2 shows frequently used methods defined in the ARRAY{T} classes. I will explain in the next chapter about methods that takes functions as parameters. As indicated in Table 2, methods of parameterized classes are influenced by Common Lisp. See Sather Class Index: ARRAY{T} for complete information (Table 2 just shows a fraction.).

Table 2: Frequently used methods in the ARRAY{T} class.

methods	explanation
`append`	It appends arrays. It takes one to three arguments.
`binary_search(e:T)`	It returns the index of `e` from a sorted array.
`copy`	It copies `self`. It takes variety of arguments.
`count(e:T)`	It return the number of `e`.
`has(e:T)`	It returns true if the array contains `e`.
`remove(e:T)`	It removes `e` from the array and returns the resulting array.
`remove_duplicates`	It removes duplicates and return the resulting array.
`reverse`	It returns the reverse-order array.
`size`	It returns the size of array.
`sort`	It sorts the array.
`str`	It converts the array to a string.
`elt!`	It returns an array element one by one.
`ind!`	It returns the index one by one.
`set!(e:T)`	It assigns a value to the element one by one.

4. TUP

The TUP is to lump objects with different data type together. Up to four objects can be lumped. The elements should belong to the subclass of $HASH. You can access the elements by methods t1, t2, t3, and t4. The TUP is used by the MAP class and is convenient to define functions that return plural values. Even functions of Sather can return values using arguments like those of C languages, using TUP is better to return plural values.

Example: tup.sa, in which the attributes of people are stored by TUP{INT, STR, CHAR, INT}.

01:     -- a simple TUP program
02:     
03:     class MAIN is
04:     
05:        shared id:INT:=0;
06:        make_person(name:STR, sex:CHAR, age:INT):TUP{INT, STR, CHAR, INT} is
07:           id:= id+1;
08:           return #(id, name, sex, age);
09:        end;
10:     
11:        person_id(p:TUP{INT,STR,CHAR,INT}):INT is
12:           return p.t1;
13:        end;
14:     
15:        person_name(p:TUP{INT,STR,CHAR,INT}):STR is
16:           return p.t2;
17:        end;
18:     
19:        person_sex(p:TUP{INT,STR,CHAR,INT}):STR is
20:           if p.t3 = 'm' then return "male";
21:           else return "female";
22:           end;
23:        end;
24:     
25:        person_age(p:TUP{INT,STR,CHAR,INT}):INT is
26:           return p.t4;
27:        end;
28:     
29:        show_person(p:TUP{INT,STR,CHAR,INT}):STR is
30:           return "ID: " + person_id(p).str + 
31:     	    "\nNAME: " + person_name(p) + 
32:     	    "\nSEX: " + person_sex(p) + 
33:     	    "\nAGE: " + person_age(p).str + "\n\n";
34:        end;
35:     
36:        main is
37:           #OUT + "TUP test using person properties.\n\n";
38:           a:ARRAY{TUP{INT,STR,CHAR,INT}}:=#(|make_person("John Smith", 'm', 50), make_person("Mary McCarthy", 'f', 25)|);
39:           loop
40:     	 #OUT + show_person(a.elt!);
41:           end;
42:        end;
43:     end;

$ sacomp tup.sa -o tup
$ ./tup
TUP test using person properties.

ID: 1
NAME: John Smith
SEX: male
AGE: 50

ID: 2
NAME: Mary McCarthy
SEX: female
AGE: 25

In fact defining PERSON class is better, I use TUP just for example.

5. MAP{T1, T2}

The MAP{T1, T2} class is hash table. See Sather Class Index: MAP for detailed information. As readers are expected to be familiar with hash tables, I just show a word count program.

01:     -- swc.sa: a simple words counts program written in sather
02:     
03:     class MAIN is
04:     
05:        const nonword_chars:STR:=" \t\n\r.,\"\\\`\':;?!()/-";  -- These characters are removed from the word if they are at the end (\W).
06:     
07:        -- check if the character is a word character.
08:        is_wordchar(c:CHAR):BOOL is
09:           return ~nonword_chars.contains(c);               -- return true if not \W
10:        end;
11:     
12:        -- truncating non_word characters from the head or tail of the word.
13:        w_truncate(w:STR, headp:BOOL):STR is               
14:           idx,begin,num:INT;
15:           num:=w.size-1;
16:           if headp then 
17:     	 idx:=0;
18:     	 begin:=1;
19:           else 
20:     	 idx:=num;
21:     	 begin:=0;
22:           end;
23:           if  w.size=0 or is_wordchar(w.char(idx))  then  
24:     	 return w;
25:           else
26:     	 return w_truncate(w.substring(begin,num), headp);
27:           end;
28:        end;
29:     
30:        -- modifying the word to add to the hash table
31:        w_modify(w:STR):STR is                             
32:           return w_truncate(w_truncate(w, false), true).lower;
33:        end;
34:     
35:        -- making a word count hash table
36:        make_hash(f:FILE):MAP{STR, INT} is                  
37:           hash::=#MAP{STR,INT};
38:           line,w:STR;
39:           loop
40:     	 until!(f.eof);
41:     	 line:=f.get_str + " ";                        -- Adding Space to pick up the last word of the line using split!
42:     	 loop
43:     	    w:=w_modify(line.split!(' '));
44:     	    if w.size > 0 then
45:     	       if hash.has_ind(w) then
46:     		  hash[w]:=hash[w]+1;
47:     	       else
48:     		  hash[w]:=1;
49:     	       end;
50:     	    end;
51:     	 end;
52:           end;
53:           return hash;
54:        end;
55:     
56:        -- getting the sorted array of the keys of the hash table
57:        get_sorted_key(wc:MAP{STR,INT}):ARRAY{STR} is 
58:           a:ARRAY{STR}:=#(wc.size);                    
59:           loop                                         
60:     	 a.set!(wc.ind!);
61:           end;
62:           return a.sort;
63:        end;
64:     
65:        -- showing the result of word count, sorted by word.
66:        show_result(wc:MAP{STR,INT}) is                  
67:           w:STR;
68:           loop
69:     	 w:=get_sorted_key(wc).elt!;
70:     	 #OUT + w + "\t" + wc[w] + "\n";
71:           end;
72:        end;
73:     
74:        -- practical main function, counting word in a file
75:        count_words(filename:STR) is                    
76:           f::=FILE::open_for_read(filename);
77:           if f.error then
78:     	 #ERR + "Cannot open " + filename + "\n";
79:           else
80:     	 show_result(make_hash(f));  
81:     	 f.close;
82:           end;
83:        end;
84:     
85:        main(av: ARRAY{STR}) is
86:           if (av.size = 2) then
87:     	 count_words(av[1]);
88:           else
89:     	 #ERR + "Usage: scw FILENAME\n";
90:           end;
91:        end;
92:     end; -- MAIN

Notes

Tricky behavior of STR::split!(c:CHAR): The behavior of this method is somehow tricky. For instance,
"This is a pen.".split!(' ')
returns "This ", "is ", "a " one by one. But it does never return "pen." ¡ª¡ª If you need the last word, you have to add a space at the end.
("This is a pen." + " ").split!(' ')
returns "pen. " at the end. Mind that the separation character attaches at the end of words.
The Online Sather Code Browser does not follow the reality.: There is a substantial difference between what is written in The Online Sather Code Browser and real behavior of Sather. In such cases, check codes under $SATHERHOME/Library.

6. LIST{T}

The LIST{T} is similar to ARRAY{T}. But more flexible than ARRAY. See Online Code Browser: LIST or source codes for detailed information.

Here is a breadth first search (BFS) program as an example of LIST{T}. BFS takes a path so far from the queue, then adds the adjacent nodes of the last node if not visited yet. Finally it adds the resulting paths at the end of the queue. The following code (bfs.sa) returns the shortest path from the start to the goal in Figure 1.

Figure 1: A graph used in bfs.sa

01:     -- bfs.sa: a simple breadth fast search
02:     
03:     class MAIN is
04:     
05:        const gr:ARRAY{ARRAY{INT}}:=| |1,2,3|, |4|, |4,5|, |6|, |0|, |6,7|, |8|, |3|, |5| |;  -- ARRAY{ARRAY{INT}} expression of the graph shown in Fig. 1
06:        attr goal:INT;          
07:        attr queue:LIST{LIST{INT}};  -- list of searched paths so far
08:     
09:        bfs is                                   
10:           if queue.size=0 then
11:     	 #OUT + "Can not find the path\n";  -- if no queue, warn
12:     	 UNIX::exit(1);                     -- and exit
13:           end;
14:           path:LIST{INT}:=queue[0];             -- take the first item of the queue
15:           queue.remove_index(0);                -- delete the first item
16:           next_nodes:ARRAY{INT}:=gr[path[path.size-1]];  -- get the array of adjacent node from the last node (path[path.size-1]) 
17:           node:INT;
18:           loop
19:     	 node:=next_nodes.elt!;             -- search the next node one by one
20:     	 if node=goal then                  -- if it is the goal,
21:     	    #OUT + "found: " + path.append(goal) + "\n";  -- show the path from the start to the goal.
22:     	    UNIX::exit(0);
23:     	 elsif ~path.has(node) then         -- if not visited yet,
24:     	    queue.append(path.append(node));  -- add the node at the end of the path so far then add the path to the end of the queue
25:     	 end;
26:           end;
27:           bfs;                    -- call bfs recursively
28:        end;
29:     	 
30:        main(av:ARRAY{STR}) is
31:           if av.size=3 then                            -- check the number of arguments
32:     	 goal:=av[2].cursor.get_int;               -- the 2nd argument is the goal
33:     	 queue:=#;                                 -- initialize the queue
34:     	 queue.append(#(|av[1].cursor.get_int|));  -- add the start point to the queue
35:     	 bfs;                                      -- do bfs
36:           else
37:     	 #ERR + "Usage: bfs START GOAL\n";
38:           end;
39:        end;
40:     end;

$ sacomp bfs.sa -o bfs
$ ./bfs 1 7                   -- search a path from node 1 to node 7 
found: {1,4,0,2,5,7}

7. FLIST{T}

The FLIST{T} is comparable to the lists of LISP. This data type is convenient to implement stacks. See Online Code Browser: FLIST for more information.

Here is a program of a reverse polish calculator as an example of a stack. Only four arithmetic operations are implemented for simplicity.

01:     -- calc.sa: a simple reverse polish calculator
02:     
03:     class MAIN is
04:     
05:        const op:STR:="+-*/";
06:        const re:REGEXP:=REGEXP::regexp("^[+\\-]?[0-9]+\\.?[0-9]*$", false);  -- regular expression of numbers
07:        shared stack:FLIST{FLTD}:=FLIST{FLTD}::create;                        -- a stack of FLTD
08:     
09:        operatorp(word:STR):BOOL is
10:           return  (word.size = 1 and op.contains(word.char(0)));
11:        end;
12:     
13:        numberp(word:STR):BOOL is
14:           return re.match(word);
15:        end;
16:     
17:        calculate(word:STR) is              -- take two items from the stack
18:           c:CHAR:=word.char(0);
19:           f1,f2, fr:FLTD;
20:           f2:=stack.pop;
21:           f1:=stack.pop;
22:           case c                           -- then operate
23:           when '+' then fr := f1+f2;
24:           when '-' then fr := f1-f2;
25:           when '*' then fr := f1*f2;
26:           when '/' then fr := f1/f2;
27:           else #ERR + "The operator is not supported.\n";
28:           end;
29:           stack:=stack.push(fr);           -- then push the result to the stack
30:        end;
31:     
32:        push_to_stack(word:STR) is
33:           stack:=stack.push(word.cursor.get_fltd);      
34:        end;
35:     
36:        main(av: ARRAY{STR}) is
37:           line, word:STR;
38:           loop
39:     	 #OUT + "> ";
40:     	 if ~void(stack) then 
41:     	    #OUT  + stack[0] + " ";
42:     	 end;
43:     	 line:=#IN.get_str;
44:     	 if line.size = 0 then break!; end;      -- terminate if no input
45:     	 line := line + " ";
46:     	 loop 
47:     	    word := line.split!(' ');
48:     	    word := word.head(word.size-1);
49:     	    if operatorp(word) then calculate(word);
50:     	    elsif numberp(word) then  push_to_stack(word);
51:     	    end;
52:     	 end;
53:           end;
54:        end;
55:     end;

$ sacomp calc.sa -o calc
$ ./calc
> 1 8 + 3.7 0.7 - /             -- (1 + 8) / (3.7 - 0.7)
> 3 0.01 *                      -- you can continue calculation from the last result
> 0.03

Notes

Regular expression: A regular expression object are created by making an instance of REGEXP class using REGEXP::regexp constructor. The first argument of the constructor is a regular expression of POSIX system. and the second is a flag (true or false) for case-insensitive. REGEXP::match is used to match. See regexp.sa for detailed information.

8. Other parameterized classes

As the parameterized classes is one of the characteristics of Sather, many kinds of them are available. Table 2 shows some of them.

Table 2: Frequently used parameterized classes.

Class	Explanation
ARRAY2{}	2 dimensional array
ARRAY3{}	3 dimensional array
BAG{}	bag. store items with no order, allowing duplication
QUEUE{}	queue. In fact, `bfs.sa` gets shorter using this class.
STACK{}	stack. `calc.sa` gets shorter with this class.
SET{}	set. methods like `union` and `intersection` are defined.

9. Summary

I have explained on the parameterized classes in this chapter. You can download the source codes shown in this chapter from here.