Changeset 733 for cpp/frams/util/multimap.cpp

Timestamp:

02/15/18 00:43:07 (7 years ago)

Author:

Maciej Komosinski

Message:

Code formatting

File:

• cpp/frams/util/multimap.cpp (modified) (2 diffs)

cpp/frams/util/multimap.cpp

@@ -8 +8 @@
 int MultiMap::getBegin() const
 {
-if (isEmpty()) return 0;
-return getBegin(0);
+        if (isEmpty()) return 0;
+        return getBegin(0);
 }
 
 int MultiMap::getEnd() const
 {
-if (isEmpty()) return -1;
-return getBegin(mappingCount()-1)-1;
+        if (isEmpty()) return -1;
+        return getBegin(mappingCount() - 1) - 1;
 }
 
 int MultiMap::findData(int x) const
 {
-if (isEmpty()) return -1;
-if (getBegin(0)>x) return -1;
-int a,b,c;
-int n=mappingCount()-1;
-a=0; b=n; // find c = last range with begin<=x
-while(1){
-        c=(a+b+1)/2;
-        if (getBegin(c)<=x)
+        if (isEmpty()) return -1;
+        if (getBegin(0) > x) return -1;
+        int a, b, c;
+        int n = mappingCount() - 1;
+        a = 0; b = n; // find c = last range with begin<=x
+        while (1){
+                c = (a + b + 1) / 2;
+                if (getBegin(c) <= x)
                 {
-                if ((c==n)||(getBegin(c+1)>x)) return c;
-                a=c;
-                }
+                        if ((c == n) || (getBegin(c + 1) > x)) return c;
+                        a = c;
+                }
+                else
+                {
+                        b = c - 1;
+                }
+        }
+}
+
+int MultiMap::addRange(int &r, const MultiRange& mr)
+{
+        // precondition: 0 <= r < (mappingCount()-1)
+        // 1.maybe change mapping in this range
+        int ret = 0;
+        SingleMapping *sm = getMapping(r);
+        if (sm->to.contains(mr)) return 0; // do nothing
+        sm->to.add(mr);
+        // after adding mr to this mapping it could be the same as the previous/next one
+        if (r > 0) // prev exists
+        {
+                SingleMapping *prev = getMapping(r - 1);
+                if (prev->to == sm->to)
+                { // splice with prev
+                        removeData(r);
+                        delete sm;
+                        sm = prev;
+                        r--;
+                        ret--;
+                }
+        }
+        if (r < (mappingCount() - 2)) // next exists
+        {
+                SingleMapping *next = getMapping(r + 1);
+                if (next->to == sm->to)
+                { // splice with next
+                        removeData(r + 1);
+                        delete next;
+                        ret--;
+                        r--;
+                }
+        }
+        return ret;
+}
+
+int MultiMap::addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr)
+{
+        // precondition: -1 <= r < mappingCount()
+        //               begin <= end
+        //               begin >= mapping.begin
+        //               end < nextmapping.begin
+        SingleMapping *m, *m2, *m1;
+        if (r < 0)
+        {
+                if (mappingCount())
+                {
+                        m = getMapping(0);
+                        if (end == (m->begin - 1))
+                        { // adjacent to m
+                                if (m->to == mr)
+                                { // shift only
+                                        m->begin = begin;
+                                        return 0;
+                                }
+                                // single add
+                                SingleMapping *newmap = new SingleMapping(begin, mr);
+                                addData(0, newmap);
+                                r = 0;
+                                return 1;
+                        }
+                }
+                // double add
+                SingleMapping *newmap = new SingleMapping(begin, mr);
+                SingleMapping *newmap2 = new SingleMapping(end + 1);
+                addData(0, newmap);
+                addData(1, newmap2);
+                r = 1;
+                return 2;
+        }
+
+        if (r == (mappingCount() - 1))
+        {
+                m = getMapping(r);
+                m1 = getMapping(r - 1);
+                if (begin == m->begin)
+                { // adjacent
+                        if (m1->to == mr)
+                        { // shift only
+                                m->begin = end + 1;
+                                return 0;
+                        }
+                        // single add
+                        m->begin = end + 1;
+                        SingleMapping *newmap = new SingleMapping(begin, mr);
+                        addData(r, newmap);
+                        return 1;
+                }
+                // double add
+                SingleMapping *newmap = new SingleMapping(begin, mr);
+                SingleMapping *newmap2 = new SingleMapping(end + 1);
+                addData(r + 1, newmap);
+                addData(r + 2, newmap2);
+                r += 2;
+                return 2;
+        }
+
+        m = getMapping(r);
+        if (m->to.contains(mr)) return 0;
+        if (begin == m->begin) // begin at range boundary
+        {
+                m2 = getMapping(r + 1);
+                if (end == (m2->begin - 1)) return addRange(r, mr);
+
+                SingleMapping *newmap = new SingleMapping(begin, m->to);
+                newmap->to.add(mr);
+                if (r > 0)
+                { // join prev possible...
+                        m1 = getMapping(r - 1);
+                        if (m1->to == newmap->to)
+                        { // joint prev = shift
+                                delete newmap;
+                                m->begin = end + 1;
+                                return 0;
+                        }
+                }
+                // single add:
+                m->begin = end + 1;
+                addData(r, newmap);
+                return 1;
+        }
+
+        m2 = getMapping(r + 1);
+        if (end == (m2->begin - 1)) // end at range boundary
+        {
+                SingleMapping *newmap = new SingleMapping(begin, m->to);
+                newmap->to.add(mr);
+                if (r < (mappingCount() - 2))
+                { // join next possible...
+                        if (m2->to == newmap->to)
+                        { // joint next = shift
+                                m2->begin = begin;
+                                delete newmap;
+                                return 0;
+                        }
+                }
+                // single add
+                r++;
+                addData(r, newmap);
+                return 1;
+        }
+        // double add:
+        SingleMapping *newmap = new SingleMapping(begin, m->to);
+        newmap->to.add(mr);
+        SingleMapping *newmap2 = new SingleMapping(end + 1, m->to);
+        addData(r + 1, newmap);
+        addData(r + 2, newmap2);
+        r += 2;
+        return 2;
+}
+
+void MultiMap::add(int begin, int end, const MultiRange& to)
+{
+        if (to.isEmpty()) return;
+        if (end < begin) return;
+        int r1 = findData(begin);
+        int r2 = findData(end);
+        if (r1 == r2)
+        {
+                addRangeBeginEnd(r1, begin, end, to);
+        }
         else
+        {
+                r2 += addRangeBeginEnd(r1, begin, getBegin(r1 + 1) - 1, to);
+                r1++;
+                for (; r1 < r2; r1++)
+                        r2 += addRange(r1, to);
+                addRangeBeginEnd(r1, getBegin(r1), end, to);
+        }
+}
+
+const MultiRange& MultiMap::map(int x) const
+{
+        static MultiRange empty;
+        int m = findData(x);
+        if (m < 0) return empty;
+        SingleMapping *sm = getMapping(m);
+        return sm->to;
+}
+
+MultiRange MultiMap::map(int begin, int end) const
+{
+        MultiRange mr;
+        int m = findData(begin);
+        for (; m < rangeCount(); m++)
+                if (m >= 0)
                 {
-                b=c-1;
-                }
-        }
-}
-
-int MultiMap::addRange(int &r,const MultiRange& mr)
-{
-// precondition: 0 <= r < (mappingCount()-1)
-// 1.maybe change mapping in this range
-int ret=0;
-SingleMapping *sm=getMapping(r);
-if (sm->to.contains(mr)) return 0; // do nothing
-sm->to.add(mr);
-// after adding mr to this mapping it could be the same as the previous/next one
-if (r>0) // prev exists
-        {
-        SingleMapping *prev=getMapping(r-1);
-        if (prev->to == sm->to)
-                { // splice with prev
-                removeData(r);
-                delete sm;
-                sm=prev;
-                r--;
-                ret--;
-                }
-        }
-if (r<(mappingCount()-2)) // next exists
-        {
-        SingleMapping *next=getMapping(r+1);
-        if (next->to == sm->to)
-                { // splice with next
-                removeData(r+1);
-                delete next;
-                ret--;
-                r--;
-                }
-        }
-return ret;
-}
-
-int MultiMap::addRangeBeginEnd(int &r,int begin,int end,const MultiRange& mr)
-{
-// precondition: -1 <= r < mappingCount()
-//               begin <= end
-//               begin >= mapping.begin
-//               end < nextmapping.begin
-SingleMapping *m,*m2,*m1;
-if (r<0)
-        {
-        if (mappingCount())
-                {
-                m=getMapping(0);
-                if (end==(m->begin-1))
-                        { // adjacent to m
-                        if (m->to==mr)
-                                { // shift only
-                                m->begin=begin;
-                                return 0;
-                                }
-                        // single add
-                        SingleMapping *newmap=new SingleMapping(begin,mr);
-                        addData(0,newmap);
-                        r=0;
-                        return 1;
-                        }
-                }
-        // double add
-        SingleMapping *newmap=new SingleMapping(begin,mr);
-        SingleMapping *newmap2=new SingleMapping(end+1);
-        addData(0,newmap);
-        addData(1,newmap2);
-        r=1;
-        return 2;
-        }
-
-if (r==(mappingCount()-1))
-        {
-        m=getMapping(r);
-        m1=getMapping(r-1);
-        if (begin==m->begin)
-                { // adjacent
-                if (m1->to==mr)
-                        { // shift only
-                        m->begin=end+1;
-                        return 0;
-                        }
-                // single add
-                m->begin=end+1;
-                SingleMapping *newmap=new SingleMapping(begin,mr);
-                addData(r,newmap);
-                return 1;
-                }
-        // double add
-        SingleMapping *newmap=new SingleMapping(begin,mr);
-        SingleMapping *newmap2=new SingleMapping(end+1);
-        addData(r+1,newmap);
-        addData(r+2,newmap2);
-        r+=2;
-        return 2;
-        }
-
-m=getMapping(r);
-if (m->to.contains(mr)) return 0;
-if (begin==m->begin) // begin at range boundary
-        {
-        m2=getMapping(r+1);
-        if (end==(m2->begin-1)) return addRange(r,mr);
-
-        SingleMapping *newmap=new SingleMapping(begin,m->to);
-        newmap->to.add(mr);
-        if (r>0)
-                { // join prev possible...
-                m1=getMapping(r-1);
-                if (m1->to==newmap->to)
-                        { // joint prev = shift
-                        delete newmap;
-                        m->begin=end+1;
-                        return 0;
-                        }
-                }
-        // single add:
-        m->begin=end+1;
-        addData(r,newmap);
-        return 1;
-        }
-
-m2=getMapping(r+1);
-if (end==(m2->begin-1)) // end at range boundary
-        {
-        SingleMapping *newmap=new SingleMapping(begin,m->to);
-        newmap->to.add(mr);
-        if (r<(mappingCount()-2))
-                { // join next possible...
-                if (m2->to==newmap->to)
-                        { // joint next = shift
-                        m2->begin=begin;
-                        delete newmap;
-                        return 0;
-                        }
-                }
-        // single add
-        r++;
-        addData(r,newmap);
-        return 1;
-        }
-// double add:
-SingleMapping *newmap=new SingleMapping(begin,m->to);
-newmap->to.add(mr);
-SingleMapping *newmap2=new SingleMapping(end+1,m->to);
-addData(r+1,newmap);
-addData(r+2,newmap2);
-r+=2;
-return 2;
-}
-
-void MultiMap::add(int begin,int end,const MultiRange& to)
-{
-if (to.isEmpty()) return;
-if (end<begin) return;
-int r1=findData(begin);
-int r2=findData(end);
-if (r1==r2)
-        {
-        addRangeBeginEnd(r1,begin,end,to);
-        }
-else
-        {
-        r2+=addRangeBeginEnd(r1,begin,getBegin(r1+1)-1,to);
-        r1++;
-        for (;r1<r2;r1++)
-                r2+=addRange(r1,to);
-        addRangeBeginEnd(r1,getBegin(r1),end,to);
-        }
-}
-
-const MultiRange& MultiMap::map(int x) const
-{
-static MultiRange empty;
-int m=findData(x);
-if (m<0) return empty;
-SingleMapping *sm=getMapping(m);
-return sm->to;
-}
-
-MultiRange MultiMap::map(int begin,int end) const
-{
-MultiRange mr;
-int m=findData(begin);
-for (;m<rangeCount();m++)
-        if (m>=0)
-        {
-        SingleMapping *sm=getMapping(m);
-        if (sm->begin > end) break;
-        mr.add(sm->to);
-        }
-return mr;
+                SingleMapping *sm = getMapping(m);
+                if (sm->begin > end) break;
+                mr.add(sm->to);
+                }
+        return mr;
 }
 
 MultiRange MultiMap::map(const MultiRange& ranges) const
 {
-MultiRange mr;
-for(int i=0;i<ranges.rangeCount();i++)
-        mr.add(map(ranges.getRange(i)));
-return mr;
+        MultiRange mr;
+        for (int i = 0; i < ranges.rangeCount(); i++)
+                mr.add(map(ranges.getRange(i)));
+        return mr;
 }
 
 IRange MultiMap::getRange(int i) const
 {
-if ((i<0)||(i>(data.size()-1))) return IRange();
-return IRange(getBegin(i),getBegin(i+1)-1);
+        if ((i<0) || (i>(data.size() - 1))) return IRange();
+        return IRange(getBegin(i), getBegin(i + 1) - 1);
 }
 
 void MultiMap::operator=(const MultiMap& mm)
 {
-clear();
-for(int i=0;i<mm.mappingCount();i++)
-        addData(i,new SingleMapping(*mm.getMapping(i)));
-}
-
-void MultiMap::addCombined(const MultiMap& m1,const MultiMap& m2)
-{
-for(int i=0;i<m1.rangeCount();i++)
-        {
-        IRange r=m1.getRange(i);
-        add(r,m2.map(m1.getMapping(i)->to));
-        }
-}
-
-void MultiMap::add(const MultiRange& from,const MultiRange& to)
-{
-for(int i=0;i<from.rangeCount();i++)
-        add(from.getRange(i),to);
+        clear();
+        for (int i = 0; i < mm.mappingCount(); i++)
+                addData(i, new SingleMapping(*mm.getMapping(i)));
+}
+
+void MultiMap::addCombined(const MultiMap& m1, const MultiMap& m2)
+{
+        for (int i = 0; i < m1.rangeCount(); i++)
+        {
+                IRange r = m1.getRange(i);
+                add(r, m2.map(m1.getMapping(i)->to));
+        }
+}
+
+void MultiMap::add(const MultiRange& from, const MultiRange& to)
+{
+        for (int i = 0; i < from.rangeCount(); i++)
+                add(from.getRange(i), to);
 }
 
 void MultiMap::addReversed(const MultiMap& m)
 {
-for(int i=0;i<m.rangeCount();i++)
-        {
-        IRange r=m.getRange(i);
-        const MultiRange& mr=m.getMapping(i)->to;
-        for (int j=0;j<mr.rangeCount();j++)
-                add(mr.getRange(j),r);
+        for (int i = 0; i < m.rangeCount(); i++)
+        {
+                IRange r = m.getRange(i);
+                const MultiRange& mr = m.getMapping(i)->to;
+                for (int j = 0; j < mr.rangeCount(); j++)
+                        add(mr.getRange(j), r);
         }
 }
 
 MultiMap::~MultiMap()
-{ clear();}
+{
+        clear();
+}
 
 void MultiMap::clear()
 {
-for(int i=0;i<data.size();i++)
-        delete getData(i);
-data.clear();
+        for (int i = 0; i < data.size(); i++)
+                delete getData(i);
+        data.clear();
 }
 
@@ -293 +295 @@
 void MultiMap::print() const
 {
-printf("{ ");
-for (int i=0;i<(mappingCount()-1);i++)
-        {
-        if (i) printf("  ");
-        SingleMapping *sm=getMapping(i);
-        SingleMapping *sm2=getMapping(i+1);
-        if (sm2->begin==sm->begin+1)
-                printf("[%d] -> ",sm->begin);
-        else
-                printf("[%d-%d] -> ",sm->begin,sm2->begin-1);
-        sm->to.print();
-        printf("\n");
-        }
-printf("}\n");
+        printf("{ ");
+        for (int i = 0; i < (mappingCount() - 1); i++)
+        {
+                if (i) printf("  ");
+                SingleMapping *sm = getMapping(i);
+                SingleMapping *sm2 = getMapping(i + 1);
+                if (sm2->begin == sm->begin + 1)
+                        printf("[%d] -> ", sm->begin);
+                else
+                        printf("[%d-%d] -> ", sm->begin, sm2->begin - 1);
+                sm->to.print();
+                printf("\n");
+        }
+        printf("}\n");
 }
 
 void MultiMap::print2() const
 {
-int y;
-int id=0,id2;
-if (isEmpty())
-        {
-        printf("{ empty }\n");
-        return;
-        }
-printf("{\n");
-for (y=getBegin();y<=getEnd();y++)
-        {
-        id2=findMappingId(y+1);
-        printf("%2d %c",y,(id2!=id)?'_':' ');
-        id=id2;
-        map(y).print2();
-        printf("\n");
-        }
-printf("}\n");
-}
+        int y;
+        int id = 0, id2;
+        if (isEmpty())
+        {
+                printf("{ empty }\n");
+                return;
+        }
+        printf("{\n");
+        for (y = getBegin(); y <= getEnd(); y++)
+        {
+                id2 = findMappingId(y + 1);
+                printf("%2d %c", y, (id2 != id) ? '_' : ' ');
+                id = id2;
+                map(y).print2();
+                printf("\n");
+        }
+        printf("}\n");
+}