1 | #ifndef ISLLIST_HH |
---|

2 | #define ISLLIST_HH |
---|

3 | |
---|

4 | template <class T> |
---|

5 | class isllist |
---|

6 | { |
---|

7 | protected: |
---|

8 | class list_node; |
---|

9 | typedef list_node *link; |
---|

10 | class list_node |
---|

11 | { |
---|

12 | public: |
---|

13 | link next; |
---|

14 | T data; |
---|

15 | |
---|

16 | list_node() {} |
---|

17 | list_node(const T& item) { data = item; } |
---|

18 | }; |
---|

19 | |
---|

20 | link list; |
---|

21 | public: |
---|

22 | class iterator |
---|

23 | { |
---|

24 | friend class isllist; |
---|

25 | public: |
---|

26 | // pseudo-protected - don't use unless you really have to |
---|

27 | link node; |
---|

28 | iterator(const link p) : node(p) {} |
---|

29 | public: |
---|

30 | iterator() {} |
---|

31 | iterator(const iterator &p) : node(p.node) {} |
---|

32 | |
---|

33 | int operator==(const iterator &p) const { return (node == p.node); } |
---|

34 | int operator!=(const iterator &p) const { return (node != p.node); } |
---|

35 | |
---|

36 | iterator& operator++() { node = node->next; return *this; } |
---|

37 | iterator next() { return node->next; } |
---|

38 | |
---|

39 | T& operator*() { return node->data; } |
---|

40 | }; |
---|

41 | |
---|

42 | iterator end() { return (link)(&list); } |
---|

43 | iterator begin_prev() { return end(); } |
---|

44 | iterator begin() { return list; } |
---|

45 | |
---|

46 | int empty() { return begin() == end(); } |
---|

47 | |
---|

48 | iterator insert_next(iterator pos, const T& item) |
---|

49 | { |
---|

50 | link p = new list_node(item); |
---|

51 | p->next = pos.node->next; |
---|

52 | pos.node->next = p; |
---|

53 | |
---|

54 | return p; |
---|

55 | } |
---|

56 | |
---|

57 | void erase_next(iterator pos) |
---|

58 | { |
---|

59 | link p = pos.node->next; |
---|

60 | pos.node->next = p->next; |
---|

61 | delete p; |
---|

62 | } |
---|

63 | |
---|

64 | int find_prev(iterator& p, const T& item) |
---|

65 | { |
---|

66 | while (p.node->next != end().node) |
---|

67 | { |
---|

68 | if (*(p.next())==item) |
---|

69 | return 1; |
---|

70 | ++p; |
---|

71 | } |
---|

72 | return 0; |
---|

73 | } |
---|

74 | |
---|

75 | void move_next(iterator&p, iterator&q) |
---|

76 | { |
---|

77 | link tmp; |
---|

78 | |
---|

79 | tmp = p.node->next; |
---|

80 | if (tmp == q.node) |
---|

81 | return; |
---|

82 | p.node->next = tmp->next; |
---|

83 | tmp->next = q.node->next; |
---|

84 | q.node->next = tmp; |
---|

85 | } |
---|

86 | |
---|

87 | int find(T& item) { iterator p = begin_prev(); return find_prev(p, item); } |
---|

88 | void insert(const T& item) { insert_next( begin_prev(), item); } |
---|

89 | void erase() { erase_next( begin_prev() ); } |
---|

90 | |
---|

91 | void erase_all() |
---|

92 | { |
---|

93 | while (!empty()) |
---|

94 | erase(); |
---|

95 | } |
---|

96 | |
---|

97 | isllist() |
---|

98 | { |
---|

99 | list = (link)&list; |
---|

100 | } |
---|

101 | |
---|

102 | ~isllist() |
---|

103 | { |
---|

104 | erase_all(); |
---|

105 | } |
---|

106 | }; |
---|

107 | |
---|

108 | #endif |
---|