Поиск элемента множества по его естественному порядку.

← →
Ш-К (2004-11-05 12:23) [0]

У меня есть переменная типа множество.
Как найти n-ый элемент переменной. Не индексируя элементы в цикле.

Просто интересно.

← →
Семен Сорокин © (2004-11-05 12:42) [1]

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

← →
Digitman © (2004-11-05 12:46) [2]

> Как найти n-ый элемент переменной

задача сводится к чтению состояния n-ного бита массива, хранящего множество.

← →
Ш-К (2004-11-05 13:12) [3]

Семен Сорокин © (05.11.04 12:42) [1]
Так и сделал.

Digitman © (05.11.04 12:46) [2]
Тогда уж, нахождения индекса n-го единичного бита.

← →
TUser © (2004-11-05 13:49) [4]

tset = (tsName1, tsName2);

var
Form1: TForm1;

implementation
uses TypInfo;

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
for i:=0 to 1 do
memo1.lines.add(getenumname(typeinfo(tset),i));
end;

← →
TUser © (2004-11-05 13:50) [5]

Хотя, это я не про то ...

← →
Digitman © (2004-11-05 13:59) [6]

> Тогда уж, нахождения индекса n-го единичного бита

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

← →
Ш-К (2004-11-05 14:35) [7]

> сначала тебе требуется узнать состояние n-ного бита

Не надо мне этого узнавать.
Что я буду знать, если, например, 3-й бит ноль? Как мне эту информацию сопоставить с поиском 3-го елемента в переменной?

А вот если отсчитать 3 встреченных единичных бита. То по найненному индексу последнего(если угодно: по фиксированному индексу простого битового массива) возможно выудить сам эломент.

← →
Digitman © (2004-11-05 15:12) [8]

> Что я буду знать, если, например, 3-й бит ноль? Как мне
> эту информацию сопоставить с поиском 3-го елемента в переменной?

так и сопоставляй !

3-й эл-т в массиве и есть 3-й бит. И этот бит м.б как сброшен, так и установлен

поясняю.

пусть мн-во задано так :

type

TMySetItem = (Вася, Петя, Гоша, Дуся);
//Вася - это 0-й индекс
//Петя - это 1-й индекс
//Гоша - это 2-й индекс
//Дуся - это 3-й индекс

TMySet = set of TMySetItem;

//резервируем массив длиной 1 байт
var
MySet: TMySet;
...

if Дуся in MySet then .. //истина, если Дуся - в компании,т.е. 3-й бит байта, соотнесенного переменной MySet, взведен

← →
Digitman © (2004-11-05 15:18) [9]

> Ш-К

а без цикла - только в асм-блоке специальной инструкцией

читаем мануал от Интел :

BSF—Bit Scan Forward
Description
Searches the source operand (second operand) for the least significant set bit (1 bit). If a least
significant 1 bit is found, its bit index is stored in the destination operand (first operand). The
source operand can be a register or a memory location; the destination operand is a register. The
bit index is an unsigned offset from bit 0 of the source operand. If the contents source operand
are 0, the contents of the destination operand is undefined.
Operation
IF SRC = 0
THEN
ZF ← 1;
DEST is undefined;
ELSE
ZF ← 0;
temp ← 0;
WHILE Bit(SRC, temp) = 0
DO
temp ← temp + 1;
DEST ← temp;
OD;
FI;
Flags Affected
The ZF flag is set to 1 if all the source operand is 0; otherwise, the ZF flag is cleared. The CF,
OF, SF, AF, and PF, flags are undefined.
Opcode Instruction Description
0F BC BSF r16,r/m16 Bit scan forward on r/m16
0F BC BSF r32,r/m32 Bit scan forward on r/m32

← →
Digitman © (2004-11-05 15:25) [10]

> Ш-К

строго говоря, без цикла в общем случае, никак не обойтись.

BSF работает с src-операндом размером в
- байт (мн-во не более чем из 8-ми элементов)
- слово (мн-во не более чем из 16-ти элементов)
- дв.слово (мн-во не более чем из 32-х элементов)

все прочие случаи приводят к циклическому вызову BSF

← →
DiamondShark © (2004-11-05 18:11) [11]

Странный вообще вопрос.
Для множеств нет вообще понятия "n-ый элемент".

Какой порядок имеется в виду?

← →
Ш-К (2004-11-09 10:40) [12]

Есть переменная типа множество (замете, не тип, а уже переменная).
Элементы, "содержащиеся" в переменной, заносятся в комбобох. Само-собой итемов у комбобоха каждый раз разное количество.
Нужно сопоставить итем, выбранный юзером, элементу множества.

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

← →
pasha_golub © (2004-11-09 10:46) [13]

Я чего-то не пойму, блин, заварушки...

TCombobox.Items:TStrings ->
TStrings.Data[Index]:Pointer

То бишь каждому лементу заноси в Дата сопоставленный элемент.

← →
Ш-К (2004-11-09 11:07) [14]

pasha_golub © (09.11.04 10:46) [13]
Я так и знал, что мысли не туда пойдут.
TCombobox я привёл для наглядности. То, что вы предлагаете, это индексирование при заносе. Если нельзя решить задачу без индесирования, так и скажите.

Повтроряюсь.
Есть тип множества, анцестируемый от перечисления.
Есть переменная этого типа.
Есть номер(инт) элемента в переменной.
Найти элемент.
Информации достаточно.

← →
Digitman © (2004-11-09 11:21) [15]

> Ш-К (09.11.04 11:07) [14]

ты никогда не задавался себе вопросом, каким образом Инспектор объектов редактирует и показывает содержимое некоего св-ва типа "множество" некоего выбранного компонента ?

так вот задайся для начала ... иди в модуль DsgnIntf.pas и изучи этот вопрос, начав с класса TSetProperty ... тогда и велосипед изобретать не придется

← →
Ш-К (2004-11-09 11:31) [16]

Digitman © (09.11.04 11:21) [15]
Задавался. Он показывает все элементы из описания типа множества.
Чуствуете разницу между типом и переменной, которая может содержать один элемент, и даже быть и пустой?

← →
pasha_golub © (2004-11-09 11:43) [17]

Придется бежать по битовому массиву, но я тут ничего сложного не вижу абсолютно. А вот что я вижу, так это не удачное планирование, рах приходится извращаться таким вот образом.

> Ш-К (09.11.04 11:31) [16]

> Задавался

значит плохо задавался.

> Он показывает все элементы из описания типа множества

не боги горшки обжигают.
есть реализация метода TSetProperty.GetValue, в теле которого есть цикл по всем эл-там мн-ва .. в цикле отбираются только эл-ты мн-ва, прошедшие IN-проверку .. каждая IN-проверка - это асм-инструкция BT

> Чуствуете разницу между типом и переменной

я чувствую одно - у тебя путаница в голове

> Ш-К (09.11.04 11:31) [16]

вот оригинальный код :

function TSetProperty.GetValue: string;
var
S: TIntegerSet;
TypeInfo: PTypeInfo;
I: Integer;
begin
Integer(S) := GetOrdValue;
TypeInfo := GetTypeData(GetPropType)^.CompType^;
Result := "[";
//вот он - цикл по всем битам "переменной", содержащей мн-во !!
for I := 0 to SizeOf(Integer) * 8 - 1 do
// i-й бит взведен ?
if I in S then
//да, взведен.
begin
//ЧТО мешает тебе вместо нижеследующих строчек реализовать свой код ?
if Length(Result) <> 1 then Result := Result + ",";
Result := Result + GetEnumName(TypeInfo, I);
end;
Result := Result + "]";
end;

Ш-К (09.11.04 11:07) [14]

> Есть номер(инт) элемента в переменной.

Вы можете толком объяснить, что Вы понимаете под номером элемента в переменной?

← →
Ш-К (2004-11-09 13:36) [21]

Digitman © (09.11.04 12:03) [19]
А есть отличия между:
Семен Сорокин © (05.11.04 12:42) [1] и
Digitman © (09.11.04 12:03) [19]?

> Ш-К (09.11.04 13:36) [21]

так-с ..

караул устал.

давай уже описывай КОНКРЕТНУЮ задачу.

безо всяких там "привел для наглядности"..

т.е. так как ее решение хочет видеть юзер .. а не твои инсинуации ..

← →
Ш-К (2004-11-10 09:31) [23]

Digitman © (09.11.04 13:47) [22]
Большое спасибо, но, имхо , решение уже звучало.
Без разницы, что перебирать: множество на вхождение элемента или битовый массив.

Всем спасибо.

> Ш-К (10.11.04 09:31) [23]

> Без разницы, что перебирать: множество на вхождение элемента
> или битовый массив

Совершенно верно.

Каждая Паскаль-конструкция

SomeSetItem IN SomeSet

в конечном итоге сводится к генерации компилятором соотв. маш.инструкции

BT (Bit Test)

у которой в числе операндов фигурируют все те же SomeSetItem (индекс бита) и SomeSet (нач.адрес блока памяти, состояния битов которого и определяет принадлежность множеству тех или иных элементов)

цикл.вызов IN-оператора приводит, соотв-но, к цикл.вызову BT-инструкции

Поиск элемента множества по его естественному порядку. Найти похожие ветки