--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

)abbrev package ORDFUNS OrderingFunctions
++ Author: Barry Trager
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors: OrderedDirectProduct
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++    This package provides ordering functions on vectors which
++ are suitable parameters for OrderedDirectProduct.

OrderingFunctions(dim,S) : T == C  where
  dim : NonNegativeInteger
  S         : OrderedAbelianMonoid
  VS       == Vector S

  T ==  with
     pureLex    :  (VS,VS)  -> Boolean
       ++ pureLex(v1,v2) return true if the vector v1 is less than the
       ++ vector v2 in the lexicographic ordering.
     totalLex   :  (VS,VS)  -> Boolean
       ++ totalLex(v1,v2) return true if the vector v1 is less than the
       ++ vector v2 in the ordering which is total degree refined by
       ++ lexicographic ordering.
     reverseLex :  (VS,VS)  -> Boolean
       ++ reverseLex(v1,v2) return true if the vector v1 is less than the
       ++ vector v2 in the ordering which is total degree refined by
       ++ the reverse lexicographic ordering.

  C == add
    n:NonNegativeInteger:=dim

 -- pure lexicographical ordering
    pureLex(v1:VS,v2:VS) : Boolean ==
      for i in 1..n repeat
        if qelt(v1,i) < qelt(v2,i) then return true
        if qelt(v2,i) < qelt(v1,i) then return false
      false

 -- total ordering refined with lex
    totalLex(v1:VS,v2:VS) :Boolean ==
      n1:S:=0
      n2:S:=0
      for i in 1..n repeat
        n1:= n1+qelt(v1,i)
        n2:=n2+qelt(v2,i)
      n1<n2 => true
      n2<n1 => false
      for i in 1..n repeat
        if qelt(v1,i) < qelt(v2,i) then return true
        if qelt(v2,i) < qelt(v1,i) then return false
      false

 -- reverse lexicographical ordering
    reverseLex(v1:VS,v2:VS) :Boolean ==
      n1:S:=0
      n2:S:=0
      for i in 1..n repeat
        n1:= n1+qelt(v1,i)
        n2:=n2+qelt(v2,i)
      n1<n2 => true
      n2<n1 => false
      for i in reverse(1..n) repeat
        if qelt(v2,i) < qelt(v1,i) then return true
        if qelt(v1,i) < qelt(v2,i) then return false
      false

)abbrev domain ODP OrderedDirectProduct

++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors: Vector, DirectProduct
++ Also See: HomogeneousDirectProduct, SplitHomogeneousDirectProduct
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++   This type represents the finite direct or cartesian product of an
++ underlying ordered component type. The ordering on the type is determined
++ by its third argument which represents the less than function on
++ vectors. This type is a suitable third argument for
++ \spadtype{GeneralDistributedMultivariatePolynomial}.

OrderedDirectProduct(dim:NonNegativeInteger,
                     S:OrderedAbelianMonoidSup,
                      f:(Vector(S),Vector(S))->Boolean):T
                             == C where
   T == DirectProductCategory(dim,S)
   C == DirectProduct(dim,S) add
        Rep:=Vector(S)
        x:% < y:% == f(x::Rep,y::Rep)

)abbrev domain HDP HomogeneousDirectProduct
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors: Vector, DirectProduct
++ Also See: OrderedDirectProduct, SplitHomogeneousDirectproduct
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++   This type represents the finite direct or cartesian product of an
++ underlying ordered component type. The vectors are ordered first
++ by the sum of their components, and then refined using a reverse
++ lexicographic ordering. This type is a suitable third argument for
++ \spadtype{GeneralDistributedMultivariatePolynomial}.

HomogeneousDirectProduct(dim,S) : T == C where
   dim : NonNegativeInteger
   S         : OrderedAbelianMonoidSup

   T == DirectProductCategory(dim,S)
   C == DirectProduct(dim,S) add
        Rep:=Vector(S)
        v1:% < v2:% ==
 -- reverse lexicographical ordering
          n1:S:=0
          n2:S:=0
          for i in 1..dim repeat
            n1:= n1+qelt(v1,i)
            n2:=n2+qelt(v2,i)
          n1<n2 => true
          n2<n1 => false
          for i in reverse(1..dim) repeat
            if qelt(v2,i) < qelt(v1,i) then return true
            if qelt(v1,i) < qelt(v2,i) then return false
          false

)abbrev domain SHDP SplitHomogeneousDirectProduct
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors: Vector, DirectProduct
++ Also See: OrderedDirectProduct, HomogeneousDirectProduct
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++   This type represents the finite direct or cartesian product of an
++ underlying ordered component type. The vectors are ordered as if
++ they were split into two blocks. The dim1 parameter specifies the
++ length of the first block. The ordering is lexicographic between
++ the blocks but acts like \spadtype{HomogeneousDirectProduct}
++ within each block. This type is a suitable third argument for
++ \spadtype{GeneralDistributedMultivariatePolynomial}.

SplitHomogeneousDirectProduct(dimtot,dim1,S) : T == C where
   NNI ==> NonNegativeInteger
   dim1,dimtot : NNI
   S         : OrderedAbelianMonoidSup

   T == DirectProductCategory(dimtot,S)
   C == DirectProduct(dimtot,S) add
        Rep:=Vector(S)
        lessThanRlex(v1:%,v2:%,low:NNI,high:NNI):Boolean ==
 -- reverse lexicographical ordering
          n1:S:=0
          n2:S:=0
          for i in low..high repeat
            n1:= n1+qelt(v1,i)
            n2:=n2+qelt(v2,i)
          n1<n2 => true
          n2<n1 => false
          for i in reverse(low..high) repeat
            if qelt(v2,i) < qelt(v1,i) then return true
            if qelt(v1,i) < qelt(v2,i) then return false
          false

        (v1:% < v2:%):Boolean ==
	  lessThanRlex(v1,v2,1,dim1) => true
	  for i in 1..dim1 repeat
		if qelt(v1,i) ~= qelt(v2,i) then return false
	  lessThanRlex(v1,v2,dim1+1,dimtot)

