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 на найденную дочернюю
// страницу
CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage;
// Устанавливаем текущий индекс ключа на листовой странице в 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,
NewPage.PageItems, 0, 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;
}
}
}
}
|
«Коллекциив .NET Framework Class Library». 
