(*~\Глагол\Отделы\Иное\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(**)                             ОТДЕЛ оРядаД;
(*============================================================================*)
(* НАЗНАЧЕНИЕ:                                                                * 
 *             обработка рядов из доступов к прозвольным/пустым наборам -     *
 *                   Сортировка, Поиск и Вставка в рядах                      *
 *               с участием вида  Пустой.Доступ  из отдела  Пустой.отд        *)
(*============================================================================*)

ИСПОЛЬЗУЕТ
        (*  \Глагол\              *)
  Пустой  ИЗ "..\..\Отделы\Иное\";


(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~общедоступная ЗАДАЧА~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Вставка-( 
                      слагД:Пустой.Доступ;        (* доступ к пустому/любому набору для вставки *)
                        (* :РЯД ИЗ Пустой.Доступ;  *)
                 рДоступов+:Пустой.РядДоступов;           (* ряд из доступов к пустому/любому набору *)
          размер_рДоступов+:ЦЕЛ;                          (* размер ряда <рДоступов+> *)
            сравнитьНаборы :ЗАДАЧА(с1-,с2-:Пустой.Вид):ЦЕЛ
               );
ПЕР
  пол,рез,
  нач,   всего:ЦЕЛ;
УКАЗ
  нач:=0;
         всего:=размер_рДоступов;
  КОЛЬЦО
    ЕСЛИ
         всего <= 0
    ТО
      ВЫХОД
    КОН;
    пол:=всего ДЕЛИТЬ 2;

    рез:=сравнитьНаборы(слагД^,рДоступов[нач+пол]^);

    ЕСЛИ
          рез <= 0
    ТО
      ЕСЛИ
          рез = 0
      ТО
        ВОЗВРАТ
      КОН;

      всего:=пол
    ИНАЧЕ
      УВЕЛИЧИТЬ(нач,пол+1);
      УМЕНЬШИТЬ(всего,пол+1)
    КОН
  КОН;

  ЕСЛИ
       размер_рДоступов=РАЗМЕР(рДоступов)
  ТО
    ВОЗВРАТ
  КОН;
       всего:=размер_рДоступов;
  ПОКА
       всего > нач
  ВЫП
    рДоступов[всего]:=рДоступов[всего-1];
    УМЕНЬШИТЬ(всего)
  КОН;

    рДоступов[нач]:=слагД;
  УВЕЛИЧИТЬ(размер_рДоступов)
КОН Вставка;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~общедоступная ЗАДАЧА~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Поиск-(
                     нСлаг-:Пустой.Вид;           (* набор-образец для поиска доступа *)
                        (* :РЯД ИЗ Пустой.Доступ;  *)
                 рДоступов+:Пустой.РядДоступов;           (* ряд из доступов к пустому/любому набору *)
          размер_рДоступов :ЦЕЛ;                          (* размер ряда <рДоступов+> *)
            сравнитьНаборы :ЗАДАЧА(с1-,с2-:Пустой.Вид):ЦЕЛ
             ):Пустой.Доступ;
ПЕР
  пол,рез,
  нач, всего:ЦЕЛ;
УКАЗ
  нач:=0;
         всего:=размер_рДоступов;
  ПОКА
         всего > 0
  ВЫП
    пол:=всего ДЕЛИТЬ 2;

    рез:=сравнитьНаборы(нСлаг,рДоступов[нач+пол]^);

    ЕСЛИ
          рез <= 0
    ТО
      ЕСЛИ
          рез = 0
      ТО
        ВОЗВРАТ рДоступов[нач+пол] 
      КОН;

      всего:=пол
    ИНАЧЕ
      УВЕЛИЧИТЬ(нач,пол+1);
      УМЕНЬШИТЬ(всего,пол+1)
    КОН
  КОН;
  ВОЗВРАТ ПУСТО
КОН Поиск;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~общедоступная ЗАДАЧА~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Сортировка-(                                            (* Упорядочить *)
                        (* :РЯД ИЗ Пустой.Доступ;  *)
                 рДоступов+:Пустой.РядДоступов;           (* ряд из доступов к пустому/любому набору *)
          размер_рДоступов :ЦЕЛ;                          (* размер ряда <рДоступов+> *)
            сравнитьНаборы :ЗАДАЧА(с1-,с2-:Пустой.Вид):ЦЕЛ
                  );
(*
 * Быстрое упорядочивание в ряду <рДоступов+> с помощью разделения на участки (Ч.Хоар) 
 *)
ПЕР
  Л,П:ЦЕЛ;               (* текущий участок                                     *)
  л,п:ЦЕЛ;               (* новый участок                                       *)

  границаД:Пустой.Доступ;(* граничное значение для разделение (доступ к набору) *)
   рядЛевД:Пустой.Доступ;(* промежуточное значение для обмена (доступ к набору) *)

  рСтэк:РЯД 32 ИЗ        (* ряд-стэк для новых участков       (ряд из наборов)  *)
                   НАБОР
                        Л,П:ЦЕЛ
                   КОН;
        глубина:ЦЕЛ;     (* текущая глубина ряда-стэка *)
УКАЗ
        глубина:=0; 
  рСтэк[глубина].Л:=0; 
  рСтэк[глубина].П:=размер_рДоступов-1;

  ПОВТОРЯТЬ (* до глубина < 0 *)
                                (* выбор из ряда-стэка последнего запроса *)
    Л:=рСтэк[глубина].Л; 
    П:=рСтэк[глубина].П;
   УМЕНЬШИТЬ(глубина);

    ПОВТОРЯТЬ (* до л > п *)
                                (* разделение рДоступов[Л]...рДоступов[П] *)
      л:=Л; п:=П;
      границаД:=рДоступов[(Л+П) ДЕЛИТЬ 2];

      ПОВТОРЯТЬ
        ПОКА
             сравнитьНаборы(рДоступов[л]^,границаД^) < 0
        ВЫП
           УВЕЛИЧИТЬ(л)
        КОН;
        ПОКА
             сравнитьНаборы(границаД^,рДоступов[п]^) < 0
        ВЫП
           УМЕНЬШИТЬ(п)
        КОН;

        ЕСЛИ
             л <= п
        ТО                                    (* обмен рДоступов[л] с рДоступов[п] *)

                        рядЛевД:=рДоступов[л];(* промежуточное значение для обмена (доступов к набору) *)

          рДоступов[л]:=рДоступов[п];
          рДоступов[п]:=рядЛевД;
          УВЕЛИЧИТЬ(л);
          УМЕНЬШИТЬ(п)
        КОН
      ДО л > п;
                      (* изменение глубины ряда-стэк <рСтэк> *)
      ЕСЛИ
           п-Л < П-л
      ТО
        ЕСЛИ
             л < П
        ТО                   (* запись в ряд-стэк запроса на упорядочивание правой части *)
          УВЕЛИЧИТЬ(глубина);
              рСтэк[глубина].Л:=л;
              рСтэк[глубина].П:=П
        КОН;
        П:=п                                  (* продолжение упорядочивания левой  части *)
      ИНАЧЕ
        ЕСЛИ
             Л < п
        ТО                   (* запись в ряд-стэк запроса на упорядочивание левой  части *)
          УВЕЛИЧИТЬ(глубина);
              рСтэк[глубина].Л:=Л;
              рСтэк[глубина].П:=п
        КОН;
        Л:=л (* продолжение упорядочивания правой части *)
      КОН
    ДО Л >= П
  ДО глубина < 0
КОН Сортировка (*Упорядочить*);

КОН оРядаД.
