Subversion Repositories Kolibri OS

Rev

Rev 7983 | 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 
 
8097 maxcodehac 4 
    Copyright (c) 2018-2020, 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 
 
129 
    IF (next # NIL) & (prev # NIL) THEN
130 
        prev.next := next;
131 
        next.prev := prev
132 
    ELSIF (next = NIL) & (prev = NIL) THEN
133 
        list.first := NIL;
134 
        list.last := NIL
135 
    ELSIF (next = NIL) & (prev # NIL) THEN
136 
        prev.next := NIL;
137 
        list.last := prev
138 
    ELSIF (next # NIL) & (prev = NIL) THEN
139 
        next.prev := NIL;
140 
        list.first := next
141 
    END
142 
 
143 
END delete;
144 
 
145 
 
146 
PROCEDURE count* (list: LIST): INTEGER;
147 
VAR
148 
    item: ITEM;
149 
    res:  INTEGER;
150 
 
151 
BEGIN
152 
    ASSERT(list # NIL);
153 
    res := 0;
154 
 
155 
    item := list.first;
156 
    WHILE item # NIL DO
157 
        INC(res);
158 
        item := item.next
159 
    END
160 
 
161 
    RETURN res
162 
END count;
163 
 
164 
 
7693 akron1 165 
PROCEDURE getidx* (list: LIST; idx: INTEGER): ITEM;
166 
VAR
167 
    item: ITEM;
168 
 
169 
BEGIN
170 
    ASSERT(list # NIL);
171 
    ASSERT(idx >= 0);
172 
 
173 
    item := list.first;
174 
    WHILE (item # NIL) & (idx > 0) DO
175 
        item := item.next;
176 
        DEC(idx)
177 
    END
178 
 
179 
    RETURN item
180 
END getidx;
181 
 
182 
 
7597 akron1 183 
PROCEDURE create* (list: LIST): LIST;
184 
BEGIN
185 
    IF list = NIL THEN
186 
        NEW(list)
187 
    END;
188 
 
7693 akron1 189 
    list.first := NIL;
190 
    list.last  := NIL
7597 akron1 191 
 
192 
    RETURN list
193 
END create;
194 
 
195 
 
7983 leency 196 
END LISTS.