Subversion Repositories Kolibri OS

Rev

Rev 7696 | Go to most recent revision | 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 
 
7696 akron1 4 
    Copyright (c) 2018-2019, 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;
35 
        list.last  := item;
36 
        item.prev  := NIL;
37 
        item.next  := NIL
38 
    ELSE
39 
        ASSERT(list.last # NIL);
40 
 
41 
        item.prev := list.last;
42 
        list.last.next := item;
43 
        item.next := NIL;
44 
        list.last := item
45 
    END
46 
END push;
47 
 
48 
 
49 
PROCEDURE pop* (list: LIST): ITEM;
50 
VAR
51 
    last: ITEM;
52 
 
53 
BEGIN
54 
    ASSERT(list # NIL);
55 
 
56 
    last := list.last;
57 
 
58 
    IF last # NIL THEN
59 
        IF last = list.first THEN
60 
            list.first := NIL;
61 
            list.last := NIL
62 
        ELSE
63 
            list.last := last.prev;
64 
            list.last.next := NIL
65 
        END;
66 
 
67 
        last.next := NIL;
68 
        last.prev := NIL
69 
    END
70 
 
71 
    RETURN last
72 
END pop;
73 
 
74 
 
75 
PROCEDURE insert* (list: LIST; cur, nov: ITEM);
76 
VAR
77 
    next: ITEM;
78 
 
79 
BEGIN
80 
    ASSERT(list # NIL);
81 
    ASSERT(nov # NIL);
82 
    ASSERT(cur # NIL);
83 
 
84 
    next := cur.next;
85 
 
86 
    IF next # NIL THEN
87 
        next.prev := nov;
88 
        nov.next := next;
89 
        cur.next := nov;
90 
        nov.prev := cur
91 
    ELSE
92 
        push(list, nov)
93 
    END
94 
 
95 
END insert;
96 
 
97 
 
98 
PROCEDURE insertL* (list: LIST; cur, nov: ITEM);
99 
VAR
100 
    prev: ITEM;
101 
 
102 
BEGIN
103 
    ASSERT(list # NIL);
104 
    ASSERT(nov # NIL);
105 
    ASSERT(cur # NIL);
106 
 
107 
    prev := cur.prev;
108 
 
109 
    IF prev # NIL THEN
110 
        prev.next := nov;
111 
        nov.prev := prev;
112 
        cur.prev := nov;
113 
        nov.next := cur
114 
    ELSE
115 
        nov.prev := NIL;
116 
        cur.prev := nov;
117 
        nov.next := cur;
118 
        list.first := nov
119 
    END
120 
 
121 
END insertL;
122 
 
123 
 
124 
PROCEDURE delete* (list: LIST; item: ITEM);
125 
VAR
126 
    prev, next: ITEM;
127 
 
128 
BEGIN
129 
    ASSERT(list # NIL);
130 
    ASSERT(item # NIL);
131 
 
132 
    prev := item.prev;
133 
    next := item.next;
134 
 
135 
    IF (next # NIL) & (prev # NIL) THEN
136 
        prev.next := next;
137 
        next.prev := prev
138 
    ELSIF (next = NIL) & (prev = NIL) THEN
139 
        list.first := NIL;
140 
        list.last := NIL
141 
    ELSIF (next = NIL) & (prev # NIL) THEN
142 
        prev.next := NIL;
143 
        list.last := prev
144 
    ELSIF (next # NIL) & (prev = NIL) THEN
145 
        next.prev := NIL;
146 
        list.first := next
147 
    END
148 
 
149 
END delete;
150 
 
151 
 
152 
PROCEDURE count* (list: LIST): INTEGER;
153 
VAR
154 
    item: ITEM;
155 
    res:  INTEGER;
156 
 
157 
BEGIN
158 
    ASSERT(list # NIL);
159 
    res := 0;
160 
 
161 
    item := list.first;
162 
    WHILE item # NIL DO
163 
        INC(res);
164 
        item := item.next
165 
    END
166 
 
167 
    RETURN res
168 
END count;
169 
 
170 
 
7693 akron1 171 
PROCEDURE getidx* (list: LIST; idx: INTEGER): ITEM;
172 
VAR
173 
    item: ITEM;
174 
 
175 
BEGIN
176 
    ASSERT(list # NIL);
177 
    ASSERT(idx >= 0);
178 
 
179 
    item := list.first;
180 
    WHILE (item # NIL) & (idx > 0) DO
181 
        item := item.next;
182 
        DEC(idx)
183 
    END
184 
 
185 
    RETURN item
186 
END getidx;
187 
 
188 
 
7597 akron1 189 
PROCEDURE create* (list: LIST): LIST;
190 
BEGIN
191 
    IF list = NIL THEN
192 
        NEW(list)
193 
    END;
194 
 
7693 akron1 195 
    list.first := NIL;
196 
    list.last  := NIL
7597 akron1 197 
 
198 
    RETURN list
199 
END create;
200 
 
201 
 
7983 leency 202 
END LISTS.