(.module:
  [lux #*
   [abstract
    [equivalence (#+ Equivalence)]
    [functor (#+ Functor)]]
   [data
    [collection
     ["." list ("#;." monoid functor)]]]])

(type: #export (Queue a)
  {#front (List a)
   #rear (List a)})

(def: #export empty
  Queue
  {#front (list)
   #rear (list)})

(def: #export (from-list entries)
  (All [a] (-> (List a) (Queue a)))
  {#front entries
   #rear (list)})

(def: #export (to-list queue)
  (All [a] (-> (Queue a) (List a)))
  (let [(^slots [#front #rear]) queue]
    (list;compose front (list.reverse rear))))

(def: #export peek
  (All [a] (-> (Queue a) (Maybe a)))
  (|>> (get@ #front) list.head))

(def: #export (size queue)
  (All [a] (-> (Queue a) Nat))
  (let [(^slots [#front #rear]) queue]
    (n/+ (list.size front)
         (list.size rear))))

(def: #export empty?
  (All [a] (-> (Queue a) Bit))
  (|>> (get@ #front) list.empty?))

(def: #export (member? Equivalence<a> queue member)
  (All [a] (-> (Equivalence a) (Queue a) a Bit))
  (let [(^slots [#front #rear]) queue]
    (or (list.member? Equivalence<a> front member)
        (list.member? Equivalence<a> rear member))))

(def: #export (pop queue)
  (All [a] (-> (Queue a) (Queue a)))
  (case (get@ #front queue)
    (^ (list)) ## Empty...
    queue

    (^ (list _)) ## Front has dried up...
    (|> queue
        (set@ #front (list.reverse (get@ #rear queue)))
        (set@ #rear (list)))
    
    (^ (list& _ front')) ## Consume front!
    (|> queue
        (set@ #front front'))))

(def: #export (push val queue)
  (All [a] (-> a (Queue a) (Queue a)))
  (case (get@ #front queue)
    #.Nil
    (set@ #front (list val) queue)

    _
    (update@ #rear (|>> (#.Cons val)) queue)))

(structure: #export (equivalence Equivalence<a>)
  (All [a] (-> (Equivalence a) (Equivalence (Queue a))))
  (def: (= qx qy)
    (:: (list.equivalence Equivalence<a>) = (to-list qx) (to-list qy))))

(structure: #export functor (Functor Queue)
  (def: (map f fa)
    {#front (|> fa (get@ #front) (list;map f))
     #rear (|> fa (get@ #rear) (list;map f))}))