Sequential Ordering Object Indexer
Pass in an object get back it is sequential index 0…n. Session specific indexing.
Example Classes at the bottom.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
public class ObjectIndexer
{
private const int BitWidth = 64;
private const int BucketDepth = 3;
private readonly FNV1a64 hasher;
internal int Count;
private long[] Indices;
internal int Length;
public List<int> loopcntlst = new List<int>();
internal object[] Objects;
private int Resizes;
public ObjectIndexer(int size = 0)
{
if (size == 0)
Length = 1607;
else
Length = size;
Count = 0;
Indices = new long[Length * BucketDepth];
Indices.Fill(-1);
Objects = new object[Length * BucketDepth];
Resizes = 0;
hasher = new FNV1a64();
}
public void Clear()
{
Count = 0;
Indices = new long[Length * BucketDepth];
Objects = new object[Length * BucketDepth];
}
private static bool IsPrimitive(object obj)
{
switch (Type.GetTypeCode(obj.GetType()))
{
case TypeCode.Boolean:
case TypeCode.Char:
case TypeCode.SByte:
case TypeCode.Byte:
case TypeCode.Int16:
case TypeCode.UInt16:
case TypeCode.Int32:
case TypeCode.UInt32:
case TypeCode.Single:
case TypeCode.String:
case TypeCode.Decimal:
case TypeCode.DateTime:
case TypeCode.Int64:
case TypeCode.UInt64:
case TypeCode.Double:
return true;
default:
return false;
}
}
private new bool Equals(object x, object y)
{
if (x == null || y == null)
return false;
var xp = IsPrimitive(x);
var yp = IsPrimitive(y);
if (xp != yp)
return false;
if (xp && yp)
return x.Equals(y);
var xb = x.GetBytes();
var yb = y.GetBytes();
if (xb.Length != yb.Length)
return false;
return xb.Compare(yb);
}
public long FindObject(object obj, out bool found)
{
var hashCode = hasher.ComputeHash(obj.GetBytes()).ToLong();
var StepPos = (hashCode & long.MaxValue) % Length;
var loopCnt = 0;
while (true)
{
loopCnt++;
if (loopCnt > BucketDepth * 8)
throw new Exception("Bucket Depth too low.");
var StartPos = (hashCode & long.MaxValue) % Length * BucketDepth;
for (var i = StartPos; i < StartPos + BucketDepth; ++i)
{
if (Objects[i] == null)
{
found = false;
loopcntlst.Add(loopCnt);
return i;
}
if (Equals(Objects[i], obj))
{
found = true;
loopcntlst.Add(loopCnt);
return i;
}
}
hashCode += StepPos;
}
}
public bool Contains(object item)
{
FindObject(item, out var found);
return found;
}
public long FindIndex(object obj)
{
long position;
bool found;
if (obj != null)
position = FindObject(obj, out found);
else
throw new ArgumentException("Object cannot be null.");
return found ? Indices[position] : -1;
}
public (long idx, bool found) GetIndex(object obj)
{
long position;
bool found;
if (obj != null)
position = FindObject(obj, out found);
else
throw new ArgumentException("Object cannot be null.");
long index;
if (!found)
{
Objects[position] = obj;
Indices[position] = Count++;
index = Indices[position];
if (Count > Length)
Resize();
}
else
{
index = Indices[position];
}
return (index, found);
}
public bool Add(object obj)
{
long position;
bool found;
if (obj != null)
position = FindObject(obj, out found);
else
throw new ArgumentException("Object cannot be null.");
if (!found)
if (Objects[position] == null)
{
Objects[position] = obj;
Indices[position] = Count++;
if (Count > Length)
Resize();
}
return found;
}
public int AddRange(IEnumerable<object> items)
{
return items.Sum(i => !Add(i) ? 0 : 1);
}
private void Resize()
{
Resizes++;
Length += Length * 2;
var idxArray = new long[Length * BucketDepth];
idxArray.Fill(-1);
var objArray = new object[Length * BucketDepth];
var cidx = Indices;
var cobjs = Objects;
Indices = idxArray;
Objects = objArray;
for (var i = 0; i < cobjs.Length; ++i)
if (cobjs[i] != null)
{
var position = FindObject(cobjs[i], out var D);
Objects[position] = cobjs[i];
Indices[position] = cidx[i];
}
}
public void TrimExcess()
{
var hi = 0;
for (var i = Length * BucketDepth - 1; i >= 0; --i)
if (Indices[i] != -1)
break;
else
hi = i;
Array.Resize(ref Objects, hi);
Array.Resize(ref Indices, hi);
Length = hi;
Recalculate();
}
private void Recalculate()
{
var idxArray = new long[Length * BucketDepth];
idxArray.Fill(-1);
var objArray = new object[Length * BucketDepth];
var cidx = Indices;
var cobjs = Objects;
Indices = idxArray;
Objects = objArray;
for (var i = 0; i < cobjs.Length; ++i)
if (cobjs[i] != null)
{
var position = FindObject(cobjs[i], out var D);
Objects[position] = cobjs[i];
Indices[position] = cidx[i];
}
}
public object[] ToArray()
{
var array = new object[Count];
var ptr = 0;
for (var i = 0; i < Objects.Length; ++i)
if (Objects[i] != null)
array[ptr++] = Objects[i];
return array;
}
public void ExceptWith(IEnumerable<object> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
if (Count == 0)
return;
if (Equals(other, this))
Clear();
else
foreach (var obj in other)
Remove(obj);
}
public void UnionWith(IEnumerable<object> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
foreach (var obj in other)
Add(obj);
}
public bool Overlaps(IEnumerable<object> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
return Count != 0 && other.Any(Contains);
}
public bool ContainsAllElements(IEnumerable<object> other)
{
return other.All(Contains);
}
public int RemoveWhere(Predicate<object> pred)
{
if (pred == null)
throw new Exception("The Predicate cannot be null.");
var matches = 0;
for (var i = 0; i < Objects.Length; ++i)
if (Objects[i] != null)
{
var obj = Objects[i];
if (pred(obj) && Remove(obj))
++matches;
}
return matches;
}
public bool Remove(object oldItem)
{
var pos = FindObject(oldItem, out var D);
if (!D)
return false;
Objects[pos] = null;
Indices[pos] = -1;
Count--;
return true;
}
}
Example HashSet Class Using Indexing.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class TestHashSetObjectIndexerIdx<T> : IEnumerable<T>
{
private T[] _array;
private ObjectIndexer Oi;
public TestHashSetObjectIndexerIdx(int size = 0)
{
Oi = new ObjectIndexer(size);
_array = new T[size];
}
public int Count => Oi.Count;
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public T[] ToArray()
{
return (T[]) _array.Clone();
}
public void Clear()
{
Oi.Clear();
Array.Clear(_array, 0, Oi.Length);
}
public bool Add(T item)
{
var idx = Oi.GetIndex(item);
if (_array.Length != Oi.Length)
Array.Resize(ref _array, Oi.Length);
_array[idx.idx] = item;
return idx.found;
}
public int AddRange(IEnumerable<T> items)
{
return items.Sum(i => !Add(i) ? 0 : 1);
}
public bool Contains(T item)
{
return Oi.ContainsObject(item);
}
public int FindEntry(T item)
{
return (int)Oi.FindIndex(item);
}
public IEnumerator<T> GetEnumerator()
{
return GetEnum();
}
public IEnumerator<T> GetEnum()
{
for (var i = 0; i < Count; i++)
if (_array[i] != null)
yield return _array[i];
}
}
Example HashSet Class Using Object Indexer as a Base Class:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class TestHashSetObjectIndexer<T> : IEnumerable<T>
{
private ObjectIndexer Oi;
public TestHashSetObjectIndexer(int size = 0)
{
Oi = new ObjectIndexer(size);
}
public int Count => Oi.Count;
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public T[] ToArray()
{
var newArray = new T[Count];
var copied = 0;
var a = (object[]) Oi.Objects.Clone();
for (var i = 0; i < Count && copied < Count; i++)
if (a[i] != null)
newArray[copied++] = (T)Convert.ChangeType(a[i], typeof(T));
return newArray;
}
public void Clear()
{
Oi.Clear();
}
public bool Add(T item)
{
return Oi.Add(item);
}
public int AddRange(IEnumerable<T> items)
{
return items.Sum(i => !Add(i) ? 0 : 1);
}
public bool Contains(T item)
{
return Oi.ContainsObject(item);
}
public int FindEntry(T item)
{
var i = Oi.FindObject(item, out var d);
return d ? (int) i : -1;
}
public IEnumerator<T> GetEnumerator()
{
return GetEnum();
}
public IEnumerator<T> GetEnum()
{
var a = (T[]) Oi.Objects.Clone();
for (var i = 0; i < Count; i++)
if (a[i] != null)
yield return (T)Convert.ChangeType(a[i], typeof(T));
}
}
Example Dictionary Class Using Object Indexer as a Base Class:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class TestDictionaryObjectIndexer<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
private ObjectIndexer _oi;
private TValue[] _values;
public TestDictionaryObjectIndexer(int size = 0)
{
_oi = new ObjectIndexer(size);
_values = new TValue[size];
}
public int Count => _oi.Count;
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return GetEnum();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public TKey[] GetKeys()
{
var kp = ToArray();
var keys = new TKey[Count];
for (var i = 0; i < Count; ++i)
keys[i] = kp[i].Key;
return keys;
}
public TValue[] GetValues()
{
var kp = ToArray();
var values = new TValue[Count];
for (var i = 0; i < Count; ++i)
values[i] = kp[i].Value;
return values;
}
public void Clear()
{
_oi.Clear();
}
public bool Add(TKey key, TValue value)
{
var pi = _oi.GetIndex(key);
if (!pi.found)
{
if (_values.Length != _oi.Length)
{
var nValues = new TValue[_oi.Length];
Array.Copy(_values, nValues, _values.Length);
_values = nValues;
}
_values[pi.idx] = value;
return false;
}
_values[pi.idx] = value;
return true;
}
public bool Contains(TKey item)
{
return _oi.ContainsObject(item);
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnum()
{
var a = (object[]) _oi.Objects.Clone();
for (var i = 0; i < Count; i++)
if (a[i] != null)
{
var k = (TKey) Convert.ChangeType(a[i], typeof(TKey));
var p = _oi.GetIndex(k);
var v = _values[p.idx];
yield return new KeyValuePair<TKey, TValue>((TKey) Convert.ChangeType(a[i], typeof(TKey)), v);
}
}
public KeyValuePair<TKey, TValue>[] ToArray()
{
var a = (object[]) _oi.Objects.Clone();
var array = new KeyValuePair<TKey, TValue>[Count];
var ptr = 0;
for (var i = 0; i < Count; i++)
if (a[i] != null)
{
var k = (TKey) Convert.ChangeType(a[i], typeof(TKey));
var p = _oi.GetIndex(k);
var v = _values[p.idx];
array[ptr++] = new KeyValuePair<TKey, TValue>((TKey) Convert.ChangeType(a[i], typeof(TKey)), v);
}
return array;
}
}