source: cpp/frams/util/multimap.cpp @ 1040

Last change on this file since 1040 was 733, checked in by Maciej Komosinski, 3 years ago

Code formatting

  • Property svn:eol-style set to native
File size: 6.6 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2015  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#include "multimap.h"
6#include <stdio.h>
7
8int MultiMap::getBegin() const
9{
10        if (isEmpty()) return 0;
11        return getBegin(0);
12}
13
14int MultiMap::getEnd() const
15{
16        if (isEmpty()) return -1;
17        return getBegin(mappingCount() - 1) - 1;
18}
19
20int MultiMap::findData(int x) const
21{
22        if (isEmpty()) return -1;
23        if (getBegin(0) > x) return -1;
24        int a, b, c;
25        int n = mappingCount() - 1;
26        a = 0; b = n; // find c = last range with begin<=x
27        while (1){
28                c = (a + b + 1) / 2;
29                if (getBegin(c) <= x)
30                {
31                        if ((c == n) || (getBegin(c + 1) > x)) return c;
32                        a = c;
33                }
34                else
35                {
36                        b = c - 1;
37                }
38        }
39}
40
41int MultiMap::addRange(int &r, const MultiRange& mr)
42{
43        // precondition: 0 <= r < (mappingCount()-1)
44        // 1.maybe change mapping in this range
45        int ret = 0;
46        SingleMapping *sm = getMapping(r);
47        if (sm->to.contains(mr)) return 0; // do nothing
48        sm->to.add(mr);
49        // after adding mr to this mapping it could be the same as the previous/next one
50        if (r > 0) // prev exists
51        {
52                SingleMapping *prev = getMapping(r - 1);
53                if (prev->to == sm->to)
54                { // splice with prev
55                        removeData(r);
56                        delete sm;
57                        sm = prev;
58                        r--;
59                        ret--;
60                }
61        }
62        if (r < (mappingCount() - 2)) // next exists
63        {
64                SingleMapping *next = getMapping(r + 1);
65                if (next->to == sm->to)
66                { // splice with next
67                        removeData(r + 1);
68                        delete next;
69                        ret--;
70                        r--;
71                }
72        }
73        return ret;
74}
75
76int MultiMap::addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr)
77{
78        // precondition: -1 <= r < mappingCount()
79        //               begin <= end
80        //               begin >= mapping.begin
81        //               end < nextmapping.begin
82        SingleMapping *m, *m2, *m1;
83        if (r < 0)
84        {
85                if (mappingCount())
86                {
87                        m = getMapping(0);
88                        if (end == (m->begin - 1))
89                        { // adjacent to m
90                                if (m->to == mr)
91                                { // shift only
92                                        m->begin = begin;
93                                        return 0;
94                                }
95                                // single add
96                                SingleMapping *newmap = new SingleMapping(begin, mr);
97                                addData(0, newmap);
98                                r = 0;
99                                return 1;
100                        }
101                }
102                // double add
103                SingleMapping *newmap = new SingleMapping(begin, mr);
104                SingleMapping *newmap2 = new SingleMapping(end + 1);
105                addData(0, newmap);
106                addData(1, newmap2);
107                r = 1;
108                return 2;
109        }
110
111        if (r == (mappingCount() - 1))
112        {
113                m = getMapping(r);
114                m1 = getMapping(r - 1);
115                if (begin == m->begin)
116                { // adjacent
117                        if (m1->to == mr)
118                        { // shift only
119                                m->begin = end + 1;
120                                return 0;
121                        }
122                        // single add
123                        m->begin = end + 1;
124                        SingleMapping *newmap = new SingleMapping(begin, mr);
125                        addData(r, newmap);
126                        return 1;
127                }
128                // double add
129                SingleMapping *newmap = new SingleMapping(begin, mr);
130                SingleMapping *newmap2 = new SingleMapping(end + 1);
131                addData(r + 1, newmap);
132                addData(r + 2, newmap2);
133                r += 2;
134                return 2;
135        }
136
137        m = getMapping(r);
138        if (m->to.contains(mr)) return 0;
139        if (begin == m->begin) // begin at range boundary
140        {
141                m2 = getMapping(r + 1);
142                if (end == (m2->begin - 1)) return addRange(r, mr);
143
144                SingleMapping *newmap = new SingleMapping(begin, m->to);
145                newmap->to.add(mr);
146                if (r > 0)
147                { // join prev possible...
148                        m1 = getMapping(r - 1);
149                        if (m1->to == newmap->to)
150                        { // joint prev = shift
151                                delete newmap;
152                                m->begin = end + 1;
153                                return 0;
154                        }
155                }
156                // single add:
157                m->begin = end + 1;
158                addData(r, newmap);
159                return 1;
160        }
161
162        m2 = getMapping(r + 1);
163        if (end == (m2->begin - 1)) // end at range boundary
164        {
165                SingleMapping *newmap = new SingleMapping(begin, m->to);
166                newmap->to.add(mr);
167                if (r < (mappingCount() - 2))
168                { // join next possible...
169                        if (m2->to == newmap->to)
170                        { // joint next = shift
171                                m2->begin = begin;
172                                delete newmap;
173                                return 0;
174                        }
175                }
176                // single add
177                r++;
178                addData(r, newmap);
179                return 1;
180        }
181        // double add:
182        SingleMapping *newmap = new SingleMapping(begin, m->to);
183        newmap->to.add(mr);
184        SingleMapping *newmap2 = new SingleMapping(end + 1, m->to);
185        addData(r + 1, newmap);
186        addData(r + 2, newmap2);
187        r += 2;
188        return 2;
189}
190
191void MultiMap::add(int begin, int end, const MultiRange& to)
192{
193        if (to.isEmpty()) return;
194        if (end < begin) return;
195        int r1 = findData(begin);
196        int r2 = findData(end);
197        if (r1 == r2)
198        {
199                addRangeBeginEnd(r1, begin, end, to);
200        }
201        else
202        {
203                r2 += addRangeBeginEnd(r1, begin, getBegin(r1 + 1) - 1, to);
204                r1++;
205                for (; r1 < r2; r1++)
206                        r2 += addRange(r1, to);
207                addRangeBeginEnd(r1, getBegin(r1), end, to);
208        }
209}
210
211const MultiRange& MultiMap::map(int x) const
212{
213        static MultiRange empty;
214        int m = findData(x);
215        if (m < 0) return empty;
216        SingleMapping *sm = getMapping(m);
217        return sm->to;
218}
219
220MultiRange MultiMap::map(int begin, int end) const
221{
222        MultiRange mr;
223        int m = findData(begin);
224        for (; m < rangeCount(); m++)
225                if (m >= 0)
226                {
227                SingleMapping *sm = getMapping(m);
228                if (sm->begin > end) break;
229                mr.add(sm->to);
230                }
231        return mr;
232}
233
234MultiRange MultiMap::map(const MultiRange& ranges) const
235{
236        MultiRange mr;
237        for (int i = 0; i < ranges.rangeCount(); i++)
238                mr.add(map(ranges.getRange(i)));
239        return mr;
240}
241
242IRange MultiMap::getRange(int i) const
243{
244        if ((i<0) || (i>(data.size() - 1))) return IRange();
245        return IRange(getBegin(i), getBegin(i + 1) - 1);
246}
247
248void MultiMap::operator=(const MultiMap& mm)
249{
250        clear();
251        for (int i = 0; i < mm.mappingCount(); i++)
252                addData(i, new SingleMapping(*mm.getMapping(i)));
253}
254
255void MultiMap::addCombined(const MultiMap& m1, const MultiMap& m2)
256{
257        for (int i = 0; i < m1.rangeCount(); i++)
258        {
259                IRange r = m1.getRange(i);
260                add(r, m2.map(m1.getMapping(i)->to));
261        }
262}
263
264void MultiMap::add(const MultiRange& from, const MultiRange& to)
265{
266        for (int i = 0; i < from.rangeCount(); i++)
267                add(from.getRange(i), to);
268}
269
270void MultiMap::addReversed(const MultiMap& m)
271{
272        for (int i = 0; i < m.rangeCount(); i++)
273        {
274                IRange r = m.getRange(i);
275                const MultiRange& mr = m.getMapping(i)->to;
276                for (int j = 0; j < mr.rangeCount(); j++)
277                        add(mr.getRange(j), r);
278        }
279}
280
281MultiMap::~MultiMap()
282{
283        clear();
284}
285
286void MultiMap::clear()
287{
288        for (int i = 0; i < data.size(); i++)
289                delete getData(i);
290        data.clear();
291}
292
293///////////////////
294
295void MultiMap::print() const
296{
297        printf("{ ");
298        for (int i = 0; i < (mappingCount() - 1); i++)
299        {
300                if (i) printf("  ");
301                SingleMapping *sm = getMapping(i);
302                SingleMapping *sm2 = getMapping(i + 1);
303                if (sm2->begin == sm->begin + 1)
304                        printf("[%d] -> ", sm->begin);
305                else
306                        printf("[%d-%d] -> ", sm->begin, sm2->begin - 1);
307                sm->to.print();
308                printf("\n");
309        }
310        printf("}\n");
311}
312
313void MultiMap::print2() const
314{
315        int y;
316        int id = 0, id2;
317        if (isEmpty())
318        {
319                printf("{ empty }\n");
320                return;
321        }
322        printf("{\n");
323        for (y = getBegin(); y <= getEnd(); y++)
324        {
325                id2 = findMappingId(y + 1);
326                printf("%2d %c", y, (id2 != id) ? '_' : ' ');
327                id = id2;
328                map(y).print2();
329                printf("\n");
330        }
331        printf("}\n");
332}
Note: See TracBrowser for help on using the repository browser.