11.6. Финал-апофеоз. Пример проектирования

11.6. Финал – апофеоз. Пример проектирования Для демонстрации всех достоинств технологии ООП рассмотрим проект «средней руки» - таблица произвольной размерности в памяти и в двоичном файле. Здесь нам пригодятся следующие элементы традиционного и объектно-ориентированного программирования:

• TEXT

     абстрактный базовый класс для представления произвольного типа данных – элемента таблицы (11.4);

• TEXT

     преобразование типов указателей для работы с различными типами данных в памяти объекта базового класса (9.2);

• TEXT

     шаблон динамического массива указателей для многократного использования линейной структуры данных с объектами разных типов (10.5, 6.2);

• TEXT

     работа  с двоичными файлами – как последовательного, так и произвольного доступа (9.5, 9.6);

• TEXT

     решение проблем идентификации и порождения объектов множества родственных классов (загрузка таблицы из файла, добавление строк).

Данный пример не является функционально полным. Отсутствующие в нем методы не являются оригинальными по содержанию и легко могут быть воспроизведены самостоятельно.

Постановка задачи Требуется разработать таблицу произвольной размерности, содержащую столбцы из заданного набора типов. В каждом столбце находятся данные одного типа. Количество столбцов и строк, имена столбцов и закрепление за ними типов являются динамическими параметрами, т.е. не «зашиты» в тексте программы, а берутся при загрузке из двоичного файла, содержащего описание заголовка, либо формируются интерактивно (при создании таблицы). Необходимо реализовать стандартный набор операций: добавление столбца (создание таблицы), добавление, вставка, удаление строки, сортировка по выбранному столбцу, сжатие (для двоичного файла), загрузка и сохранение в файле.

Данные произвольного типа Основанная задача – обеспечить динамическую привязку типов данных к столбцам. Для этого необходимо создать сущность – абстрактный тип данных: базовый класс, который позволить объединить все хранимые в таблице типы данных одним представлением. Этот класс может вообще не иметь собственного содержания, например, не иметь данных и включать в себя только пустые полиморфные методы (виртуальные функции). В 12.4 мы уже ввели понятие интерфейса (в Java интерфейс существует как элемент языка, здесь мы его вводим как технологический прием). Методы класса обеспечивают необходимый набор действий, выполняемых в таблице над любым типом данных:

• TEXT

     идентификация класса, к которому принадлежит текущий объект;

• TEXT

     «клонирование» - полиморфное создание копии объекта произвольного типа;

• TEXT

     ввод-вывод объекта из внешнего (символьного) представления;

• TEXT

     загрузка и сохранение объекта в последовательный двоичный поток (файл), определение размерности объекта в файле;

• TEXT

     сравнение и сложение объектов;

//------------------------------------------------------------------------------------------------------------116

//----------- "Пустой" абстрактный базовый класс для произвольного типа данных

class ADT{

public: ADT(){}

// Вируальный деструктор для полиморфного удаления по указателю на БК

virtual ~ADT(){}

// Интерфейсные методы

virtual int type()=0; // Возвращает ID класса

virtual char* name()=0; // Возвращает имя класса

virtual int get(char[])=0; // Ввод из внешнего представления

virtual char *put()=0; // Вывод во внешнее представление

virtual int save(fstream &F)=0; // Сохранение в двоичный поток

virtual int load(fstream &F)=0; // Загрузка из в двоичного потока

virtual ADT *clone()=0; // Создание копии (клона) объекта

virtual int cmp(ADT*)=0; // Сравнение объектов

virtual int add(ADT*)=0; // Сложение объектов 1=1+2

virtual int fsize()=0; // Возвращает размер объекта в файле

};

Виртуальный деструктор необходим, поскольку уничтожение объектов будет производиться через указатель на базовый класс ADT, поскольку хранение объектов будет осуществляться во всех структурах данных именно таким образом.

На самом деле в Си++ существует (хотя далеко не полная) система идентификации объектов, позволяющая получить сведения о классе, к которому он принадлежит. Здесь мы введем собственный механизм хотя бы для того, чтобы обеспечить независимость представления таблицы в файле от версии компилятора.

Но все-таки желательно внести в базовый класс некоторую функциональность, общую для всех типов данных. Для этого можно выбрать форму представления данных объекта на низком уровне как непрерывной области памяти изменяющегося размера. Тогда для большинства типов данных (целые, вещественные, дата/время, строка переменной размерности) достаточно будет имеющегося представления в базовом классе. В противном случае необходимо будет дополнить производный класс необходимыми данными, унаследовав и переопределив с их учетом непустые методы базового класса. Для работы же с данными базового класса необходимо будет использовать технику преобразования типов указателей (9.2).

//------------------------------------------------------------------------------------------------------------116

//--- Абстрактный базовый класс объектов, основанный на непрерывной области памяти

class ADT_mem{

public: int n; // текущая размерность

        void       *pd;                  // область данных

ADT_mem(void *q, int n0){ // Конструктор

        n=n0;

        pd=new char[n];

        char *q1,*q2;

        for (q1=(char*)q,q2=(char*)pd; n0!=0; n0--)

                    *q2++ = *q1++;

        }

// Вируальный деструктор для полиморфного удаления по указателю на БК

virtual ~ADT_mem(){ delete []pd; }

// Интерфейсные методы

virtual int type()=0; // Возвращает ID класса

virtual char* name()=0; // Возвращает имя класса

virtual int get(char[])=0; // Ввод из внешнего представления

virtual char *put()=0; // Вывод во внешнее представление

virtual int save(fstream &F){ // Сохранение в двоичный поток

        F.write((char*)&n,sizeof(int));       // в формате записи переменной длины

        F.write((char*)pd,n);

        return F.good();}

virtual int load(fstream &F){ // Загрузка из в двоичного потока

        delete []pd;                                // в формате записи переменной длины

        pd=NULL;                                  // с разрушением старого содержимого

        F.read((char*)&n,sizeof(int));

        if (!F.good()) return 0;

        pd=new char[n];

        F.read((char*)pd,n);

        return F.good();}

virtual ADT_mem *clone()=NULL; // Создание копии (клона) объекта

virtual int cmp(ADT_mem*)=NULL; // Сравнение объектов

virtual int add(ADT_mem*)=NULL; // Сложение объектов 1=1+2

virtual int fsize() // Возвращает размер объекта в файле

        { return n+sizeof(void*); } // Размер записи в двоичном файле

};

В этом классе определены методы сохранения и загрузки в двоичный файл в виде записи переменной длины, а также конструктор и деструктор для области памяти (динамического массива байтов) известного размера. Производные классы конкретных типов данных используют область данных в базовом классе pd, преобразуя этот указатель от void к тому типу, который хранится в данном классе. Для целого числа это будет int, через преобразованный указатель можно интерпретировать содержимое области данных в соответствии с целым типом - (int)pd. Размерность объекта передается константой, клонирование объекта представляет собой создание динамического объекта производного класса, в конструктор которого передаются параметры текущего объекта.

//------------------------------------------------------------------------------------------------------------116

// Класс целого числа, построенный на классе непрерывной памяти

class Int : public ADT_mem{

public: Int(int a): ADT_mem(&a,sizeof(int)){}

        ~Int(){}

// Интерфейсные методы

        int type(){return 1;}                                 // Возвращает ID класса

        char* name(){ return "Int";}                      // Возвращает имя класса

        int get(char c[]){                                     // Ввод из внешнего представления

                    istrstream S(c);

                    S >> *(int*)pd;

                    return 1; }

        char *put(){                                            // Вывод во внешнее представление

                    char *c=new char[10];

                    ostrstream S(c,10);

                    S << *(int*)pd << '\0';

                    return c; }

        ADT_mem *clone()

{ return new Int((int)pd); } // Создание копии (клона) объекта

        int cmp(ADT_mem *q){                           // Сравнение объектов 

                    if (type()!=q->type())                    // Разные классы - сравнение ID

                                return type()-q->type();

                    return *(int*)pd - *(int*)(q->pd);  }

        int add(ADT_mem *q){                            // Сложение объектов

                    if (type()!=q->type())                    // Разные классы - 0

                                return 0;

                    *(int*)pd+=*(int*)(q->pd);

                    return 1; }

};

Аналогичным образом можно реализовать класс строк переменной длины, но в этом случае размерность области данных в базовом классе устанавливается в равной размеру строки (strlen(c)+1) и используются функции копирования строк.

При реализации объектов более сложной природы можно попытаться максимально использовать средства базового класса. Например, матрицу переменной размерности можно представить в виде последовательно уложенных в память строк – линейный массив, разместив их в базовом классе. Тогда до любого элемента матрицы можно добраться посредством выражения ((double)pd)[imm+j], где mm – число столбцов матрицы. Указатель области данных pd приводится к указателю на массив вещественных чисел. Сами же размерности матрицы nn и mm можно вынести в производный класс. Тогда необходимо переопределить методы загрузки и сохранения в двоичный поток, сохраняя в производном классе размерности и явно вызывая метод базового класса для сохранения коэффициентов матрицы.

//------------------------------------------------------------------------------------------------------------116

// Класс линеаризованной матрицы, построенный на классе непрерывной памяти

class Matrix : public ADT_mem{

        int nn,mm;                                             // Размерности в ПК, данные в БК

public:

        // Конструктор передает область данных в БК, вычисляя ее размерность в байтах

        Matrix(int n0, int m0, double d[]): ADT_mem(d,n0*m0*sizeof(double)){

                    nn=n0; mm=m0; }

        ~Matrix(){}

// Интерфейсные методы

        …

        ADT_mem *clone(){ return new Matrix(nn,mm,(double*)pd);}

        int load(fstream &F){

                    F.read((char*)&nn,sizeof(int));      // Читать размерности

                    F.read((char*)&mm,sizeof(int));

                    return ADT_mem::load(F);           // Читать область данных средствами БК

                    }

        int save(fstream &F){

                    F.write((char*)&nn,sizeof(int));

                    F.write((char*)&mm,sizeof(int));

                    return ADT_mem::save(F);

                    }

        };

«Клонирование» объектов и «виртуальный конструктор» Базовые классы ADT и ADT_mem дают возможность программе работать с объектами, хранящими данные различных типов, единообразно с точки зрения представленного в классе набора методов. Это единообразие распространяется на процедуру уничтожения динамических объектов, поскольку виртуальный деструктор позволяет корректно выполнить операцию delete через указатель на базовый класс. Однако создание объектов и их конструирование не укладывается в такую схему: операцией new нельзя создать объект, класс которого меняется в процессе выполнения программы. Иначе говоря, динамические конструирование объектов не предусмотрено в Си++.

В нашей задаче элементы используются элементы динамического конструирования: строки таблицы создаются по некоторому описанию, которое устанавливает соответствие между столбцом таблицы и типом данных в нем. Решить эту проблему можно путем «клонирования» объектов, т.е. введения полиморфного метода, который при его вызове через указатель на базовый класс создает точную динамическую копию объекта в производном классе. Таким образом можно создать объект заранее неизвестного типа при наличии объекта-прародителя. Как мы уже видели, для этой цели вводится метод clone.

Идея «клонирования» может быть распространена и на строку таблицы. Она представляет собой линейную структуру данных, хранящую указатели на базовый класс ADT (ADT_mem), за которыми «скрываются» объекты конкретных типов. Очевидно, что можно «клонировать» и строку, если создать динамическую копию структуры данных, в которую поместить клоны (копии) хранимых объектов. Тогда в таблице достаточно иметь одну строку – прототип, с которой при добавлении или загрузке строк просто снимаются копии.

Еще одна проблема связана с сохранением таблицы в файле и ее загрузкой. Как известно, в файле нельзя хранить образы объектов, а можно только хранить их данные. Более того, при загрузке надо как-то идентифицировать их классы. Поэтому при сохранении описания таблицы в файле для каждого столбца записывается идентификатор типа данных. Он может быть получен от объекта полиморфным методом type().

Но тогда при загрузке описания необходима обратная процедура восстановления для каждого столбца объекта-прародителя, идентификатор которого получен из файла. По существу ее можно назвать виртуальным конструктором. Для этого необходимо иметь набор статических объектов всех известных типов (например, массив указателей). При его просмотре ищется объект идентификатор типа у которого (метод type) совпадает с предъявленным на вход. С него создается динамическая копия (клон).

//------------------------------------------------------------------------------------------------------------116

// Набор объектов - прототипов - аналог виртуального конструктора

static Int I0(0);

static String S0("");

static double d[1];

static Float F0(0);

static Matrix M0(1,1,d);

static ADT_mem *proto[]={&I0,&F0,&S0,&M0,NULL};

ADT_mem *Mtable::create_ADT(int k){

        for (int i=0;proto[i]!=NULL;i++)

                    if (proto[i]->type()==k)

                                return proto[i]->clone();

        return NULL; }

Шаблон динамической структуры данных Для унификации всех линейных структур данных создается шаблон динамического массива указателей (ДМУ) с операциями управления размерностью, добавления, извлечения (при необходимости вставки и удаления). Использование указателей, а не значений обусловлено тем, что при хранении последних необходимо четко определять действия, связанные с их копированием (конструктор копирования, присваивание), а также неэффективностью работы с копиями, если речь идет об объектах большой размерности.

Принимается еще одно соглашение. Массив указателей должен содержать указатели только на динамические объекты, являющиеся «собственностью» шаблона. Это значит, что при разрушении структуры данных в деструкторе следует уничтожать и указуемые объекты. С одной стороны, это исключает возможность разделения объекта несколькими структурами данных, но с другой стороны не позволит нам «терять» объекты при разрушении структур данных (при любом уровне сложности).

Таблица в памяти Для работы с любыми таблицами (в памяти и в файле) нам потребуется еще один класс – класс строки таблицы (record). Он не содержит в себе ничего оригинального, включает в себя шаблонный класс – динамический массив указателей на хранимые объекты (указатели типа ADT_mem*), а также методы клонирования, загрузки и сохранения в последовательный двоичный поток.

//------------------------------------------------------------------------------------------------------------116

// Класс строки таблицы

class record{

public: DMU<ADT_mem> R;

        ADT_mem *operator[](int m){ return R[m]; }

        record *clone(){

                    record *q=new record;

                    for (int i=0;i<R.size();i++) q->R.add(R[i]->clone());

                    return q; }

        int save(fstream &F){

                    for (int i=0;i<R.size();i++)

                                if (!R[i]->save(F)) return 0;

                    return 1;}

        int load(fstream &F){

                    for (int i=0;i<R.size();i++)

                                if (!R[i]->load(F)) return 0;

                    return 1;}

        void add(ADT_mem *q){ R.add(q); }

        int fsize(){

                    for (int s=0,i=0;i<R.size();i++)

                                s+=R[i]->fsize();

                    return s;}};

Разработанные классы позволяют достаточно просто описать данные класса – таблицы. Это – ее размерности, строка-заголовок (с которой производится клонирование при включении новых строк в таблицу), имена столбцов, содержащиеся в динамическом массиву указателей на объекты класса String. Что же касается самих данных, то для них достаточно создать шаблонный класс динамического массива указателей на объекты record.

//------------------------------------------------------------------------------------------------------------116

// Класс таблицы в памяти

class Mtable{

        int nc,nr;                                   // Размерности таблицы

        record HEAD;                            // Строка заголовка – record объектов-прототипов

        DMU<String> NAMES;               // Имена столбцов

        DMU<record> TBL;                    // Строки таблицы – ДМУ на record

        … };

Операции манипулирования с данными в таблице записываются компактно, поскольку основные действия реализованы в нижележащих классах и последовательность действий отражает сущность операции на абстрактном уровне.

//------------------------------------------------------------------------------------------------------------116

// Добавление строки в таблицу

void Mtable::add(){

        record *q=HEAD.clone();                        // Создать клон с заголовка

        for (int i=0;i<nc;i++){                               // Для всех столбцов

                    char c[80],*s;

                    s=NAMES[i]->put();                   // Вывод подсказки – имя и тип столбца

                    printf("%s(%s):",s,HEAD[i]->name());

                    delete []s;

                    gets(c);                                     // Ввод данных по внешней форме

                    (*q)[i]->get(c);                            // Полиморфный метод загрузки содержимого

                    }                                               // объекта из внешнего представления

        TBL.add(q);                                           // Добавить объект-строку в таблицу

        nr++;}                                                   // Увеличить счетчик записей

Сортировка таблицы производится по любому столбцу. Для этого используется «быстрая» сортировка (7.2), синтаксически адаптированная под используемые структуры данных.

//------------------------------------------------------------------------------------------------------------116

//-- Быстрая сортировка

void Mtable::sort(int k,int a,int b){

        if (a>=b) return;

        for(int i=a,j=b,mode=1;i<j;mode ? j--: i++)

                    if ((*TBL[i])[k]->cmp((*TBL[j])[k])>0){

                                TBL.swap(i,j);

                                mode=!mode;

                                }

        sort(k,a,i-1);

        sort(k,i+1,b);

        }

void Mtable::sort(int k){ sort(k,0,nr-1); }

Метод сохранения таблицы в последовательном двоичном файле отрабатывает «саморазворачивающийся» формат:

• TEXT

     размерности таблицы;

• TEXT

     описатели столбцов. Для каждого сохраняется идентификатор типа данных столбца (метод type), получаемый из строки-заголовка HEAD и строка имени в формате объекта String;

• TEXT

     данные таблицы сохраняются строка за строкой. Сохранение строки (объекта record) в свою очередь приводит к последовательному сохранению объектов, производимому полиморфным методом save в соответствующих производный классах хранимых данных.

//------------------------------------------------------------------------------------------------------------116

// Сохранение в двоичном файле

int Mtable::save(char nm[]){

        fstream F;

        F.open(nm,ios::out | ios::binary | ios::trunc);         // Двоичный файл на запись

        F.write((char*)&nc,sizeof(int));                             // Сохранить размерности

        F.write((char*)&nr,sizeof(int));

        for (int i=0;i<nc;i++){                                           // Для каждого столбца -

                    int t=HEAD[i]->type();                             // внутрениий идентификатор типа

                    F.write((char*)&t,sizeof(int));                    // и строка имени

                    NAMES[i]->save(F);

                    }

        for (i=0;i<nr;i++) TBL[i]->save(F);             // Далее – строки таблицы

        F.close();

        return 1; }

При загрузке таблицы из файла выполняется та же последовательность действий, но при чтении создаются динамические объекты, которые загружаются содержимым двоичного файла, затем указатели на них помещается в соответствующие структуры данных. При чтении описателей столбцов для каждого идентификатора типа объекта выполняется процедура «виртуального конструирования», после чего полученный динамический объект нужного класса помещается в строку-заголовок HEAD. При загрузке данных производится «клонирование» строки-заголовка, чтение в нее данных и сохранение указателя в ДМУ таблицы.

//------------------------------------------------------------------------------------------------------------116

// Загрузка из двоичного файла

int Mtable::load(char nm[]){

        fstream F;

        F.open(nm,ios::in | ios::binary);               // Двоичный для чтения            

        F.read((char*)&nc,sizeof(int));                  // Читать размерности

        F.read((char*)&nr,sizeof(int));

        for (int i=0;i<nc;i++){                               // Чтение заголовка

                    int t;

                    F.read((char*)&t,sizeof(int));        // Идентификатор класса для данных столбца

                    HEAD.add(create_ADT(t));          // Создать объект-прототип по идентификатору

                    String *s=new String("");             // и добавить в строку-заголовок

                    s->load(F);                                // Читать имя столбца в объект String

                    NAMES.add(s);                         // и добавить в ДМУ имен столбцов

                    }

        for (i=0;i<nr;i++){                                    // Чтение данных таблицы

                    record *q=HEAD.clone();            // Создать клон с заголовочной записи

                    q->load(F);                                // Загрузить последовательно ее объекты

                    TBL.add(q);                               // Добавить в таблицу – ДМУ на строки

                    }

        F.close();

        return 1;}

Таблица в двоичном файле Переход от размещения таблицы в памяти к размещению ее в двоичном файле не сопровождается принципиальными изменениями разработанных классов. Заголовок таблицы и ее записи таблицы имеют в файле практически тот же формат, но загружаются по требованию и адресуются через массив файловых указателей (9.6):

• TEXT

     в начале файла размещается заголовок фиксированного формата: число столбцов - nc, число строк - nr, размерность массива файловых указателей - sz, адрес массива файловых указателей на строки таблицы – p0. Ввиду изменяющейся размерности массив файловых указателей постоянно меняет свое размещение в файле, поэтому в начале файла записывается его текущий адрес;

• TEXT

     далее последовательно размещаются описатели столбцов: каждый из них содержит идентификатор типа данных столбца (целое) и строку имени. Формат строки имени соответствует формату записи объекта Srting (целый счетчик длины строки (с учетом символа ограничителя) и сама строка);

• TEXT

     объекты, содержащиеся в строке таблицы, сохраняются последовательно друг за другом, каждый в своем формате (формат записи объекта record);

Класс таблицы в двоичном файле Ftable является производным от fstream, что позволяет по умолчанию использовать все методы файла базового класса. Управляющая часть файла – переменные nc,nr,sz,p0 являются данными объекта Ftable, аналогично, массив файловых указателей загружается в объект в виде динамического массива pp, содержащего переменные типа long.

//------------------------------------------------------------------------------------------------------------116

class Ftable:fstream{

        int nc,nr,sz;

        long p0;                                     // Адрес ДМУ в ДФ

        long *pp;                                   // Массив файловых указателей на записи

        record HEAD;                            // Строка заголовка – record объектов-прототипов

        DMU<String> NAMES;               // Имена столбцов

        …

Первая группа методов класса обеспечивает загрузку управляющих структур двоичного файла в объект Ftable, обновление их из объекта в двоичном файле (заголовка и массива файловых указателей), а также различные варианты задания в двоичном файле пустой таблицы (интерактивное, копия структуры открытой таблицы). При создании пустой таблицы соблюдается такая последовательность размещения: заголовок, описатели столбцов, пустой массив файловых указателей.

//------------------------------------------------------------------------------------------------------------116

// Сохранение структуры текущей таблицы в отдельном файле

void Ftable::create_head(char nm[]){

        fstream F(nm,ios::out | ios::binary | ios::trunc);

        long p0_new=p0;                                    // Адрес размещения массива указателей

        int nr0=0;                                              // в новом файле

        F.write((char*)&nc,sizeof(int));                 // Записать заголовок и описатели столбцов

        F.write((char*)&nr0,sizeof(int));                // из текущего объекта в новый файл

        F.write((char*)&sz,sizeof(int));

        F.write((char*)&p0_new,sizeof(long));

        for (int i=0;i<nc;i++){

                    int t=HEAD[i]->type();

                    F.write((char*)&t,sizeof(int));

                    NAMES[i]->save(F); }

        p0_new=F.tellg();                                   // Получить адрес массива файловых указателей

        long vv=0;                                              // в новом файле

        for (i=0;i<sz;i++)                                    // Записать пустой массив указателей

                    F.write((char*)&vv,sizeof(long));

        F.seekg(3*sizeof(int));                            // Вернуться на место размещения p0

        F.write((char*)&p0_new,sizeof(long));       // Обновить начальный адрес (p0)



        F.close(); }

Особенностью метода открытия двоичного файла является формирование строки – заголовка HEAD аналогично тому, как это делалось при чтении таблицы, размещаемой в памяти. В остальном же она сводится к последовательности позиционирований и чтений данных.

Проблема переменной размерности массива файловых указателей решается просто. При переполнении динамического массива в памяти производится перераспределение памяти функцией realloc, после чего производится позиционирование в конец файла и чтение текущего адреса методом ftell в переменную p0 как адреса его нового размещения. После чего вызов метода update_sys обеспечивает запись массива на новое место. Область, занятая «старым» массивом, становится мусором.

void Ftable::extend(){

        if (nr!=sz) return;                                    // Нет переполнения - выйти

        sz*=2;                                                   // Удвоить размерность

        pp=(long*)realloc(pp,sz*sizeof(long));       // Перераспределить память

        for (int i=sz/2;i<sz;i++) pp[i]=0;               // Обнулить новую вторую  половину

        seekg(0,ios::end);                                  // (для порядка)

        p0=tellg();                                              // Спозиционироваться на конец файла

        update_sys(); }                                      // и получить новый адрес, обновить

Операции над строками таблицы осуществляются с использованием объектов класса record при наличии в объекте загруженного массива файловых указателей, поэтому они пишутся компактно и по существу выполняемого алгоритма.

//------------------------------------------------------------------------------------------------------------116

// Добавление записи

void Ftable::add(record *p){

        seekg(0,ios::end);                      // Позиционироваться в конец файла

        pp[nr++]=tellg();                         // Получить адрес записи и сохранить в массиве pp

        p->save(*this);                           // Записать record в файл как последовательность

        extend();                                   // объектов

        }                                               // Проверить на переполнение массива указателей

// Получение записи по логическому номеру

record *Ftable::get(int m){

        if (m<0 || m>=nr) return NULL;     // Проверка правильности логического номера

        record *p=HEAD.clone();            // Клонировать строку заголовка таблицы

        seekg(pp[m]);                            // Позиционироваться по адресу записи

        p->load(*this);                            // Загрузить последовательность объектов

        return p;                                    // *this – ссылка на базовый класс - fstream

        }

// Обновление записи

void Ftable::update(record *q, int k){

        if (k<0 || k>=nr) return;

        record *old=get(k);                     // Прочитать старую запись из файла

        if (q->fsize()<=old->fsize())          // Если запись не увеличилась -

                    seekg(pp[k]);                 // позиционироваться по старому адресу

        else      {

                    seekg(0,ios::end);          // Иначе  - позиционироваться в конец файла

                    pp[k]=tellg(); }                // и запомнить новый адрес

        q->save(*this); }                         // Обновить запись по установленному адресу

Таким образом, интерфейс пользования основан на получении динамических объектов класса record, содержащих данные строк таблицы.

На последнем уровне находятся методы, работающие со всей таблицей. Прежде всего это касается «сбора мусора». «Мусор» (неиспользуемые участи файла) возникают в нашем варианте в трех случаях:

• TEXT

     переполнение массива файловых указателей;

• TEXT

     удаление строк таблицы;

• TEXT

     обновление строк таблицы, когда общий размер записи в файле обновленной строки (метод fsize) превышает размер содержащейся в нем (в этом случае она пишется в конец файла).

«Сбор мусора» или сжатие осуществляются путем создания нового файла со структурой текущей таблицы и последовательного копирования туда всех строк (т.е. доступных данных).

//------------------------------------------------------------------------------------------------------------116

// сжатие – «сбор мусора»

void Ftable::compress(char nm[]){

        Ftable::create_head(nm);            // Создать новый файл со структурой текущей таблицы

        Ftable T;                                   // с текущей размерностью массива указателей

        T.load(nm);                                // Открыть его в объекте T

        for (int i=0;i<nr;i++){                   // Прочитать все строки

                    record *p=get(i);

                    T.add(p);                       // Добавить их в новую таблицу

                    delete p; }                      // Удалить динамический объект record

        T.close(); }                                 // Закрыть новую таблицу

При сортировке данных в файле следует подробнее рассмотреть эффективность реализации различных вариантов с точки зрения числа операций перечитывания строк таблицы. В самом примитивном случае можно каждый раз заново читать необходимые объекты – строки на каждом шаге цикла, затем удаляя их. Тогда в самом лучшем случае «быстрая» сортировка даст нам log2N повторных чтений каждой строки, а значит и всей таблицы. Можно полностью загрузить все строки в память, что на самом деле неэффективно с точки зрения ее использования. Промежуточный вариант состоит в загрузке объектов того столбца, по которому происходит сортировка. Естественно, что сортировка состоит в перестановках (обменах) в массиве файловых указателей и не касается самих строк.

//------------------------------------------------------------------------------------------------------------116

//-- Быстрая сортировка

// COL – массив указателей на загруженные объекты сортируемого столбца

void Ftable::sort(DMU<ADT_mem> *COL,int a,int b){

        if (a>=b) return;

        for(int i=a,j=b,mode=1;i<j;mode ? j--: i++)

                    if ((*COL)[i]->cmp((*COL)[j])>0){

                                COL->swap(i,j);                          // Одновременный обмен указателей

                                long c=pp[i]; pp[i]=pp[j]; pp[j]=c;  // в массиве файловых указателей

                                mode=!mode;                            // и в массиве указателей столбца

                                }

        sort(COL,a,i-1); sort(COL,i+1,b); }

void Ftable::sort(int k){

        if (k<0 || k>=nc) return;

        DMU<ADT_mem> *pcol=new DMU<ADT_mem>;

        for (int i=0;i<nr;i++){                                           // Чтение данных столбца

                    record *q=get(i);                                     // Читать всю строку таблицы

                    pcol->add((*q)[k]->clone());                     // Клонировать объект k-го столбца

                    delete q; }                                              // и добавить указатель на него в

        sort(pcol,0,nr-1);                                                // ДМУ на объекты столбца

        delete pcol;                                                      

        update_sys(); }                                                  // Обновить в файле массив указателей

В заключение приведем дамп полученного двоичного файла (на любителя). Его чтение, в принципе, может потребоваться при отладке программы.

рис. 116-1. Двоичное представление (дамп) файла таблицы