Реализация методов класса BitSetSimple
Пред. Глава 39. Битовая реализация числового множества След.

Реализация методов класса BitSetSimple

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

Методы add и delete

Начнём с простого: методов add и delete. Как мы уже писали, добавление и удаление числа реализуется как установка или очистка некоторого бита в строке. 

Perl
sub add($)
{
	shift->set(shift, 1);
}

sub delete($)
{
	shift->set(shift, 0);
}

Несмотря на то, что метод set ещё не готов, мы им уже воспользовались. Первый shift (слева от ->) в телах этих процедур вычисляется первым по счёту, и возвращает сам объект. Потом для этого объекта вызывается метод set, первый параметр которого, добавляемое/удаляемое число, подбирается при помощи второго shift. Второй параметр при вызове set истинный или ложный, в зависимости от того, добавляется или удаляется число. Приведённый код методов add и delete является укороченной версией следующего кода: 

Perl
sub add($)
{
	my $self=shift;
	my $i=shift;
	$self->set($i, 1);
}

sub delete($)
{
	my $self=shift;
	my $i=shift;
	$self->set($i, 0);
}

Короткая версия не требует создания локальных переменных $self и $i, которые затем используются только один раз.

Метод get

Для определения состояния i-го бита в битовой строке нужно, во первых, получить эту строку. Вспомним, что объект класса BitSetSimple является по совместительству ссылкой на нужную нам битовую строку. Саму строку можно получить, разадресовав ссылку при помощи оператора разадресования ${…} ссылки на скаляр: ${$self}. Поскольку выражение-ссылка в фигурных скобках является просто переменной, можно то же самое записать короче: $$self.

Во-вторых, нужно вычислить местоположение x байта, содержащего i-й бит в строке, и положение y бита в этом байте. Как мы уже выяснили, x = i div 8 , y = i mod 8 . Первое из выражений на Perl записывается как int($i/8), второе — как $i % 8.

Нужно иметь в виду, что x-го байта в битовой строке может не найтись, но в этом случае числа i множество не содержит. Признаком этой ситуации является выполнение неравенства length $$self<=int($i/8). В противном случае действуем по известной схеме: 

Perl
my $x=int($i/8);				находим номер байта
my $y=$i % 8;					находим номер бита в этом байте
my $char=substr $$self, $x, 1;	извлекаем $x-й символ из битовой строки
my $byte=ord $char;				находим числовое значение этого символа
my $result=$byte&(1<<$y);		переменная $result содержит результат проверки
return $result;					возвращаем $result

Все определяемые здесь переменные используются однократно, и без них можно было бы обойтись, что мы и сделаем: 

Perl
return ord(substr $$self, int($i/8), 1)&(1<<($i % 8));

Метод get готов: 

Perl
sub get($)
{
	my $self=shift;
	my $i=shift;
	return 0 if length $$self<=int($i/8);
	return ord(substr $$self, int($i/8), 1)&(1<<($i % 8));
}

Метод set

Для начала отправим параметры в соответствующие переменные: 

Perl
my $self=shift;
my $i=shift;
my $value=shift;

Если битовая строка имеет недостаточную длину, добавим в её конец необходимое количество нулевых байтов (точнее, символов, чьё числовое значение равно нулю). Для такого символа есть литеральное представление \0 (конечно, оно работает в ""-строках). Выражение "\0" можно было бы заменить на chr 0. 

Perl
while(length $$self<=int($i/8))
{
	$$self.="\0";
}

Теперь у битовой строки достаточная длина, и она содержит интересующий нас байт. Извлечём его: 

Perl
my $byte=ord substr $$self, int($i/8), 1;

В зависимости от значения переменной $value нужно или установить, или очистить $i-й бит. Как это сделать, мы знаем: 

Perl
if($value)
{
	$byte|=(1<<($i % 8));
}
else
{
	$byte&=~(1<<($i % 8));
}

Вставим изменённый байт (вернее, соответствующий ему символ) на старое место в битовой строке: 

Perl
substr $$self, int($i/8), 1, chr $byte;

Если в битовой строке после всех этих действий образовались нулевые символы в конце, удалим их (процедура chop удаляет последний символ в строке): 

Perl
while(length $$self and (substr $$self, -1, 1) eq "\0")
{
	chop $$self;
}

Обратите внимание на второй параметр при вызове substr. Это должен быть номер символа в строке, но он отрицательный. В этом случае место начала подстроки отсчитывается от конца строки. Таким образом, выражение substr($$self, -1, 1) возвращает последний символ в строке. Можно было бы написать даже так: substr($$self, -1) (не указывая длину подстроки). Если длина подстроки не задана, подстрока простирается до самого конца строки. 

Perl
sub set($$)
{
	my $self=shift;
	my $i=shift;
	my $value=shift;
	while(length $$self<=int($i/8))
	{
		$$self.="\0";
	}
	my $byte=ord substr $$self, int($i/8), 1;
	if($value)
	{
		$byte|=(1<<($i % 8));
	}
	else
	{
		$byte&=~(1<<($i % 8));
	}
	substr $$self, int($i/8), 1, chr $byte;
	while(length $$self and (substr $$self, -1) eq "\0")
	{
		chop $$self;
	}
}

Метод toString

Определим переменную $string, в которой должно оказаться строковое представление множества (не окружённое фигурными скобками, они будут добавлены позднее). 

Perl
my $self=shift;
my $string='';

Затем следует совершенно очевидный двойной цикл: во внешнем цикле перебираются байты в битовой строке, во внутреннем — биты этих байтов. Если какой-то бит установлен, вычисляем соответствующее ему число $i (для этого используем выражение 8*$x+$y) и добавляем это число в строку $string вместе с последующей запятой. 

Perl
for(my $x=0; $x<length $$self; $x++)
{
	for(my $y=0; $y<8; $y++)
	{
		my $i=8*$x+$y;
		$string.="$i," if $self->get($i);
	}
}

Написав это, мы подумали: нельзя ли короче? Зачем перебирать номера байтов и битов, чтобы затем вычислять по ним число $i, когда можно организовать перебор самих чисел $i? Вот так-то лучше: 

Perl
for(my $i=0; $i<8*length $$self; $i++)
{
	$string.="$i," if $self->get($i);
}

Если этот цикл хоть раз сработает, после последнего добавленного в строку $string числа окажется запятая, которая там не нужна. Уберём её, и возвратим строку $string, не забывая про закрывающую фигурную скобку: 

Perl
chop $string if (substr $string, -1) eq ',';
return "{$string}";

Всё в сборе будет выглядеть так: 

Perl
sub toString()
{
	my $self=shift;
	my $string='';
	for(my $i=0; $i<8*length $$self; $i++)
	{
		$string.="$i," if $self->get($i);
	}
	chop $string if (substr $string, -1) eq ',';
	return "{$string}";
}

Модуль готов.

Пред. Наверх След.
Глава 39. Битовая реализация числового множества Начало Готовая программа (предварительная версия)
Информатика-54© А. Н. Швец