<|start_filename|>Src/HNSW.Net/MessagePackCompat/StringEncoding.cs<|end_filename|>
﻿using System.Text;

namespace MessagePackCompat
{
    internal static class StringEncoding
    {
        public static readonly Encoding UTF8 = new UTF8Encoding(false);
    }
}

<|start_filename|>Src/HNSW.Net/IProvideRandomValues.cs<|end_filename|>
﻿using System;
using System.Runtime.CompilerServices;

namespace HNSW.Net
{
    public interface IProvideRandomValues
    {
        bool IsThreadSafe { get; }

        /// <summary>
        /// Generates a random float. Values returned are from 0.0 up to but not including 1.0.
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        float NextFloat();

        /// <summary>
        /// Fills the elements of a specified array of bytes with random numbers.
        /// </summary>
        /// <param name="buffer">An array of bytes to contain random numbers.</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void NextFloats(Span<float> buffer);

        /// <summary>
        /// Returns a random integer that is within a specified range.
        /// </summary>
        /// <param name="minValue">The inclusive lower bound of the random number returned.</param>
        /// <param name="maxValue">The exclusive upper bound of the random number returned. maxValue must be greater than or equal to minValue.</param>
        /// <returns>A 32-bit signed integer greater than or equal to minValue and less than maxValue; that is, the range of return values includes minValue but not maxValue. If minValue
        //  equals maxValue, minValue is returned.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int Next(int minValue, int maxValue);
    }
}


<|start_filename|>Src/HNSW.Net/MessagePackCompat/FloatBits.cs<|end_filename|>
﻿using System;
using System.Runtime.InteropServices;

namespace MessagePackCompat
{
    // safe accessor of Single/Double's underlying byte.
    // This code is borrowed from MsgPack-Cli https://github.com/msgpack/msgpack-cli

    [StructLayout(LayoutKind.Explicit)]
    internal struct Float32Bits
    {
        [FieldOffset(0)]
        public readonly float Value;

        [FieldOffset(0)]
        public readonly Byte Byte0;

        [FieldOffset(1)]
        public readonly Byte Byte1;

        [FieldOffset(2)]
        public readonly Byte Byte2;

        [FieldOffset(3)]
        public readonly Byte Byte3;

        public Float32Bits(float value)
        {
            this = default(Float32Bits);
            this.Value = value;
        }

        public Float32Bits(byte[] bigEndianBytes, int offset)
        {
            this = default(Float32Bits);

            if (BitConverter.IsLittleEndian)
            {
                this.Byte0 = bigEndianBytes[offset + 3];
                this.Byte1 = bigEndianBytes[offset + 2];
                this.Byte2 = bigEndianBytes[offset + 1];
                this.Byte3 = bigEndianBytes[offset];
            }
            else
            {
                this.Byte0 = bigEndianBytes[offset];
                this.Byte1 = bigEndianBytes[offset + 1];
                this.Byte2 = bigEndianBytes[offset + 2];
                this.Byte3 = bigEndianBytes[offset + 3];
            }
        }
    }

    [StructLayout(LayoutKind.Explicit)]
    internal struct Float64Bits
    {
        [FieldOffset(0)]
        public readonly double Value;

        [FieldOffset(0)]
        public readonly Byte Byte0;

        [FieldOffset(1)]
        public readonly Byte Byte1;

        [FieldOffset(2)]
        public readonly Byte Byte2;

        [FieldOffset(3)]
        public readonly Byte Byte3;

        [FieldOffset(4)]
        public readonly Byte Byte4;

        [FieldOffset(5)]
        public readonly Byte Byte5;

        [FieldOffset(6)]
        public readonly Byte Byte6;

        [FieldOffset(7)]
        public readonly Byte Byte7;

        public Float64Bits(double value)
        {
            this = default(Float64Bits);
            this.Value = value;
        }

        public Float64Bits(byte[] bigEndianBytes, int offset)
        {
            this = default(Float64Bits);

            if (BitConverter.IsLittleEndian)
            {
                this.Byte0 = bigEndianBytes[offset + 7];
                this.Byte1 = bigEndianBytes[offset + 6];
                this.Byte2 = bigEndianBytes[offset + 5];
                this.Byte3 = bigEndianBytes[offset + 4];
                this.Byte4 = bigEndianBytes[offset + 3];
                this.Byte5 = bigEndianBytes[offset + 2];
                this.Byte6 = bigEndianBytes[offset + 1];
                this.Byte7 = bigEndianBytes[offset];
            }
            else
            {
                this.Byte0 = bigEndianBytes[offset];
                this.Byte1 = bigEndianBytes[offset + 1];
                this.Byte2 = bigEndianBytes[offset + 2];
                this.Byte3 = bigEndianBytes[offset + 3];
                this.Byte4 = bigEndianBytes[offset + 4];
                this.Byte5 = bigEndianBytes[offset + 5];
                this.Byte6 = bigEndianBytes[offset + 6];
                this.Byte7 = bigEndianBytes[offset + 7];
            }
        }
    }
}

<|start_filename|>Src/HNSW.Net/DistanceUtils.cs<|end_filename|>
﻿// <copyright file="DistanceUtils.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;

    public static class DistanceUtils
    {
        public static bool LowerThan<TDistance>(TDistance x, TDistance y) where TDistance : IComparable<TDistance>
        {
            return x.CompareTo(y) < 0;
        }

        public static bool GreaterThan<TDistance>(TDistance x, TDistance y) where TDistance : IComparable<TDistance>
        {
            return x.CompareTo(y) > 0;
        }

        public static bool IsEqual<TDistance>(TDistance x, TDistance y) where TDistance : IComparable<TDistance>
        {
            return x.CompareTo(y) == 0;
        }
    }
}


<|start_filename|>Src/HNSW.Net/Properties/AssemblyInfo.cs<|end_filename|>
// <copyright file="AssemblyInfo.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

using System.Runtime.CompilerServices;

[assembly: InternalsVisibleTo("HNSW.Net.Tests")]

<|start_filename|>Src/HNSW.Net/Algorithms.Algorithm4.cs<|end_filename|>
﻿// <copyright file="Node.Algorithm4.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal partial class Algorithms
    {
        /// <summary>
        /// The implementation of the SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keepPrunedConnections) algorithm.
        /// Article: Section 4. Algorithm 4.
        /// </summary>
        /// <typeparam name="TItem">The typeof the items in the small world.</typeparam>
        /// <typeparam name="TDistance">The type of the distance in the small world.</typeparam>
        internal sealed class Algorithm4<TItem, TDistance> : Algorithm<TItem, TDistance> where TDistance : struct, IComparable<TDistance>
        {
            public Algorithm4(Graph<TItem, TDistance>.Core graphCore) : base(graphCore)
            {
            }

            /// <inheritdoc/>
            internal override List<int> SelectBestForConnecting(List<int> candidatesIds, TravelingCosts<int, TDistance> travelingCosts, int layer)
            {
                /*
                 * q ← this
                 * R ← ∅    // result
                 * W ← C    // working queue for the candidates
                 * if expandCandidates  // expand candidates
                 *   for each e ∈ C
                 *     for each eadj ∈ neighbourhood(e) at layer lc
                 *       if eadj ∉ W
                 *         W ← W ⋃ eadj
                 *
                 * Wd ← ∅ // queue for the discarded candidates
                 * while │W│ gt 0 and │R│ lt M
                 *   e ← extract nearest element from W to q
                 *   if e is closer to q compared to any element from R
                 *     R ← R ⋃ e
                 *   else
                 *     Wd ← Wd ⋃ e
                 *
                 * if keepPrunedConnections // add some of the discarded connections from Wd
                 *   while │Wd│ gt 0 and │R│ lt M
                 *   R ← R ⋃ extract nearest element from Wd to q
                 *
                 * return R
                 */

                IComparer<int> fartherIsOnTop = travelingCosts;
                IComparer<int> closerIsOnTop = fartherIsOnTop.Reverse();

                var layerM = GetM(layer);

                var resultHeap = new BinaryHeap<int>(new List<int>(layerM + 1), fartherIsOnTop);
                var candidatesHeap = new BinaryHeap<int>(candidatesIds, closerIsOnTop);

                // expand candidates option is enabled
                if (GraphCore.Parameters.ExpandBestSelection)
                {
                    var visited = new HashSet<int>(candidatesHeap.Buffer);
                    var toAdd = new HashSet<int>();
                    foreach (var candidateId in candidatesHeap.Buffer)
                    {
                        var candidateNeighborsIDs = GraphCore.Nodes[candidateId][layer];
                        foreach (var candidateNeighbourId in candidateNeighborsIDs)
                        {
                            if (!visited.Contains(candidateNeighbourId))
                            {
                                toAdd.Add(candidateNeighbourId);
                                visited.Add(candidateNeighbourId);
                            }
                        }
                    }
                    foreach(var id in toAdd)
                    {
                        candidatesHeap.Push(id);
                    }
                }

                // main stage of moving candidates to result
                var discardedHeap = new BinaryHeap<int>(new List<int>(candidatesHeap.Buffer.Count), closerIsOnTop);
                while (candidatesHeap.Buffer.Any() && resultHeap.Buffer.Count < layerM)
                {
                    var candidateId = candidatesHeap.Pop();
                    var farestResultId = resultHeap.Buffer.FirstOrDefault();

                    if (!resultHeap.Buffer.Any() || DistanceUtils.LowerThan(travelingCosts.From(candidateId), travelingCosts.From(farestResultId)))
                    {
                        resultHeap.Push(candidateId);
                    }
                    else if (GraphCore.Parameters.KeepPrunedConnections)
                    {
                        discardedHeap.Push(candidateId);
                    }
                }

                // keep pruned option is enabled
                if (GraphCore.Parameters.KeepPrunedConnections)
                {
                    while (discardedHeap.Buffer.Any() && resultHeap.Buffer.Count < layerM)
                    {
                        resultHeap.Push(discardedHeap.Pop());
                    }
                }

                return resultHeap.Buffer;
            }
        }
    }
}


<|start_filename|>Src/HNSW.Net.Demo/MetricsEventListener.cs<|end_filename|>
﻿// <copyright file="Program.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net.Demo
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Tracing;
    using System.Linq;

    public static partial class Program
    {
        private class MetricsEventListener : EventListener
        {
            private readonly EventSource eventSource;

            public MetricsEventListener(EventSource eventSource)
            {
                this.eventSource = eventSource;
                EnableEvents(this.eventSource, EventLevel.LogAlways, EventKeywords.All, new Dictionary<string, string> { { "EventCounterIntervalSec", "1" } });
            }

            public override void Dispose()
            {
                DisableEvents(eventSource);
                base.Dispose();
            }

            protected override void OnEventWritten(EventWrittenEventArgs eventData)
            {
                var counterData = eventData.Payload?.FirstOrDefault() as IDictionary<string, object>;
                if (counterData?.Count == 0)
                {
                    return;
                }

                Console.WriteLine($"[{counterData["Name"]:n1}]: Avg={counterData["Mean"]:n1}; SD={counterData["StandardDeviation"]:n1}; Count={counterData["Count"]}");
            }
        }
    }
}


<|start_filename|>Src/HNSW.Net/ScopeLatencyTracker.cs<|end_filename|>
﻿// <copyright file="ScopeLatencyTracker.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Diagnostics;

    /// <summary>
    /// Latency tracker for using scope.
    /// TODO: make it ref struct in C# 8.0
    /// </summary>
    internal struct ScopeLatencyTracker : IDisposable
    {
        private long StartTimestamp;
        private Action<float> LatencyCallback;

        /// <summary>
        /// Initializes a new instance of the <see cref="ScopeLatencyTracker"/> struct.
        /// </summary>
        /// <param name="callback">The latency reporting callback to associate with the scope.</param>
        internal ScopeLatencyTracker(Action<float> callback)
        {
            StartTimestamp = callback != null ? Stopwatch.GetTimestamp() : 0;
            LatencyCallback = callback;
        }

        /// <summary>
        /// Reports the time ellsapsed between the tracker creation and this call.
        /// </summary>
        public void Dispose()
        {
            const long ticksPerMicroSecond = TimeSpan.TicksPerMillisecond / 1000;
            if (LatencyCallback != null)
            {
                long ellapsedMuS = (Stopwatch.GetTimestamp() - StartTimestamp) / ticksPerMicroSecond;
                LatencyCallback(ellapsedMuS);
            }
        }
    }
}


<|start_filename|>Src/HNSW.Net/DistanceCache.cs<|end_filename|>
﻿// <copyright file="DistanceCache.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

using System;
using System.Runtime.CompilerServices;

namespace HNSW.Net
{
    internal class DistanceCache<TDistance> where TDistance : struct
    {
        /// <summary>
        /// https://referencesource.microsoft.com/#mscorlib/system/array.cs,2d2b551eabe74985,references
        /// We use powers of 2 for efficient modulo
        /// 2^28 = 268435456
        /// 2^29 = 536870912
        /// 2^30 = 1073741824
        /// </summary>
        private const int MaxArrayLength = 268435456; // 0x10000000;

        private TDistance[] values;

        private long[] keys;

        internal int HitCount;

        internal DistanceCache()
        {
        }

        internal void Resize(int pointsCount, bool overwrite)
        {
            if(pointsCount <=0) { pointsCount = 1024; }

            long capacity = ((long)pointsCount * (pointsCount + 1)) >> 1;
            capacity = capacity < MaxArrayLength ? capacity : MaxArrayLength;

            if (keys is null || capacity > keys.Length || overwrite)
            {
                int i0 = 0;
                if (keys is null || overwrite)
                {
                    keys   = new long[(int)capacity];
                    values = new TDistance[(int)capacity];
                }
                else
                {
                    i0 = keys.Length;
                    Array.Resize(ref keys,   (int)capacity);
                    Array.Resize(ref values, (int)capacity);
                }

                // TODO: may be there is a better way to warm up cache and force OS to allocate pages
                keys.AsSpan().Slice(i0).Fill(-1);
                values.AsSpan().Slice(i0).Fill(default);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal TDistance GetValue(int fromId, int toId, Func<int,int,TDistance> getter)
        {
            long key = MakeKey(fromId, toId);
            int hash = (int)(key & (keys.Length - 1));

            if (keys[hash] == key)
            {
                HitCount++;
                return values[hash];
            }
            else
            {
                var d = getter(fromId, toId);
                keys[hash] = key;
                values[hash] = d;
                return d;
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void SetValue(int fromId, int toId, TDistance distance)
        {
            long key = MakeKey(fromId, toId);
            int hash = (int)(key & (keys.Length - 1));
            keys[hash] = key;
            values[hash] = distance;
        }

        /// <summary>
        /// Builds key for the pair of points.
        /// MakeKey(fromId, toId) == MakeKey(toId, fromId)
        /// </summary>
        /// <param name="fromId">The from point identifier.</param>
        /// <param name="toId">The to point identifier.</param>
        /// <returns>Key of the pair.</returns>
        private static long MakeKey(int fromId, int toId)
        {
            return fromId > toId ? (((long)fromId * (fromId + 1)) >> 1) + toId : (((long)toId * (toId + 1)) >> 1) + fromId;
        }
    }
}


<|start_filename|>Src/HNSW.Net/ThreadSafeFastRandom.cs<|end_filename|>
﻿using System;
using System.Runtime.CompilerServices;

namespace HNSW.Net
{
    internal static class ThreadSafeFastRandom
    {
        private static readonly Random _global = new Random();

        [ThreadStatic]
        private static FastRandom _local;

        private static int GetGlobalSeed()
        {
            int seed;
            lock (_global)
            {
                seed = _global.Next();
            }
            return seed;
        }

        /// <summary>
        /// Returns a non-negative random integer.
        /// </summary>
        /// <returns>A 32-bit signed integer that is greater than or equal to 0 and less than System.Int32.MaxValue.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Next()
        {
            var inst = _local;
            if (inst == null)
            {
                int seed;
                seed = GetGlobalSeed();
                _local = inst = new FastRandom(seed);
            }
            return inst.Next();
        }

        /// <summary>
        /// Returns a non-negative random integer that is less than the specified maximum.
        /// </summary>
        /// <param name="maxValue">The exclusive upper bound of the random number to be generated. maxValue must be greater than or equal to 0.</param>
        /// <returns>A 32-bit signed integer that is greater than or equal to 0, and less than maxValue; that is, the range of return values ordinarily includes 0 but not maxValue. However,
        //  if maxValue equals 0, maxValue is returned.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Next(int maxValue)
        {
            var inst = _local;
            if (inst == null)
            {
                int seed;
                seed = GetGlobalSeed();
                _local = inst = new FastRandom(seed);
            }
            int ans;
            do
            {
                ans = inst.Next(maxValue);
            } while (ans == maxValue);

            return ans;
        }

        /// <summary>
        /// Returns a random integer that is within a specified range.
        /// </summary>
        /// <param name="minValue">The inclusive lower bound of the random number returned.</param>
        /// <param name="maxValue">The exclusive upper bound of the random number returned. maxValue must be greater than or equal to minValue.</param>
        /// <returns>A 32-bit signed integer greater than or equal to minValue and less than maxValue; that is, the range of return values includes minValue but not maxValue. If minValue
        //  equals maxValue, minValue is returned.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Next(int minValue, int maxValue)
        {
            var inst = _local;
            if (inst == null)
            {
                int seed;
                seed = GetGlobalSeed();
                _local = inst = new FastRandom(seed);
            }
            return inst.Next(minValue, maxValue);
        }

        /// <summary>
        /// Generates a random float. Values returned are from 0.0 up to but not including 1.0.
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static float NextFloat()
        {
            var inst = _local;
            if (inst == null)
            {
                int seed;
                seed = GetGlobalSeed();
                _local = inst = new FastRandom(seed);
            }
            return inst.NextFloat();
        }

        /// <summary>
        /// Fills the elements of a specified array of bytes with random numbers.
        /// </summary>
        /// <param name="buffer">An array of bytes to contain random numbers.</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void NextFloats(Span<float> buffer)
        {
            var inst = _local;
            if (inst == null)
            {
                int seed;
                seed = GetGlobalSeed();
                _local = inst = new FastRandom(seed);
            }
            inst.NextFloats(buffer);
        }
    }
}

<|start_filename|>Src/HNSW.Net/DefaultRandomGenerator.cs<|end_filename|>
﻿using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Text;

namespace HNSW.Net
{
    public sealed class DefaultRandomGenerator : IProvideRandomValues
    {
        /// <summary>
        /// This is the default configuration (it supports the optimization process to be executed on multiple threads)
        /// </summary>
        public static DefaultRandomGenerator Instance { get; } = new DefaultRandomGenerator(allowParallel: true);

        /// <summary>
        /// This uses the same random number generator but forces the optimization process to run on a single thread (which may be desirable if multiple requests may be processed concurrently
        /// or if it is otherwise not desirable to let a single request access all of the CPUs)
        /// </summary>
        public static DefaultRandomGenerator DisableThreading { get; } = new DefaultRandomGenerator(allowParallel: false);

        private DefaultRandomGenerator(bool allowParallel) => IsThreadSafe = allowParallel;

        public bool IsThreadSafe { get; }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Next(int minValue, int maxValue) => ThreadSafeFastRandom.Next(minValue, maxValue);

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public float NextFloat() => ThreadSafeFastRandom.NextFloat();

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void NextFloats(Span<float> buffer) => ThreadSafeFastRandom.NextFloats(buffer);
    }
}


<|start_filename|>Src/HNSW.Net/IProgressReporter.cs<|end_filename|>
﻿namespace HNSW.Net
{
    public interface IProgressReporter
    {
        void Progress(int current, int total);
    }
}


<|start_filename|>Src/HNSW.Net/Node.cs<|end_filename|>
﻿// <copyright file="Node.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using MessagePack;
    using System.Collections.Generic;

    /// <summary>
    /// The implementation of the node in hnsw graph.
    /// </summary>
    [MessagePackObject]
    public struct Node
    {
        [Key(0)]
        public List<List<int>> Connections;

        [Key(1)] public int Id;

        /// <summary>
        /// Gets the max layer where the node is presented.
        /// </summary>
        [IgnoreMember]
        public int MaxLayer
        {
            get
            {
                return Connections.Count - 1;
            }
        }

        /// <summary>
        /// Gets connections ids of the node at the given layer
        /// </summary>
        /// <param name="layer">The layer to get connections at.</param>
        /// <returns>The connections of the node at the given layer.</returns>
        public List<int> this[int layer]
        {
            get
            {
                return Connections[layer];
            }
            set
            {
                Connections[layer] = value;
            }
        }
    }
}


<|start_filename|>Src/HNSW.Net/Algorithms.cs<|end_filename|>
﻿// <copyright file="Node.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Collections.Generic;

    internal partial class Algorithms
    {
        /// <summary>
        /// The abstract class representing algorithm to control node capacity.
        /// </summary>
        /// <typeparam name="TItem">The typeof the items in the small world.</typeparam>
        /// <typeparam name="TDistance">The type of the distance in the small world.</typeparam>
        internal abstract class Algorithm<TItem, TDistance> where TDistance : struct, IComparable<TDistance>
        {
            protected readonly Graph<TItem, TDistance>.Core GraphCore;

            protected readonly Func<int, int, TDistance> NodeDistance;

            public Algorithm(Graph<TItem, TDistance>.Core graphCore)
            {
                GraphCore = graphCore;
                NodeDistance = graphCore.GetDistance;
            }

            /// <summary>
            /// Creates a new instance of the <see cref="Node"/> struct. Controls the exact type of connection lists.
            /// </summary>
            /// <param name="nodeId">The identifier of the node.</param>
            /// <param name="maxLayer">The max layer where the node is presented.</param>
            /// <returns>The new instance.</returns>
            internal virtual Node NewNode(int nodeId, int maxLayer)
            {
                var connections = new List<List<int>>(maxLayer + 1);
                for (int layer = 0; layer <= maxLayer; ++layer)
                {
                    // M + 1 neighbours to not realloc in AddConnection when the level is full
                    int layerM = GetM(layer) + 1;
                    connections.Add(new List<int>(layerM));
                }

                return new Node
                {
                    Id = nodeId,
                    Connections = connections
                };
            }

            /// <summary>
            /// The algorithm which selects best neighbours from the candidates for the given node.
            /// </summary>
            /// <param name="candidatesIds">The identifiers of candidates to neighbourhood.</param>
            /// <param name="travelingCosts">Traveling costs to compare candidates.</param>
            /// <param name="layer">The layer of the neighbourhood.</param>
            /// <returns>Best nodes selected from the candidates.</returns>
            internal abstract List<int> SelectBestForConnecting(List<int> candidatesIds, TravelingCosts<int, TDistance> travelingCosts, int layer);

            /// <summary>
            /// Get maximum allowed connections for the given level.
            /// </summary>
            /// <remarks>
            /// Article: Section 4.1:
            /// "Selection of the Mmax0 (the maximum number of connections that an element can have in the zero layer) also
            /// has a strong influence on the search performance, especially in case of high quality(high recall) search.
            /// Simulations show that setting Mmax0 to M(this corresponds to kNN graphs on each layer if the neighbors
            /// selection heuristic is not used) leads to a very strong performance penalty at high recall.
            /// Simulations also suggest that 2∙M is a good choice for Mmax0;
            /// setting the parameter higher leads to performance degradation and excessive memory usage."
            /// </remarks>
            /// <param name="layer">The level of the layer.</param>
            /// <returns>The maximum number of connections.</returns>
            internal int GetM(int layer)
            {
                return layer == 0 ? 2 * GraphCore.Parameters.M : GraphCore.Parameters.M;
            }

            /// <summary>
            /// Tries to connect the node with the new neighbour.
            /// </summary>
            /// <param name="node">The node to add neighbour to.</param>
            /// <param name="neighbour">The new neighbour.</param>
            /// <param name="layer">The layer to add neighbour to.</param>
            internal void Connect(Node node, Node neighbour, int layer)
            {
                var nodeLayer = node[layer];
                nodeLayer.Add(neighbour.Id);
                if (nodeLayer.Count > GetM(layer))
                {
                    var travelingCosts = new TravelingCosts<int, TDistance>(NodeDistance, node.Id);
                    node[layer] = SelectBestForConnecting(nodeLayer, travelingCosts, layer);
                }
            }
        }

    }
}


<|start_filename|>Src/HNSW.Net.Tests/SmallWorldTests.cs<|end_filename|>
﻿// <copyright file="SmallWorldTests.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net.Tests
{
    using System;
    using System.Collections.Generic;
    using System.Globalization;
    using System.IO;
    using System.Linq;
    using Microsoft.VisualStudio.TestTools.UnitTesting;

    /// <summary>
    /// Tests for <see cref="SmallWorld{TItem, TDistance}"/>
    /// </summary>
    [TestClass]
    public class SmallWorldTests
    {
        // Set floating point error to 5.96 * 10^-7
        // For cosine distance error can be bigger in theory but for test data it's not the case.
        private const float FloatError = 0.000000596f;

        private IReadOnlyList<float[]> vectors;

        /// <summary>
        /// Initializes test resources.
        /// </summary>
        [TestInitialize]
        public void TestInitialize()
        {
            var data = File.ReadAllLines(@"vectors.txt");
            vectors = data.Select(r => Array.ConvertAll(r.Split('\t'), x => float.Parse(x, CultureInfo.CurrentCulture))).ToList();
        }

        /// <summary>
        /// Basic test for knn search - this test might fail sometimes, as the construction of the graph does not guarantee an exact answer
        /// </summary>
        [TestMethod]
        public void KNNSearchTest()
        {
            var parameters = new SmallWorld<float[], float>.Parameters();
            var graph = new SmallWorld<float[], float>(CosineDistance.NonOptimized, DefaultRandomGenerator.Instance, parameters);
            graph.AddItems(vectors);

            int bestWrong = 0;
            float maxError = float.MinValue;

            for (int i = 0; i < vectors.Count; ++i)
            {
                var result = graph.KNNSearch(vectors[i], 20);
                var best = result.OrderBy(r => r.Distance).First();
                Assert.AreEqual(20, result.Count);
                if (best.Id != i)
                {
                    bestWrong++;
                }
                maxError = Math.Max(maxError, best.Distance);
            }
            Assert.AreEqual(0, bestWrong);
            Assert.AreEqual(0, maxError, FloatError);
        }

        /// <summary>
        /// Basic test for knn search - this test might fail sometimes, as the construction of the graph does not guarantee an exact answer
        /// </summary>
        [DataTestMethod]
        [DataRow(false,false)]
        [DataRow(false,true)]
        [DataRow(true, false)]
        [DataRow(true, true)]
        public void KNNSearchTestAlgorithm4(bool expandBestSelection, bool keepPrunedConnections )
        {
            var parameters = new SmallWorld<float[], float>.Parameters() { NeighbourHeuristic = NeighbourSelectionHeuristic.SelectHeuristic, ExpandBestSelection = expandBestSelection, KeepPrunedConnections = keepPrunedConnections };
            var graph = new SmallWorld<float[], float>(CosineDistance.NonOptimized, DefaultRandomGenerator.Instance, parameters);
            graph.AddItems(vectors);

            int bestWrong = 0;
            float maxError = float.MinValue;

            for (int i = 0; i < vectors.Count; ++i)
            {
                var result = graph.KNNSearch(vectors[i], 20);
                var best = result.OrderBy(r => r.Distance).First();
                Assert.AreEqual(20, result.Count);
                if (best.Id != i)
                {
                    bestWrong++;
                }
                maxError = Math.Max(maxError, best.Distance);
            }
            Assert.AreEqual(0, bestWrong);
            Assert.AreEqual(0, maxError, FloatError);
        }

        /// <summary>
        /// Serialization deserialization tests.
        /// </summary>
        [TestMethod]
        public void SerializeDeserializeTest()
        {
            byte[] buffer;
            string original;

            // restrict scope of original graph
            var stream = new MemoryStream();
            {
                var parameters = new SmallWorld<float[], float>.Parameters()
                {
                    M = 15,
                    LevelLambda = 1 / Math.Log(15),
                };

                var graph = new SmallWorld<float[], float>(CosineDistance.NonOptimized, DefaultRandomGenerator.Instance, parameters);
                graph.AddItems(vectors);

                graph.SerializeGraph(stream);
                original = graph.Print();
            }
            stream.Position = 0;

            var copy = SmallWorld<float[], float>.DeserializeGraph(vectors, CosineDistance.NonOptimized, DefaultRandomGenerator.Instance, stream);

            Assert.AreEqual(original, copy.Print());
        }
    }
}

<|start_filename|>Src/HNSW.Net/Graph.Utils.cs<|end_filename|>
﻿// <copyright file="Graph.Utils.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal partial class Graph<TItem, TDistance>
    {
        /// <summary>
        /// Runs breadth first search.
        /// </summary>
        /// <param name="core">The graph core.</param>
        /// <param name="entryPoint">The entry point.</param>
        /// <param name="layer">The layer of the graph where to run BFS.</param>
        /// <param name="visitAction">The action to perform on each node.</param>
        internal static void BFS(Core core, Node entryPoint, int layer, Action<Node> visitAction)
        {
            var visitedIds = new HashSet<int>();
            var expansionQueue = new Queue<int>(new[] { entryPoint.Id });

            while (expansionQueue.Any())
            {
                var currentNode = core.Nodes[expansionQueue.Dequeue()];
                if (!visitedIds.Contains(currentNode.Id))
                {
                    visitAction(currentNode);
                    visitedIds.Add(currentNode.Id);
                    foreach (var neighbourId in currentNode[layer])
                    {
                        expansionQueue.Enqueue(neighbourId);
                    }
                }
            }
        }

        internal class VisitedBitSet
        {
            private int[] Buffer;

            internal VisitedBitSet(int nodesCount)
            {
                Buffer = new int[(nodesCount >> 5) + 1];
            }

            internal bool Contains(int nodeId)
            {
                int carrier = Buffer[nodeId >> 5];
                return ((1 << (nodeId & 31)) & carrier) != 0;
            }

            internal void Add(int nodeId)
            {
                int mask = 1 << (nodeId & 31);
                Buffer[nodeId >> 5] |= mask;
            }

            internal void Clear()
            {
                Array.Clear(Buffer, 0, Buffer.Length);
            }
        }
    }
}

<|start_filename|>Src/HNSW.Net/TravelingCosts.cs<|end_filename|>
﻿// <copyright file="TravelingCosts.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// Implementation of distance calculation from an arbitrary point to the given destination.
    /// </summary>
    /// <typeparam name="TItem">Type of the points.</typeparam>
    /// <typeparam name="TDistance">Type of the distance.</typeparam>
    public class TravelingCosts<TItem, TDistance> : IComparer<TItem>
    {
        private static readonly Comparer<TDistance> DistanceComparer = Comparer<TDistance>.Default;

        private readonly Func<TItem, TItem, TDistance> Distance;

        public TravelingCosts(Func<TItem, TItem, TDistance> distance, TItem destination)
        {
            Distance = distance;
            Destination = destination;
        }

        public TItem Destination { get; }

        public TDistance From(TItem departure)
        {
            return Distance(departure, Destination);
        }

        /// <summary>
        /// Compares 2 points by the distance from the destination.
        /// </summary>
        /// <param name="x">Left point.</param>
        /// <param name="y">Right point.</param>
        /// <returns>
        /// -1 if x is closer to the destination than y;
        /// 0 if x and y are equally far from the destination;
        /// 1 if x is farther from the destination than y.
        /// </returns>
        public int Compare(TItem x, TItem y)
        {
            var fromX = From(x);
            var fromY = From(y);
            return DistanceComparer.Compare(fromX, fromY);
        }
    }
}


<|start_filename|>src/HNSW.Net/NeighbourSelectionHeuristic.cs<|end_filename|>
﻿// <copyright file="SmallWorld.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    /// <summary>
    /// Type of heuristic to select best neighbours for a node.
    /// </summary>
    public enum NeighbourSelectionHeuristic
    {
        /// <summary>
        /// Marker for the Algorithm 3 (SELECT-NEIGHBORS-SIMPLE) from the article. Implemented in <see cref="Algorithms.Algorithm3{TItem, TDistance}"/>
        /// </summary>
        SelectSimple,

        /// <summary>
        /// Marker for the Algorithm 4 (SELECT-NEIGHBORS-HEURISTIC) from the article. Implemented in <see cref="Algorithms.Algorithm4{TItem, TDistance}"/>
        /// </summary>
        SelectHeuristic
    }
}


<|start_filename|>Src/HNSW.Net/Graph.Core.cs<|end_filename|>
﻿// <copyright file="Graph.Core.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.
// </copyright>

namespace HNSW.Net
{
    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Runtime.CompilerServices;
    using System.Threading;
    using MessagePack;

    using static HNSW.Net.EventSources;

    internal partial class Graph<TItem, TDistance>
    {
        internal class Core
        {
            private readonly Func<TItem, TItem, TDistance> Distance;

            private readonly DistanceCache<TDistance> DistanceCache;

            private long DistanceCalculationsCount;

            internal List<Node> Nodes { get; private set; }

            internal List<TItem> Items { get; private set; }

            internal Algorithms.Algorithm<TItem, TDistance> Algorithm { get; private set; }

            internal SmallWorld<TItem, TDistance>.Parameters Parameters { get; private set; }

            internal float DistanceCacheHitRate => (float)(DistanceCache?.HitCount ?? 0) / DistanceCalculationsCount;

            internal Core(Func<TItem, TItem, TDistance> distance, SmallWorld<TItem, TDistance>.Parameters parameters)
            {
                Distance = distance;
                Parameters = parameters;
                
                var initialSize = Math.Max(1024, parameters.InitialItemsSize);

                Nodes = new List<Node>(initialSize);
                Items = new List<TItem>(initialSize);

                switch (Parameters.NeighbourHeuristic)
                {
                    case NeighbourSelectionHeuristic.SelectSimple:
                    {
                        Algorithm = new Algorithms.Algorithm3<TItem, TDistance>(this);
                        break;
                    }
                    case NeighbourSelectionHeuristic.SelectHeuristic:
                    {
                        Algorithm = new Algorithms.Algorithm4<TItem, TDistance>(this);
                        break;
                    }
                }

                if (Parameters.EnableDistanceCacheForConstruction)
                {
                    DistanceCache = new DistanceCache<TDistance>();
                    DistanceCache.Resize(parameters.InitialDistanceCacheSize, false);
                }

                DistanceCalculationsCount = 0;
            }

            internal IReadOnlyList<int> AddItems(IReadOnlyList<TItem> items, IProvideRandomValues generator, CancellationToken cancellationToken)
            {
                int newCount = items.Count;

                var newIDs = new List<int>();
                Items.AddRange(items);
                DistanceCache?.Resize(newCount, false);

                int id0 = Nodes.Count;

                for (int id = 0; id < newCount; ++id)
                {
                    Nodes.Add(Algorithm.NewNode(id0 + id, RandomLayer(generator, Parameters.LevelLambda)));
                    newIDs.Add(id0 + id);
                    cancellationToken.ThrowIfCancellationRequested();
                }
                return newIDs;
            }

            internal void ResizeDistanceCache(int newSize)
            {
                DistanceCache?.Resize(newSize, true);
            }

            internal void Serialize(Stream stream)
            {
                MessagePackSerializer.Serialize(stream, Nodes);
            }

            internal void Deserialize(IReadOnlyList<TItem> items, Stream stream)
            {
                // readStrict: true -> removed, as not available anymore on MessagePack 2.0 - also probably not necessary anymore
                //                     see https://github.com/neuecc/MessagePack-CSharp/pull/663
                Nodes = MessagePackSerializer.Deserialize<List<Node>>(stream);
                Items.AddRange(items);
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            internal TDistance GetDistance(int fromId, int toId)
            {
                DistanceCalculationsCount++;
                if (DistanceCache is object)
                {
                    return DistanceCache.GetValue(fromId, toId, GetDistanceSkipCache);
                }
                else
                {
                    return Distance(Items[fromId], Items[toId]);
                }
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private TDistance GetDistanceSkipCache(int fromId, int toId)
            {
                return Distance(Items[fromId], Items[toId]);
            }

            private static int RandomLayer(IProvideRandomValues generator, double lambda)
            {
                var r = -Math.Log(generator.NextFloat()) * lambda;
                return (int)r;
            }
        }
    }
}
