Advertisement
Guest User

Untitled

a guest
Oct 18th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 KB | None | 0 0
  1. /// Возвращаем указатель pNodeLast образущий с указателем pNodeBefore неделимую цепочку(например, a1, a2,...,an)
  2. /// находящуюся в диапазоне (pNodeBefore; pNodeLast]
  3. DNARepairer::NodeDNA* findUnbreakableChain(const DNARepairer::NodeDNA* pNodeBefore)
  4. {
  5.     if(pNodeBefore->next == nullptr)
  6.         return nullptr;
  7.  
  8.     DNARepairer::NodeDNA* pNodeLast = pNodeBefore->next;
  9.     string id = pNodeLast->value.id;
  10.     int number = pNodeLast->value.number;
  11.  
  12.     while (pNodeLast->next != nullptr)
  13.     {
  14.         if (pNodeLast->next->value.id != id || pNodeLast->next->value.number != ++number)
  15.             return pNodeLast;
  16.         pNodeLast = pNodeLast->next;
  17.     }
  18.     return pNodeLast;
  19. }
  20.  
  21. /// Возвращает вершину после которой можно вставить цепочку
  22. DNARepairer::NodeDNA* findNodeToPlaceAfter(int number, DNARepairer::DNAChain* chain)
  23. {
  24.     DNARepairer::NodeDNA* head = chain->getPreHead();
  25.  
  26.     if (head->next == nullptr) // if chain is empty return nullptr
  27.         return head;
  28.  
  29.     while (head->next != nullptr && head->next->value.number < number)
  30.         head = head->next;
  31.  
  32.     return head;
  33. }
  34.  
  35. void DNARepairer::placeId2DnaMapToStorage(Id2DnaMap& repairedDNAMap)
  36. {
  37.     _dnaStorage.deleteNodes(_dnaStorage.getPreHead(), _dnaStorage.getLastNode());
  38.     for (auto i = ++repairedDNAMap.begin(); i != repairedDNAMap.end(); ++i)
  39.         _dnaStorage.addElementToEnd(*i->second);
  40. }
  41.  
  42. void DNARepairer::repairDNA()
  43. {
  44.     // Хранилище для починенных ДНК
  45.     Id2DnaMap repairedDNAMap = std::map<std::string, DNAChain*>();
  46.  
  47.     NodeDNAChain* pChain = _dnaStorage.getPreHead();
  48.     // Обход цепочек ДНК
  49.     while(pChain->next != nullptr)
  50.     {
  51.         pChain = pChain->next;
  52.         NodeDNA* pNode = pChain->value.getPreHead();
  53.         // Обход элементов цепочки
  54.         while(pNode->next != nullptr)
  55.         {
  56.             // Находим недилимую цепочку (pNode; pNodeLast]
  57.             NodeDNA* pNodeLast = findUnbreakableChain(pNode);
  58.             // Если
  59.             if(repairedDNAMap[pNode->next->value.id] == nullptr)
  60.                 repairedDNAMap[pNode->next->value.id] = new DNAChain();
  61.             // Находим в repairedDNAMap место куда, можно вставить эту цепочку
  62.             NodeDNA* pNodeToPlaceAfter = findNodeToPlaceAfter(pNode->next->value.number, repairedDNAMap[pNode->next->value.id]);
  63.             // Вставляем
  64.             repairedDNAMap[pNode->value.id]->moveNodesAfter(pNodeToPlaceAfter, pNode, pNodeLast);
  65.         }
  66.     }
  67.  
  68.     // запихиваем repairedDNAMap в DNA storage
  69.     placeId2DnaMapToStorage(repairedDNAMap);
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement