Changeset 733 for cpp


Ignore:
Timestamp:
02/15/18 00:43:07 (7 years ago)
Author:
Maciej Komosinski
Message:

Code formatting

Location:
cpp/frams/util
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • cpp/frams/util/list.h

    r286 r733  
    1616class SListStats
    1717{
    18   public:
    19 int objects, allocations, copied, totalmem, usedmem;
    20 SListStats():objects(0),allocations(0),copied(0),totalmem(0),usedmem() {}
    21 ~SListStats()
     18public:
     19        int objects, allocations, copied, totalmem, usedmem;
     20        SListStats():objects(0),allocations(0),copied(0),totalmem(0),usedmem() {}
     21        ~SListStats()
    2222        {
    23         printf("------------------------\n"
    24                " SListStats:\n"
    25                " objects     = %ld\n"
    26                " allocations = %ld\n"
    27                " copied      = %ld\n"
    28                " total mem   = %ld\n"
    29                " usage       = %ld %%\n"
    30                "------------------------\n",
    31                objects,allocations,copied,totalmem,(usedmem*100)/totalmem);
     23                printf("------------------------\n"
     24                        " SListStats:\n"
     25                        " objects     = %ld\n"
     26                        " allocations = %ld\n"
     27                        " copied      = %ld\n"
     28                        " total mem   = %ld\n"
     29                        " usage       = %ld %%\n"
     30                        "------------------------\n",
     31                        objects,allocations,copied,totalmem,(usedmem*100)/totalmem);
    3232        }
    3333};
    … …  
    3838{
    3939protected:
    40 int have,used,pos; // ile,zaj,poz
    41 T *mem;
    42 void resize(int x)
     40        int have, used, pos; // ile,zaj,poz
     41        T *mem;
     42        void resize(int x)
    4343        {
    44         if (mem || x)
     44                if (mem || x)
    4545                {
    46                 mem=(T*)realloc(mem,x*sizeof(T));
     46                        mem = (T*)realloc(mem, x*sizeof(T));
    4747#ifdef SLISTSTATS
    48                 SListStats::stats.allocations++;
    49                 SListStats::stats.copied+=sizeof(T)*min(x,have);
     48                        SListStats::stats.allocations++;
     49                        SListStats::stats.copied+=sizeof(T)*min(x,have);
    5050#endif 
    5151                }
    52         have=x;
     52                have = x;
    5353        }
    5454
    5555public:
    5656
    57 SListTempl(const SListTempl<T>& src):have(0),used(0),pos(0),mem(0)
    58         {(*this)=src;}
    59 SListTempl():have(0),used(0),pos(0),mem(0)
     57        SListTempl(const SListTempl<T>& src) :have(0), used(0), pos(0), mem(0)
     58        {
     59                (*this) = src;
     60        }
     61        SListTempl() :have(0), used(0), pos(0), mem(0)
    6062        {}
    61 ~SListTempl()
     63        ~SListTempl()
    6264        {
    6365#ifdef SLISTSTATS
    64         SListStats::stats.objects++;
    65         SListStats::stats.totalmem+=sizeof(T)*have;
    66         SListStats::stats.usedmem+=sizeof(T)*used;
     66                SListStats::stats.objects++;
     67                SListStats::stats.totalmem+=sizeof(T)*have;
     68                SListStats::stats.usedmem+=sizeof(T)*used;
    6769#endif
    68         hardclear();
     70                hardclear();
    6971        }
    7072
    71 void needSize(int s)
    72         { if (s>have) resize(s+3+s/8); }
    73 void operator+=(const T& e) ///< append one element
    74  {append(e);}
    75 void operator-=(const T& e) ///< remove one element
    76  {int i; if ((i=find(e))>=0) remove(i);}
    77 void remove(int i,int n=1) ///< remove n elements from position i
     73        void needSize(int s)
    7874        {
    79         if ((i>=size())||(i<0)) return;
    80         if (i>(size()-n)) n=size()-i;
    81         if (pos>=i) pos-=n;
    82         memmove(mem+i,mem+i+n,sizeof(T)*(used-n-i));
    83         used-=n;
     75                if (s > have) resize(s + 3 + s / 8);
    8476        }
    85 void operator-=(int i) {remove(i);} ///< remove element from position i
    86 T& operator()(int i) const ///< return element at position i
    87         {return mem[i];}
    88 bool hasMore() {return pos<size();}
    89 int operator==(const SListTempl<T>& l) const ///< compare list
    90  {
    91  if (size() != l.size()) return 0;
    92  for (int i=0;i<size();i++) if (l.mem[i] != mem[i]) return 0;
    93  return 1;
    94  }
    95 int find(const T& e) const ///< return position of element, or -1 if not found
    96         { for (int i=0;i<size();i++) if (mem[i]==e) return i;   return -1; }
    97 void append(const T& data) ///< add 1 element
    98         {needSize(size()+1); mem[used++]=data;}
    99 void append(const T* data,int n) ///< add n elements
     77        void operator+=(const T& e) ///< append one element
    10078        {
    101         needSize(size()+n);
    102         memcpy(mem+used,data,sizeof(T)*n);
    103         used+=n;
     79                append(e);
    10480        }
    105 void insert(int p,T* data,int n) ///< insert n elements at position p
     81        void operator-=(const T& e) ///< remove one element
    10682        {
    107         if (p>size()) p=size();
    108         needSize(size()+n);
    109         memmove(mem+p+n,mem+p,sizeof(T)*(size()-p));
    110         memcpy(mem+p,data,sizeof(T)*n);
    111         if (pos>p) pos+=n;
     83                int i; if ((i = find(e)) >= 0) remove(i);
    11284        }
    113 void insert(int p,const T& data) ///< insert 1 element at position p
     85        void remove(int i, int n = 1) ///< remove n elements from position i
    11486        {
    115         if (p>size()) p=size();
    116         needSize(size()+1);
    117         memmove(mem+p+1,mem+p,sizeof(T)*(size()-p));
    118         if (pos>p) pos++;
    119         mem[p]=data;
    120         used++;
     87                if ((i >= size()) || (i<0)) return;
     88                if (i>(size() - n)) n = size() - i;
     89                if (pos >= i) pos -= n;
     90                memmove(mem + i, mem + i + n, sizeof(T)*(used - n - i));
     91                used -= n;
    12192        }
    122 void set(int p,const T& d)
    123         { needSize(p+1); mem[p]=d; if (used<(p+1)) used=p+1;}
    124 void setSize(int s)
    125         { needSize(s); used=s;}
    126 T& get(int i) const {return operator()(i);}
    127 void clear() {used=0;} ///< remove all elements
    128 void hardclear() {resize(0); used=0;} ///< remove all elements and free mem
    129 int size() const {return used;} ///< list size
    130 void operator=(const SListTempl<T>&src) ///duplicate
    131  {
    132  setSize(src.size());
    133  memcpy(mem, src.mem, src.size()*sizeof(T));
    134  }
    135 void operator+=(const SListTempl<T>&src) ///< append src contents
    136  {
    137  needSize(size()+src.size());
    138  memcpy(mem+used, src.mem, src.size()*sizeof(T));
    139  used+=src.used;
    140  }
    141 void trim(int newsiz)
    142         {if (newsiz<used) used=newsiz;}
     93        void operator-=(int i) { remove(i); } ///< remove element from position i
     94        T& operator()(int i) const ///< return element at position i
     95        {
     96                return mem[i];
     97        }
     98        bool hasMore() { return pos < size(); }
     99        int operator==(const SListTempl<T>& l) const ///< compare list
     100        {
     101                if (size() != l.size()) return 0;
     102                for (int i = 0; i<size(); i++) if (l.mem[i] != mem[i]) return 0;
     103                return 1;
     104        }
     105        int find(const T& e) const ///< return position of element, or -1 if not found
     106        {
     107                for (int i = 0; i<size(); i++) if (mem[i] == e) return i;   return -1;
     108        }
     109        void append(const T& data) ///< add 1 element
     110        {
     111                needSize(size() + 1); mem[used++] = data;
     112        }
     113        void append(const T* data, int n) ///< add n elements
     114        {
     115                needSize(size() + n);
     116                memcpy(mem + used, data, sizeof(T)*n);
     117                used += n;
     118        }
     119        void insert(int p, T* data, int n) ///< insert n elements at position p
     120        {
     121                if (p>size()) p = size();
     122                needSize(size() + n);
     123                memmove(mem + p + n, mem + p, sizeof(T)*(size() - p));
     124                memcpy(mem + p, data, sizeof(T)*n);
     125                if (pos > p) pos += n;
     126        }
     127        void insert(int p, const T& data) ///< insert 1 element at position p
     128        {
     129                if (p > size()) p = size();
     130                needSize(size() + 1);
     131                memmove(mem + p + 1, mem + p, sizeof(T)*(size() - p));
     132                if (pos > p) pos++;
     133                mem[p] = data;
     134                used++;
     135        }
     136        void set(int p, const T& d)
     137        {
     138                needSize(p + 1); mem[p] = d; if (used < (p + 1)) used = p + 1;
     139        }
     140        void setSize(int s)
     141        {
     142                needSize(s); used = s;
     143        }
     144        T& get(int i) const { return operator()(i); }
     145        void clear() { used = 0; } ///< remove all elements
     146        void hardclear() { resize(0); used = 0; } ///< remove all elements and free mem
     147        int size() const { return used; } ///< list size
     148        void operator=(const SListTempl<T>&src) ///duplicate
     149        {
     150                setSize(src.size());
     151                memcpy(mem, src.mem, src.size()*sizeof(T));
     152        }
     153        void operator+=(const SListTempl<T>&src) ///< append src contents
     154        {
     155                needSize(size() + src.size());
     156                memcpy(mem + used, src.mem, src.size()*sizeof(T));
     157                used += src.used;
     158        }
     159        void trim(int newsiz)
     160        {
     161                if (newsiz < used) used = newsiz;
     162        }
    143163};
    144164
    … …  
    148168// usage example: FOREACH(char*,t,thelist) printf("t=%s\n",t);
    149169
    150 template<class T> class PtrListTempl: public SListTempl<T>
     170template<class T> class PtrListTempl : public SListTempl < T >
    151171{
    152    public:
    153 T operator()(int i) const ///< return element at position i
    154      {if (i>=this->size()) return 0; else return this->mem[i];}
     172public:
     173        T operator()(int i) const ///< return element at position i
     174        {
     175                if (i >= this->size()) return 0; else return this->mem[i];
     176        }
    155177
    156 T get(int i) const {return operator()(i);}
    157 T& getref(int i) const {return SListTempl<T>::get(i);}
     178        T get(int i) const { return operator()(i); }
     179        T& getref(int i) const { return SListTempl<T>::get(i); }
    158180};
    159181
    160182
    161 typedef PtrListTempl<void*> SList;
     183        typedef PtrListTempl<void*> SList;
    162184
    163185#endif

  • cpp/frams/util/multimap.cpp

    r286 r733  
    88int MultiMap::getBegin() const
    99{
    10 if (isEmpty()) return 0;
    11 return getBegin(0);
     10        if (isEmpty()) return 0;
     11        return getBegin(0);
    1212}
    1313
    1414int MultiMap::getEnd() const
    1515{
    16 if (isEmpty()) return -1;
    17 return getBegin(mappingCount()-1)-1;
     16        if (isEmpty()) return -1;
     17        return getBegin(mappingCount() - 1) - 1;
    1818}
    1919
    2020int MultiMap::findData(int x) const
    2121{
    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)
     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)
    3030                {
    31                 if ((c==n)||(getBegin(c+1)>x)) return c;
    32                 a=c;
    33                 }
     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        }
    34201        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)
    35226                {
    36                 b=c-1;
    37                 }
    38         }
    39 }
    40 
    41 int 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 
    76 int 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 
    191 void 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 
    211 const 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 
    220 MultiRange 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;
     227                SingleMapping *sm = getMapping(m);
     228                if (sm->begin > end) break;
     229                mr.add(sm->to);
     230                }
     231        return mr;
    232232}
    233233
    234234MultiRange MultiMap::map(const MultiRange& ranges) const
    235235{
    236 MultiRange mr;
    237 for(int i=0;i<ranges.rangeCount();i++)
    238         mr.add(map(ranges.getRange(i)));
    239 return mr;
     236        MultiRange mr;
     237        for (int i = 0; i < ranges.rangeCount(); i++)
     238                mr.add(map(ranges.getRange(i)));
     239        return mr;
    240240}
    241241
    242242IRange MultiMap::getRange(int i) const
    243243{
    244 if ((i<0)||(i>(data.size()-1))) return IRange();
    245 return IRange(getBegin(i),getBegin(i+1)-1);
     244        if ((i<0) || (i>(data.size() - 1))) return IRange();
     245        return IRange(getBegin(i), getBegin(i + 1) - 1);
    246246}
    247247
    248248void MultiMap::operator=(const MultiMap& mm)
    249249{
    250 clear();
    251 for(int i=0;i<mm.mappingCount();i++)
    252         addData(i,new SingleMapping(*mm.getMapping(i)));
    253 }
    254 
    255 void 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 
    264 void MultiMap::add(const MultiRange& from,const MultiRange& to)
    265 {
    266 for(int i=0;i<from.rangeCount();i++)
    267         add(from.getRange(i),to);
     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);
    268268}
    269269
    270270void MultiMap::addReversed(const MultiMap& m)
    271271{
    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);
     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);
    278278        }
    279279}
    280280
    281281MultiMap::~MultiMap()
    282 { clear();}
     282{
     283        clear();
     284}
    283285
    284286void MultiMap::clear()
    285287{
    286 for(int i=0;i<data.size();i++)
    287         delete getData(i);
    288 data.clear();
     288        for (int i = 0; i < data.size(); i++)
     289                delete getData(i);
     290        data.clear();
    289291}
    290292
    … …  
    293295void MultiMap::print() const
    294296{
    295 printf("{ ");
    296 for (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         }
    308 printf("}\n");
     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");
    309311}
    310312
    311313void MultiMap::print2() const
    312314{
    313 int y;
    314 int id=0,id2;
    315 if (isEmpty())
    316         {
    317         printf("{ empty }\n");
    318         return;
    319         }
    320 printf("{\n");
    321 for (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         }
    329 printf("}\n");
    330 }
     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}

  • cpp/frams/util/multimap.h

    r304 r733  
    1010class SingleMapping
    1111{
    12   public:
    13 SingleMapping(int b,const MultiRange& t):begin(b),to(t) {}
    14 SingleMapping(int b):begin(b) {}
    15 SingleMapping(const SingleMapping& sm):begin(sm.begin),to(sm.to) {}
    16 int begin;
    17 MultiRange to;
     12public:
     13        SingleMapping(int b, const MultiRange& t) :begin(b), to(t) {}
     14        SingleMapping(int b) :begin(b) {}
     15        SingleMapping(const SingleMapping& sm) :begin(sm.begin), to(sm.to) {}
     16        int begin;
     17        MultiRange to;
    1818};
    1919
    2020/** MultiMap - used for conversion mapping.
    21     Read about how mappings work: http://www.framsticks.com/files/common/GeneticMappingsInArtificialGenomes.pdf
    22     see @ref convmap
    23 */
     21        Read about how mappings work: http://www.framsticks.com/files/common/GeneticMappingsInArtificialGenomes.pdf
     22        see @ref convmap
     23        */
    2424class MultiMap
    2525{
    26 /** list of (SingleMapping*) */
    27 SList data;
     26        /** list of (SingleMapping*) */
     27        SList data;
    2828
    29 SingleMapping* getData(int i) const {return (SingleMapping*)data(i);}
    30 void addData(int i,SingleMapping* mapping) {data.insert(i,(void*)mapping);}
    31 void removeData(int i) {data.remove(i);}
    32 int findData(int x) const;
    33 int getBegin(int i) const {return getData(i)->begin;}
     29        SingleMapping* getData(int i) const { return (SingleMapping*)data(i); }
     30        void addData(int i, SingleMapping* mapping) { data.insert(i, (void*)mapping); }
     31        void removeData(int i) { data.remove(i); }
     32        int findData(int x) const;
     33        int getBegin(int i) const { return getData(i)->begin; }
    3434
    35 // addRangeXXX return the shift for range numbers > r
    36 int addRange(int &r,const MultiRange& mr);
    37 // value of 'r' is adjusted according to its range number change
    38 int addRangeBeginEnd(int &r,int begin,int end,const MultiRange& mr);
     35        // addRangeXXX return the shift for range numbers > r
     36        int addRange(int &r, const MultiRange& mr);
     37        // value of 'r' is adjusted according to its range number change
     38        int addRangeBeginEnd(int &r, int begin, int end, const MultiRange& mr);
    3939
    40   public:
    41 MultiMap() {}
    42 MultiMap(const MultiMap& mm) {operator=(mm);}
    43 ~MultiMap();
    44 void operator=(const MultiMap& mm);
     40public:
     41        MultiMap() {}
     42        MultiMap(const MultiMap& mm) { operator=(mm); }
     43        ~MultiMap();
     44        void operator=(const MultiMap& mm);
    4545
    46 void clear();
    47 int isEmpty() const {return data.size()==0;}
    48 int mappingCount() const {return data.size();}
    49 SingleMapping* getMapping(int i) const {return (SingleMapping*)getData(i);}
    50 int findMappingId(int x) const {return findData(x);}
    51 int rangeCount() const {return isEmpty()?0:data.size()-1;}
    52 IRange getRange(int i) const;
     46        void clear();
     47        int isEmpty() const { return data.size() == 0; }
     48        int mappingCount() const { return data.size(); }
     49        SingleMapping* getMapping(int i) const { return (SingleMapping*)getData(i); }
     50        int findMappingId(int x) const { return findData(x); }
     51        int rangeCount() const { return isEmpty() ? 0 : data.size() - 1; }
     52        IRange getRange(int i) const;
    5353
    54 int getBegin() const;
    55 int getEnd() const;
     54        int getBegin() const;
     55        int getEnd() const;
    5656
    57 void add(const IRange& from,const IRange& to) {add(from.begin, from.end, MultiRange(to));}
    58 void add(const IRange& from,const MultiRange& to) {add(from.begin, from.end, to);}
    59 void add(int from1,int from2,int to1,int to2) {add(from1,from2,MultiRange(to1,to2));}
    60 void add(int from1,int from2,const MultiRange& to);
    61 void add(const MultiRange& from,const MultiRange& to);
    62 void add(const MultiMap& mm);
    63 void addCombined(const MultiMap& m1,const MultiMap& m2);
    64 void addReversed(const MultiMap& mm);
     57        void add(const IRange& from, const IRange& to) { add(from.begin, from.end, MultiRange(to)); }
     58        void add(const IRange& from, const MultiRange& to) { add(from.begin, from.end, to); }
     59        void add(int from1, int from2, int to1, int to2) { add(from1, from2, MultiRange(to1, to2)); }
     60        void add(int from1, int from2, const MultiRange& to);
     61        void add(const MultiRange& from, const MultiRange& to);
     62        void add(const MultiMap& mm);
     63        void addCombined(const MultiMap& m1, const MultiMap& m2);
     64        void addReversed(const MultiMap& mm);
    6565
    66 const MultiRange& map(int x) const;
    67 MultiRange map(int begin,int end) const;
    68 MultiRange map(const IRange& range) const {return map(range.begin, range.end);}
    69 MultiRange map(const MultiRange& ranges) const;
     66        const MultiRange& map(int x) const;
     67        MultiRange map(int begin, int end) const;
     68        MultiRange map(const IRange& range) const { return map(range.begin, range.end); }
     69        MultiRange map(const MultiRange& ranges) const;
    7070
    71 void print() const;
    72 void print2() const;
     71        void print() const;
     72        void print2() const;
    7373};
    7474

  • cpp/frams/util/multirange.cpp

    r286 r733  
    1010int IRange::operator==(const IRange& r)
    1111{
    12 if (isEmpty()&&r.isEmpty()) return 1;
    13 return (begin==r.begin)&&(end==r.end);
     12        if (isEmpty() && r.isEmpty()) return 1;
     13        return (begin == r.begin) && (end == r.end);
    1414}
    1515
    1616void IRange::intersect(const IRange& r)
    1717{
    18 if (r.begin>begin) begin=r.begin;
    19 if (r.end<end) end=r.end;
     18        if (r.begin > begin) begin = r.begin;
     19        if (r.end < end) end = r.end;
    2020}
    2121void IRange::add(const IRange& r)
    2222{
    23 if (r.begin<begin) begin=r.begin;
    24 if (r.end>end) end=r.end;
     23        if (r.begin < begin) begin = r.begin;
     24        if (r.end > end) end = r.end;
    2525}
    2626
    2727void IRange::print() const
    2828{
    29 if (begin==end) printf("[%d]",begin);
    30 else printf("[%d-%d]",begin,end);
     29        if (begin == end) printf("[%d]", begin);
     30        else printf("[%d-%d]", begin, end);
    3131}
    3232
    … …  
    3535void MultiRange::print() const
    3636{
    37 printf("[");
    38 for (int i=0;i<data.size();i+=2)
    39         {
    40         int b=getData(i);
    41         int e=getData(i+1);
    42         if (i) printf(",");
    43         if (b==e) printf("%d",b);
    44         else printf("%d-%d",b,e);
    45         }
    46 printf("]");
     37        printf("[");
     38        for (int i = 0; i < data.size(); i += 2)
     39        {
     40                int b = getData(i);
     41                int e = getData(i + 1);
     42                if (i) printf(",");
     43                if (b == e) printf("%d", b);
     44                else printf("%d-%d", b, e);
     45        }
     46        printf("]");
    4747}
    4848
    4949void MultiRange::print2() const
    5050{
    51 const IRange& r=singleRange();
    52 for(int i=0;i<=r.end;i++)
    53         printf(contains(i)?"X":".");
     51        const IRange& r = singleRange();
     52        for (int i = 0; i <= r.end; i++)
     53                printf(contains(i) ? "X" : ".");
    5454}
    5555
    5656void MultiRange::shift(int delta)
    5757{
    58 for(int i=0;i<data.size();i++)
    59         data.get(i)+=delta;
     58        for (int i = 0; i<data.size(); i++)
     59                data.get(i) += delta;
    6060}
    6161
    6262int MultiRange::findRange(int x) const
    6363{
    64 if (isEmpty()) return -1;
    65 if (getData(0)>x) return -1;
    66 int a,b,c;
    67 int n=rangeCount()-1;
    68 a=0; b=n; // find c = last range with begin<=x
    69 while(1){
    70         c=(a+b+1)/2;
    71         if (getBegin(c)<=x)
    72                 {
    73                 if ((c==n)||(getBegin(c+1)>x)) return c;
    74                 a=c;
    75                 }
    76         else
    77                 {
    78                 b=c-1;
    79                 }
    80         }
    81 }
    82 
    83 void MultiRange::addRange(int i,int b,int e)
    84 {
    85 data.insert(2*i,b);
    86 data.insert(2*i+1,e);
    87 }
    88 
    89 void MultiRange::removeRanges(int r1,int r2)
    90 {
    91 //data.remove(2*r1,(r2-r1)*2+2);
    92 for (;r2>=r1;r2--)
    93         removeRange(r2);
     64        if (isEmpty()) return -1;
     65        if (getData(0)>x) return -1;
     66        int a, b, c;
     67        int n = rangeCount() - 1;
     68        a = 0; b = n; // find c = last range with begin<=x
     69        while (1){
     70                c = (a + b + 1) / 2;
     71                if (getBegin(c) <= x)
     72                {
     73                        if ((c == n) || (getBegin(c + 1) > x)) return c;
     74                        a = c;
     75                }
     76                else
     77                {
     78                        b = c - 1;
     79                }
     80        }
     81}
     82
     83void MultiRange::addRange(int i, int b, int e)
     84{
     85        data.insert(2 * i, b);
     86        data.insert(2 * i + 1, e);
     87}
     88
     89void MultiRange::removeRanges(int r1, int r2)
     90{
     91        //data.remove(2*r1,(r2-r1)*2+2);
     92        for (; r2 >= r1; r2--)
     93                removeRange(r2);
    9494}
    9595
    9696void MultiRange::removeRange(int i)
    9797{
    98 data.remove(2*i,2);
     98        data.remove(2 * i, 2);
    9999}
    100100
    101101void MultiRange::clear()
    102 {data.clear();}
     102{
     103        data.clear();
     104}
    103105
    104106int MultiRange::isEmpty() const
    105107{
    106 return rangeCount()==0;
     108        return rangeCount() == 0;
    107109}
    108110
    109111IRange MultiRange::singleRange() const
    110112{
    111 if (isEmpty()) return IRange();
    112 int b=getData(0);
    113 int e=getData(data.size()-1);
    114 return IRange(b,e);
     113        if (isEmpty()) return IRange();
     114        int b = getData(0);
     115        int e = getData(data.size() - 1);
     116        return IRange(b, e);
    115117}
    116118
    117119int MultiRange::rangeCount() const
    118120{
    119 return data.size()/2;
     121        return data.size() / 2;
    120122}
    121123
    122124IRange MultiRange::getRange(int i) const
    123125{
    124 if ((i<0)||(i>=rangeCount())) return IRange();
    125 return IRange(getData(2*i),getData(2*i+1));
     126        if ((i < 0) || (i >= rangeCount())) return IRange();
     127        return IRange(getData(2 * i), getData(2 * i + 1));
    126128}
    127129
    128130void MultiRange::remove(int begin, int end)
    129131{
    130 if (end<begin) return; // NOP
    131 int count=rangeCount();
    132 if (!count) return;
    133 int r1=findRange(begin);
    134 int r2=findRange(end);
    135 if (r2<0) return; // NOP
    136 if (r1==r2)
    137         {
    138         int e=getEnd(r1);
    139         int b=getBegin(r1);
    140         if (begin<=e)
    141                 {
    142                 if (end>=e)
     132        if (end < begin) return; // NOP
     133        int count = rangeCount();
     134        if (!count) return;
     135        int r1 = findRange(begin);
     136        int r2 = findRange(end);
     137        if (r2<0) return; // NOP
     138        if (r1 == r2)
     139        {
     140                int e = getEnd(r1);
     141                int b = getBegin(r1);
     142                if (begin <= e)
     143                {
     144                        if (end >= e)
    143145                        {
    144                         if (begin>b)
    145                                 setEnd(r1,begin-1);
     146                                if (begin>b)
     147                                        setEnd(r1, begin - 1);
     148                                else
     149                                        removeRange(r1);
     150                        }
    146151                        else
    147                                 removeRange(r1);
    148                         }
    149                 else
    150152                        {
    151                         if (begin>b)
     153                                if (begin > b)
    152154                                { //split
    153                                 addRange(r1+1,end+1,e);
    154                                 setEnd(r1,begin-1);
     155                                        addRange(r1 + 1, end + 1, e);
     156                                        setEnd(r1, begin - 1);
    155157                                }
    156                         else
     158                                else
    157159                                {
    158                                 setBegin(r1,end+1);
     160                                        setBegin(r1, end + 1);
    159161                                }
    160162                        }
    161163                }
    162164        }
    163 else
    164         {
    165         if (r1>=0)
    166                 {
    167                 int e1=getEnd(r1);
    168                 int b1=getBegin(r1);
    169                 if (begin<=e1)
     165        else
     166        {
     167                if (r1 >= 0)
     168                {
     169                        int e1 = getEnd(r1);
     170                        int b1 = getBegin(r1);
     171                        if (begin <= e1)
    170172                        {
    171                         if (begin==b1)
     173                                if (begin == b1)
    172174                                {
    173                                 removeRange(r1);
    174                                 r2--;
    175                                 r1--;
     175                                        removeRange(r1);
     176                                        r2--;
     177                                        r1--;
    176178                                }
    177                         else
     179                                else
    178180                                {
    179                                 setEnd(r1,begin-1);
     181                                        setEnd(r1, begin - 1);
    180182                                }
    181183                        }
    182184                }
    183         int e2=getEnd(r2);
    184         if (end<e2)
    185                 {
    186                 setBegin(r2,end+1);
    187                 removeRanges(r1+1,r2-1);
    188                 }
    189         else
    190                 {
    191                 removeRanges(r1+1,r2);
     185                int e2 = getEnd(r2);
     186                if (end < e2)
     187                {
     188                        setBegin(r2, end + 1);
     189                        removeRanges(r1 + 1, r2 - 1);
     190                }
     191                else
     192                {
     193                        removeRanges(r1 + 1, r2);
    192194                }
    193195        }
    … …  
    196198void MultiRange::add(int begin, int end)
    197199{
    198 if (end<begin) return; // NOP
    199 int count=rangeCount();
    200 int last=count-1;
    201 int r1=findRange(begin);
    202 int r2=findRange(end);
    203 if (r2<0) // special case: before first range
    204         {
    205         if (count&&(getData(0)==(end+1)))
    206                 setData(0,begin);
    207         else
    208                 addRange(0,begin,end);
    209         return;
    210         }
    211 if (r1<0) // special case: begin is before first range
    212         {
    213         setData(0,begin);
    214         r1=0;
    215         }
    216 // now r1>=0 and r2>=0
    217 int joinbegin=(begin<=(getEnd(r1)+1));
    218 int joinend=(r2<last)&&(end>=(getBegin(r2+1)-1));
    219 const int SAME=1;
    220 const int JOINBEGIN=2;
    221 const int JOINEND=4;
    222 int action=((r1==r2)?SAME:0)+(joinbegin?JOINBEGIN:0)+(joinend?JOINEND:0);
    223 switch(action)
    224         {
    225         case SAME+JOINBEGIN+JOINEND: // remove 1 range
    226                 setEnd(r1,getEnd(r1+1));
    227                 removeRange(r1+1);
    228                 break;
    229         case SAME+JOINBEGIN: // extend 1 range
    230                 setEnd(r1,max(getEnd(r2),end));
    231                 break;
    232         case SAME+JOINEND: // extend 1 range
    233                 setBegin(r1+1,begin);
     200        if (end < begin) return; // NOP
     201        int count = rangeCount();
     202        int last = count - 1;
     203        int r1 = findRange(begin);
     204        int r2 = findRange(end);
     205        if (r2 < 0) // special case: before first range
     206        {
     207                if (count && (getData(0) == (end + 1)))
     208                        setData(0, begin);
     209                else
     210                        addRange(0, begin, end);
     211                return;
     212        }
     213        if (r1 < 0) // special case: begin is before first range
     214        {
     215                setData(0, begin);
     216                r1 = 0;
     217        }
     218        // now r1>=0 and r2>=0
     219        int joinbegin = (begin <= (getEnd(r1) + 1));
     220        int joinend = (r2 < last) && (end >= (getBegin(r2 + 1) - 1));
     221        const int SAME = 1;
     222        const int JOINBEGIN = 2;
     223        const int JOINEND = 4;
     224        int action = ((r1 == r2) ? SAME : 0) + (joinbegin ? JOINBEGIN : 0) + (joinend ? JOINEND : 0);
     225        switch (action)
     226        {
     227        case SAME + JOINBEGIN + JOINEND: // remove 1 range
     228                setEnd(r1, getEnd(r1 + 1));
     229                removeRange(r1 + 1);
     230                break;
     231        case SAME + JOINBEGIN: // extend 1 range
     232                setEnd(r1, max(getEnd(r2), end));
     233                break;
     234        case SAME + JOINEND: // extend 1 range
     235                setBegin(r1 + 1, begin);
    234236                break;
    235237        case SAME: // add 1 range
    236                 addRange(r1+1,begin,end);
    237                 break;
    238 
    239         case JOINBEGIN+JOINEND: // extend r2+1
    240                 setBegin(r2+1,getBegin(r1));
    241                 removeRanges(r1,r2);
     238                addRange(r1 + 1, begin, end);
     239                break;
     240
     241        case JOINBEGIN + JOINEND: // extend r2+1
     242                setBegin(r2 + 1, getBegin(r1));
     243                removeRanges(r1, r2);
    242244                break;
    243245        case JOINBEGIN: // extend r1
    244                 setEnd(r1,max(end,getEnd(r2)));
    245                 removeRanges(r1+1,r2);
     246                setEnd(r1, max(end, getEnd(r2)));
     247                removeRanges(r1 + 1, r2);
    246248                break;
    247249        case JOINEND: // extend r2+1
    248                 setBegin(r2+1,begin);
    249                 removeRanges(r1+1,r2);
     250                setBegin(r2 + 1, begin);
     251                removeRanges(r1 + 1, r2);
    250252                break;
    251253        case 0: // extend r2
    252                 setBegin(r2,begin);
    253                 setEnd(r2,max(end,getEnd(r2)));
    254                 removeRanges(r1+1,r2-1);
     254                setBegin(r2, begin);
     255                setEnd(r2, max(end, getEnd(r2)));
     256                removeRanges(r1 + 1, r2 - 1);
    255257                break;
    256258        }
    … …  
    259261void MultiRange::remove(const MultiRange &mr)
    260262{
    261 for(int i=0;i<mr.rangeCount();i++)
    262         {
    263         IRange r=mr.getRange(i);
    264         remove(r);
     263        for (int i = 0; i < mr.rangeCount(); i++)
     264        {
     265                IRange r = mr.getRange(i);
     266                remove(r);
    265267        }
    266268}
    … …  
    268270void MultiRange::add(const MultiRange &mr)
    269271{
    270 for(int i=0;i<mr.rangeCount();i++)
    271         {
    272         IRange r=mr.getRange(i);
    273         add(r);
     272        for (int i = 0; i < mr.rangeCount(); i++)
     273        {
     274                IRange r = mr.getRange(i);
     275                add(r);
    274276        }
    275277}
    … …  
    277279void MultiRange::intersect(const MultiRange &mr)
    278280{
    279 // = this - (1-mr)
    280 MultiRange full(singleRange());
    281 full.remove(mr);
    282 remove(full);
     281        // = this - (1-mr)
     282        MultiRange full(singleRange());
     283        full.remove(mr);
     284        remove(full);
    283285}
    284286
    285287int MultiRange::contains(const MultiRange &mr) const
    286288{
    287 for(int i=0;i<mr.rangeCount();i++)
    288         {
    289         IRange r=mr.getRange(i);
    290         if (!contains(r)) return 0;
    291         }
    292 return 1;
     289        for (int i = 0; i < mr.rangeCount(); i++)
     290        {
     291                IRange r = mr.getRange(i);
     292                if (!contains(r)) return 0;
     293        }
     294        return 1;
    293295}
    294296
    295297int MultiRange::contains(int x) const
    296298{
    297 int r=findRange(x);
    298 if (r<0) return 0;
    299 return getEnd(r)>=x;
     299        int r = findRange(x);
     300        if (r < 0) return 0;
     301        return getEnd(r) >= x;
    300302}
    301303
    302304int MultiRange::contains(const IRange& r) const
    303305{
    304 if (r.isEmpty()) return 0;
    305 int r1=findRange(r.begin);
    306 if (r1<0) return 0;
    307 return getRange(r1).contains(r);
     306        if (r.isEmpty()) return 0;
     307        int r1 = findRange(r.begin);
     308        if (r1 < 0) return 0;
     309        return getRange(r1).contains(r);
    308310}
    309311
    310312void MultiRange::intersect(int begin, int end)
    311313{
    312 if (isEmpty()) return;
    313 if (end<begin) {clear(); return;}
    314 IRange sr=singleRange();
    315 remove(sr.begin, begin-1);
    316 remove(end+1, sr.end);
    317 }
     314        if (isEmpty()) return;
     315        if (end < begin) { clear(); return; }
     316        IRange sr = singleRange();
     317        remove(sr.begin, begin - 1);
     318        remove(end + 1, sr.end);
     319}

  • cpp/frams/util/multirange.h

    r286 r733  
    1212   - (a,a) contains single integer: a
    1313   - (a,b) contains [b-a+1] integers
    14  */
     14   */
    1515class IRange
    1616{
    17   public:
    18 int begin,end;
    19 IRange():begin(0),end(0) {}
    20 IRange(int b,int e):begin(b),end(e) {}
    21 IRange(const IRange& r):begin(r.begin),end(r.end) {}
    22 int size() const {return end-begin+1;}
    23 int isEmpty() const {return end<begin;}
    24 void makeEmpty() {end=begin;}
    25 void set(int b,int e) {begin=b; end=e;}
    26 void intersect(const IRange& r);
    27 void add(const IRange& r);
    28 /** all empty ranges are equal */
    29 int operator==(const IRange& r);
    30 void operator=(const IRange& r) {begin=r.begin; end=r.end;}
    31 int contains(int x) {return (x>=begin)&&(x<=end);}
    32 int contains(const IRange& r) {return !r.isEmpty()&&contains(r.begin)&&contains(r.end);}
    33 void print() const;
     17public:
     18        int begin, end;
     19        IRange() :begin(0), end(0) {}
     20        IRange(int b, int e) :begin(b), end(e) {}
     21        IRange(const IRange& r) :begin(r.begin), end(r.end) {}
     22        int size() const { return end - begin + 1; }
     23        int isEmpty() const { return end < begin; }
     24        void makeEmpty() { end = begin; }
     25        void set(int b, int e) { begin = b; end = e; }
     26        void intersect(const IRange& r);
     27        void add(const IRange& r);
     28        /** all empty ranges are equal */
     29        int operator==(const IRange& r);
     30        void operator=(const IRange& r) { begin = r.begin; end = r.end; }
     31        int contains(int x) { return (x >= begin) && (x <= end); }
     32        int contains(const IRange& r) { return !r.isEmpty() && contains(r.begin) && contains(r.end); }
     33        void print() const;
    3434};
    3535
    … …  
    3737class MultiRange
    3838{
    39 /** subsequent ranges in array, stored as: {begin1,end1,begin2,end2,...}
    40     there are data.size()/2 ranges.
    41     all ranges are sorted by 'begin' value.
    42     ranges cannot intersect.
    43  */
    44 SListTempl<int> data;
    45 int getData(int i) const {return (int)data(i);}
    46 void setData(int i,int x) {data.set(i,x);}
    47 int getBegin(int i) const {return getData(2*i);}
    48 int getEnd(int i) const {return getData(2*i+1);}
    49 void setBegin(int i,int x) {setData(2*i,x);}
    50 void setEnd(int i,int x) {setData(2*i+1,x);}
    51 /** find the last range with begin<=x
    52  @return -1 if not found */
    53 int findRange(int x) const;
    54 void addRange(int i,int b,int e);
    55 void removeRange(int i);
    56 void removeRanges(int r1,int r2);
     39        /** subsequent ranges in array, stored as: {begin1,end1,begin2,end2,...}
     40                there are data.size()/2 ranges.
     41                all ranges are sorted by 'begin' value.
     42                ranges cannot intersect.
     43                */
     44        SListTempl<int> data;
     45        int getData(int i) const { return (int)data(i); }
     46        void setData(int i, int x) { data.set(i, x); }
     47        int getBegin(int i) const { return getData(2 * i); }
     48        int getEnd(int i) const { return getData(2 * i + 1); }
     49        void setBegin(int i, int x) { setData(2 * i, x); }
     50        void setEnd(int i, int x) { setData(2 * i + 1, x); }
     51        /** find the last range with begin<=x
     52        @return -1 if not found */
     53        int findRange(int x) const;
     54        void addRange(int i, int b, int e);
     55        void removeRange(int i);
     56        void removeRanges(int r1, int r2);
    5757
    58   public:
    59 MultiRange() {}
    60 MultiRange(const MultiRange &mr) {data=mr.data;}
    61 void operator=(const MultiRange &mr) {data=mr.data;}
    62 MultiRange(const IRange &r) {add(r);}
    63 MultiRange(int begin,int end) {add(begin,end);}
    64 MultiRange(int x) {add(x);}
     58public:
     59        MultiRange() {}
     60        MultiRange(const MultiRange &mr) { data = mr.data; }
     61        void operator=(const MultiRange &mr) { data = mr.data; }
     62        MultiRange(const IRange &r) { add(r); }
     63        MultiRange(int begin, int end) { add(begin, end); }
     64        MultiRange(int x) { add(x); }
    6565
    66 int operator==(const MultiRange &mr) const {return data==mr.data;}
     66        int operator==(const MultiRange &mr) const { return data == mr.data; }
    6767
    68 void clear();
    69 int isEmpty() const;
     68        void clear();
     69        int isEmpty() const;
    7070
    71 IRange singleRange() const;
    72 int rangeCount() const;
    73 IRange getRange(int i) const;
     71        IRange singleRange() const;
     72        int rangeCount() const;
     73        IRange getRange(int i) const;
    7474
    75 void add(int x) {add(x,x);}
    76 void add(const IRange& r) {add(r.begin,r.end);}
    77 void add(int begin, int end);
    78 void add(const MultiRange &mr);
     75        void add(int x) { add(x, x); }
     76        void add(const IRange& r) { add(r.begin, r.end); }
     77        void add(int begin, int end);
     78        void add(const MultiRange &mr);
    7979
    80 void remove(int x) {remove(x,x);}
    81 void remove(const IRange& r) {remove(r.begin,r.end);}
    82 void remove(int begin, int end);
    83 void remove(const MultiRange &mr);
     80        void remove(int x) { remove(x, x); }
     81        void remove(const IRange& r) { remove(r.begin, r.end); }
     82        void remove(int begin, int end);
     83        void remove(const MultiRange &mr);
    8484
    85 int contains(int x) const;
    86 int contains(const IRange& r) const;
    87 int contains(const MultiRange &mr) const;
     85        int contains(int x) const;
     86        int contains(const IRange& r) const;
     87        int contains(const MultiRange &mr) const;
    8888
    89 void intersect(const IRange& r) {intersect(r.begin,r.end);}
    90 void intersect(int begin, int end);
    91 void intersect(const MultiRange &mr);
     89        void intersect(const IRange& r) { intersect(r.begin, r.end); }
     90        void intersect(int begin, int end);
     91        void intersect(const MultiRange &mr);
    9292
    93 void shift(int delta);
     93        void shift(int delta);
    9494
    95 void print() const;
    96 void print2() const;
     95        void print() const;
     96        void print2() const;
    9797};
    9898
    9999#endif
    100 
    101 
    102 
    103 
    104 
Note: See TracChangeset for help on using the changeset viewer.