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

Last change on this file since 121 was 121, checked in by sz, 7 years ago

updated file headers and makefiles

  • Property svn:eol-style set to native
File size: 6.1 KB
Line 
1// This file is a part of the Framsticks GDK.
2// Copyright (C) 2002-2014  Maciej Komosinski and Szymon Ulatowski.  See LICENSE.txt for details.
3// Refer to http://www.framsticks.com/ for further information.
4
5#include "multimap.h"
6#include <stdio.h>
7
8int MultiMap::getBegin() const
9{
10if (isEmpty()) return 0;
11return getBegin(0);
12}
13
14int MultiMap::getEnd() const
15{
16if (isEmpty()) return -1;
17return getBegin(mappingCount()-1)-1;
18}
19
20int MultiMap::findData(int x) const
21{
22if (isEmpty()) return -1;
23if (getBegin(0)>x) return -1;
24int a,b,c;
25int n=mappingCount()-1;
26a=0; b=n; // find c = last range with begin<=x
27while(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
45int ret=0;
46SingleMapping *sm=getMapping(r);
47if (sm->to.contains(mr)) return 0; // do nothing
48sm->to.add(mr);
49// after adding mr to this mapping it could be the same as the previous/next one
50if (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        }
62if (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        }
73return 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
82SingleMapping *m,*m2,*m1;
83if (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
111if (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
137m=getMapping(r);
138if (m->to.contains(mr)) return 0;
139if (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
162m2=getMapping(r+1);
163if (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:
182SingleMapping *newmap=new SingleMapping(begin,m->to);
183newmap->to.add(mr);
184SingleMapping *newmap2=new SingleMapping(end+1,m->to);
185addData(r+1,newmap);
186addData(r+2,newmap2);
187r+=2;
188return 2;
189}
190
191void MultiMap::add(int begin,int end,const MultiRange& to)
192{
193if (to.isEmpty()) return;
194if (end<begin) return;
195int r1=findData(begin);
196int r2=findData(end);
197if (r1==r2)
198        {
199        addRangeBeginEnd(r1,begin,end,to);
200        }
201else
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{
213static MultiRange empty;
214int m=findData(x);
215if (m<0) return empty;
216SingleMapping *sm=getMapping(m);
217return sm->to;
218}
219
220MultiRange MultiMap::map(int begin,int end) const
221{
222MultiRange mr;
223int m=findData(begin);
224for (;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        }
231return mr;
232}
233
234MultiRange MultiMap::map(const MultiRange& ranges) const
235{
236MultiRange mr;
237for(int i=0;i<ranges.rangeCount();i++)
238        mr.add(map(ranges.getRange(i)));
239return mr;
240}
241
242IRange MultiMap::getRange(int i) const
243{
244if ((i<0)||(i>(data.size()-1))) return IRange();
245return IRange(getBegin(i),getBegin(i+1)-1);
246}
247
248void MultiMap::operator=(const MultiMap& mm)
249{
250clear();
251for(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{
257for(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{
266for(int i=0;i<from.rangeCount();i++)
267        add(from.getRange(i),to);
268}
269
270void MultiMap::addReversed(const MultiMap& m)
271{
272for(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{ clear();}
283
284void MultiMap::clear()
285{
286for(int i=0;i<data.size();i++)
287        delete getData(i);
288data.clear();
289}
290
291///////////////////
292
293void MultiMap::print() const
294{
295printf("{ ");
296for (int i=0;i<(mappingCount()-1);i++)
297        {
298        if (i) printf("  ");
299        SingleMapping *sm=getMapping(i);
300        SingleMapping *sm2=getMapping(i+1);
301        if (sm2->begin==sm->begin+1)
302                printf("[%d] -> ",sm->begin);
303        else
304                printf("[%d-%d] -> ",sm->begin,sm2->begin-1);
305        sm->to.print();
306        printf("\n");
307        }
308printf("}\n");
309}
310
311void MultiMap::print2() const
312{
313int y;
314int id=0,id2;
315if (isEmpty())
316        {
317        printf("{ empty }\n");
318        return;
319        }
320printf("{\n");
321for (y=getBegin();y<=getEnd();y++)
322        {
323        id2=findMappingId(y+1);
324        printf("%2d %c",y,(id2!=id)?'_':' ');
325        id=id2;
326        map(y).print2();
327        printf("\n");
328        }
329printf("}\n");
330}
Note: See TracBrowser for help on using the repository browser.