''' <summary>
''' Contains an implementation of the DBSCAN algorithm. This class cannot be inherited.
''' </summary>
Public Class DbscanAlgorithm

#Region "constructors"

    Private Sub New()
    End Sub

#End Region

#Region "methods"

    ''' <summary>
    ''' Clusters the specified points using the specified value and minimum points to form a cluster.
    ''' </summary>
    ''' <param name="points">The points to cluster.</param>
    ''' <param name="eps">The value to use to find neighoring points.</param>
    ''' <param name="minimumClusterCount">The minimum number of points to form a cluster.</param>
    ''' <returns>The number of clusters created from the collection.</returns>
    Public Shared Function Dbscan(Of XType, YType)(points As IDbscanPoint(Of XType, YType)(), eps As Double, minimumClusterCount As Integer) As Integer
        Dim cid As Integer = 0

        For Each p As IDbscanPoint(Of XType, YType) In points
            If Not p.IsVisited Then
                p.IsVisited = True

                Dim neighbors As IDbscanPoint(Of XType, YType)() = DbscanAlgorithm.GetNeighors(points, p, eps)

                If neighbors.Length < minimumClusterCount Then
                    p.IsNoise = True
                Else
                    cid += 1
                    DbscanAlgorithm.ExpandCluster(points, p, neighbors, cid, eps, minimumClusterCount)
                End If
            End If
        Next

        Return cid
    End Function

    Private Shared Sub ExpandCluster(Of XType, YType)(points As IDbscanPoint(Of XType, YType)(), p As IDbscanPoint(Of XType, YType), neighbors As IDbscanPoint(Of XType, YType)(), cid As Integer, eps As Double, minimumClusterCount As Integer)
        p.ClusterId = cid

        Dim q As New Queue(Of IDbscanPoint(Of XType, YType))(neighbors)

        While q.Count > 0
            Dim n As IDbscanPoint(Of XType, YType) = q.Dequeue()
            If Not n.IsVisited Then
                n.IsVisited = True

                Dim ns As IDbscanPoint(Of XType, YType)() = DbscanAlgorithm.GetNeighors(points, n, eps)
                If ns.Length >= minimumClusterCount Then
                    For Each item As IDbscanPoint(Of XType, YType) In ns
                        q.Enqueue(item)
                    Next
                End If
            ElseIf Not n.ClusterId.HasValue Then
                n.ClusterId = cid
            End If
        End While
    End Sub

    Private Shared Function GetNeighors(Of XType, YType)(points As IDbscanPoint(Of XType, YType)(), point As IDbscanPoint(Of XType, YType), eps As Double) As IDbscanPoint(Of XType, YType)()
        Dim neighbors As New List(Of IDbscanPoint(Of XType, YType))()
        neighbors.Add(point)

        For Each p As IDbscanPoint(Of XType, YType) In points
            If point.IsNeighbor(p, eps) Then
                neighbors.Add(p)
            End If
        Next

        Return neighbors.ToArray()
    End Function

#End Region

End Class

''' <summary>
''' Contains an implementation of the <see cref="IDbscanPoint"/> interface 
''' using <see cref="double"/> types for the X and Y components.
''' </summary>
<System.Diagnostics.DebuggerDisplay("\{X={X}, Y={Y}\}")> _
Public Class DbscanPoint
    Implements IDbscanPoint(Of Double, Double)

#Region "properties"

    ''' <summary>
    ''' Gets or sets the X component of the point.
    ''' </summary>
    Public Property X() As Double Implements IDbscanPoint(Of Double, Double).X
        
    ''' <summary>
    ''' Gets or sets the Y component of the point.
    ''' </summary>
    Public Property Y() As Double Implements IDbscanPoint(Of Double, Double).Y
        
    ''' <summary>
    ''' Gets or sets a value indicating whether the point is noise.
    ''' </summary>
    Public Property IsNoise() As Boolean Implements IDbscanPoint(Of Double, Double).IsNoise
        
    ''' <summary>
    ''' Gets or sets a value indicating whether the point was visited.
    ''' </summary>
    Public Property IsVisited() As Boolean Implements IDbscanPoint(Of Double, Double).IsVisited
        
    ''' <summary>
    ''' Gets or sets a value indicating the cluster id.
    ''' </summary>
    Public Property ClusterId() As Integer? Implements IDbscanPoint(Of Double, Double).ClusterId
        
#End Region

#Region "constructors"

    ''' <summary>
    ''' Initializes a new instance of the <see cref="DbscanPoint"/> class.
    ''' </summary>
    Public Sub New()
    End Sub

    ''' <summary>
    ''' Initializes a new instance of the <see cref="DbscanPoint"/> class with the specified values.
    ''' </summary>
    ''' <param name="x">The X component of the point.</param>
    ''' <param name="y">The Y component of the point.</param>
    Public Sub New(x As Double, y As Double)
        Me.X = x
        Me.Y = y
    End Sub

#End Region

#Region "methods"

    ''' <summary>
    ''' Determines whether the specified point neighbors the current instance using the specified value.
    ''' </summary>
    ''' <param name="point">The point to test as a neighor.</param>
    ''' <param name="eps">The value to use to find neighoring points.</param>
    ''' <returns>True if the point is a neighbor; otherwise, false.</returns>
    Public Function IsNeighbor(point As IDbscanPoint(Of Double, Double), eps As Double) As Boolean Implements IDbscanPoint(Of Double, Double).IsNeighbor
        Return (Math.Pow(point.X - Me.X, 2) + Math.Pow(point.Y - Me.Y, 2) < Math.Pow(eps, 2))
    End Function

#End Region

End Class

''' <summary>
''' Contains the functionality an object requires to perform a DBSCAN.
''' </summary>
Public Interface IDbscanPoint(Of XType, YType)

#Region "properties"

    ''' <summary>
    ''' Gets or sets the X component of the point.
    ''' </summary>
    Property X() As XType

    ''' <summary>
    ''' Gets or sets the Y component of the point.
    ''' </summary>
    Property Y() As YType

    ''' <summary>
    ''' Gets or sets a value indicating whether the point is noise.
    ''' </summary>
    Property IsNoise() As Boolean

    ''' <summary>
    ''' Gets or sets a value indicating whether the point was visited.
    ''' </summary>
    Property IsVisited() As Boolean

    ''' <summary>
    ''' Gets or sets a value indicating the cluster id.
    ''' </summary>
    Property ClusterId() As Integer?

#End Region

#Region "methods"

    ''' <summary>
    ''' Determines whether the specified point neighbors the current instance using the specified value.
    ''' </summary>
    ''' <param name="point">The point to test as a neighor.</param>
    ''' <param name="eps">The value to use to find neighoring points.</param>
    ''' <returns>True if the point is a neighbor; otherwise, false.</returns>
    Function IsNeighbor(point As IDbscanPoint(Of XType, YType), eps As Double) As Boolean

#End Region

End Interface