.Net R-Tree

Why mess around with r-trees?

When its possible to use linq. vb.net code ftw

Module Module1

 Sub Main()
  Dim appos As New List(Of Appo)
  appos.Add(New Appo(New Date(2009, 12, 1, 11, 45, 0), New Date(2009, 12, 1, 12, 0, 0)))
  appos.Add(New Appo(New Date(2009, 12, 1, 12, 0, 0), New Date(2009, 12, 1, 12, 15, 0)))
  appos.Add(New Appo(New Date(2009, 12, 1, 12, 10, 0), New Date(2009, 12, 1, 12, 25, 0)))
  appos.Add(New Appo(New Date(2009, 12, 1, 12, 1, 0), New Date(2009, 12, 1, 12, 2, 0)))

' 

' The linq query that looks for overlaps.

'
  Dim overlaps = From a1 As Appo In appos From a2 In appos Select a1, a2 _
               Where (appos.IndexOf(a1) < appos.IndexOf(a2)) AndAlso _
               ( _
                ((a1.StartTime >= a2.StartTime) AndAlso (a1.FinishTime <= a2.FinishTime)) _
                OrElse _
                ((a1.StartTime < a2.StartTime) AndAlso (a1.FinishTime > a2.StartTime)) _
                OrElse _
                ((a1.StartTime > a2.StartTime) AndAlso (a1.StartTime < a2.StartTime) _ 

AndAlso (a2.FinishTime >= a2.FinishTime)) _
                )

  For Each overlap In overlaps
   Console.WriteLine(overlap.a1)
   Console.WriteLine("overlaps")
   Console.WriteLine(overlap.a2)
   Console.WriteLine()
  Next
 End Sub

End Module
Public Class Appo
 Private m_st As Date
 Private m_et As Date

 Public Sub New(ByVal st As Date, ByVal et As Date)
  m_et = et : m_st = st
 End Sub
 Public ReadOnly Property du() As TimeSpan
  Get
   Return m_et.Subtract(m_st)
  End Get
 End Property
 Public ReadOnly Property StartTime() As DateTime
  Get
   Return m_st
  End Get
 End Property
 Public ReadOnly Property FinishTime() As DateTime
  Get
   Return m_et
  End Get
 End Property
 Public Overrides Function ToString() As String
  Return String.Format("[{0} - {1}]", m_st, m_et)
 End Function
End Class

edited to make code stay within lines.

I bow down to your superior solution. i never would have thought of sorting it first.

Your algorithm in 2 lines.

Dim ovlap = (From a1 As Appo In appos Order By a1.StartTime)
 Dim o = ovlap.Select(Of ova)(New Func(Of Appo, Integer, ova) _
    (Function(a As Appo, i As Integer) _
      If(i > 0 AndAlso _
       ovlap(i - 1).FinishTime >= ovlap(i).StartTime, _
       New ova With {.A1 = ovlap(i - 1), .A2 = ovlap(i)}, _
       Nothing))).Where( _
       New Func(Of ova, Boolean) _

       (Function(oa As ova) (oa.A1 IsNot Nothing) AndAlso (oa.A2 IsNot Nothing)))

Need a helper structure.

Public Structure ova
 Public A1 As Appo
 Public A2 As Appo
End Structure

It needs to be sorted by FinishTime not starttime

Can the appointments span multiple days? Say 2300 --> 0100

In my original it at least (n^2)) * (2( n Log 2))  * => O(n^2)

Approx. itl depends on the algorithm used for IndexOf( )

The second is (n^2+n)/2 => O(n^2)