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

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

Code formatting

  • Property svn:eol-style set to native
File size: 6.6 KB
RevLine 
[286]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.
[109]4
5#include "multimap.h"
6#include <stdio.h>
7
8int MultiMap::getBegin() const
9{
[733]10        if (isEmpty()) return 0;
11        return getBegin(0);
[109]12}
13
14int MultiMap::getEnd() const
15{
[733]16        if (isEmpty()) return -1;
17        return getBegin(mappingCount() - 1) - 1;
[109]18}
19
20int MultiMap::findData(int x) const
21{
[733]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)
[109]30                {
[733]31                        if ((c == n) || (getBegin(c + 1) > x)) return c;
32                        a = c;
[109]33                }
[733]34                else
[109]35                {
[733]36                        b = c - 1;
[109]37                }
38        }
39}
40
[733]41int MultiMap::addRange(int &r, const MultiRange& mr)
[109]42{
[733]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
[109]51        {
[733]52                SingleMapping *prev = getMapping(r - 1);
53                if (prev->to == sm->to)
[109]54                { // splice with prev
[733]55                        removeData(r);
56                        delete sm;
57                        sm = prev;
58                        r--;
59                        ret--;
[109]60                }
61        }
[733]62        if (r < (mappingCount() - 2)) // next exists
[109]63        {
[733]64                SingleMapping *next = getMapping(r + 1);
65                if (next->to == sm->to)
[109]66                { // splice with next
[733]67                        removeData(r + 1);
68                        delete next;
69                        ret--;
70                        r--;
[109]71                }
72        }
[733]73        return ret;
[109]74}
75
[733]76int MultiMap::addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr)
[109]77{
[733]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)
[109]84        {
[733]85                if (mappingCount())
[109]86                {
[733]87                        m = getMapping(0);
88                        if (end == (m->begin - 1))
[109]89                        { // adjacent to m
[733]90                                if (m->to == mr)
[109]91                                { // shift only
[733]92                                        m->begin = begin;
93                                        return 0;
[109]94                                }
[733]95                                // single add
96                                SingleMapping *newmap = new SingleMapping(begin, mr);
97                                addData(0, newmap);
98                                r = 0;
99                                return 1;
[109]100                        }
101                }
[733]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]109        }
110
[733]111        if (r == (mappingCount() - 1))
[109]112        {
[733]113                m = getMapping(r);
114                m1 = getMapping(r - 1);
115                if (begin == m->begin)
[109]116                { // adjacent
[733]117                        if (m1->to == mr)
[109]118                        { // shift only
[733]119                                m->begin = end + 1;
120                                return 0;
[109]121                        }
[733]122                        // single add
123                        m->begin = end + 1;
124                        SingleMapping *newmap = new SingleMapping(begin, mr);
125                        addData(r, newmap);
126                        return 1;
[109]127                }
[733]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;
[109]135        }
136
[733]137        m = getMapping(r);
138        if (m->to.contains(mr)) return 0;
139        if (begin == m->begin) // begin at range boundary
[109]140        {
[733]141                m2 = getMapping(r + 1);
142                if (end == (m2->begin - 1)) return addRange(r, mr);
[109]143
[733]144                SingleMapping *newmap = new SingleMapping(begin, m->to);
145                newmap->to.add(mr);
146                if (r > 0)
[109]147                { // join prev possible...
[733]148                        m1 = getMapping(r - 1);
149                        if (m1->to == newmap->to)
[109]150                        { // joint prev = shift
[733]151                                delete newmap;
152                                m->begin = end + 1;
153                                return 0;
[109]154                        }
155                }
[733]156                // single add:
157                m->begin = end + 1;
158                addData(r, newmap);
159                return 1;
[109]160        }
161
[733]162        m2 = getMapping(r + 1);
163        if (end == (m2->begin - 1)) // end at range boundary
[109]164        {
[733]165                SingleMapping *newmap = new SingleMapping(begin, m->to);
166                newmap->to.add(mr);
167                if (r < (mappingCount() - 2))
[109]168                { // join next possible...
[733]169                        if (m2->to == newmap->to)
[109]170                        { // joint next = shift
[733]171                                m2->begin = begin;
172                                delete newmap;
173                                return 0;
[109]174                        }
175                }
[733]176                // single add
177                r++;
178                addData(r, newmap);
179                return 1;
[109]180        }
[733]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;
[109]189}
190
[733]191void MultiMap::add(int begin, int end, const MultiRange& to)
[109]192{
[733]193        if (to.isEmpty()) return;
194        if (end < begin) return;
195        int r1 = findData(begin);
196        int r2 = findData(end);
197        if (r1 == r2)
[109]198        {
[733]199                addRangeBeginEnd(r1, begin, end, to);
[109]200        }
[733]201        else
[109]202        {
[733]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);
[109]208        }
209}
210
211const MultiRange& MultiMap::map(int x) const
212{
[733]213        static MultiRange empty;
214        int m = findData(x);
215        if (m < 0) return empty;
216        SingleMapping *sm = getMapping(m);
217        return sm->to;
[109]218}
219
[733]220MultiRange MultiMap::map(int begin, int end) const
[109]221{
[733]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;
[109]232}
233
234MultiRange MultiMap::map(const MultiRange& ranges) const
235{
[733]236        MultiRange mr;
237        for (int i = 0; i < ranges.rangeCount(); i++)
238                mr.add(map(ranges.getRange(i)));
239        return mr;
[109]240}
241
242IRange MultiMap::getRange(int i) const
243{
[733]244        if ((i<0) || (i>(data.size() - 1))) return IRange();
245        return IRange(getBegin(i), getBegin(i + 1) - 1);
[109]246}
247
248void MultiMap::operator=(const MultiMap& mm)
249{
[733]250        clear();
251        for (int i = 0; i < mm.mappingCount(); i++)
252                addData(i, new SingleMapping(*mm.getMapping(i)));
[109]253}
254
[733]255void MultiMap::addCombined(const MultiMap& m1, const MultiMap& m2)
[109]256{
[733]257        for (int i = 0; i < m1.rangeCount(); i++)
[109]258        {
[733]259                IRange r = m1.getRange(i);
260                add(r, m2.map(m1.getMapping(i)->to));
[109]261        }
262}
263
[733]264void MultiMap::add(const MultiRange& from, const MultiRange& to)
[109]265{
[733]266        for (int i = 0; i < from.rangeCount(); i++)
267                add(from.getRange(i), to);
[109]268}
269
270void MultiMap::addReversed(const MultiMap& m)
271{
[733]272        for (int i = 0; i < m.rangeCount(); i++)
[109]273        {
[733]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);
[109]278        }
279}
280
281MultiMap::~MultiMap()
[733]282{
283        clear();
284}
[109]285
286void MultiMap::clear()
287{
[733]288        for (int i = 0; i < data.size(); i++)
289                delete getData(i);
290        data.clear();
[109]291}
292
293///////////////////
294
295void MultiMap::print() const
296{
[733]297        printf("{ ");
298        for (int i = 0; i < (mappingCount() - 1); i++)
[109]299        {
[733]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");
[109]309        }
[733]310        printf("}\n");
[109]311}
312
313void MultiMap::print2() const
314{
[733]315        int y;
316        int id = 0, id2;
317        if (isEmpty())
[109]318        {
[733]319                printf("{ empty }\n");
320                return;
[109]321        }
[733]322        printf("{\n");
323        for (y = getBegin(); y <= getEnd(); y++)
[109]324        {
[733]325                id2 = findMappingId(y + 1);
326                printf("%2d %c", y, (id2 != id) ? '_' : ' ');
327                id = id2;
328                map(y).print2();
329                printf("\n");
[109]330        }
[733]331        printf("}\n");
[109]332}
Note: See TracBrowser for help on using the repository browser.