---
--- Yu Hirate, Hayato Yamana: Generalized Sequential Pattern Mining with Item Interval, Journal of Computer Vol. 1, No 3, June 2006
---

--
-- Configuration
--

def items {a} : [a] := [a, b, c, d, e, f]

def ISDB {a} : [[[(Integer, [a])]]] :=
  [[[(0, [a]), (86400, [a, b, c]), (259200, [a, c])]]
  ,[[(0, [a, d]), (259200, [c])]]
  ,[[(0, [a, e, f]), (172800, [a, b])]]]

def N : Integer := length ISDB
def minSup : Integer := ceiling (0.5 * N)

def C1 : Integer := 0      -- min_interval
def C2 : Integer := 172800 -- max_interval
def C3 : Integer := 0      -- min_whole_interval
def C4 : Integer := 300000 -- max_whole_interval

def I (t: Integer) : Integer := floor (rtof (t / (60 * 60 * 24)))

--
-- Utils
--

def query {a, b, c} : Matcher [(Integer, a)] := list (integer, eq)

def sequence {a, b, c} : Matcher [(Integer, [a])] := list (time, list eq)

def time {a, b} : Matcher Integer := matcher
  | interval $ $ as (integer, integer) with
    | $t -> [(I t, t)]
  | $ as something with
    | $tgt -> [tgt]


--
-- Algorithm
--

-- calculate ISDB|α
def project {Eq a} (α: [(Integer, a)]) (ISDB: [[[(Integer, [a])]]]) : [[[(Integer, [a])]]] := match α as query with
  | (#0, $x) :: $α' -> project' α' (map (\xss -> matchAllDFS xss as set sequence with
                                                 | (_ ++ ($t, _ ++ #x :: $cs) :: $ls) :: _
                                                 -> (0, cs) :: (map (\t' xs -> (t' - t, xs)) ls))
                                        ISDB)

def project' α ISDB := match α as query with
  | [] -> ISDB
  | ($a, $x) :: $α' -> project' (map (\b y -> (b - a, y))  α')
                                (map (\xss -> matchAllDFS xss as set sequence with
                                              | (_ ++ (interval #a $t, _ ++ #x :: $cs) :: $ls) :: _
                                              -> (0, cs) :: (map (\t' xs -> (t' - t, xs)) ls))
                                     ISDB)
  
-- main function
def gspm items ISDB I minSup C1 C2 C3 C4 :=
  let φ := [] in
  let R := [] in
  let fs := filter (\α ISDB' -> match ISDB' as multiset sequence with
                                | loop $i (1, minSup) (![] :: ...) _ -> True
                                | _ -> False)
                   (map (\α -> (α, project α ISDB)) (map (\x -> [(0, x)]) items)) in
  let iss := map (\α ISDB' -> α) fs in
  iss ++ concat (map (\α ISDB' -> projection α ISDB' I minSup C1 C2 C3 C4) fs)

def projection α ISDB' I minSup C1 C2 C3 C4 :=
  let fs := filter (\a t x -> C1 <= t && t <= C2) (freqItem ISDB' minSup C1 C2 C3 C4) in
  let iss' := map (\a t x -> α ++ [(a, x)]) fs in
  -- TODO: apply C4
  -- TODO: apply C3
  iss' ++ concat (map (\α' -> projection α' (project α' ISDB) I minSup C1 C2 C3 C4)
                      iss')

def freqItem ISDB minSup C1 C2 C3 C4 :=
  matchAll ISDB as list (list sequence) with
  | first (interval $a $t) $x
      (loop $i (2, minSup)
         (first (interval #a _) #x ...)
         !(first (interval #a _) #x _))
  -> (a, t, x)

def first := \pt px ps =>
  {@ ++ (@ ++ (@ ++ ((interval $t _ & ~pt), _ ++ ($x & ~px) :: _) :: _) :: _) :: @,
   (!(_ ++ (_ ++ (_ ++ (interval #t _, _ ++ #x :: _) :: _) :: _) :: _),
    !(_ ++ (_ ++ (interval #t _, _ ++ #x :: _) :: _) :: _),
    !(_ ++ (interval #t _, _ ++ #x :: _) :: _),
    ~ps)}

--
-- Execute
--

--gspm items ISDB I minSup C1 C2 C3 C4


--
-- Test
--


assertEqual "project (level 1)"
  (project [(0, a)] ISDB)
  [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]], [[(0, [d]), (259200, [c])]], [[(0, [e, f]), (172800, [a, b])], [(0, [b])]]]

assertEqual "project (level 2)"
  (project [(0, a),(0, b)] ISDB)
  [[[(0, [c]), (172800, [a, c])]], [], [[(0, [])]]]

assertEqual "project (level 2)"
  (project [(0, a),(2, a)] ISDB)
  [[[(0, [c])]], [], [[(0, [b])]]]

assertEqual "freqItem"
  (freqItem
     [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]], [[(0, [d]), (259200, [c])]], [[(0, [e, f]), (172800, [a, b])], [(0, [b])]]]
     minSup C1 C2 C3 C4)
  [(0, 0, b), (3, 259200, c), (2, 172800, a)]

assertEqual "filter freqItem by interval"
  (filter (\a t x -> C1 <= t && t <= C2)
    (freqItem
       [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]],
        [[(0, [d]), (259200, [c])]],
        [[(0, [b])]]]
       minSup C1 C2 C3 C4))
  [(0, 0, b)]

assertEqual "gspm result"
  (gspm items ISDB I minSup C1 C2 C3 C4)
  [[(0, a)], [(0, b)], [(0, c)], [(0, a), (0, b)], [(0, a), (2, a)]]