OberonCore
https://forum.oberoncore.ru/

Линейный поиск по двунаправленному кольцевому списку
https://forum.oberoncore.ru/viewtopic.php?f=86&t=6075
Страница 1 из 1

Автор:  kekc_leader [ Среда, 21 Июнь, 2017 22:55 ]
Заголовок сообщения:  Линейный поиск по двунаправленному кольцевому списку

Широко известна схема цикла «линейный поиск», которая имеет следующий вид:
Код:
Взять_первую_ситуацию;
WHILE ~ситуации_закончились & ~искомое_найдено DO Взять_следующую_ситуацию END;
IF ~ситуации_закончились THEN (* Искомое найдено *) END

При работе над проектом Oberon Vision (аналог Turbo Vision — библиотеки для создания псевдографического интерфейса пользователя) оказалось, что элементы меню, окна и прочее удобно организовывать в двунаправленные кольца (то есть двунаправленные списки, в которых первый и последний элементы также взаимно связаны).
Код:
TYPE Control* = POINTER TO ControlDesc;
  ControlDesc* = RECORD
    parent*: Control; (* Указатель на непосредственный родительский элемент *)
    children*: Control; (* Указатель на первый дочерний элемент *)
    prev*, next*: Control; (* Указатели на братские элементы для организации двунаправленного кольца *)
    caption*: ARRAY 256 OF CHAR
  END;

Одна из подзадач заключается в нахождении среди братских элементов (sibling elements), включая и сам элемент, элемента с определённым свойством. Например, необходимо найти элемент меню, у которого внутри строкового поля caption была бы определённая буква, перед которой стоит символ "&" (элемент "Save &As..." должен отреагировать на букву "A"). Это нужно для того, чтобы при нажатии на ту или иную клавишу, срабатывал соответствующий элемент меню.

У меня получился такой код:
Код:
PROCEDURE MenuKeyDown*(c: Control; key: G.Key);
VAR p: Control; (* Поиск осуществляется среди братских элементов 'c', включая его самого. *)
  br: Control; (* Элемент-барьер *)
  found: BOOLEAN;
BEGIN
  ...
  p := c.prev;
  br := p;
  REPEAT
    p := p.next;
    found := MenuHotkey(p(Menu), CHR(key.sym))
  UNTIL found OR (p = br);
  IF found THEN
    p.do.click(p)
  END;
  ...
END MenuKeyDown;

Как видите, данный код не соответствует вышеупомянутой схеме линейного поиска. Как решить данную задачу более правильно?

Автор:  albobin [ Среда, 21 Июнь, 2017 23:55 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Не имея ввиду "более правильное", предложение такое - проверить начальный элемент на наличие свойства, а, уж в случае его отсутствия, переходить на обход братьев по схеме линейного поиска.

Автор:  Иван Денисов [ Четверг, 22 Июнь, 2017 05:36 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Вот так должно сработать и это ближе к схеме
Код:
 
  p := c;
  WHILE  (p # NIL) & ~ MenuHotkey(p(Menu), CHR(key.sym)) DO
    IF p.next # с THEN p := p.next ELSE p := NIL END
  END;
  IF p # NIL THEN p.do.click(p) END;
  ...

Автор:  kekc_leader [ Четверг, 22 Июнь, 2017 13:03 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Иван Денисов писал(а):
Вот так должно сработать и это ближе к схеме

Отлично! То, что надо.

Автор:  Info21 [ Четверг, 22 Июнь, 2017 16:59 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Чего-то не вижу? Почему не просто

WHILE (p.next # c) ...
p := p.next
END;
IF p.next # c ...

?

Автор:  Иван Денисов [ Четверг, 22 Июнь, 2017 17:09 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Info21 писал(а):
Чего-то не вижу? Почему не просто

WHILE (p.next # c) ...
p := p.next
END;
IF p.next # c ...

?

Так не получится "защучить" последний элемент при условии выполнения проверки на нем.

Автор:  albobin [ Четверг, 22 Июнь, 2017 17:44 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Добавлю, что в случае цепочки из одного "закольцованного" элемента, тело цикла WHILE (p.next # c) вообще не выполнится.
Кстати тут "двунаправленность" и даже "закольцованность" принципиально ничего кардинально усложняющего по сравнению с линейным списком (строкой, файлом и т.д) не привносит. Просто везде надо определить соответствующий рассматриваемому случаю EOF.

Автор:  Илья Ермаков [ Четверг, 22 Июнь, 2017 20:40 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Как вариант:

Код:
p := first.next;
WHILE (p # first) & ~условие_поиска DO
  p := p.next
END;
IF условие_поиска THEN

END


Относительно схемы ЛП меняется условие в IF.
Цикл такой же, инвариант такой же.
Другая инициализация цикла (принимаем за начальный не первый, а второй элемент, а первый - за конец. Мы вольны в кольцевом списке, всё элементы эквивалентны. Главное, что не имеем права начать с того же, которым заканчиваем.)

Но в классическом ЛП end => UNDEFINED(условие_поиска), поэтому проверка по ~end.
А тут E p end & условие_поиска (существует на множестве всех выполнений программы).
И A p DEFINED(условие_поиска).
Отсюда другой IF в конце.

Ы?

Автор:  Илья Ермаков [ Пятница, 07 Июль, 2017 18:56 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Отвечаю здесь на viewtopic.php?p=101253#p101253

Цитата:
Вот здесь viewtopic.php?p=101164#p101164 приведено решение с грубой ошибкой. Поиск начинается со второго элемента, но если элемент один?


Так всё нормально будет, если он там один! Цикл не выполнится ни разу - и будет сразу проверка завершающего элемента (первого).
Другой вопрос, что это расчитано на непустой список. Так что придётся держать в нём "пустышку".

Цитата:
Само собой, я тогда тоже задумался над примером. И синтезировал (быстро, но не мгновенно!) рабочий вариант.
Он короче варианта Ивана Денисова.


Не томите ) Давайте вариант сюда.

Автор:  Peter Almazov [ Суббота, 08 Июль, 2017 08:22 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

На этой площадке не веду такую деятельность.

Автор:  Иван Денисов [ Суббота, 08 Июль, 2017 13:25 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Peter Almazov писал(а):
На этой площадке не веду такую деятельность.

А я придумал вариант еще короче вашего! ;)

Автор:  adva [ Вторник, 11 Июль, 2017 07:42 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Иван Денисов писал(а):
Peter Almazov писал(а):
На этой площадке не веду такую деятельность.

А я придумал вариант еще короче вашего! ;)

Чё, теперь в моде у кого короче ) ?

Автор:  kekc_leader [ Четверг, 13 Июль, 2017 14:14 ]
Заголовок сообщения:  Re: Линейный поиск по двунаправленному кольцевому списку

Вот как вариант т. Денисова выглядит в рабочем коде:
Код:
  ...
ELSIF (x # 0) & (c.children # NIL) THEN
  p := c.children; br := p;
  WHILE (p # NIL) &
    ~((p.x <= x) & (x < p.x + p.w) &
      (p.y <= y) & (y < p.y + p.h)) DO
    IF p.next = br THEN p := NIL ELSE p := p.next END
  END;
  IF (p # NIL) & (p.do.mouseDown # NIL) THEN
    p.do.mouseDown(p, x - p.x, y - p.y, button)
  END
END


Вполне годится. Остальные варианты прочёл только сейчас.
Если использовать вариант без IF'а внутри WHILE'а, то, пожалуй, имеет смысл выделить условие проверки координат в отдельную процедуру. Ещё важно отметить, что перебирать элементы кольца в данной задаче необходимо начиная с первого, то есть с c.children. В этом случае, когда пользователь нажимает мышкой на место на экране, где находятся сразу несколько окнон, то событие будет направлено окну, находящемуся впереди.

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/