public bool
NavigateKey(K key)
{
// Устанавливаем индекс
элемента в 0.
_currentElementIndex = 0;
// Если есть второй
уровень...
if (_pageCount > 1)
{
// Перебираем грани
int hi = _pageCount -
1;
int lo = 0;
while (lo
<= hi)
{
int i =
(lo + hi) >> 1;
int result
= _comparer.Compare(NodeArray[i].Key, key);
if (result
< 0)
lo = i +
1;
else
{
hi = i - 1;
if (result == 0)
{
// Ключ найден на
2 уровне. Устанавливаем текущую
// страницу
CurrentLeafPage.
_currentPageIndex
= i;
CurrentLeafPage =
NodeArray[_currentPageIndex].ChildPage;
_selected = true;
return true;
}
}
}
// Ключ не найден на 2
уровне.
// Проверяем на
возможность того, что искомый ключ –
// наименьший из
имеющихся в объекте.
if (hi < 0)
{
// Данный ключ меньше
наименьшего хранимого ключа.
// Встаем на самый
первый элемент двухуровневого массива
_currentPageIndex = 0;
CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage;
_selected = false;
// Возвращаем
информацию о том, что ключ не найден.
return false;
}
else
{
// Данный ключ
попадает в диапазон ключей нижележащей страницы.
// Изменяем текущую
страницу CurrentLeafPage на найденную дочернюю
// страницу
// Устанавливаем текущий индекс ключа на листовой
странице в 1,
// т.к. 0 уже проверяли.
_currentElementIndex = 1;
}
}
// Пытаемся найти индекс
искомого ключа или индекс, в котором он должен
// был находиться.
hi =
CurrentLeafPage.Count - 1;
lo = _currentElementIndex;
while (lo
<= hi)
{
int i = (lo
+ hi) >> 1;
int result =
_comparer.Compare(CurrentLeafPage.PageItems[i].Key, key);
if (result
< 0)
lo = i +
1;
else
{
hi = i -
1;
if (result
== 0)
{
// Нашли!
_currentElementIndex = i;
_selected = true;
return
true;
}
}
}
// Не нашли...
_selected =
false;
// Помещаем в
_currentElementIndex позицию в которую
// можно добавить элемент с искомым ключом.
_currentElementIndex =
lo;
return false;
}
// Процедура вставки в текущую
позицию
private void
Insert(K Key)
{
// Вставляем ключ в
текущую позицию, расширяя тем самым массив на 1 элемент.
// Сдвигаем элементы,
чтобы освободить место для вставляемого.
Array.Copy(CurrentLeafPage.PageItems,
_currentElementIndex,
CurrentLeafPage.PageItems,
_currentElementIndex + 1,
CurrentLeafPage.Count - _currentElementIndex);
// Увеличиваем количество хранимых элементов на
странице и вставляем ключ.
CurrentLeafPage.Count++;
CurrentLeafPage.PageItems[_currentElementIndex].Key = Key;
if
(_currentElementIndex==0)
NodeArray[_currentPageIndex].Key = key;
version++; // Произошли изменения, увеличиваем
текущую версию.
//
// Если текущая страница
листовая полностью заполнена,
// то существуют 2
варианта. Можно либо перенести элемент с текущей
// страницы на соседнюю,
либо разбить страницу на 2.
//
if
(CurrentLeafPage.Count == BTConst.MaxCount)
{
// Страница полностью
заполнена.
// Если второго уровня
нет...
if (_pageCount == 1)
{
// ... то создаем
второй уровень.
//
// Для этого делим
текущую страницу пополам...
LeafPage<K,V> NewPage = new
LeafPage<K,V>();
// ...исправляем ссылки в полях NextPage и PriorPage
// чтобы можно было
осуществлять сквозную навигацию
// по листовым
страницам.
CurrentLeafPage.NextPage = NewPage;
NewPage.PriorPage =
CurrentLeafPage;
// Перемещаем
половину элементов исходного массива в новый.
Array.Copy(CurrentLeafPage.PageItems,
BTConst.MidlCount,
Array.Clear(CurrentLeafPage.PageItems, BTConst.MidlCount, BTConst.MidlCount);
// Создаем массив второго уровня и помещаем в него
ссылки
// на листовые
страницы.
NodeArray = new
NodeItem[BTConst.MaxCount];
_pageCount = 2; // Теперь страниц две.
NodeArray[0].Key = CurrentLeafPage.PageItems[0].Key;
NodeArray[0].ChildPage = CurrentLeafPage;
NodeArray[1].Key = NewPage.PageItems[0].Key;
NodeArray[1].ChildPage = NewPage;
// Задаем количество
элементов на страницах.
CurrentLeafPage.Count =
BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Если текущий элемент переместился на новую
страницу...
if (_currentElementIndex
>= BTConst.MidlCount)
{
// Изменяем
значение текущей страницы на новое...
CurrentLeafPage =
NewPage;
// ... и текущего
индекса на ней.
_currentElementIndex -= BTConst.MidlCount;
}
}
else
{
// Если второй
уровень уже существует.
// Если есть страница
слева от текущей...
LeafPage<K,V> LeftPage =
CurrentLeafPage.PriorPage;
if (LeftPage != null)
{
// ... и она
заполнена менее, чем на MaxFill (3/4)...
if (LeftPage.Count <= BTConst.MaxFill)
{
// можно
перекинуть значения на левую страницу.
// Находим нужное
количесво элементов для переброски.
int MoveCount = (BTConst.MaxCount -
LeftPage.Count) / 2;
// Перемещаем начальные элементы из текущей страницы
// в конец левой
страницы...
Array.Copy(CurrentLeafPage.PageItems, 0,
LeftPage.PageItems, LeftPage.Count,
MoveCount);
// И сдвигаем оставшиеся элементы страницы в начало.
Array.Copy(CurrentLeafPage.PageItems,
MoveCount,
CurrentLeafPage.PageItems, 0, CurrentLeafPage.Count - MoveCount);
// Затираем перемещенные элементы.
Array.Clear(CurrentLeafPage.PageItems,
CurrentLeafPage.Count - MoveCount, MoveCount);
// Так как
нулевой элемент на странице изменился, необходимо
//
откорректировать значение ключа, ссылающегося на эту страницу
// в массиве
верхнего уровня.
// Исправляем
значение ключа в верхнем уровне так, чтобы его
// значение было
равным значению ключа нулевого элемента
//
соответствующей листовой страницы.
NodeArray[_currentPageIndex].Key = CurrentLeafPage.PageItems[0].Key;
// Текущий ключ
был перемещен.
// Если он
переместился на левую страницу, изменяем значение
// текущей
страницы и текущего индекса на ней так, чтобы они
// указывали на вставленный ключ.
if
(_currentElementIndex < MoveCount)
{
_currentElementIndex += LeftPage.Count;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
CurrentLeafPage = LeftPage;
}
else
{
_currentElementIndex -= MoveCount;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
}
return;
}
// Если с левой
страницей не получилось, попробуем с правой.
// Код этого шага
аналогичен вышеприведенному.
// Его можно найти в
файле, сопровождающем статью.
...
// Не получилось
перебросить элементы на соседние страницы,
// так как они
заполнены.
// Выделяем новую
страницу аналогично тому, как это делалось выше,
// при выделении
верхнего уровня, за тем исключением, что нужно
// скорректировать
ссылки на близлежащие листовые страницы.
// Этот код пропущен
для краткости.
...
// Вставляем ссылку
на новую страницу в массив верхнего уровня
Array.Copy(NodeArray, _currentPageIndex +
1, NodeArray,
_currentPageIndex + 2, _pageCount - _currentPageIndex - 1);
NodeArray[_currentPageIndex + 1].Key = NewPage.PageItems[0].Key;
NodeArray[_currentPageIndex + 1].ChildPage = NewPage;
CurrentLeafPage.Count = BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Проверяем текущую
позицию вставляемого элемента (код пропущен)
...
// Если массив верхнего
уровня полностью заполнен просто увеличиваем
// его емкость в 2
раза (в Б+деревьях в этом случае выстраивается
// новый уровень).
if
(_pageCount == NodeArray.Length)
{
NodeItem[] NewNodeArray = new NodeItem[2 * _pageCount];
Array.Copy(NodeArray, 0, NewNodeArray, 0, _pageCount);
NodeArray = NewNodeArray;
}
}
}
}
|