fork download 
  1. #include <iostream>
  2. #include <cassert>
  3. #include <vector>
  4. #include <cctype>
  5.  
  6. int const ADD_SIZE = 10;
  7.  
  8. class MyIntSet {
  9. private:
  10.   std::pair<int, int> *setTable;
  11.   int tableSize;
  12.   int tableCapacitySize;
  13.  
  14.   void _initialize();
  15.   void _erase(std::pair<int, int> *p);
  16.   void _insert(std::pair<int, int> *p, std::pair<int, int>q);
  17.  
  18.   std::pair<int, int> *positionToInsert(int,  bool &);
  19.  
  20. public:
  21.   MyIntSet() { this->_initialize(); }
  22.   MyIntSet(int beg, int end) {this->_initialize(); this->insert(beg, end); }
  23.   ~MyIntSet();
  24.   void insert(int n);
  25.   void insert(int beg, int end);
  26.   void erase(int n);
  27.   bool isFoundP(int n);
  28.   bool isEmptyP();
  29.  
  30.   bool isRegularP();
  31.   void dump();
  32.  
  33. };
  34.  
  35. /* コンストラクタ共通 */
  36. void MyIntSet::_initialize() {
  37.   setTable = nullptr;
  38.   tableSize = 0;
  39.   tableCapacitySize = 0;
  40. }
  41.  
  42. /* myVector 要素削除  */
  43. /* 配列の縮小は行わない */
  44. void MyIntSet::_erase(std::pair<int, int> *erase_point) {
  45.   assert(erase_point >= setTable && erase_point < &setTable[tableSize]);
  46.   std::pair<int, int> *p, *q;
  47.   if (tableSize > 0) {
  48.     p = erase_point;
  49.     q = p + 1;
  50.     for (; q != &setTable[tableSize]; p++, q++)
  51.       *p = *q;
  52.     --tableSize;
  53.     if (tableSize == 0) {
  54.       delete[] setTable;
  55.       setTable = nullptr;
  56.       tableCapacitySize = 0;
  57.     }
  58.   }  
  59. }
  60.  
  61. /* myVector 要素追加  */
  62. void MyIntSet::_insert(std::pair<int, int> *insert_point, std::pair<int, int>insert_value) {
  63.   assert((insert_point >= setTable && insert_point <= &setTable[tableSize]) || (insert_point == nullptr && tableCapacitySize == 0));
  64.  
  65.   if (tableSize >= tableCapacitySize) {
  66.     /* リサイズ */
  67.     tableCapacitySize += ADD_SIZE; tableCapacitySize *= 2;
  68.     std::pair<int, int> *setTableNew = new std::pair<int, int>[tableCapacitySize];
  69.     std::pair<int, int> *p, *q;
  70.     for (p = setTable, q = setTableNew; p != &setTable[tableSize]; p++, q++) {
  71.       *q = *p;
  72.     }
  73.     /* インサート位置のリサイズによる修正 */
  74.     if (insert_point == nullptr)
  75.       insert_point = setTableNew;
  76.     else
  77.       insert_point =setTableNew + (insert_point - setTable);
  78.  
  79.     delete[] setTable;
  80.     setTable = setTableNew;
  81.   }
  82.  
  83.   /* データの移動 */
  84.   std::pair<int, int> *p, *q;
  85.   if (tableSize > 0) {
  86.     p = &setTable[tableSize - 1];
  87.     q = &setTable[tableSize];
  88.     for (; p >= insert_point; --p, --q)
  89.       *q = *p;
  90.   }
  91.   tableSize++;
  92.   *insert_point = insert_value;
  93. }
  94.  
  95. MyIntSet::~MyIntSet() { delete[] setTable; setTable = nullptr; }
  96.  
  97. /*-------------------------------------------------------------------------*/
  98. /*
  99. std::pair<int, int> *MyIntSet::positionToInsertObsolete(int n, bool &isInSet) {
  100.   std::pair<int, int> *p;
  101.   for (p = &this->setTable[0]; p != &this->setTable[tableSize]; p++) {
  102.     if (n >= p->first && n <= p->second) {
  103.       isInSet = true;
  104.       return p;
  105.     }
  106.     if (n < p->first) {
  107.       isInSet = false;
  108.       return p;
  109.     }
  110.   }
  111.   isInSet = false;
  112.   return p;
  113. }
  114. */
  115.  
  116. /* binary-search */
  117. std::pair<int, int> *MyIntSet::positionToInsert(int n, bool &isBelongToSet) {
  118.   int s = 0, t = tableSize, h;
  119.   if (tableSize == 0) {
  120.     isBelongToSet = false;
  121.     return setTable;
  122.   }
  123.   for (;;) {
  124.     if (s >= t) {
  125.       isBelongToSet = false;
  126.       return &setTable[t];
  127.     }
  128.  
  129.     h = (s + t) / 2;
  130.  
  131.     if (n >= setTable[h].first && n <= setTable[h].second) {
  132.       isBelongToSet = true;
  133.       return &setTable[h];
  134.     }
  135.     if (n < setTable[h].first) {
  136.       if ((h > 0 && n > setTable[h - 1].second) || h == 0) {
  137.         isBelongToSet = false;
  138.         return &setTable[h];
  139.       }
  140.       t = h;
  141.       continue;
  142.     }
  143.     if (n > setTable[h].second) {
  144.       s = h + 1;
  145.       continue;
  146.     }
  147.     std::cout << "positionToInsert(): s = " << s << ", t = " << t << std::endl;
  148.     assert(1==0);
  149.   }
  150. }
  151.  
  152. /*-------------------------------------------------------------------------*/
  153. /* 集合に n は含まれるか？*/
  154. bool MyIntSet::isFoundP(int n) {
  155.   bool isBelongToMyIntSet;
  156.  
  157.   this->positionToInsert(n, /*ref*/isBelongToMyIntSet);
  158.   if (isBelongToMyIntSet) {
  159.     return true;
  160.   }
  161.   return false;
  162. }
  163.  
  164. /* for デバッグ・ダンプ*/
  165. void MyIntSet::dump() {
  166.   std::pair<int, int> *p;
  167.   for (p = &this->setTable[0]; p != &this->setTable[tableSize]; p++)
  168.     std::cout << p->first << "-" << p->second << ",";
  169.   std::cout << std::endl;
  170. }
  171.  
  172. /* for デバッグ・集合の内部表現が矛盾なく正しいか？*/
  173. bool MyIntSet::isRegularP() {
  174.   std::pair<int, int> *p;
  175.   bool isRegularReturn = true;
  176.   for (p = &this->setTable[0]; p != &this->setTable[tableSize]; p++) {
  177.     if (p->first > p->second) {
  178.       isRegularReturn = false;
  179.       break;
  180.     }
  181.     if (p != &setTable[0] && p->first <= (p - 1)->second) {
  182.       isRegularReturn = false;
  183.       break;
  184.     }
  185.   }  
  186.   if (isRegularReturn == false) {
  187.     this->dump();
  188.   }
  189.   return isRegularReturn;
  190. }
  191.  
  192. /* 集合への整数要素の追加 */
  193. void MyIntSet::insert(int n) {
  194.   std::pair<int, int> *p;  
  195.   bool isBelongToMyIntSet;
  196.   bool isStored = false;
  197.  
  198.   p = this->positionToInsert(n, /*ref*/isBelongToMyIntSet);
  199.   if (isBelongToMyIntSet) {
  200.     return;
  201.   }
  202.   if (p != &setTable[0] && (p - 1)->second == n - 1) {
  203.     (p - 1)->second = n;
  204.     isStored = true;
  205.   }
  206.   if (p != &setTable[tableSize] && p->first == n + 1) {
  207.     p->first = n;
  208.     isStored = true;
  209.   }
  210.   if (p != &setTable[tableSize] && (p - 1)->second == p->first) {
  211.     /* section merging */
  212.     (p - 1)->second = p->second;
  213.     this->_erase(p);
  214.     isStored = true;
  215.   }
  216.   if (!isStored)
  217.     this->_insert(p, std::pair<int, int>(n, n));
  218. }
  219.  
  220. void MyIntSet::insert(int beg, int end) {
  221.   for (int n = beg; n <= end; n++)
  222.     this->insert(n);
  223. }
  224.  
  225. /* 集合への整数要素の削除 */
  226. void MyIntSet::erase(int n) {
  227.   std::pair<int, int> *p;  
  228.   bool isBelongToMyIntSet;
  229.  
  230.   p = this->positionToInsert(n, /*ref*/isBelongToMyIntSet);
  231.   if (!isBelongToMyIntSet) return;
  232.  
  233.   if (n == p->first && n == p->second) {
  234.     this->_erase(p);
  235.     return;
  236.   }
  237.  
  238.   if (n == p->first && n < p->second) {
  239.     p->first++;
  240.     return;
  241.   }
  242.   if (n == p->second && n > p->first) {
  243.     p->second--;
  244.     return;
  245.   }
  246.   /* division */
  247.   int q = p->second;
  248.   p->second = n - 1;
  249.   this->_insert(++p, std::pair<int, int>(n + 1, q));
  250. }
  251.  
  252. bool MyIntSet::isEmptyP() {
  253.   return (this->tableSize == 0);
  254. }
  255.  
  256. /*-------------------------------------------------*/
  257. int const min = 1;
  258. int const max = 999;
  259.  
  260. void anchor_list(std::string str) {
  261.   MyIntSet myIntSet;
  262.  
  263.   if (str.find(">>") != 0) return;
  264.   std::string::const_iterator p = str.begin(), q;
  265.   p++; p++;
  266.   for (; p != str.end();) {
  267.     if (!isdigit(*p))
  268.       break;
  269.     q = p;
  270.     while (isdigit(*p)) p++;
  271.     int n = std::atoi(std::string(q, p).c_str());
  272.     if (p == str.end()) {
  273.       myIntSet.insert(n);
  274.       break;
  275.     }
  276.     if (*p == ',') {
  277.       myIntSet.insert(n);
  278.       p++;
  279.       continue;
  280.     }
  281.     if (*p == '-') {
  282.       p++;
  283.       if (*p == ',') {
  284.         myIntSet.insert(n, max);
  285.         p++;
  286.         continue;
  287.       }
  288.       if (p == str.end()) {
  289.         myIntSet.insert(n, max);
  290.         continue;
  291.       }
  292.       if (isdigit(*p)) {
  293.         q = p;
  294.         while (isdigit(*p)) p++;
  295.         int m = std::atoi(std::string(q, p).c_str());
  296.         if (n > m) {int t = n; n = m; m = t; }
  297.         myIntSet.insert(n, m);
  298.         if (*p == ',') {
  299.           p++;
  300.           continue;
  301.         }
  302.       }
  303.       break;
  304.     }
  305.   }    
  306.   int buf = -1;
  307.   std::cout << "[ ";
  308.  
  309.   for (int n = min; n <= max; n++) {
  310.     if (myIntSet.isFoundP(n)) {
  311.       if (buf != -1) std::cout << buf << ",";
  312.       buf = n;
  313.     }
  314.   }
  315.   if (buf != -1)
  316.     std::cout << buf;
  317.   std::cout << " ]";
  318. }
  319.  
  320. void f(std::string str) {
  321.   std::cout << str << " : ";
  322.   anchor_list(str);
  323.   std::cout << std::endl;
  324. }
  325.  
  326. int main() {
  327.   f(">>1");
  328.   f(">>1-3");
  329.   f(">>1,3");
  330.   f(">>1,3-5");
  331.   f(">>1,1");
  332.   f(">>1-3,2");
  333.   f(">>1-4,2-3");
  334.   f(">>1-4,3-5");
  335.  
  336.   f(">>1-3,5,9-10");
  337.   f(">>000000-000000001");
  338.   f(">>2894");
  339.   f(">>0-2,998-1000");
  340.   f(">>3,0-3,4,5,6,4,2-8");
  341.   f(">>1-3,5,9-10");
  342.   f(">>4-1");
  343.   f(">>7-4,5-9");
  344.   f(">>990-");
  345.   f(">>5-5");
  346.   f(">>6-5,998-,10-8");
  347.  
  348.   return 0;
  349. }
  350. /* end */
  351.  
Success #stdin #stdout 0s 4268KB
comments (?)
stdin 
Standard input is empty
stdout 
>>1 : [ 1 ]
>>1-3 : [ 1,2,3 ]
>>1,3 : [ 1,3 ]
>>1,3-5 : [ 1,3,4,5 ]
>>1,1 : [ 1 ]
>>1-3,2 : [ 1,2,3 ]
>>1-4,2-3 : [ 1,2,3,4 ]
>>1-4,3-5 : [ 1,2,3,4,5 ]
>>1-3,5,9-10 : [ 1,2,3,5,9,10 ]
>>000000-000000001 : [ 1 ]
>>2894 : [  ]
>>0-2,998-1000 : [ 1,2,998,999 ]
>>3,0-3,4,5,6,4,2-8 : [ 1,2,3,4,5,6,7,8 ]
>>1-3,5,9-10 : [ 1,2,3,5,9,10 ]
>>4-1 : [ 1,2,3,4 ]
>>7-4,5-9 : [ 4,5,6,7,8,9 ]
>>990- : [ 990,991,992,993,994,995,996,997,998,999 ]
>>5-5 : [ 5 ]
>>6-5,998-,10-8 : [ 5,6,8,9,10,998,999 ]
https://ideone.com/vm8qnp
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!