fork(1) download
copy 
  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. std::pair<int, int> *MyIntSet::positionToInsertObsolete(int n, bool &isInSet) {
  99.   std::pair<int, int> *p;
  100.   for (p = &this->setTable[0]; p != &this->setTable[tableSize]; p++) {
  101.     if (n >= p->first && n <= p->second) {
  102.       isInSet = true;
  103.       return p;
  104.     }
  105.     if (n < p->first) {
  106.       isInSet = false;
  107.       return p;
  108.     }
  109.   }
  110.   isInSet = false;
  111.   return p;
  112. }
  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 = 99999;
  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.       q = p;
  284.       while (isdigit(*p)) p++;
  285.       int m = std::atoi(std::string(q, p).c_str());
  286.       myIntSet.insert(n, m);
  287.       if (*p == ',') {
  288.         p++;
  289.         continue;
  290.       }
  291.       break;
  292.     }
  293.   }    
  294.   int buf = -1;
  295.   std::cout << "[ ";
  296.  
  297.   for (int n = min; n <= max; n++) {
  298.     if (myIntSet.isFoundP(n)) {
  299.       if (buf != -1) std::cout << buf << ",";
  300.       buf = n;
  301.     }
  302.   }
  303.   if (buf != -1)
  304.     std::cout << buf;
  305.   std::cout << " ]";
  306. }
  307.  
  308. void f(std::string str) {
  309.   std::cout << str << " : ";
  310.   anchor_list(str);
  311.   std::cout << std::endl;
  312. }
  313.  
  314. int main() {
  315.   f(">>1");
  316.   f(">>1-3");
  317.   f(">>1,3");
  318.   f(">>1-3,5,9-10");
  319.   f(">>000000-000000001");
  320.   f(">>289494");
  321.   f(">>0-2,99998-100000");
  322.   f(">>3,0-3,4,5,6,4,2-8");
  323.   f(">>1-3,5,9-10");
  324.  
  325.   return 0;
  326. }
  327. /* end */
  328.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
>>1 : [ 1 ]
>>1-3 : [ 1,2,3 ]
>>1,3 : [ 1,3 ]
>>1-3,5,9-10 : [ 1,2,3,5,9,10 ]
>>000000-000000001 : [ 1 ]
>>289494 : [  ]
>>0-2,99998-100000 : [ 1,2,99998,99999 ]
>>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 ]
https://ideone.com/Fbgth4
language:
C++ (gcc 8.3)
created:
6 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!