{- |
  An 'Olist' is an /ordered list/. The main function of this module is the implementation of the finite subset structure of a given type @a@. Finite sets are represented as ordered lists and the basic set functions and relations like 'union', 'intersection', 'included' etc. are provided.
-}

module Olist (

  -- * The @Olist@ type

  Olist,

  -- * The construction and test for ordered lists

  olist,
  -- | For example,
  --
  -- > > olist ["b", "c", "b", "a", "c", "a"]
  -- > ["a","b","c"]
  --
  -- As the example shows, multiple occuring members are deleted.
  --
  -- (The implementation builts the ordered list with component-wise 'insert' and that is not an optimal sorting algorithm in general.
  -- But it is optimal, when the argument is an already ordered list. We use 'olist' only as a an additional safety-mechanism for
  -- functions like @ext :: p -> [a] -> p@, where in most cases the second argument will usually be an @Olist a@ value, anyway.)

  isOlist,
  -- | Checks if the given argument is ordered.

  -- * The empty list

  empty,
  -- | Returns the empty list @[]@, i.e.
  --
  -- > > Olist.empty
  -- > []
  --
  -- (Note, that there is also an @empty@ function in the @Costack@ module.)

  isEmpty,
  -- | Checks on emptiness; i.e. it is the same as the Haskell native @null@.
  --
  -- > > isEmpty [1,2,3]
  -- > False

  -- * Singular operations on ordered lists

  member,
  -- | For example,
  --
  -- > > member 7 [3,5,7,9]
  -- > True
  -- > > 4 `member` [2,3,4,5]
  -- > True

  insert,
  -- | For example,
  --
  -- > > insert 7 [3,5,9,11]
  -- > [3,5,7,9,11]
  -- > > insert 7 [3,5,7,9,11]
  -- > [3,5,7,9,11]

  delete,
  -- | For example,
  --
  -- > > delete 7 [3,5,7,9,11]
  -- > [3,5,9,11]
  -- > > delete 7 [3,5,9,11]
  -- > [3,5,9,11]

  -- * The common binary operations on sets

  -- | These functions all assume, that the arguments are actually 'Olist' values. Otherwise, the function doesn't terminate with an
  -- error, it just produces unintended results.

  included,
  -- | Implementation of ⊆ on (finite) sets. For example,
  --
  -- > > included "acd" "abcd"        -- recall, that "acd" is the list ['a', 'c', 'd']
  -- > True
  -- > > [2,4] `included` [1,2,3,4,5]
  -- > True

  properlyIncluded,
  -- | Implementation of the strict version ⊂ of ⊆, i.e. the first argument must be included, but different to the second one.

  disjunct,
  -- | Two finite sets, i.e. two ordered lists are /disjunct/ iff they do not have a common member. For example
  --
  -- > > disjunct "acd" "bef"
  -- > True
  -- > > "abc" `disjunct` "bef"
  -- > False
  -- > > [] `disjunct` [1,2,3]
  -- > True

  properlyDisjunct,
  -- | Two finite sets are /properly disjunct/ iff they are disjunct and none of them is empty.
  --
  -- > > [] `properlyDisjunct` [1,2,3]
  -- > False

  equal,
  -- | The equality of two finite sets; actually it is just another name for @(==)@ on ordered lists.

  union,
  -- | The implementation of ∪, for example
  --
  -- > > [1,2,4,5] `union` [1,3,5,7]
  -- > [1,2,3,4,5,7]

  intersection,
  -- | The implementation of ∩, for example
  --
  -- > > [1,2,4,5] `intersection` [1,3,5,7]
  -- > [1,5]

  difference,
  -- | Implementation of the difference operator \ on sets. For example,
  --
  -- > > [1,2,4,5] `difference` [1,3,5,7]
  -- > [2,4]

  opposition,
  -- | The /opposition/ or /symmetric difference/ @S@∇@T@ of two sets @S@, @T@ is defined as @(S\T)∪(T\S)@. For example,
  --
  -- > > [1,2,4,5] `opposition` [1,3,5,7]
  -- > [2,3,4,7]

  unionList,
  -- | Returns the union of a list of ordered lists. For example,
  --
  -- > > unionList [[1,3,5], [1,2,3], [1,5,9]]
  -- > [1,2,3,5,9]
  -- > > unionList []
  -- > []

  intersectionList,
  -- | Returns the intersection of a list of ordered lists. The result is undefined for the empty list.
  --
  -- > > intersectionList [[1,3,5], [1,2,3], [1,5,9]]
  -- > [1]
  -- > > intersectionList []
  -- > *** Exception: Olist.intersectionList: not defined for empty list argument

) where ---------------------------------------------------------------------------------------------------------------

-- the type of ordered lists

  type Olist a = [a]

-- order list construction

  olist :: Ord a => [a] -> Olist a
  olist [] = []
  olist (a:aL) = insert a (olist aL)

  isOlist :: Ord a => [a] -> Bool
  isOlist [] = True
  isOlist [a] = True
  isOlist (a:b:cL) = (a < b) && isOlist (b:cL)

-- empty list

  empty :: Ord a => Olist a
  empty = []

  isEmpty :: Ord a => Olist a -> Bool
  isEmpty = null

-- singular operations

  member :: Ord a => a -> Olist a -> Bool
  member a [] = False
  member a (b:bL) = case compare a b of
    LT -> False
    EQ -> True
    GT -> member a bL

  insert :: Ord a => a -> Olist a -> Olist a
  insert a [] = [a]
  insert a (b:bL) = case compare a b of
    LT -> a:b:bL
    EQ -> b:bL
    GT -> b : (insert a bL)

  delete :: Ord a => a -> Olist a -> Olist a
  delete a [] = []
  delete a (b:bL) = case compare a b of
    LT -> b:bL
    EQ -> bL
    GT -> b : (delete a bL)

-- binary operations

  included :: Ord a => Olist a -> Olist a -> Bool
  included [] bL = True
  included aL [] = False
  included (a:aL) (b:bL) = case compare a b of
    LT -> False
    EQ -> included aL bL
    GT -> included (a:aL) bL

  properlyIncluded :: Ord a => Olist a -> Olist a -> Bool
  properlyIncluded [] [] = False
  properlyIncluded [] bL = True
  properlyIncluded aL [] = False
  properlyIncluded (a:aL) (b:bL) = case compare a b of
    LT -> False
    EQ -> properlyIncluded aL bL
    GT -> included (a:aL) bL

  disjunct :: Ord a => Olist a -> Olist a -> Bool
  disjunct [] bL = True
  disjunct bL [] = True
  disjunct (a:aL) (b:bL) = case compare a b of
    LT -> disjunct aL (b:bL)
    EQ -> False
    GT -> disjunct (a:aL) bL

  properlyDisjunct :: Ord a => Olist a -> Olist a -> Bool
  properlyDisjunct [] bL = False
  properlyDisjunct bL [] = False
  properlyDisjunct (a:aL) (b:bL) = case compare a b of
    LT -> disjunct aL (b:bL)
    EQ -> False
    GT -> disjunct (a:aL) bL

  equal :: Ord a => Olist a -> Olist a -> Bool
  equal = (==)

  union :: Ord a => Olist a -> Olist a -> Olist a
  union [] bL = bL
  union aL [] = aL
  union (a:aL) (b:bL) = case compare a b of
    LT -> a : (union aL (b:bL))
    EQ -> a : (union aL bL)
    GT -> b : (union (a:aL) bL)

  intersection :: Ord a => Olist a -> Olist a -> Olist a
  intersection [] bL = []
  intersection aL [] = []
  intersection (a:aL) (b:bL) = case compare a b of
    LT -> intersection aL (b:bL)
    EQ -> a : (intersection aL bL)
    GT -> intersection (a:aL) bL

  difference :: Ord a => Olist a -> Olist a -> Olist a
  difference [] bL = []
  difference aL [] = aL
  difference (a:aL) (b:bL) = case compare a b of
    LT -> a : (difference aL (b:bL))
    EQ -> difference aL bL
    GT -> difference (a:aL) bL

  opposition :: Ord a => Olist a -> Olist a -> Olist a
  opposition [] bL = bL
  opposition aL [] = aL
  opposition (a:aL) (b:bL) = case compare a b of
    LT -> a : (opposition aL (b:bL))
    EQ -> opposition aL bL
    GT -> b : (opposition (a:aL) bL)

  unionList :: Ord a => [Olist a] -> Olist a
  unionList = foldl union []

  intersectionList :: Ord a => [Olist a] -> Olist a
  intersectionList [] = error "Olist.intersectionList: not defined for empty list argument"
  intersectionList aL = foldl1 intersection aL