Ignore:
Timestamp:
Jun 20, 2015, 3:52:41 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in

Location:
icGREP/icgrep-devel/icgrep/UCD
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r4189 r4611  
    2323#include <iostream>
    2424
    25 class Uset_Iterator {
    26 public:
    27     Uset_Iterator(UnicodeSet s) : uSet(s), run_no(0), offset(0), quad_no(0) {};
    28     bool at_end();
    29     RunStructure current_run();
    30     bitquad_t get_quad();
    31     void advance(int n);
    32 private:
    33     UnicodeSet uSet;
    34     int run_no;
    35     int offset;
    36     int quad_no;
    37 };
    38 
    3925bool Uset_Iterator::at_end() {
    40   return run_no == uSet.runs.size();
     26    return run_no == uSet.runs.size();
    4127}
    4228
    4329RunStructure Uset_Iterator::current_run() {
    44   RunStructure this_run = uSet.runs[run_no];
    45   return RunStructure(this_run.run_type, this_run.run_length - offset);
     30    RunStructure this_run = uSet.runs[run_no];
     31    return RunStructure(this_run.run_type, this_run.run_length - offset);
    4632}
    4733
    4834bitquad_t Uset_Iterator::get_quad() {
    49   RunStructure this_run = uSet.runs[run_no];
    50   if (this_run.run_type == Empty) return 0;
    51   else if (this_run.run_type == Full) return FullQuadMask;
    52   else return uSet.quads[quad_no];
     35    RunStructure this_run = uSet.runs[run_no];
     36    if (this_run.run_type == Empty) return 0;
     37    else if (this_run.run_type == Full) return FullQuadMask;
     38    else return uSet.quads[quad_no];
    5339}
    5440
    5541void Uset_Iterator::advance(int n) {
    56   while (n > 0) {
    57     RunStructure this_run = uSet.runs[run_no];
    58     int remain = this_run.run_length - offset;
    59     if (remain > n) {
    60       offset += n;
    61       if (this_run.run_type == Mixed) quad_no += n;
    62       n = 0;
    63     }
    64     else if (remain == n) {
    65       run_no += 1;
    66       offset = 0;
    67       if (this_run.run_type == Mixed) quad_no += n;
    68       n = 0;
     42    while (n > 0) {
     43        RunStructure this_run = uSet.runs[run_no];
     44        int remain = this_run.run_length - offset;
     45        if (remain > n) {
     46            offset += n;
     47            if (this_run.run_type == Mixed) quad_no += n;
     48            n = 0;
     49        }
     50        else if (remain == n) {
     51            run_no += 1;
     52            offset = 0;
     53            if (this_run.run_type == Mixed) quad_no += n;
     54            n = 0;
     55        }
     56        else {
     57            run_no += 1;
     58            offset = 0;
     59            if (this_run.run_type == Mixed) quad_no += remain;
     60            n -= remain;
     61        }
     62    }
     63}
     64
     65void UnicodeSet::append_run(run_type_t run_type, int run_length) {
     66    if (run_length == 0) {
     67        return;
     68    }
     69    else if (runs.size() == 0) {
     70        runs.emplace_back(run_type, run_length);
    6971    }
    7072    else {
    71       run_no += 1;
    72       offset = 0;
    73       if (this_run.run_type == Mixed) quad_no += remain;
    74       n -= remain;
    75     }
    76   }
    77 }
    78 
    79 void UnicodeSet::append_run(run_type_t run_type, int run_length) {
    80     if (run_length == 0) return;
    81     if (runs.size() == 0) runs.push_back(RunStructure(run_type, run_length));
    82     else {
    83       RunStructure last_run = runs[runs.size()-1];
    84       if (last_run.run_type == run_type) runs[runs.size()-1].run_length += run_length;
    85       else runs.push_back(RunStructure(run_type, run_length));
     73        RunStructure last_run = runs[runs.size()-1];
     74        if (last_run.run_type == run_type) {
     75            runs[runs.size()-1].run_length += run_length;
     76        }
     77        else {
     78            runs.emplace_back(run_type, run_length);
     79        }
    8680    }
    8781    quad_count += run_length;
     
    10195}
    10296
    103 void Dump_uset(UnicodeSet s) {
    104     UnicodeSet iset;
     97void Dump_uset(const UnicodeSet & s) {
    10598    Uset_Iterator it(s);
    10699    while (!it.at_end()) {
    107       RunStructure this_run = it.current_run();
    108       if (this_run.run_type == Empty) {
    109         std::cout << "Empty(" << this_run.run_length << ")\n";
    110         it.advance(this_run.run_length);
    111       }
    112       else if (this_run.run_type == Full) {
    113         std::cout << "Full(" << this_run.run_length << ")\n";
    114         it.advance(this_run.run_length);
    115       }
    116       else {
    117         for (int i = 0; i < this_run.run_length; i++) {
    118           std::cout << "Mixed(" << std::hex << it.get_quad() << std::dec << ")\n";
    119           it.advance(1);
    120         }
    121       }
    122     }
    123 }
    124 
    125 
     100        RunStructure this_run = it.current_run();
     101        if (this_run.run_type == Empty) {
     102            std::cout << "Empty(" << this_run.run_length << ")\n";
     103            it.advance(this_run.run_length);
     104        }
     105        else if (this_run.run_type == Full) {
     106            std::cout << "Full(" << this_run.run_length << ")\n";
     107            it.advance(this_run.run_length);
     108        }
     109        else {
     110            for (int i = 0; i < this_run.run_length; i++) {
     111                std::cout << "Mixed(" << std::hex << it.get_quad() << std::dec << ")\n";
     112                it.advance(1);
     113            }
     114        }
     115    }
     116}
    126117
    127118UnicodeSet empty_uset() {
    128119    UnicodeSet iset;
    129     iset.runs.push_back(RunStructure(Empty, UnicodeQuadCount));
     120    iset.runs.emplace_back(Empty, UnicodeQuadCount);
    130121    iset.quad_count = UnicodeQuadCount;
    131122    return iset;
     
    166157}
    167158
    168 UnicodeSet uset_complement (UnicodeSet s) {
     159UnicodeSet uset_complement (const UnicodeSet & s) {
    169160    assert(s.quad_count == UnicodeQuadCount);
    170161    UnicodeSet iset;
    171162    Uset_Iterator it(s);
    172163    while (!it.at_end()) {
    173       RunStructure this_run = it.current_run();
    174       if (this_run.run_type == Empty) {
    175         iset.append_run(Full, this_run.run_length);
    176         it.advance(this_run.run_length);
    177       }
    178       else if (this_run.run_type == Full) {
    179         iset.append_run(Empty, this_run.run_length);
    180         it.advance(this_run.run_length);
    181       }
    182       else {
    183         for (int i = 0; i < this_run.run_length; i++) {
    184           iset.append_quad(FullQuadMask ^ it.get_quad());
    185           it.advance(1);
    186         }
    187       }
    188     }
    189     return iset;
    190 }
    191 
    192 UnicodeSet uset_intersection (UnicodeSet s1, UnicodeSet s2) {
     164        RunStructure this_run = it.current_run();
     165        if (this_run.run_type == Empty) {
     166            iset.append_run(Full, this_run.run_length);
     167            it.advance(this_run.run_length);
     168        }
     169        else if (this_run.run_type == Full) {
     170            iset.append_run(Empty, this_run.run_length);
     171            it.advance(this_run.run_length);
     172        }
     173        else {
     174            for (int i = 0; i < this_run.run_length; i++) {
     175                iset.append_quad(FullQuadMask ^ it.get_quad());
     176                it.advance(1);
     177            }
     178        }
     179    }
     180    return iset;
     181}
     182
     183UnicodeSet uset_intersection (const UnicodeSet & s1, const UnicodeSet & s2) {
    193184    assert(s1.quad_count == UnicodeQuadCount);
    194185    assert(s2.quad_count == UnicodeQuadCount);
     
    197188    Uset_Iterator i2(s2);
    198189    while (!i1.at_end()) {
    199       RunStructure run1 = i1.current_run();
    200       RunStructure run2 = i2.current_run();
    201       int n = std::min(run1.run_length, run2.run_length);
    202       if ((run1.run_type == Empty) || (run2.run_type == Empty)) {
    203         iset.append_run(Empty, n);
    204         i1.advance(n);
    205         i2.advance(n);
    206       }
    207       else if ((run1.run_type == Full) && (run2.run_type == Full)) {
    208         iset.append_run(Full, n);
    209         i1.advance(n);
    210         i2.advance(n);
    211       }
    212       else if (run1.run_type == Full) {
    213         for (int i = 0; i < n; i++) {
    214           iset.append_quad(i2.get_quad());
    215           i2.advance(1);
    216         }
    217         i1.advance(n); 
    218       }
    219       else if (run2.run_type == Full) {
    220         for (int i = 0; i < n; i++) {
    221           iset.append_quad(i1.get_quad());
    222           i1.advance(1);
    223         }
    224         i2.advance(n); 
    225       }
    226       else {
    227         for (int i = 0; i < n; i++) {
    228           iset.append_quad(i1.get_quad() & i2.get_quad());
    229           i1.advance(1);
    230           i2.advance(1);
    231         }
    232       }
    233     }
    234     return iset;
    235 }
    236 
    237 UnicodeSet uset_union (UnicodeSet s1, UnicodeSet s2) {
     190        RunStructure run1 = i1.current_run();
     191        RunStructure run2 = i2.current_run();
     192        int n = std::min(run1.run_length, run2.run_length);
     193        if ((run1.run_type == Empty) || (run2.run_type == Empty)) {
     194            iset.append_run(Empty, n);
     195            i1.advance(n);
     196            i2.advance(n);
     197        }
     198        else if ((run1.run_type == Full) && (run2.run_type == Full)) {
     199            iset.append_run(Full, n);
     200            i1.advance(n);
     201            i2.advance(n);
     202        }
     203        else if (run1.run_type == Full) {
     204            for (int i = 0; i < n; i++) {
     205                iset.append_quad(i2.get_quad());
     206                i2.advance(1);
     207            }
     208            i1.advance(n);
     209        }
     210        else if (run2.run_type == Full) {
     211            for (int i = 0; i < n; i++) {
     212                iset.append_quad(i1.get_quad());
     213                i1.advance(1);
     214            }
     215            i2.advance(n);
     216        }
     217        else {
     218            for (int i = 0; i < n; i++) {
     219                iset.append_quad(i1.get_quad() & i2.get_quad());
     220                i1.advance(1);
     221                i2.advance(1);
     222            }
     223        }
     224    }
     225    return iset;
     226}
     227
     228UnicodeSet uset_union (const UnicodeSet & s1, const UnicodeSet & s2) {
    238229    assert(s1.quad_count == UnicodeQuadCount);
    239230    assert(s2.quad_count == UnicodeQuadCount);
     
    242233    Uset_Iterator i2(s2);
    243234    while (!i1.at_end()) {
    244       RunStructure run1 = i1.current_run();
    245       RunStructure run2 = i2.current_run();
    246       int n = std::min(run1.run_length, run2.run_length);
    247       if ((run1.run_type == Empty) && (run2.run_type == Empty)) {
    248         iset.append_run(Empty, n);
    249         i1.advance(n);
    250         i2.advance(n);
    251       }
    252       else if ((run1.run_type == Full) || (run2.run_type == Full)) {
    253         iset.append_run(Full, n);
    254         i1.advance(n);
    255         i2.advance(n);
    256       }
    257       else if (run1.run_type == Empty) {
    258         for (int i = 0; i < n; i++) {
    259           iset.append_quad(i2.get_quad());
    260           i2.advance(1);
    261         }
    262         i1.advance(n); 
    263       }
    264       else if (run2.run_type == Empty) {
    265         for (int i = 0; i < n; i++) {
    266           iset.append_quad(i1.get_quad());
    267           i1.advance(1);
    268         }
    269         i2.advance(n); 
    270       }
    271       else {
    272         for (int i = 0; i < n; i++) {
    273           iset.append_quad(i1.get_quad() | i2.get_quad());
    274           i1.advance(1);
    275           i2.advance(1);
    276         }
    277       }
    278     }
    279     return iset;
    280 }
    281 
    282 UnicodeSet uset_difference (UnicodeSet s1, UnicodeSet s2) {
     235        RunStructure run1 = i1.current_run();
     236        RunStructure run2 = i2.current_run();
     237        int n = std::min(run1.run_length, run2.run_length);
     238        if ((run1.run_type == Empty) && (run2.run_type == Empty)) {
     239            iset.append_run(Empty, n);
     240            i1.advance(n);
     241            i2.advance(n);
     242        }
     243        else if ((run1.run_type == Full) || (run2.run_type == Full)) {
     244            iset.append_run(Full, n);
     245            i1.advance(n);
     246            i2.advance(n);
     247        }
     248        else if (run1.run_type == Empty) {
     249            for (int i = 0; i < n; i++) {
     250                iset.append_quad(i2.get_quad());
     251                i2.advance(1);
     252            }
     253            i1.advance(n);
     254        }
     255        else if (run2.run_type == Empty) {
     256            for (int i = 0; i < n; i++) {
     257                iset.append_quad(i1.get_quad());
     258                i1.advance(1);
     259            }
     260            i2.advance(n);
     261        }
     262        else {
     263            for (int i = 0; i < n; i++) {
     264                iset.append_quad(i1.get_quad() | i2.get_quad());
     265                i1.advance(1);
     266                i2.advance(1);
     267            }
     268        }
     269    }
     270    return iset;
     271}
     272
     273UnicodeSet uset_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
    283274    assert(s1.quad_count == UnicodeQuadCount);
    284275    assert(s2.quad_count == UnicodeQuadCount);
     
    287278    Uset_Iterator i2(s2);
    288279    while (!i1.at_end()) {
    289       RunStructure run1 = i1.current_run();
    290       RunStructure run2 = i2.current_run();
    291       int n = std::min(run1.run_length, run2.run_length);
    292       if ((run1.run_type == Empty) || (run2.run_type == Full)) {
    293         iset.append_run(Empty, n);
    294         i1.advance(n);
    295         i2.advance(n);
    296       }
    297       else if ((run1.run_type == Full) && (run2.run_type == Empty)) {
    298         iset.append_run(Full, n);
    299         i1.advance(n);
    300         i2.advance(n);
    301       }
    302       else if (run1.run_type == Full) {
    303         for (int i = 0; i < n; i++) {
    304           iset.append_quad(FullQuadMask ^ i2.get_quad());
    305           i2.advance(1);
    306         }
    307         i1.advance(n); 
    308       }
    309       else if (run2.run_type == Empty) {
    310         for (int i = 0; i < n; i++) {
    311           iset.append_quad(i1.get_quad());
    312           i1.advance(1);
    313         }
    314         i2.advance(n); 
    315       }
    316       else {
    317         for (int i = 0; i < n; i++) {
    318           iset.append_quad(i1.get_quad() & ~i2.get_quad());
    319           i1.advance(1);
    320           i2.advance(1);
    321         }
    322       }
    323     }
    324     return iset;
    325 }
    326 
    327 UnicodeSet uset_symmetric_difference (UnicodeSet s1, UnicodeSet s2) {
     280        RunStructure run1 = i1.current_run();
     281        RunStructure run2 = i2.current_run();
     282        int n = std::min(run1.run_length, run2.run_length);
     283        if ((run1.run_type == Empty) || (run2.run_type == Full)) {
     284            iset.append_run(Empty, n);
     285            i1.advance(n);
     286            i2.advance(n);
     287        }
     288        else if ((run1.run_type == Full) && (run2.run_type == Empty)) {
     289            iset.append_run(Full, n);
     290            i1.advance(n);
     291            i2.advance(n);
     292        }
     293        else if (run1.run_type == Full) {
     294            for (int i = 0; i < n; i++) {
     295                iset.append_quad(FullQuadMask ^ i2.get_quad());
     296                i2.advance(1);
     297            }
     298            i1.advance(n);
     299        }
     300        else if (run2.run_type == Empty) {
     301            for (int i = 0; i < n; i++) {
     302                iset.append_quad(i1.get_quad());
     303                i1.advance(1);
     304            }
     305            i2.advance(n);
     306        }
     307        else {
     308            for (int i = 0; i < n; i++) {
     309                iset.append_quad(i1.get_quad() & ~i2.get_quad());
     310                i1.advance(1);
     311                i2.advance(1);
     312            }
     313        }
     314    }
     315    return iset;
     316}
     317
     318UnicodeSet uset_symmetric_difference (const UnicodeSet & s1, const UnicodeSet & s2) {
    328319    assert(s1.quad_count == UnicodeQuadCount);
    329320    assert(s2.quad_count == UnicodeQuadCount);
     
    332323    Uset_Iterator i2(s2);
    333324    while (!i1.at_end()) {
    334       RunStructure run1 = i1.current_run();
    335       RunStructure run2 = i2.current_run();
    336       int n = std::min(run1.run_length, run2.run_length);
    337       if (((run1.run_type == Empty) && (run2.run_type == Full)) || ((run1.run_type == Full) && (run2.run_type == Empty))) {
    338         iset.append_run(Full, n);
    339         i1.advance(n);
    340         i2.advance(n);
    341       }
    342       else if (((run1.run_type == Full) && (run2.run_type == Full)) || ((run1.run_type == Empty) && (run2.run_type == Empty))) {
    343         iset.append_run(Empty, n);
    344         i1.advance(n);
    345         i2.advance(n);
    346       }
    347       else if (run1.run_type == Empty) {
    348         for (int i = 0; i < n; i++) {
    349           iset.append_quad(i2.get_quad());
    350           i2.advance(1);
    351         }
    352         i1.advance(n); 
    353       }
    354       else if (run2.run_type == Empty) {
    355         for (int i = 0; i < n; i++) {
    356           iset.append_quad(i1.get_quad());
    357           i1.advance(1);
    358         }
    359         i2.advance(n); 
    360       }
    361       else if (run1.run_type == Full) {
    362         for (int i = 0; i < n; i++) {
    363           iset.append_quad(FullQuadMask ^ i2.get_quad());
    364           i2.advance(1);
    365         }
    366         i1.advance(n); 
    367       }
    368       else if (run2.run_type == Empty) {
    369         for (int i = 0; i < n; i++) {
    370           iset.append_quad(FullQuadMask ^ i1.get_quad());
    371           i1.advance(1);
    372         }
    373         i2.advance(n); 
    374       }
    375       else {
    376         for (int i = 0; i < n; i++) {
    377           iset.append_quad(i1.get_quad() ^ i2.get_quad());
    378           i1.advance(1);
    379           i2.advance(1);
    380         }
    381       }
    382     }
    383     return iset;
    384 }
    385 
    386 bool uset_member(UnicodeSet s, int codepoint){
     325        RunStructure run1 = i1.current_run();
     326        RunStructure run2 = i2.current_run();
     327        int n = std::min(run1.run_length, run2.run_length);
     328        if (((run1.run_type == Empty) && (run2.run_type == Full)) || ((run1.run_type == Full) && (run2.run_type == Empty))) {
     329            iset.append_run(Full, n);
     330            i1.advance(n);
     331            i2.advance(n);
     332        }
     333        else if (((run1.run_type == Full) && (run2.run_type == Full)) || ((run1.run_type == Empty) && (run2.run_type == Empty))) {
     334            iset.append_run(Empty, n);
     335            i1.advance(n);
     336            i2.advance(n);
     337        }
     338        else if (run1.run_type == Empty) {
     339            for (int i = 0; i < n; i++) {
     340                iset.append_quad(i2.get_quad());
     341                i2.advance(1);
     342            }
     343            i1.advance(n);
     344        }
     345        else if (run2.run_type == Empty) {
     346            for (int i = 0; i < n; i++) {
     347                iset.append_quad(i1.get_quad());
     348                i1.advance(1);
     349            }
     350            i2.advance(n);
     351        }
     352        else if (run1.run_type == Full) {
     353            for (int i = 0; i < n; i++) {
     354                iset.append_quad(FullQuadMask ^ i2.get_quad());
     355                i2.advance(1);
     356            }
     357            i1.advance(n);
     358        }
     359        else if (run2.run_type == Empty) {
     360            for (int i = 0; i < n; i++) {
     361                iset.append_quad(FullQuadMask ^ i1.get_quad());
     362                i1.advance(1);
     363            }
     364            i2.advance(n);
     365        }
     366        else {
     367            for (int i = 0; i < n; i++) {
     368                iset.append_quad(i1.get_quad() ^ i2.get_quad());
     369                i1.advance(1);
     370                i2.advance(1);
     371            }
     372        }
     373    }
     374    return iset;
     375}
     376
     377bool uset_member(const UnicodeSet & s, int codepoint){
    387378    int quad_no = codepoint / quad_bits;
    388379    bitquad_t quad_val = 1 << (codepoint & mod_quad_bit_mask);
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r4189 r4611  
    44#include <vector>
    55#include <ostream>
     6
    67//
    78// unicode_set.h - representing and manipulating sets of Unicode
     
    3839
    3940struct RunStructure {
    40   RunStructure(run_type_t r, uint16_t lgth) : run_type(r), run_length(lgth) {};
     41  RunStructure(run_type_t r, uint16_t lgth) : run_type(r), run_length(lgth) {}
    4142  run_type_t run_type;
    4243  uint16_t run_length;
     
    5859//
    5960//  Nullary constructor for incremental building.
    60     UnicodeSet() : runs(std::vector<RunStructure>()), quads(std::vector<bitquad_t>()), quad_count(0) {};
     61    UnicodeSet() : runs(std::vector<RunStructure>()), quads(std::vector<bitquad_t>()), quad_count(0) {}
    6162//
    6263//  Ternary constructor for constant construction using precomputed data.
    63     UnicodeSet(std::vector<RunStructure> r, std::vector<bitquad_t> q, int c) : runs(r), quads(q), quad_count(c) {};
     64    UnicodeSet(std::initializer_list<RunStructure> r, std::initializer_list<bitquad_t> q, int c) : runs(r), quads(q), quad_count(c) {}
    6465};
    6566
    66     void Dump_uset(UnicodeSet s);
    67     UnicodeSet empty_uset();
    68     UnicodeSet singleton_uset(int codepoint);
    69     UnicodeSet range_uset(int lo_codepoint, int hi_codepoint);
    70     UnicodeSet uset_complement (UnicodeSet s);
    71     UnicodeSet uset_union(UnicodeSet s1, UnicodeSet s2);
    72     UnicodeSet uset_intersection(UnicodeSet s1, UnicodeSet s2);
    73     UnicodeSet uset_difference(UnicodeSet s1, UnicodeSet s2);
    74     UnicodeSet uset_symmetric_difference(UnicodeSet s1, UnicodeSet s2);
    75     bool uset_member(UnicodeSet s, int codepoint);
     67void Dump_uset(UnicodeSet s);
     68UnicodeSet empty_uset();
     69UnicodeSet singleton_uset(int codepoint);
     70UnicodeSet range_uset(int lo_codepoint, int hi_codepoint);
     71UnicodeSet uset_complement (const UnicodeSet &s);
     72UnicodeSet uset_union(const UnicodeSet & s1, const UnicodeSet & s2);
     73UnicodeSet uset_intersection(const UnicodeSet &s1, const UnicodeSet &s2);
     74UnicodeSet uset_difference(const UnicodeSet &s1, const UnicodeSet &s2);
     75UnicodeSet uset_symmetric_difference(const UnicodeSet & s1, const UnicodeSet & s2);
     76bool uset_member(const UnicodeSet & s, int codepoint);
     77
     78class Uset_Iterator {
     79public:
     80    Uset_Iterator(const UnicodeSet & s) : uSet(s), run_no(0), offset(0), quad_no(0) {}
     81    bool at_end();
     82    RunStructure current_run();
     83    bitquad_t get_quad();
     84    void advance(int n);
     85private:
     86    const UnicodeSet & uSet;
     87    int run_no;
     88    int offset;
     89    int quad_no;
     90};
    7691
    7792#endif
Note: See TracChangeset for help on using the changeset viewer.