An implementation of an index of values that are stored across an array of blocks. More...

Inheritance diagram for Deveel.Data.Index.BlockIndexBase< T >:

Classes
class	Enumerator

Public Member Functions
void	Insert (int index, T value)

void	Add (T value)

T	RemoveAt (int index)

bool	Contains (T value)

void	InsertSort (T value)

bool	UniqueInsertSort (T value)

bool	RemoveSort (T value)

bool	Contains (object key, IIndexComparer< T > comparer)

void	InsertSort (object key, T value, IIndexComparer< T > comparer)

T	RemoveSort (object key, T value, IIndexComparer< T > comparer)

int	SearchLast (object key, IIndexComparer< T > comparer)

int	SearchFirst (object key, IIndexComparer< T > comparer)

IIndexEnumerator< T >	GetEnumerator ()

IIndexEnumerator< T >	GetEnumerator (int startOffset, int endOffset)

Protected Member Functions
	BlockIndexBase ()

	BlockIndexBase (IEnumerable< IIndexBlock< T >> blocks)

	BlockIndexBase (IEnumerable< T > values)

	BlockIndexBase (IIndex< T > index)

abstract IIndexBlock< T >	NewBlock ()
	Creates a new IIndexBlock<T> for the given implementation. More...

virtual void	OnDeleteBlock (IIndexBlock< T > block)
	Called when the class decides the given IIndexBlock<T> is no longer needed. More...

Package Functions
void	CopyToArray (T[] array, int offset, int length)
	Copies the data from each block into the given int[] array. More...

Properties
List< IIndexBlock< T > >	Blocks `[get, private set]`

bool	IsReadOnly `[get, set]`

int	Count `[get, private set]`

T	this[int index] `[get]`

Private Member Functions
IIndexBlock< T >	InsertBlock (int index, IIndexBlock< T > block)
	Inserts a block at the given position in the index. More...

void	RemoveBlock (int index)
	Removes a block from the given position in the index. More...

void	InsertIntoBlock (T value, int blockIndex, IIndexBlock< T > block, int position)
	Inserts a value in the given block position in the list. More...

T	RemoveFromBlock (int blockIndex, IIndexBlock< T > block, int position)
	Removes the value from the given position in the specified block. More...

int	FindBlockContaining (object key, IIndexComparer< T > comparer)
	Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator. More...

int	FindLastBlock (object key, IIndexComparer< T > comparer)
	Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator. More...

int	FindFirstBlock (object key, IIndexComparer< T > c)
	Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator. More...

int	FindLastBlock (T val)
	Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given value. More...

void	CheckImmutable ()
	Checks if the current index is mutable. More...

IEnumerator< T > IEnumerable< T >.	GetEnumerator ()

IEnumerator IEnumerable.	GetEnumerator ()

Static Private Member Functions
static bool	IsSmallerOrEqual (T x, T y)

static bool	IsGreaterOrEqual (T x, T y)

static bool	IsGreater (T x, T y)

static bool	IsSmaller (T x, T y)

Detailed Description

An implementation of an index of values that are stored across an array of blocks.

This allows for quicker insertion and deletion of values, including other memory saving benefits.

The class works as follows:

The index can contain any number of integer values.
Each value is stored within a block of integers A block is of finite size.
When a block becomes full, values are moved around until enough space is free. This may be by inserting a new block or by shifting informations from one block to another.
When a block becomes empty, it is removed.

The benefits of this system are that inserts and deletes are fast even for very large lists. There are no megabyte sized arraycopies. Also, the object could be extended to a version that pages un-used blocks to disk thus saving precious system memory.

Note: The following methods are not optimal: Item(int), Insert(int, T), RemoveAt(int).
Specifically, they slow as the specified index nears the end of large lists.

This type of structure is very fast for large sorted lists where values can be inserted at any position within the list. Care needs to be taken for lists where values are inserted and removed constantly, because fragmentation of the list blocks can occur. For example, adding 60,000 random entries followed by removing 50,000 random entries will result in many only partially filled blocks. Since each block takes a constant amount of memory, this may not be acceptable.

Type Constraints

T	:	IComparable<T>
T	:	IEquatable<T>

Definition at line 63 of file BlockIndexBase_T.cs.

Constructor & Destructor Documentation

Deveel.Data.Index.BlockIndexBase< T >.BlockIndexBase ( )

inlineprotected

Definition at line 64 of file BlockIndexBase_T.cs.

                                    {
             Count = 0;
             IsReadOnly = false;
             Blocks = new List<IIndexBlock<T>>(10);
         }

Deveel.Data.Index.BlockIndexBase< T >.BlockIndexBase ( IEnumerable< IIndexBlock< T >> blocks )

inlineprotected

Definition at line 70 of file BlockIndexBase_T.cs.

             : this() {
             foreach (var block in blocks) {
                 Blocks.Add(block);
                 Count += block.Count;
             }
         }

Deveel.Data.Index.BlockIndexBase< T >.BlockIndexBase ( IEnumerable< T > values )

inlineprotected

Definition at line 78 of file BlockIndexBase_T.cs.

             : this() {
             foreach (var value in values) {
                 Add(value);
             }
         }

Deveel.Data.Index.BlockIndexBase< T >.BlockIndexBase ( IIndex< T > index )

inlineprotected

Definition at line 85 of file BlockIndexBase_T.cs.

             : this() {
             if (index is BlockIndexBase<T>) {
                 // Optimization for when the input list is a BlockIntegerList
                 var blockIndex = (BlockIndexBase<T>) index;
 
                 var inBlocks = blockIndex.Blocks;
                 int inBlocksCount = inBlocks.Count;
                 // For each block in 'blockIndex'
                 for (int i = 0; i < inBlocksCount; ++i) {
                     // get the block.
                     var block = inBlocks[i];
                     // Insert a new block in this object.
                     var destBlock = InsertBlock(i, NewBlock());
                     // Copy the contents of the source block to the new destination block.
                     block.CopyTo(destBlock);
                 }
 
                 // Set the size of the list
                 Count = blockIndex.Count; //count;
             } else {
                 // The case when IIntegerList type is not known
                 var i = index.GetEnumerator();
                 while (i.MoveNext()) {
                     Add(i.Current);
                 }
             }
 
             // If the given list is immutable then set this list to immutable
             if (index.IsReadOnly)
                 IsReadOnly = true;
         }

Member Function Documentation

void Deveel.Data.Index.BlockIndexBase< T >.Add ( T value )

inline

Definition at line 547 of file BlockIndexBase_T.cs.

                                  {
             CheckImmutable();
 
             int size = Blocks.Count;
             var block = Blocks[size - 1];
             InsertIntoBlock(value, size - 1, block, block.Count);
         }

void Deveel.Data.Index.BlockIndexBase< T >.CheckImmutable ( )

inlineprivate

Checks if the current index is mutable.

This is called before any mutable operations on the index: if the index is mutable and empty then an empty block is added to the index.

Exceptions

InvalidOperationException Thrown if the index is read-only.

Definition at line 499 of file BlockIndexBase_T.cs.

                                       {
             if (IsReadOnly)
                 throw new InvalidOperationException("Index is read-only.");
 
             // HACK: We have a side effect of checking whether the list is immutable.
             //   If the block list doesn't contain any entries we add one here.  This
             //   hack reduces the memory requirements.
             if (Blocks.Count == 0) {
                 InsertBlock(0, NewBlock());
             }
         }

bool Deveel.Data.Index.BlockIndexBase< T >.Contains ( T value )

inline

Definition at line 572 of file BlockIndexBase_T.cs.

                                       {
             int blockIndex = FindLastBlock(value);
 
             if (blockIndex < 0)
                 // We didn't find in the list, so return false.
                 return false;
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // Find, if not there then return false.
             return block.SearchLast(value) >= 0;
         }

bool Deveel.Data.Index.BlockIndexBase< T >.Contains	(	object	key,
		IIndexComparer< T >	comparer
	)

inline

Definition at line 684 of file BlockIndexBase_T.cs.

                                                                      {
             int blockIndex = FindBlockContaining(key, comparer);
 
             if (blockIndex < 0)
                 // We didn't find in the list, so return false.
                 return false;
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // Find, if not there then return false.
             return block.BinarySearch(key, comparer) >= 0;
         }

void Deveel.Data.Index.BlockIndexBase< T >.CopyToArray	(	T[]	array,
		int	offset,
		int	length
	)

inlinepackage

Copies the data from each block into the given int[] array.

Parameters

array
offset
length

The int[] array must be big enough to fit all the data in this list.

Definition at line 520 of file BlockIndexBase_T.cs.

                                                                      {
             if (array.Length < length || (offset + length) > Count)
                 throw new InvalidOperationException("Size mismatch.");
 
             foreach (var block in Blocks) {
                 offset += block.CopyTo(array, offset);
             }
         }

int Deveel.Data.Index.BlockIndexBase< T >.FindBlockContaining	(	object	key,
		IIndexComparer< T >	comparer
	)

inlineprivate

Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator.

Parameters

key
comparer

Returns

Definition at line 290 of file BlockIndexBase_T.cs.

                                                                                 {
             if (Count == 0)
                 return -1;
 
             int low = 0;
             int high = Blocks.Count - 1;
 
             while (low <= high) {
                 int mid = (low + high)/2;
                 var block = Blocks[mid];
 
                 // Is what we are searching for lower than the bottom value?
                 if (comparer.CompareValue(block.Bottom, (DataObject) key) > 0) {
                     high = mid - 1;
                 }
                     // No, then is it greater than the highest value?
                 else if (comparer.CompareValue(block.Top, (DataObject) key) < 0) {
                     low = mid + 1;
                 }
                     // Must be inside this block then!
                 else {
                     return mid;
                 }
             }
 
             return -(low + 1); // key not found.
         }

int Deveel.Data.Index.BlockIndexBase< T >.FindFirstBlock	(	object	key,
		IIndexComparer< T >	c
	)

inlineprivate

Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator.

Parameters

key
c

Returns

Definition at line 379 of file BlockIndexBase_T.cs.

                                                                     {
             if (Count == 0) {
                 return -1;
             }
 
             int low = 0;
             int high = Blocks.Count - 1;
 
             while (low <= high) {
 
                 if (high - low <= 2) {
                     for (int i = low; i <= high; ++i) {
                         var block1 = Blocks[i];
                         if (c.CompareValue(block1.Top, (DataObject) key) >= 0) {
                             if (c.CompareValue(block1.Bottom, (DataObject) key) <= 0)
                                 return i;
                             return -(i + 1);
                         }
                     }
                     return -(high + 1) - 1;
                 }
 
                 int mid = (low + high)/2;
                 var block = Blocks[mid];
 
                 // Is what we are searching for lower than the bottom value?
                 if (c.CompareValue(block.Bottom, (DataObject) key) > 0) {
                     high = mid - 1;
                 }
                     // No, then is it greater than the highest value?
                 else if (c.CompareValue(block.Top, (DataObject) key) < 0) {
                     low = mid + 1;
                 }
                     // Equal, so highest must be someplace between mid and high.
                 else {
                     high = mid;
                 }
             }
 
             return -(low + 1); // key not found.
         }

int Deveel.Data.Index.BlockIndexBase< T >.FindLastBlock	(	object	key,
		IIndexComparer< T >	comparer
	)

inlineprivate

Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given key value using the IIndexComparer<T> as a lookup comparator.

Parameters

key
comparer

Returns

Definition at line 327 of file BlockIndexBase_T.cs.

                                                                           {
             if (Count == 0)
                 return -1;
 
             int low = 0;
             int high = Blocks.Count - 1;
 
             while (low <= high) {
                 if (high - low <= 2) {
                     for (int i = high; i >= low; --i) {
                         var block1 = Blocks[i];
                         if (comparer.CompareValue(block1.Bottom, (DataObject) key) <= 0) {
                             if (comparer.CompareValue(block1.Top, (DataObject) key) >= 0)
                                 return i;
                             return -(i + 1) - 1;
                         }
                     }
                     return -(low + 1);
                 }
 
                 int mid = (low + high)/2;
                 var block = Blocks[mid];
 
                 // Is what we are searching for lower than the bottom value?
                 if (comparer.CompareValue(block.Bottom, (DataObject) key) > 0) {
                     high = mid - 1;
                 }
                     // No, then is it greater than the highest value?
                 else if (comparer.CompareValue(block.Top, (DataObject) key) < 0) {
                     low = mid + 1;
                 }
                     // Equal, so highest must be someplace between mid and high.
                 else {
                     low = mid;
                     if (low == high) {
                         return low;
                     }
                 }
             }
 
             return -(low + 1); // key not found.
         }

int Deveel.Data.Index.BlockIndexBase< T >.FindLastBlock ( T val )

inlineprivate

Uses a binary search algorithm to quickly determine the index of the IIndexBlock<T> within 'blocks' of the block that contains the given value.

Parameters

val

Returns

Definition at line 444 of file BlockIndexBase_T.cs.

                                          {
             if (Count == 0) {
                 return -1;
             }
 
             int low = 0;
             int high = Blocks.Count - 1;
 
             while (low <= high) {
 
                 if (high - low <= 2) {
                     for (int i = high; i >= low; --i) {
                         var block1 = Blocks[i];
                         if (IsSmallerOrEqual(block1.Bottom, val)) {
                             if (IsGreaterOrEqual(block1.Top, val))
                                 return i;
                             return -(i + 1) - 1;
                         }
                     }
                     return -(low + 1);
                 }
 
                 int mid = (low + high)/2;
                 var block = Blocks[mid];
 
                 // Is what we are searching for lower than the bottom value?
                 if (IsGreater(block.Bottom,val)) {
                     high = mid - 1;
                 }
                     // No, then is it greater than the highest value?
                 else if (IsSmaller(block.Top, val)) {
                     low = mid + 1;
                 }
                     // Equal, so highest must be someplace between mid and high.
                 else {
                     low = mid;
                     if (low == high) {
                         return low;
                     }
                 }
             }
 
             return -(low + 1); // key not found.
         }

IIndexEnumerator<T> Deveel.Data.Index.BlockIndexBase< T >.GetEnumerator ( )

inline

Definition at line 808 of file BlockIndexBase_T.cs.

                                                    {
             return GetEnumerator(0, Count - 1);
         }

IIndexEnumerator<T> Deveel.Data.Index.BlockIndexBase< T >.GetEnumerator	(	int	startOffset,
		int	endOffset
	)

inline

Definition at line 812 of file BlockIndexBase_T.cs.

                                                                                  {
             return new Enumerator(this, startOffset, endOffset);
         }

IEnumerator<T> IEnumerable<T>. Deveel.Data.Index.BlockIndexBase< T >.GetEnumerator ( )

inlineprivate

Definition at line 816 of file BlockIndexBase_T.cs.

                                                       {
             return GetEnumerator();
         }

IEnumerator IEnumerable. Deveel.Data.Index.BlockIndexBase< T >.GetEnumerator ( )

inlineprivate

Definition at line 820 of file BlockIndexBase_T.cs.

                                                 {
             return GetEnumerator();
         }

void Deveel.Data.Index.BlockIndexBase< T >.Insert	(	int	index,
		T	value
	)

inline

Definition at line 529 of file BlockIndexBase_T.cs.

                                                {
             CheckImmutable();
 
             int size = Blocks.Count;
             int start = 0;
             for (int i = 0; i < size; ++i) {
                 var block = Blocks[i];
                 int bsize = block.Count;
                 if (index >= start && index <= start + bsize) {
                     InsertIntoBlock(value, i, block, index - start);
                     return;
                 }
                 start += bsize;
             }
 
             throw new ArgumentOutOfRangeException("index");
         }

IIndexBlock<T> Deveel.Data.Index.BlockIndexBase< T >.InsertBlock	(	int	index,
		IIndexBlock< T >	block
	)

inlineprivate

Inserts a block at the given position in the index.

Parameters

index
block

Returns

Definition at line 165 of file BlockIndexBase_T.cs.

                                                                             {
             Blocks.Insert(index, block);
 
             // Point to next in the list.
             if (index + 1 < Blocks.Count) {
                 var nextBlock = Blocks[index + 1];
                 block.Next = nextBlock;
                 nextBlock.Previous = block;
             } else {
                 block.Next = null;
             }
 
             // Point to previous in the list.
             if (index > 0) {
                 var prevBlock = Blocks[index - 1];
                 block.Previous = prevBlock;
                 prevBlock.Next = block;
             } else {
                 block.Previous = null;
             }
 
             return block;
         }

void Deveel.Data.Index.BlockIndexBase< T >.InsertIntoBlock	(	T	value,
		int	blockIndex,
		IIndexBlock< T >	block,
		int	position
	)

inlineprivate

Inserts a value in the given block position in the list.

Parameters

value
blockIndex
block
position

Definition at line 223 of file BlockIndexBase_T.cs.

                                                                                                   {
             block.Insert(value, position);
 
             ++Count;
             // Is the block full?
             if (block.IsFull) {
                 // We need to move half of the data out of this block into either the
                 // next block or create a new block to store it.
 
                 // The size that we going to zap out of this block.
                 int moveSize = (block.Count/7) - 1;
 
                 // The block to move half the data from this block.
                 IIndexBlock<T> moveTo;
 
                 // Is there a next block?
                 if (blockIndex < Blocks.Count - 1) {
                     var nextBlock = Blocks[blockIndex + 1];
                     // Yes, can this block contain half the values from this block?
                     if (nextBlock.CanContain(moveSize)) {
                         moveTo = nextBlock;
                     } else {
                         // Can't contain so insert a new block.
                         moveTo = InsertBlock(blockIndex + 1, NewBlock());
                     }
 
                 } else {
                     // No next block so create a new block
                     moveTo = InsertBlock(blockIndex + 1, NewBlock());
                 }
 
                 // 'moveTo' should be set to the block we are to use to move half the
                 // data from this block.
                 block.MoveTo(moveTo, 0, moveSize);
             }
         }

void Deveel.Data.Index.BlockIndexBase< T >.InsertSort ( T value )

inline

Definition at line 586 of file BlockIndexBase_T.cs.

                                         {
             CheckImmutable();
 
             int blockIndex = FindLastBlock(value);
 
             if (blockIndex < 0) {
                 // Not found a block,
                 // The block to insert the value,
                 blockIndex = (-(blockIndex + 1)) - 1;
                 if (blockIndex < 0) {
                     blockIndex = 0;
                 }
             }
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // The point to insert in the block,
             int i = block.SearchLast(value);
             if (i < 0) {
                 i = -(i + 1);
             } else {
                 i = i + 1;
                 // NOTE: A block can never become totally full so it's always okay to
                 //   skip one ahead.
             }
 
             // Insert value into the block,
             InsertIntoBlock(value, blockIndex, block, i);
         }

void Deveel.Data.Index.BlockIndexBase< T >.InsertSort	(	object	key,
		T	value,
		IIndexComparer< T >	comparer
	)

inline

Definition at line 698 of file BlockIndexBase_T.cs.

                                                                                 {
             CheckImmutable();
 
             int blockIndex = FindLastBlock(key, comparer);
 
             if (blockIndex < 0) {
                 // Not found a block,
                 // The block to insert the value,
                 blockIndex = (-(blockIndex + 1)) - 1;
                 if (blockIndex < 0) {
                     blockIndex = 0;
                 }
             }
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // The point to insert in the block,
             int i = block.SearchLast(key, comparer);
             if (i < 0) {
                 i = -(i + 1);
             } else {
                 i = i + 1;
                 // NOTE: A block can never become totally full so it's always okay to
                 //   skip one ahead.
             }
 
             // Insert value into the block,
             InsertIntoBlock(value, blockIndex, block, i);
         }

static bool Deveel.Data.Index.BlockIndexBase< T >.IsGreater	(	T	x,
		T	y
	)

inlinestaticprivate

Definition at line 429 of file BlockIndexBase_T.cs.

                                                 {
             return x.CompareTo(y) > 0;
         }

static bool Deveel.Data.Index.BlockIndexBase< T >.IsGreaterOrEqual	(	T	x,
		T	y
	)

inlinestaticprivate

Definition at line 425 of file BlockIndexBase_T.cs.

                                                        {
             return x.CompareTo(y) >= 0;
         }

static bool Deveel.Data.Index.BlockIndexBase< T >.IsSmaller	(	T	x,
		T	y
	)

inlinestaticprivate

Definition at line 433 of file BlockIndexBase_T.cs.

                                                 {
             return x.CompareTo(y) < 0;
         }

static bool Deveel.Data.Index.BlockIndexBase< T >.IsSmallerOrEqual	(	T	x,
		T	y
	)

inlinestaticprivate

Definition at line 421 of file BlockIndexBase_T.cs.

                                                        {
             return x.CompareTo(y) <= 0;
         }

abstract IIndexBlock<T> Deveel.Data.Index.BlockIndexBase< T >.NewBlock ( )

protectedpure virtual

Creates a new IIndexBlock<T> for the given implementation.

Returns

Implemented in Deveel.Data.Index.BlockIndex< T >.

virtual void Deveel.Data.Index.BlockIndexBase< T >.OnDeleteBlock ( IIndexBlock< T > block )

inlineprotectedvirtual

Called when the class decides the given IIndexBlock<T> is no longer needed.

Parameters

block

Provided as an event for derived classes to intercept.

Definition at line 155 of file BlockIndexBase_T.cs.

155 {

156 }

T Deveel.Data.Index.BlockIndexBase< T >.RemoveAt ( int index )

inline

Definition at line 555 of file BlockIndexBase_T.cs.

                                      {
             CheckImmutable();
 
             int size = Blocks.Count;
             int start = 0;
             for (int i = 0; i < size; ++i) {
                 var block = Blocks[i];
                 int bsize = block.Count;
                 if (index >= start && index <= start + bsize) {
                     return RemoveFromBlock(i, block, index - start);
                 }
                 start += bsize;
             }
 
             throw new ArgumentOutOfRangeException("index");
         }

void Deveel.Data.Index.BlockIndexBase< T >.RemoveBlock ( int index )

inlineprivate

Removes a block from the given position in the index.

Parameters

index

Definition at line 193 of file BlockIndexBase_T.cs.

                                             {
             // Alter linked list pointers.
             IIndexBlock<T> newPrev = null;
             IIndexBlock<T> newNext = null;
             if (index + 1 < Blocks.Count) {
                 newNext = Blocks[index + 1];
             }
             if (index > 0) {
                 newPrev = Blocks[index - 1];
             }
 
             if (newPrev != null) {
                 newPrev.Next = newNext;
             }
             if (newNext != null) {
                 newNext.Previous = newPrev;
             }
 
             var beenRemoved = Blocks[index];
             Blocks.RemoveAt(index);
             OnDeleteBlock(beenRemoved);
         }

T Deveel.Data.Index.BlockIndexBase< T >.RemoveFromBlock	(	int	blockIndex,
		IIndexBlock< T >	block,
		int	position
	)

inlineprivate

Removes the value from the given position in the specified block.

Parameters

blockIndex
block
position

It returns the value that used to be at that position.

Returns

Definition at line 270 of file BlockIndexBase_T.cs.

                                                                                       {
             var oldValue = block.RemoveAt(position);
             --Count;
             // If we have emptied out this block, then we should remove it from the
             // list.
             if (block.IsEmpty && Blocks.Count > 1)
                 RemoveBlock(blockIndex);
 
             return oldValue;
         }

bool Deveel.Data.Index.BlockIndexBase< T >.RemoveSort ( T value )

inline

Definition at line 650 of file BlockIndexBase_T.cs.

                                         {
             CheckImmutable();
 
             int blockIndex = FindLastBlock(value);
 
             if (blockIndex < 0) {
                 // Not found a block,
                 // The block to remove the value,
                 blockIndex = (-(blockIndex + 1)) - 1;
                 if (blockIndex < 0) {
                     blockIndex = 0;
                 }
             }
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // The point to remove the block,
             int i = block.SearchLast(value);
             if (i < 0) {
                 // This means we can't found the value in the given block, so return
                 // false.
                 return false;
             }
 
             // Remove value into the block,
             var valRemoved = RemoveFromBlock(blockIndex, block, i);
             if (!value.Equals(valRemoved))
                 throw new InvalidOperationException("Incorrect value removed.");
 
             // Value removed so return true.
             return true;
         }

T Deveel.Data.Index.BlockIndexBase< T >.RemoveSort	(	object	key,
		T	value,
		IIndexComparer< T >	comparer
	)

inline

Definition at line 729 of file BlockIndexBase_T.cs.

                                                                              {
             CheckImmutable();
 
             // Find the range of blocks that the value is in.
             int origBlockIndex = FindFirstBlock(key, comparer);
             int blockIndex = origBlockIndex;
             int lastBlockIndex = Blocks.Count - 1;
 
             if (blockIndex < 0)
                 // Not found in a block,
                 throw new InvalidOperationException("Value (" + key + ") was not found in the list.");
 
             var block = Blocks[blockIndex];
             int i = block.IndexOf(value);
             while (i == -1) {
                 // If not found, go to next block
                 ++blockIndex;
                 if (blockIndex > lastBlockIndex)
                     throw new InvalidOperationException("Value (" + key + ") was not found in the list.");
 
                 block = Blocks[blockIndex];
                 // Try and find the value within this block
                 i = block.IndexOf(value);
             }
 
             // Remove value from the block,
             return RemoveFromBlock(blockIndex, block, i);
         }

int Deveel.Data.Index.BlockIndexBase< T >.SearchFirst	(	object	key,
		IIndexComparer< T >	comparer
	)

inline

Definition at line 783 of file BlockIndexBase_T.cs.

                                                                        {
             int blockNum = FindFirstBlock(key, comparer);
             int sr;
 
             if (blockNum < 0) {
                 // Guarenteed not found in any blocks so return start of insert block
                 blockNum = (-(blockNum + 1)); // - 1;
                 sr = -1;
             } else {
                 // We got a block, so find out if it's in the block or not.
                 var block = Blocks[blockNum];
 
                 // Try and find it in the block,
                 sr = block.SearchFirst(key, comparer);
             }
 
             int offset = 0;
             for (int i = 0; i < blockNum; ++i) {
                 var block = Blocks[i];
                 offset += block.Count;
             }
 
             return sr >= 0 ? offset + sr : -offset + sr;
         }

int Deveel.Data.Index.BlockIndexBase< T >.SearchLast	(	object	key,
		IIndexComparer< T >	comparer
	)

inline

Definition at line 758 of file BlockIndexBase_T.cs.

                                                                       {
             int blockIndex = FindLastBlock(key, comparer);
             int sr;
 
             if (blockIndex < 0) {
                 // Guarenteed not found in any blocks so return start of insert block
                 blockIndex = (-(blockIndex + 1)); // - 1;
                 sr = -1;
             } else {
                 // We got a block, so find out if it's in the block or not.
                 var block = Blocks[blockIndex];
 
                 // Try and find it in the block,
                 sr = block.SearchLast(key, comparer);
             }
 
             int offset = 0;
             for (int i = 0; i < blockIndex; ++i) {
                 var block = Blocks[i];
                 offset += block.Count;
             }
 
             return sr >= 0 ? offset + sr : -offset + sr;
         }

bool Deveel.Data.Index.BlockIndexBase< T >.UniqueInsertSort ( T value )

inline

Definition at line 617 of file BlockIndexBase_T.cs.

                                               {
             CheckImmutable();
 
             int blockIndex = FindLastBlock(value);
 
             if (blockIndex < 0) {
                 // Not found a block,
                 // The block to insert the value,
                 blockIndex = (-(blockIndex + 1)) - 1;
                 if (blockIndex < 0) {
                     blockIndex = 0;
                 }
             }
 
             // We got a block, so find out if it's in the block or not.
             var block = Blocks[blockIndex];
 
             // The point to insert in the block,
             int i = block.SearchLast(value);
             if (i < 0) {
                 i = -(i + 1);
             } else {
                 // This means we found the value in the given block, so return false.
                 return false;
             }
 
             // Insert value into the block,
             InsertIntoBlock(value, blockIndex, block, i);
 
             // Value inserted so return true.
             return true;
         }