Subversion Repositories Kolibri OS

Rev

Rev 8097 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
7983 leency 1 
(*
7597 akron1 2 
    BSD 2-Clause License
3 
 
8859 leency 4 
    Copyright (c) 2018-2021, Anton Krotov
7597 akron1 5 
    All rights reserved.
6 
*)
7 
 
8 
MODULE LISTS;
9 
 
10 
IMPORT C := COLLECTIONS;
11 
 
12 
 
13 
TYPE
14 
 
15 
    ITEM* = POINTER TO RECORD (C.ITEM)
16 
 
17 
        prev*, next*: ITEM
18 
 
19 
    END;
20 
 
21 
    LIST* = POINTER TO RECORD
22 
 
23 
        first*, last*: ITEM
24 
 
25 
    END;
26 
 
27 
 
28 
PROCEDURE push* (list: LIST; item: ITEM);
29 
BEGIN
30 
    ASSERT(list # NIL);
31 
    ASSERT(item # NIL);
32 
 
33 
    IF list.first = NIL THEN
34 
        list.first := item;
8097 maxcodehac 35 
        item.prev  := NIL
7597 akron1 36 
    ELSE
37 
        ASSERT(list.last # NIL);
38 
        item.prev := list.last;
8097 maxcodehac 39 
        list.last.next := item
40 
    END;
41 
    list.last := item;
42 
    item.next := NIL
7597 akron1 43 
END push;
44 
 
45 
 
46 
PROCEDURE pop* (list: LIST): ITEM;
47 
VAR
48 
    last: ITEM;
49 
 
50 
BEGIN
51 
    ASSERT(list # NIL);
52 
 
53 
    last := list.last;
54 
 
55 
    IF last # NIL THEN
56 
        IF last = list.first THEN
57 
            list.first := NIL;
58 
            list.last := NIL
59 
        ELSE
60 
            list.last := last.prev;
61 
            list.last.next := NIL
62 
        END;
63 
 
64 
        last.next := NIL;
65 
        last.prev := NIL
66 
    END
67 
 
68 
    RETURN last
69 
END pop;
70 
 
71 
 
72 
PROCEDURE insert* (list: LIST; cur, nov: ITEM);
73 
VAR
74 
    next: ITEM;
75 
 
76 
BEGIN
77 
    ASSERT(list # NIL);
78 
    ASSERT(nov # NIL);
79 
    ASSERT(cur # NIL);
80 
 
81 
    next := cur.next;
82 
 
83 
    IF next # NIL THEN
84 
        next.prev := nov;
85 
        nov.next := next;
86 
        cur.next := nov;
87 
        nov.prev := cur
88 
    ELSE
89 
        push(list, nov)
90 
    END
91 
 
92 
END insert;
93 
 
94 
 
95 
PROCEDURE insertL* (list: LIST; cur, nov: ITEM);
96 
VAR
97 
    prev: ITEM;
98 
 
99 
BEGIN
100 
    ASSERT(list # NIL);
101 
    ASSERT(nov # NIL);
102 
    ASSERT(cur # NIL);
103 
 
104 
    prev := cur.prev;
105 
 
106 
    IF prev # NIL THEN
107 
        prev.next := nov;
8097 maxcodehac 108 
        nov.prev := prev
7597 akron1 109 
    ELSE
110 
        nov.prev := NIL;
111 
        list.first := nov
8097 maxcodehac 112 
    END;
113 
    cur.prev := nov;
114 
    nov.next := cur
7597 akron1 115 
END insertL;
116 
 
117 
 
118 
PROCEDURE delete* (list: LIST; item: ITEM);
119 
VAR
120 
    prev, next: ITEM;
121 
 
122 
BEGIN
123 
    ASSERT(list # NIL);
124 
    ASSERT(item # NIL);
125 
 
126 
    prev := item.prev;
127 
    next := item.next;
128 
 
8859 leency 129 
    IF next # NIL THEN
130 
        IF prev # NIL THEN
131 
            prev.next := next;
132 
            next.prev := prev
133 
        ELSE
134 
            next.prev := NIL;
135 
            list.first := next
136 
        END
137 
    ELSE
138 
        IF prev # NIL THEN
139 
            prev.next := NIL;
140 
            list.last := prev
141 
        ELSE
142 
            list.first := NIL;
143 
            list.last := NIL
144 
        END
7597 akron1 145 
    END
146 
END delete;
147 
 
148 
 
149 
PROCEDURE count* (list: LIST): INTEGER;
150 
VAR
151 
    item: ITEM;
152 
    res:  INTEGER;
153 
 
154 
BEGIN
155 
    ASSERT(list # NIL);
156 
    res := 0;
157 
 
158 
    item := list.first;
159 
    WHILE item # NIL DO
160 
        INC(res);
161 
        item := item.next
162 
    END
163 
 
164 
    RETURN res
165 
END count;
166 
 
167 
 
7693 akron1 168 
PROCEDURE getidx* (list: LIST; idx: INTEGER): ITEM;
169 
VAR
170 
    item: ITEM;
171 
 
172 
BEGIN
173 
    ASSERT(list # NIL);
174 
    ASSERT(idx >= 0);
175 
 
176 
    item := list.first;
177 
    WHILE (item # NIL) & (idx > 0) DO
178 
        item := item.next;
179 
        DEC(idx)
180 
    END
181 
 
182 
    RETURN item
183 
END getidx;
184 
 
185 
 
7597 akron1 186 
PROCEDURE create* (list: LIST): LIST;
187 
BEGIN
188 
    IF list = NIL THEN
189 
        NEW(list)
190 
    END;
191 
 
7693 akron1 192 
    list.first := NIL;
193 
    list.last  := NIL
7597 akron1 194 
 
195 
    RETURN list
196 
END create;
197 
 
198 
 
7983 leency 199 
END LISTS.