code

/*Рассматривается список поддиректорий и файлов некоторой директории в Linux, например:
.
./download_client.sh
./random1000_queries_sport.txt
./times.txt
./site
./site/site_kz_domains_random1000_2011-07-26.txt
./site/site_ru_domains_top1000_2011-07-27.txt
./site/site_by_domains_top1000_2011-07-27.txt
./site/kz
./site/kz/random1000
./site/kz/random1000/site_kz_random1000_2011-07-16.xml
./site/ru
./site/ru/random1000
необходимо этот список из одного формата преобразовать в другой формат.
В первых двух строках даны названия входного и выходного формата. Обе строки из мно-
жества «find», «python», «acm1», «acm2», «acm3», «xml». В последующих строках в формате,
соответствующем входному формату из первой строки, описано дерево директорий.
В частности, если перечислена
какая-то поддиректория, то перечислены и все ее родительские директории вплоть до корневой,
а также все ее поддиректории и файлы в них рекурсивно. Если есть элемент списка, у которого нет
потомков в дереве, то это файл, иначе это директория. Соответственно, нет пустых директорий на
нижнем уровне дерева. Все идентификаторы файлов и директорий — уникальные целые числа в
диапазоне от 0 до (231􀀀1). Идентификатор корневой директории всегда равен 0. Идентификатор
родительской вершины всегда меньше идентификатора дочерней вершины.
Имена файлов и папок — непустые строки, состоящие из строчных и заглавных символов латин-
ского алфавита, цифр, символов тире, подчеркивания и точки.

Формат «find»
13
. 0
./download_client.sh 1
./random1000_queries_sport.txt 2
./times.txt 3
./site 4
./site/site_kz_domains_random1000_2011-07-26.txt 5
./site/site_ru_domains_top1000_2011-07-27.txt 6
./site/site_by_domains_top1000_2011-07-27.txt 7
./site/kz 8
./site/kz/random1000 9
./site/kz/site_kz_random1000_2011-07-16.xml 10
./site/ru 11
./site/ru/random1000 12

Формат «python»
13
. 0
    download_client.sh 1
    random1000_queries_sport.txt 2
    times.txt 3
    site 4
        site_kz_domains_random1000_2011-07-26.txt 5
        site_ru_domains_top1000_2011-07-27.txt 6
        site_by_domains_top1000_2011-07-27.txt 7
        kz 8
            random1000 9
            site_kz_random1000_2011-07-16.xml 10
        ru 11
            random1000 12

Формат «acm1»
В первой строке число n — общее количество файлов и директорий. Далее n строк. В i-й строке
название файла или директории, пробел и идентификатор. Идентификаторы упорядочены по
возрастанию. Далее еще n строк. В i-й строке вначале записано число k — количество детей
вершины с i-м по порядку идентификатором. Затем еще k чисел через пробел — идентификаторы
детей в порядке возрастания.
13
. 0
download_client.sh 1
random1000_queries_sport.txt 2
times.txt 3
site 4
site_kz_domains_random1000_2011-07-26.txt 5
site_ru_domains_top1000_2011-07-27.txt 6
site_by_domains_top1000_2011-07-27.txt 7
kz 8
random1000 9
site_kz_random1000_2011-07-16.xml 10
ru 11
random1000 12
4 1 2 3 4
0
0
0
5 5 6 7 8 11
0
0
0
2 9 10
0
0
1 12
0

Формат «acm2»
В первой строке число n — общее количество файлов и директорий. Далее n строк. В i-й строке
название файла или директории, пробел и идентификатор. Идентификаторы упорядочены по
возрастанию. Далее еще n строк. В i-й строке записан идентификатор родителя вершины с i-м
идентификатором или 􀀀1, если это корневая вершина.

13
. 0
download_client.sh 1
random1000_queries_sport.txt 2
times.txt 3
site 4
site_kz_domains_random1000_2011-07-26.txt 5
site_ru_domains_top1000_2011-07-27.txt 6
site_by_domains_top1000_2011-07-27.txt 7
kz 8
random1000 9
site_kz_random1000_2011-07-16.xml 10
ru 11
random1000 12
-1
0
0
0
0
4
4
4
4
8
8
4
11

Формат «acm3»
В первой строке число n — общее количество файлов и директорий. Далее n строк. В i-й строке
название файла или директории, пробел и идентификатор. Идентификаторы упорядочены по воз-
растанию. Далее еще (n 􀀀 1) строка — описания ребер дерева. Каждое ребро описывается двумя
идентификаторами вершин, записанными через пробел. Сначала записан меньший идентифика-
тор, затем больший. Ребра выписаны в порядке возрастания первого идентификатора вершины,
а при равенстве первых идентификаторов — в порядке возрастания второго идентификатора
вершины.
13
. 0
download_client.sh 1
random1000_queries_sport.txt 2
times.txt 3
site 4
site_kz_domains_random1000_2011-07-26.txt 5
site_ru_domains_top1000_2011-07-27.txt 6
site_by_domains_top1000_2011-07-27.txt 7
kz 8
random1000 9
site_kz_random1000_2011-07-16.xml 10
ru 11
random1000 12
0 1
0 2
0 3
0 4
4 5
4 6
4 7
4 8
4 11
8 9
8 10
11 12

Формат «xml»
<dir name=’.’ id=’0’>
  <file name=’download_client.sh’ id=’1’/>
  <file name=’random1000_queries_sport.txt’ id=’2’/>
  <file name=’times.txt’ id=’3’/>
  <dir name=’site’ id=’4’>
    <file name=’site_kz_domains_random1000_2011-07-26.txt’ id=’5’/>
    <file name=’site_ru_domains_top1000_2011-07-27.txt’ id=’6’/>
    <file name=’site_by_domains_top1000_2011-07-27.txt’ id=’7’/>
    <dir name=’kz’ id=’8’>
      <file name=’random1000’ id=’9’/>
      <file name=’site_kz_random1000_2011-07-16.xml’ id=’10’/>
    </dir>
    <dir name=’ru’ id=’11’>
      <file name=’random1000’ id=’12’/>
    </dir>
  </dir>
</dir>

Сделал почти все, осталось сделать формат find. Не применял никакие структуры данных. Так как не имею опыта работы с ними.
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int numOfDir;
string formats[6] = {"find", "python", "acm1", "acm2", "acm3", "xml"};
string separates[6] = {"/", "    ", "", "", "", ""};
string inSep;
string outSep;
vector<string> list;
vector<int> strokeId;
vector<string> folderNames;
vector<int> folderId;
vector<int> parentId;
vector<string> elements;
vector<int> depth;
int inF;
int outF;

int checkFormat( const string *);
void getList();
void getInfo();
int findIdOfFolder(const string *);
void displayList(int, int);
void howManyChild(const int *, vector<int> &);
void displayStat();
void parFoldOut(int);
void fixNI();
void getStat();
int compareIdFold(const string *, int);
bool checkFoldExist(int);
bool readXml(int *, int);

int main()
{
  string inFormat;
  string outFormat;

  cin >> inFormat;
  cin >> outFormat;
  inF = checkFormat( &inFormat );
  outF = checkFormat( &outFormat );

  if (inF != 5)
    cin >> numOfDir;


  inSep = separates[ inF ];
  outSep = separates[ outF ];

  getList();
  getInfo();
  displayList(1, 0);


  displayStat();



  return 0;
}

int checkFormat( const string *format )
{
  for (int i = 0; i < 6; i++ )
    {
      if (*format == formats[i])
    return i;
    }
  return -1;
}

void getList()
{
  string buff;
  int id;
  if (inF != 5)
    {
      cin >> ws;
      for (int i = 0; i < numOfDir; i++)
    {
      if (inF == 1)
        {
          getline(cin, buff);
          //      cout << buff << endl; // <-------------------------------
          id = i;
        }
      else if (inF == 0 || inF == 2 || inF == 3 || inF == 4)
        {
          cin >> buff;
          cin >> id;
        }
      list.push_back( buff );
      strokeId.push_back( id );
      if (inF == 4)
        {
          folderNames.push_back(".");
          folderId.push_back(0);
        }

    }
    }
  else
    {
      cin >> ws;
      int beg = 0;
      readXml(&beg, -1);
    }
}

void getInfo()
{
  size_t posE;
  size_t posB;
  string element;
  string workFolder;
  int currentId;
  int depthStr;
  for(int i = 0; i < numOfDir; i++)
    {
      posB = 0;
      posE = 0;
      if (inF == 0)
    {
      posE = list[ i ].find_last_of( "/" );
      element = list[ i ].substr( posE+1 );
    }
      else if (inF == 1)
    {
      posE = list[i].find_first_not_of(" ");
      posB = list[i].find_last_of(" ");
      //      cout << posE << "<-----" << posB << "< ---------" << endl; // <-----------------------------------
      if (posE != string::npos)
        {
          depth.push_back(posE/4);
          element = list[ i ].substr( posE, posB-posE );
        }
      else
        element = list[ i ].substr(0, 1);
    }
      else if (inF == 2 || inF == 3 || inF == 4)
    {
      element = list[i];
      if (i == 0)
        parentId.push_back(-1);
      else
        parentId.push_back(0);
    }

      elements.push_back(element);
      if (inF == 0 || inF == 1)
    {
      if (element.find(".") != string::npos)
        { }
      else
        {
          folderNames.push_back(element);
          folderId.push_back(i);
        }
      if (inF == 0)
        {
          posB = list[ i ].rfind( "/", posE-1 );

          if ( posB != string::npos)
        {
          posB++;
          workFolder = list[i].substr(posB, posE-posB);
        }
          else
        {
          workFolder = ".";
        }
        }
      else if (inF == 1)
        {
          if (depth[i] == 0)
        {
          workFolder = ".";
        }
          else if (depth[i] > depth[i-1])
        {
          workFolder = elements[i-1];
        }
          else if (depth[i] == depth[i-1])
        {
          workFolder = elements[ parentId[i-1] ];
        }
          else if (depth[i] < depth[i-1])
        {
          int j = i-1;
          //          int deep = depth[i-1]-depth[i];
          //          int tempId = i;
          // findParent(deep, tempId);
          while (depth[i] != depth[j])
            {
              --j;
            }
          workFolder = elements[ parentId[j] ];
        }
        }



      if (i == 0)
        {
          folderNames.push_back(".");
          folderId.push_back(0);
          parentId.push_back(-1);
        }
      else
        {
          currentId = findIdOfFolder( &workFolder );
          parentId.push_back(currentId);
        }
    }
      //      cout << workFolder << " " << strokeId[i] << " " << parentId[i] << endl;
    }
  if (inF == 2 || inF == 3 || inF == 4)
    getStat();
  if (inF != 5)
    fixNI();
}

int findParent(int deep, int id)
{
  if (deep = 0)
    return id;
  else
    {
      id = parentId[id - 1];
      deep--;
      findParent(deep, id);
    }
}

int findIdOfFolder( const string *folder)
{
  int id;
  for (int i = 0; i < folderNames.size(); i++)
    {
      if (*folder == folderNames[i])
    {
      id = folderId[i];
      return id;
    }
    }
  return 999;
}

void displayList(int depth, int dirId)
{
  vector<int> child;
  int fold;
  int jjj;
  if (dirId == 0 && outF == 1)//python
    {
      cout << folderNames[0] << " " << folderId[0] << endl;
    }
  else if (dirId == 0 && outF == 5) // xml
    {
      cout << "<dir name='" << elements[0] << "' id='" << strokeId[0] << "'>" << endl;
    }
  howManyChild( &dirId, child);

  for (vector<int>::iterator it = child.begin(); it != child.end(); it++)
    {
      for (int d = 0; d < depth; d++)
    {
      if (outF == 1) // For python
        cout << "    ";
      else if (outF == 5)
        cout << "  "; // For xml
    }
      if (outF == 1) // python
    {
      cout << elements[ *it ] << " " << strokeId[*it] << endl;
      string buff1 = elements[ *it ];
      jjj = strokeId[*it];
      fold = compareIdFold(&buff1, jjj);
      if (fold != 999)
        {
          displayList(depth+1, *it);
        }
    }
      else if (outF == 5) // xml
    {
      string bufff = elements[*it];
      jjj = strokeId[*it];
      fold = compareIdFold(&bufff, jjj);
      //      fold = findIdOfFolder(&bufff);
      if (fold != 999)
        {
          cout << "<dir name='" << elements[*it] <<"' id='" << strokeId[*it] << "'>" << endl;
          displayList(depth+1, *it);
          for (int d = 0; d < depth; d++)
        cout << "  ";

          cout << "</dir>" << endl;
        }
      else
        {
          cout << "<file name='" << elements[*it] <<  "' id='" << strokeId[*it] << "'>" << endl;
        }
    }
    }
  if (dirId == 0 && outF == 5) // xml
    {
      cout << "</dir>" << endl;
    }

}

void howManyChild(const int *id, vector<int> &childId)
{
  for (int i = 0; i < numOfDir; i++)
    {
      if (parentId[i] == *id)
    {
      childId.push_back(i);
    }
    }
}

void displayStat()
{
  string buff2;
  int fold;
  vector<int> stat;
  int jjj;
  for (int i = 0; i < numOfDir; i++)
    {
      if ( outF== 2) // For acm1
    {
      buff2 = elements[i];
      jjj = strokeId[i];
      fold = compareIdFold(&buff2, jjj);
      if (fold == 999)
        cout << 0 << endl;
      else
        {
          howManyChild(&fold, stat);
          cout << stat.size() << " ";
          for (int j = 0; j < stat.size(); j++)
        {
          cout << stat[j] << " ";
        }
          cout << endl;
        }
      stat.clear();
    }

      else if ( outF == 3 ) // For acm2
    {
      cout << parentId[i] << endl;
    }

      else if (outF == 4) // For acm3
    {
        parFoldOut(i);
    }
      else if (outF == 5)
    {
      //      printXml();
      //      break;
    }
    }
}

void parFoldOut(int i)
{
  for (int j = 0; j < numOfDir; j++)
    {
      if (parentId[j] == i)
    cout << parentId[j] << " " << strokeId[j] << endl;
    }
}

void fixNI()
{
  for (int h = 0; h < folderId.size(); h++)
    {
      int num = 0;
      for (int i = 0; i < numOfDir; i++)
    {
      if (folderId[h] == parentId[i])
        num++;
    }
      if (num == 0)
    {
      folderNames.erase(folderNames.begin()+h);
      folderId.erase(folderId.begin()+h);
    }
    }

}

int compareIdFold(const string *fold, int id)
{
  int it;
  for (int i = 0; i < folderNames.size(); i++)
    {
      if (*fold == folderNames[i] && id == folderId[i])
    {
      it = folderId[i];
      return it;
    }
    }
  return 999;
}

void getStat()
{
  int num;
  for (int i = 0; i < numOfDir; i++)
    {
      if (inF == 2)
    {
      cin >> num;
      if (num != 0)
        {
          int buffId;
          folderNames.push_back(elements[i]);
          folderId.push_back(i);
          cout << elements[i] << endl;
          for (int j = 0; j < num; j++)
        {
          cin >> buffId;
          parentId[buffId] = i;
        }
        }
    }
      else if (inF == 3)
    {
      cin >> num;
      parentId[i] = num;
      if (checkFoldExist(num) == false)
        {
          folderId.push_back(num);
          if (num == -1)
        num = 0;
          folderNames.push_back(elements[num]);

        }

    }
      else if (inF == 4 && i != 0)
    {
      cin >> num;
      int bj;
      cin >> bj;
      parentId[bj] = num;
      if (checkFoldExist(num) == false)
        {
          folderId.push_back(num);
          folderNames.push_back(elements[num]);
        }
    }
    }
}

bool checkFoldExist(int foldId)
{
  for (int i = 0; i < folderNames.size(); i++)
    {
      if (folderId[i] == foldId)
    return true;
    }
  return false;
}
bool readXml(int *idb, int parId)
{
  size_t bPos = 0;
  size_t ePos = 0;
  string element;
  string buff;

  do
    {
      getline(cin, buff);
      bPos = buff.find_first_of("'", bPos);
      ePos = buff.find_first_of("'", bPos+1);
      if (bPos != string::npos && ePos != string::npos)
    {
      element = buff.substr(bPos+1, ePos-bPos-1);
      elements.push_back(element);
      strokeId.push_back(*idb);
      parentId.push_back(parId);
      *idb += 1;
      if (buff.find("<dir name") != string::npos)
        {
          folderNames.push_back(element);
          folderId.push_back(*idb-1);
          readXml(idb, *idb-1);
        }
    }

      bPos = buff.find_first_not_of(" ");
      if (bPos != string::npos)
    buff = buff.substr(bPos);
      else
    buff = buff.substr(0);
      if (parId == -1)
    break;
    } while (buff != "</dir>");
  numOfDir = *idb;
}