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

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

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

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

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

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

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, которые затем используются только один раз.

Для определения состояния 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). В противном случае действуем по известной схеме:

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

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

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

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

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));
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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;
	}
}

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

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

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

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? Вот так-то лучше:

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

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

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

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

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}";
}

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

Информатика-54© А. Н. Швец