How to implement pointer forward or backward using an iterator

Recently, Professor Zhou Ligong has published his painstaking work "Programming and Data Structure" after years of effort. The electronic version is now freely available for download by electronic engineers and college students. With the authorization from Professor Zhou, the content of this book is being serialized.

> > >> 1.1.1 Algorithm Interface

Since an iterator can easily move forward or backward, it can be used to implement the bubble sort algorithm. Its function prototype is as follows:

Void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap);

In this function, p_if represents the iterator interface used by the algorithm. Begin and end are a pair of iterators that define the range on which the algorithm operates, but they do not necessarily correspond to the first and last elements of the container. This allows the algorithm to handle any data range. To ensure the validity of the range, it is common to use a half-open interval representation, i.e., [begin, end), which includes all elements between begin and end (excluding end). When begin == end, the range is empty.

The compare function is also a comparison function, but it compares the values of two iterators. Its type, compare_t, is defined as follows:

Typedef int (*compare_t)(iterator_t it1, iterator_t it2);

The swap function exchanges the data corresponding to two iterators. Its type, swap_t, is defined as follows:

Typedef void (*swap_t)(iterator_t it1, iterator_t it2);

As seen, the interface only contains an iterator, with no trace of the container itself. This completely separates the container from the bubble sorting algorithm. The iterator-based bubble sort algorithm is shown in Listing 3.56.

Listing 3.56: Bubble Sort Algorithm Function

1 void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap)

2 {

3 int flag = 1; // flag = 1 indicates no exchange has occurred

4 iterator_t it1 = begin; // it1 points to the first element of the array

5 iterator_t it2 = end;

6

7 iterator_t it_next; // it_next points to the next element of it1

8 if (begin == end) { //no elements to sort

9 return;

10 }

11 iterator_prev(p_if, &it2); // it2 points to the last element to be sorted

12 while (it2 != begin) {

13 it1 = begin;

14 flag = 1;

15 while(it1 != it2) {

16 it_next = it1; //temporary variable

17 iterator_next(p_if, &it_next); // it_next points to the next element of it1

18 if(compare(it1, it_next) > 0) {

19 swap(it1, it_next); //exchange elements

20 flag = 0; // flag = 0 indicates an exchange has occurred

21 }

22 it1 = it_next; //move to the next element

23 }

24 if (flag) return; //no exchange, already sorted

25 iterator_prev(p_if, &it2); // move it2 forward

26 }

27 }

Let’s test the iterator-based bubble sort algorithm with a simple example. See Listing 3.57 for details. We insert integers into a doubly linked list, add 5, 4, 3, 2, 1 at the end, then call dlist_foreach() to traverse the list and check the result. Then we call the algorithm library's iter_sort() to sort the list. After sorting, the elements should be in ascending order. We call dlist_foreach() again to verify the result.

Listing 3.57: Using Doubly Linked Lists, Algorithms, and Iterators

1 #include

2 #include "iterator.h"

3

4 typedef struct _dlist_int{

5 dlist_node_t node; //linked list node

6 int data; // integer data

7 }dlist_int_t;

8

9 int list_node_process(void *p_arg, dlist_node_t *p_node)

10 {

11 printf("%d ", ((dlist_int_t *)p_node)->data);

12 return 0;

13 }

14

15 static int __compare(iterator_t it1, iterator_t it2)

16 {

17 return ((dlist_int_t *)it1)->data - ((dlist_int_t *)it2)->data;

18 }

19

20 static void __swap(iterator_t it1, iterator_t it2)

21 {

22 int data = ((dlist_int_t *)it2)->data;

23 ((dlist_int_t *)it2)->data = ((dlist_int_t *)it1)->data;

24 ((dlist_int_t *)it1)->data = data;

25 }

26

27 int main(int argc, char *argv[])

28 {

29 iterator_if_t iterator_if;

30 dlist_head_t head; //define the head of the list

31 dlist_int_t node[5]; //define 5 nodes

32 int i;

33

34 dlist_init(&head);

35

36 for (i = 0; i < 5; i++) { //add 5 nodes to the end

37 node[i].data = 5 - i; //values are 5 ~ 1

38 dlist_add_tail(&head, &(node[i].node));

39 }

40 dlist_iterator_if_get(&iterator_if);

41

42 printf("Before bubble sort:");

43 dlist_foreach (&head, list_node_process, NULL); //print before sorting

44

45 iter_sort(&iterator_if, dlist_begin_get(&head), dlist_end_get(&head), __compare, __swap);

46

47 printf("After bubble sort:");

48 dlist_foreach (&head, list_node_process, NULL); //print after sorting

49 return 0;

50 }

Here, the dlist_foreach() traversal function is used. Since the iterator can implement bubble sorting, a simple traversal algorithm can be implemented using the iterator, and this traversal is independent of the specific container. The prototype of the traversal function is as follows:

Void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg);

Where p_if represents the iterator interface used by the algorithm, begin and end represent the range of iterators the algorithm needs to process, and visit is a user-defined function to traverse the iterator. Its type visit_t is defined as follows:

Typedef int (*visit_t)(void *p_arg, iterator_t it);

The visit parameter is a function pointer that takes p_arg and it as arguments. Each time a node is traversed, the function pointed to by visit is called. The value passed to p_arg is the user-defined parameter, which is the same as the p_arg parameter of the iter_foreach() function. The value of p_arg is determined entirely by the user and passed to the current iterator during traversal. The implementation of the iter_foreach() function can be found in Listing 3.58.

Listing 3.58: Traversal Algorithm Function

1 void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg)

2 {

3 iterator_t it = begin;

4 while(it != end) {

5 if (visit(p_arg, it) < 0) { //if the return value is negative, the user has terminated the traversal

6 return;

7 }

8 iterator_next(p_if, &it); //move the iterator forward

9 }

10 }

Now, lines 43 and 48 of the dlist_foreach() function in Listing 3.57 can be modified to use the iter_foreach() function. Can we achieve the same effect?

If the data is stored in an array, how would you use the existing bubble sort algorithm? Since arrays are also containers, you only need to implement array-based iterators, as shown in Listing 3.59.

Listing 3.59: Implementing the Iterator Interface for Arrays

1 typedef int element_type_t;

2

3 static void __array_iterator_next(iterator_t *p_iter)

4 {

5 (*(element_type_t **)(p_iter))++; //move the iterator to the next element

6 }

7

8 static void __array_iterator_prev(iterator_t *p_iter)

9 {

10 (*(element_type_t **)(p_iter))--; //move the iterator to the previous element

11 }

12

13 void array_iterator_if_get(iterator_if_t *p_if)

14 {

15 iterator_if_init(p_if, __array_iterator_next, __array_iterator_prev);

16 }

Based on the new iterator, the bubble sort algorithm can be used directly. See Listing 3.60.

Listing 3.60: Using Arrays, Algorithms, and Iterators

1 #include

2 #include "iterator.h"

3

4 static int __visit(void *p_arg, iterator_t it)

5 {

6 printf("%d ", *(int *)it);

7 return 0;

8 }

9

10 static int __compare(iterator_t it1, iterator_t it2)

11 {

12 return *(int *)it1 - *(int *)it2;

13 }

14

15 static void __swap(iterator_t it1, iterator_t it2)

16 {

17 int data = *(int *)it2;

18 *(int *)it2 = *(int *)it1;

19 *(int *)it1 = data;

20 }

21

22 int main(int argc, char *argv[])

23 {

24 iterator_if_t iterator_if;

25 int a[] = {5, 3, 2, 4, 1};

26 array_iterator_if_get(&iterator_if);

27

28 printf("Before bubble sort:");

29 iter_foreach(&iterator_if, a, a + 5, __visit, NULL);

30

31 iter_sort(&iterator_if, a, a + 5, __compare, __swap);

32

33 printf("After bubble sort:");

34 iter_foreach(&iterator_if, a, a + 5, __visit, NULL);

35 return 0;

36 }

As seen, the iterative bubble sort algorithm is reused. If there are hundreds of functions in the algorithm library, implementing just two functions of the iterator interface can allow code reuse. Clearly, an iterator provides a more flexible way to access elements in a container without exposing its internal structure.