Хранит данные в массиве массивов. В случае добавления данных изменяться может только общий массив. Но его можно изначально сделать большим -(вместимость списка = размер массива x 2 ^ BlockSize).
Проверками границ особо не заботился.
На хрена такой класс нужен - слабо представляю.
Синтаксис:
Используется csharp
public class JaggedList<T>
{
private const int BlockSize = 10; // сделать 2 для теста
private const int BlockOffset= 1 << BlockSize;
private const int BlockMask = BlockOffset - 1;
private T[][] _intances;
public int count;
public int capacity;
public T this[int index]
{
get
{
if(index < 0 || index >= capacity) throw new IndexOutOfRangeException();
return _intances[index >> BlockSize][index & BlockMask];
}
set
{
if (index < 0 || index >= capacity) throw new IndexOutOfRangeException();
_intances[index >> BlockSize][index & BlockMask] = value;
}
}
public JaggedList(int cap = 4)
{
_intances = new T[(cap >> BlockSize) + 1][];
Expand(cap);
}
public void Expand(int newCapacity)
{
var block = capacity >> BlockSize;
var newBlock = newCapacity >> BlockSize;
if (newBlock >= _intances.Length) Array.Resize(ref _intances, newBlock + 1);
for (var i = block; i <= newBlock; i++)
{
if(_intances[i] == null) _intances[i] = new T[BlockOffset];
}
capacity = newCapacity;
}
public void Add(T item)
{
if(count + 1 >= capacity) Expand(capacity << 1);
//Expand(capacity + BlockOffset); ?? обычно оптимально по степеням двойки
this[count] = item;
count++;
}
private void MoveRangeRight(int index, int rangeSize)
{
if(count + rangeSize >= capacity) Expand(count + rangeSize);
for (var i = count - 1; i >= index; i--)
{
var newIndex = i + rangeSize;
_intances[newIndex >> BlockSize][newIndex & BlockMask] =
_intances[i >> BlockSize][i & BlockMask];
}
count += rangeSize;
}
public void InsertRange(int index, IList<T> items)
{
MoveRangeRight(index, items.Count);
for (var i = 0; i < items.Count; i++)
this[index + i] = items[i];
}
public void Insert(int index, T item)
{
MoveRangeRight(index, 1);
this[index] = item;
}
public void RemoveRange(int index, int rangeSize)
{
for (var i = index + rangeSize; i < count; i++)
{
var newIndex = i - rangeSize;
_intances[newIndex >> BlockSize][newIndex & BlockMask] =
_intances[i >> BlockSize][i & BlockMask];
}
//Call T Finalizer
for (var i = count - rangeSize; i < count; i++)
{
_intances[i >> BlockSize][i & BlockMask] = default(T);
}
count -= rangeSize;
}
public void Clear()
{
for (var i = 0; i < count; i++)
_intances[i >> BlockSize][i & BlockMask] = default(T);
count = 0;
}
//некрасиво, но предельно прозрачно
public List<T> ToList()
{
var list = new List<T>(capacity);
for(var i = 0; i < count; i++) list.Add(this[i]);
return list;
}
}
{
private const int BlockSize = 10; // сделать 2 для теста
private const int BlockOffset= 1 << BlockSize;
private const int BlockMask = BlockOffset - 1;
private T[][] _intances;
public int count;
public int capacity;
public T this[int index]
{
get
{
if(index < 0 || index >= capacity) throw new IndexOutOfRangeException();
return _intances[index >> BlockSize][index & BlockMask];
}
set
{
if (index < 0 || index >= capacity) throw new IndexOutOfRangeException();
_intances[index >> BlockSize][index & BlockMask] = value;
}
}
public JaggedList(int cap = 4)
{
_intances = new T[(cap >> BlockSize) + 1][];
Expand(cap);
}
public void Expand(int newCapacity)
{
var block = capacity >> BlockSize;
var newBlock = newCapacity >> BlockSize;
if (newBlock >= _intances.Length) Array.Resize(ref _intances, newBlock + 1);
for (var i = block; i <= newBlock; i++)
{
if(_intances[i] == null) _intances[i] = new T[BlockOffset];
}
capacity = newCapacity;
}
public void Add(T item)
{
if(count + 1 >= capacity) Expand(capacity << 1);
//Expand(capacity + BlockOffset); ?? обычно оптимально по степеням двойки
this[count] = item;
count++;
}
private void MoveRangeRight(int index, int rangeSize)
{
if(count + rangeSize >= capacity) Expand(count + rangeSize);
for (var i = count - 1; i >= index; i--)
{
var newIndex = i + rangeSize;
_intances[newIndex >> BlockSize][newIndex & BlockMask] =
_intances[i >> BlockSize][i & BlockMask];
}
count += rangeSize;
}
public void InsertRange(int index, IList<T> items)
{
MoveRangeRight(index, items.Count);
for (var i = 0; i < items.Count; i++)
this[index + i] = items[i];
}
public void Insert(int index, T item)
{
MoveRangeRight(index, 1);
this[index] = item;
}
public void RemoveRange(int index, int rangeSize)
{
for (var i = index + rangeSize; i < count; i++)
{
var newIndex = i - rangeSize;
_intances[newIndex >> BlockSize][newIndex & BlockMask] =
_intances[i >> BlockSize][i & BlockMask];
}
//Call T Finalizer
for (var i = count - rangeSize; i < count; i++)
{
_intances[i >> BlockSize][i & BlockMask] = default(T);
}
count -= rangeSize;
}
public void Clear()
{
for (var i = 0; i < count; i++)
_intances[i >> BlockSize][i & BlockMask] = default(T);
count = 0;
}
//некрасиво, но предельно прозрачно
public List<T> ToList()
{
var list = new List<T>(capacity);
for(var i = 0; i < count; i++) list.Add(this[i]);
return list;
}
}
Проверка работы:
Синтаксис:
Используется csharp
var jaggedList = new JaggedList<int>(100);
for (var i = 0; i < 100; i++)
{
jaggedList.Add(i);
}
var l1 = jaggedList.ToList();
jaggedList.InsertRange(2, new int[]{105,106,107});
var l2 = jaggedList.ToList();
jaggedList.RemoveRange(5, 3);
var l3 = jaggedList.ToList();
for (var i = 0; i < 100; i++)
{
jaggedList.Add(i);
}
var l1 = jaggedList.ToList();
jaggedList.InsertRange(2, new int[]{105,106,107});
var l2 = jaggedList.ToList();
jaggedList.RemoveRange(5, 3);
var l3 = jaggedList.ToList();