path: root/compiler/GHC/Data/Graph/Inductive/Graph.hs

-- (c) 1999-2005 by Martin Erwig (see copyright at bottom)
-- | Static and Dynamic Inductive Graphs
--
-- Code is from Hackage `fgl` package version 5.7.0.3
--
module GHC.Data.Graph.Inductive.Graph (
    -- * General Type Defintions
    -- ** Node and Edge Types
    Node,LNode,UNode,
    Edge,LEdge,UEdge,
    -- ** Types Supporting Inductive Graph View
    Adj,Context,MContext,Decomp,GDecomp,UContext,UDecomp,
    Path,LPath(..),UPath,
    -- * Graph Type Classes
    -- | We define two graph classes:
    --
    --   Graph: static, decomposable graphs.
    --    Static means that a graph itself cannot be changed
    --
    --   DynGraph: dynamic, extensible graphs.
    --             Dynamic graphs inherit all operations from static graphs
    --             but also offer operations to extend and change graphs.
    --
    -- Each class contains in addition to its essential operations those
    -- derived operations that might be overwritten by a more efficient
    -- implementation in an instance definition.
    --
    -- Note that labNodes is essentially needed because the default definition
    -- for matchAny is based on it: we need some node from the graph to define
    -- matchAny in terms of match. Alternatively, we could have made matchAny
    -- essential and have labNodes defined in terms of ufold and matchAny.
    -- However, in general, labNodes seems to be (at least) as easy to define
    -- as matchAny. We have chosen labNodes instead of the function nodes since
    -- nodes can be easily derived from labNodes, but not vice versa.
    Graph(..),
    DynGraph(..),
    -- * Operations
    order,
    size,
    -- ** Graph Folds and Maps
    ufold,gmap,nmap,emap,nemap,
    -- ** Graph Projection
    nodes,edges,toEdge,edgeLabel,toLEdge,newNodes,gelem,
    -- ** Graph Construction and Destruction
    insNode,insEdge,delNode,delEdge,delLEdge,delAllLEdge,
    insNodes,insEdges,delNodes,delEdges,
    buildGr,mkUGraph,
    -- ** Subgraphs
    gfiltermap,nfilter,labnfilter,labfilter,subgraph,
    -- ** Graph Inspection
    context,lab,neighbors,lneighbors,
    suc,pre,lsuc,lpre,
    out,inn,outdeg,indeg,deg,
    hasEdge,hasNeighbor,hasLEdge,hasNeighborAdj,
    equal,
    -- ** Context Inspection
    node',lab',labNode',neighbors',lneighbors',
    suc',pre',lpre',lsuc',
    out',inn',outdeg',indeg',deg',
    -- * Pretty-printing
    prettify,
    prettyPrint,
    -- * Ordering of Graphs
    OrdGr(..)
) where

import GHC.Prelude

import           Control.Arrow (first)
import           Data.Function (on)
import qualified Data.IntSet   as IntSet
import           Data.List     (delete, groupBy, sort, sortBy, (\\))
import           Data.Maybe    (fromMaybe, isJust)

import GHC.Utils.Panic

-- | Unlabeled node
type  Node   = Int
-- | Labeled node
type LNode a = (Node,a)
-- | Quasi-unlabeled node
type UNode   = LNode ()

-- | Unlabeled edge
type  Edge   = (Node,Node)
-- | Labeled edge
type LEdge b = (Node,Node,b)
-- | Quasi-unlabeled edge
type UEdge   = LEdge ()

-- | Unlabeled path
type Path    = [Node]
-- | Labeled path
newtype LPath a = LP { unLPath :: [LNode a] }

instance (Show a) => Show (LPath a) where
  show (LP xs) = show xs

instance (Eq a) => Eq (LPath a) where
  (LP [])        == (LP [])        = True
  (LP ((_,x):_)) == (LP ((_,y):_)) = x==y
  (LP _)         == (LP _)         = False

instance (Ord a) => Ord (LPath a) where
  compare (LP [])        (LP [])        = EQ
  compare (LP ((_,x):_)) (LP ((_,y):_)) = compare x y
  compare _ _ = panic "LPath: cannot compare two empty paths"

-- | Quasi-unlabeled path
type UPath   = [UNode]

-- | Labeled links to or from a 'Node'.
type Adj b        = [(b,Node)]
-- | Links to the 'Node', the 'Node' itself, a label, links from the 'Node'.
--
--   In other words, this captures all information regarding the
--   specified 'Node' within a graph.
type Context a b  = (Adj b,Node,a,Adj b) -- Context a b "=" Context' a b "+" Node
type MContext a b = Maybe (Context a b)
-- | 'Graph' decomposition - the context removed from a 'Graph', and the rest
-- of the 'Graph'.
type Decomp g a b = (MContext a b,g a b)
-- | The same as 'Decomp', only more sure of itself.
type GDecomp g a b  = (Context a b,g a b)

-- | Unlabeled context.
type UContext     = ([Node],Node,[Node])
-- | Unlabeled decomposition.
type UDecomp g    = (Maybe UContext,g)

-- | Minimum implementation: 'empty', 'isEmpty', 'match', 'mkGraph', 'labNodes'
class Graph gr where
  {-# MINIMAL empty, isEmpty, match, mkGraph, labNodes #-}

  -- | An empty 'Graph'.
  empty     :: gr a b

  -- | True if the given 'Graph' is empty.
  isEmpty   :: gr a b -> Bool

  -- | Decompose a 'Graph' into the 'MContext' found for the given node and the
  -- remaining 'Graph'.
  match     :: Node -> gr a b -> Decomp gr a b

  -- | Create a 'Graph' from the list of 'LNode's and 'LEdge's.
  --
  --   For graphs that are also instances of 'DynGraph', @mkGraph ns
  --   es@ should be equivalent to @('insEdges' es . 'insNodes' ns)
  --   'empty'@.
  mkGraph   :: [LNode a] -> [LEdge b] -> gr a b

  -- | A list of all 'LNode's in the 'Graph'.
  labNodes  :: gr a b -> [LNode a]

  -- | Decompose a graph into the 'Context' for an arbitrarily-chosen 'Node'
  -- and the remaining 'Graph'.
  matchAny  :: gr a b -> GDecomp gr a b
  matchAny g = case labNodes g of
                 []      -> panic "Match Exception, Empty Graph"
                 (v,_):_ | (Just c,g') <- match v g -> (c,g')
                 _       -> panic "This can't happen: failed to match node in graph"


  -- | The number of 'Node's in a 'Graph'.
  noNodes   :: gr a b -> Int
  noNodes = length . labNodes

  -- | The minimum and maximum 'Node' in a 'Graph'.
  nodeRange :: gr a b -> (Node,Node)
  nodeRange g
    | isEmpty g = panic "nodeRange of empty graph"
    | otherwise = (minimum vs, maximum vs)
    where
      vs = nodes g

  -- | A list of all 'LEdge's in the 'Graph'.
  labEdges  :: gr a b -> [LEdge b]
  labEdges = ufold (\(_,v,_,s)->(map (\(l,w)->(v,w,l)) s ++)) []

class (Graph gr) => DynGraph gr where
  -- | Merge the 'Context' into the 'DynGraph'.
  --
  --   Context adjacencies should only refer to either a Node already
  --   in a graph or the node in the Context itself (for loops).
  --
  --   Behaviour is undefined if the specified 'Node' already exists
  --   in the graph.
  (&) :: Context a b -> gr a b -> gr a b


-- | The number of nodes in the graph.  An alias for 'noNodes'.
order :: (Graph gr) => gr a b -> Int
order = noNodes

-- | The number of edges in the graph.
--
--   Note that this counts every edge found, so if you are
--   representing an unordered graph by having each edge mirrored this
--   will be incorrect.
--
--   If you created an unordered graph by either mirroring every edge
--   (including loops!) or using the @undir@ function in
--   "Data.Graph.Inductive.Basic" then you can safely halve the value
--   returned by this.
size :: (Graph gr) => gr a b -> Int
size = length . labEdges

-- | Fold a function over the graph by recursively calling 'match'.
ufold :: (Graph gr) => (Context a b -> c -> c) -> c -> gr a b -> c
ufold f u g
  | isEmpty g = u
  | otherwise = f c (ufold f u g')
  where
    (c,g') = matchAny g

-- | Map a function over the graph by recursively calling 'match'.
gmap :: (DynGraph gr) => (Context a b -> Context c d) -> gr a b -> gr c d
gmap f = ufold (\c->(f c&)) empty
{-# NOINLINE [0] gmap #-}

-- | Map a function over the 'Node' labels in a graph.
nmap :: (DynGraph gr) => (a -> c) -> gr a b -> gr c b
nmap f = gmap (\(p,v,l,s)->(p,v,f l,s))
{-# NOINLINE [0] nmap #-}

-- | Map a function over the 'Edge' labels in a graph.
emap :: (DynGraph gr) => (b -> c) -> gr a b -> gr a c
emap f = gmap (\(p,v,l,s)->(map1 f p,v,l,map1 f s))
  where
    map1 g = map (first g)
{-# NOINLINE [0] emap #-}

-- | Map functions over both the 'Node' and 'Edge' labels in a graph.
nemap :: (DynGraph gr) => (a -> c) -> (b -> d) -> gr a b -> gr c d
nemap fn fe = gmap (\(p,v,l,s) -> (fe' p,v,fn l,fe' s))
  where
    fe' = map (first fe)
{-# NOINLINE [0] nemap #-}

-- | List all 'Node's in the 'Graph'.
nodes :: (Graph gr) => gr a b -> [Node]
nodes = map fst . labNodes

-- | List all 'Edge's in the 'Graph'.
edges :: (Graph gr) => gr a b -> [Edge]
edges = map toEdge . labEdges

-- | Drop the label component of an edge.
toEdge :: LEdge b -> Edge
toEdge (v,w,_) = (v,w)

-- | Add a label to an edge.
toLEdge :: Edge -> b -> LEdge b
toLEdge (v,w) l = (v,w,l)

-- | The label in an edge.
edgeLabel :: LEdge b -> b
edgeLabel (_,_,l) = l

-- | List N available 'Node's, i.e. 'Node's that are not used in the 'Graph'.
newNodes :: (Graph gr) => Int -> gr a b -> [Node]
newNodes i g
  | isEmpty g = [0..i-1]
  | otherwise = [n+1..n+i]
  where
    (_,n) = nodeRange g

-- | 'True' if the 'Node' is present in the 'Graph'.
gelem :: (Graph gr) => Node -> gr a b -> Bool
gelem v = isJust . fst . match v

-- | Insert a 'LNode' into the 'Graph'.
insNode :: (DynGraph gr) => LNode a -> gr a b -> gr a b
insNode (v,l) = (([],v,l,[])&)
{-# NOINLINE [0] insNode #-}

-- | Insert a 'LEdge' into the 'Graph'.
insEdge :: (DynGraph gr) => LEdge b -> gr a b -> gr a b
insEdge (v,w,l) g = (pr,v,la,(l,w):su) & g'
  where
    (mcxt,g') = match v g
    (pr,_,la,su) = fromMaybe
                     (panic ("insEdge: cannot add edge from non-existent vertex " ++ show v))
                     mcxt
{-# NOINLINE [0] insEdge #-}

-- | Remove a 'Node' from the 'Graph'.
delNode :: (Graph gr) => Node -> gr a b -> gr a b
delNode v = delNodes [v]

-- | Remove an 'Edge' from the 'Graph'.
--
--   NOTE: in the case of multiple edges, this will delete /all/ such
--   edges from the graph as there is no way to distinguish between
--   them.  If you need to delete only a single such edge, please use
--   'delLEdge'.
delEdge :: (DynGraph gr) => Edge -> gr a b -> gr a b
delEdge (v,w) g = case match v g of
                    (Nothing,_)          -> g
                    (Just (p,v',l,s),g') -> (p,v',l,filter ((/=w).snd) s) & g'

-- | Remove an 'LEdge' from the 'Graph'.
--
--   NOTE: in the case of multiple edges with the same label, this
--   will only delete the /first/ such edge.  To delete all such
--   edges, please use 'delAllLedge'.
delLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b
delLEdge = delLEdgeBy delete

-- | Remove all edges equal to the one specified.
delAllLEdge :: (DynGraph gr, Eq b) => LEdge b -> gr a b -> gr a b
delAllLEdge = delLEdgeBy (filter . (/=))

delLEdgeBy :: (DynGraph gr) => ((b,Node) -> Adj b -> Adj b)
              -> LEdge b -> gr a b -> gr a b
delLEdgeBy f (v,w,b) g = case match v g of
                           (Nothing,_)          -> g
                           (Just (p,v',l,s),g') -> (p,v',l,f (b,w) s) & g'

-- | Insert multiple 'LNode's into the 'Graph'.
insNodes   :: (DynGraph gr) => [LNode a] -> gr a b -> gr a b
insNodes vs g = foldl' (flip insNode) g vs
{-# INLINABLE insNodes #-}

-- | Insert multiple 'LEdge's into the 'Graph'.
insEdges :: (DynGraph gr) => [LEdge b] -> gr a b -> gr a b
insEdges es g = foldl' (flip insEdge) g es
{-# INLINABLE insEdges #-}

-- | Remove multiple 'Node's from the 'Graph'.
delNodes :: (Graph gr) => [Node] -> gr a b -> gr a b
delNodes vs g = foldl' (snd .: flip match) g vs

-- | Remove multiple 'Edge's from the 'Graph'.
delEdges :: (DynGraph gr) => [Edge] -> gr a b -> gr a b
delEdges es g = foldl' (flip delEdge) g es

-- | Build a 'Graph' from a list of 'Context's.
--
--   The list should be in the order such that earlier 'Context's
--   depend upon later ones (i.e. as produced by @'ufold' (:) []@).
buildGr :: (DynGraph gr) => [Context a b] -> gr a b
buildGr = foldr (&) empty

-- | Build a quasi-unlabeled 'Graph'.
mkUGraph :: (Graph gr) => [Node] -> [Edge] -> gr () ()
mkUGraph vs es = mkGraph (labUNodes vs) (labUEdges es)
   where
     labUEdges = map (`toLEdge` ())
     labUNodes = map (flip (,) ())

-- | Build a graph out of the contexts for which the predicate is
-- satisfied by recursively calling 'match'.
gfiltermap :: DynGraph gr => (Context a b -> MContext c d) -> gr a b -> gr c d
gfiltermap f = ufold (maybe id (&) . f) empty

-- | Returns the subgraph only containing the labelled nodes which
-- satisfy the given predicate.
labnfilter :: Graph gr => (LNode a -> Bool) -> gr a b -> gr a b
labnfilter p gr = delNodes (map fst . filter (not . p) $ labNodes gr) gr

-- | Returns the subgraph only containing the nodes which satisfy the
-- given predicate.
nfilter :: DynGraph gr => (Node -> Bool) -> gr a b -> gr a b
nfilter f = labnfilter (f . fst)

-- | Returns the subgraph only containing the nodes whose labels
-- satisfy the given predicate.
labfilter :: DynGraph gr => (a -> Bool) -> gr a b -> gr a b
labfilter f = labnfilter (f . snd)

-- | Returns the subgraph induced by the supplied nodes.
subgraph :: DynGraph gr => [Node] -> gr a b -> gr a b
subgraph vs = let vs' = IntSet.fromList vs
              in nfilter (`IntSet.member` vs')

-- | Find the context for the given 'Node'.  Causes an error if the 'Node' is
-- not present in the 'Graph'.
context :: (Graph gr) => gr a b -> Node -> Context a b
context g v = fromMaybe (panic ("Match Exception, Node: "++show v))
                        (fst (match v g))

-- | Find the label for a 'Node'.
lab :: (Graph gr) => gr a b -> Node -> Maybe a
lab g v = fmap lab' . fst $ match v g

-- | Find the neighbors for a 'Node'.
neighbors :: (Graph gr) => gr a b -> Node -> [Node]
neighbors = map snd .: lneighbors

-- | Find the labelled links coming into or going from a 'Context'.
lneighbors :: (Graph gr) => gr a b -> Node -> Adj b
lneighbors = maybe [] lneighbors' .: mcontext

-- | Find all 'Node's that have a link from the given 'Node'.
suc :: (Graph gr) => gr a b -> Node -> [Node]
suc = map snd .: context4l

-- | Find all 'Node's that link to to the given 'Node'.
pre :: (Graph gr) => gr a b -> Node -> [Node]
pre = map snd .: context1l

-- | Find all 'Node's that are linked from the given 'Node' and the label of
-- each link.
lsuc :: (Graph gr) => gr a b -> Node -> [(Node,b)]
lsuc = map flip2 .: context4l

-- | Find all 'Node's that link to the given 'Node' and the label of each link.
lpre :: (Graph gr) => gr a b -> Node -> [(Node,b)]
lpre = map flip2 .: context1l

-- | Find all outward-bound 'LEdge's for the given 'Node'.
out :: (Graph gr) => gr a b -> Node -> [LEdge b]
out g v = map (\(l,w)->(v,w,l)) (context4l g v)

-- | Find all inward-bound 'LEdge's for the given 'Node'.
inn :: (Graph gr) => gr a b -> Node -> [LEdge b]
inn g v = map (\(l,w)->(w,v,l)) (context1l g v)

-- | The outward-bound degree of the 'Node'.
outdeg :: (Graph gr) => gr a b -> Node -> Int
outdeg = length .: context4l

-- | The inward-bound degree of the 'Node'.
indeg :: (Graph gr) => gr a b -> Node -> Int
indeg  = length .: context1l

-- | The degree of the 'Node'.
deg :: (Graph gr) => gr a b -> Node -> Int
deg = deg' .: context

-- | The 'Node' in a 'Context'.
node' :: Context a b -> Node
node' (_,v,_,_) = v

-- | The label in a 'Context'.
lab' :: Context a b -> a
lab' (_,_,l,_) = l

-- | The 'LNode' from a 'Context'.
labNode' :: Context a b -> LNode a
labNode' (_,v,l,_) = (v,l)

-- | All 'Node's linked to or from in a 'Context'.
neighbors' :: Context a b -> [Node]
neighbors' (p,_,_,s) = map snd p++map snd s

-- | All labelled links coming into or going from a 'Context'.
lneighbors' :: Context a b -> Adj b
lneighbors' (p,_,_,s) = p ++ s

-- | All 'Node's linked to in a 'Context'.
suc' :: Context a b -> [Node]
suc' = map snd . context4l'

-- | All 'Node's linked from in a 'Context'.
pre' :: Context a b -> [Node]
pre' = map snd . context1l'

-- | All 'Node's linked from in a 'Context', and the label of the links.
lsuc' :: Context a b -> [(Node,b)]
lsuc' = map flip2 . context4l'

-- | All 'Node's linked from in a 'Context', and the label of the links.
lpre' :: Context a b -> [(Node,b)]
lpre' = map flip2 . context1l'

-- | All outward-directed 'LEdge's in a 'Context'.
out' :: Context a b -> [LEdge b]
out' c@(_,v,_,_) = map (\(l,w)->(v,w,l)) (context4l' c)

-- | All inward-directed 'LEdge's in a 'Context'.
inn' :: Context a b -> [LEdge b]
inn' c@(_,v,_,_) = map (\(l,w)->(w,v,l)) (context1l' c)

-- | The outward degree of a 'Context'.
outdeg' :: Context a b -> Int
outdeg' = length . context4l'

-- | The inward degree of a 'Context'.
indeg' :: Context a b -> Int
indeg' = length . context1l'

-- | The degree of a 'Context'.
deg' :: Context a b -> Int
deg' (p,_,_,s) = length p+length s

-- | Checks if there is a directed edge between two nodes.
hasEdge :: Graph gr => gr a b -> Edge -> Bool
hasEdge gr (v,w) = w `elem` suc gr v

-- | Checks if there is an undirected edge between two nodes.
hasNeighbor :: Graph gr => gr a b -> Node -> Node -> Bool
hasNeighbor gr v w = w `elem` neighbors gr v

-- | Checks if there is a labelled edge between two nodes.
hasLEdge :: (Graph gr, Eq b) => gr a b -> LEdge b -> Bool
hasLEdge gr (v,w,l) = (w,l) `elem` lsuc gr v

-- | Checks if there is an undirected labelled edge between two nodes.
hasNeighborAdj :: (Graph gr, Eq b) => gr a b -> Node -> (b,Node) -> Bool
hasNeighborAdj gr v a = a `elem` lneighbors gr v

----------------------------------------------------------------------
-- GRAPH EQUALITY
----------------------------------------------------------------------

slabNodes :: (Graph gr) => gr a b -> [LNode a]
slabNodes = sortBy (compare `on` fst) . labNodes

glabEdges :: (Graph gr) => gr a b -> [GroupEdges b]
glabEdges = map (GEs . groupLabels)
            . groupBy ((==) `on` toEdge)
            . sortBy (compare `on` toEdge)
            . labEdges
  where
    groupLabels les = toLEdge (toEdge (head les)) (map edgeLabel les)

equal :: (Eq a,Eq b,Graph gr) => gr a b -> gr a b -> Bool
equal g g' = slabNodes g == slabNodes g' && glabEdges g == glabEdges g'
-- This assumes that nodes aren't repeated (which shouldn't happen for
-- sane graph instances).  If node IDs are repeated, then the usage of
-- slabNodes cannot guarantee stable ordering.

-- Newtype wrapper just to test for equality of multiple edges.  This
-- is needed because without an Ord constraint on `b' it is not
-- possible to guarantee a stable ordering on edge labels.
newtype GroupEdges b = GEs (LEdge [b])
  deriving (Show, Read)

instance (Eq b) => Eq (GroupEdges b) where
  (GEs (v1,w1,bs1)) == (GEs (v2,w2,bs2)) = v1 == v2
                                           && w1 == w2
                                           && eqLists bs1 bs2

eqLists :: (Eq a) => [a] -> [a] -> Bool
eqLists xs ys = null (xs \\ ys) && null (ys \\ xs)
-- OK to use \\ here as we want each value in xs to cancel a *single*
-- value in ys.

----------------------------------------------------------------------
-- UTILITIES
----------------------------------------------------------------------

-- auxiliary functions used in the implementation of the
-- derived class members
--
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
-- f .: g = \x y->f (g x y)
-- f .: g = (f .) . g
-- (.:) f = ((f .) .)
-- (.:) = (.) (.) (.)
(.:) = (.) . (.)

flip2 :: (a,b) -> (b,a)
flip2 (x,y) = (y,x)

-- projecting on context elements
--
context1l :: (Graph gr) => gr a b -> Node -> Adj b
context1l = maybe [] context1l' .: mcontext

context4l :: (Graph gr) => gr a b -> Node -> Adj b
context4l = maybe [] context4l' .: mcontext

mcontext :: (Graph gr) => gr a b -> Node -> MContext a b
mcontext = fst .: flip match

context1l' :: Context a b -> Adj b
context1l' (p,v,_,s) = p++filter ((==v).snd) s

context4l' :: Context a b -> Adj b
context4l' (p,v,_,s) = s++filter ((==v).snd) p

----------------------------------------------------------------------
-- PRETTY PRINTING
----------------------------------------------------------------------

-- | Pretty-print the graph.  Note that this loses a lot of
--   information, such as edge inverses, etc.
prettify :: (DynGraph gr, Show a, Show b) => gr a b -> String
prettify g = foldr (showsContext . context g) id (nodes g) ""
  where
    showsContext (_,n,l,s) sg = shows n . (':':) . shows l
                                . showString "->" . shows s
                                . ('\n':) . sg

-- | Pretty-print the graph to stdout.
prettyPrint :: (DynGraph gr, Show a, Show b) => gr a b -> IO ()
prettyPrint = putStr . prettify

----------------------------------------------------------------------
-- Ordered Graph
----------------------------------------------------------------------

-- | OrdGr comes equipped with an Ord instance, so that graphs can be
--   used as e.g. Map keys.
newtype OrdGr gr a b = OrdGr { unOrdGr :: gr a b }
  deriving (Read,Show)

instance (Graph gr, Ord a, Ord b) => Eq (OrdGr gr a b) where
  g1 == g2 = compare g1 g2 == EQ

instance (Graph gr, Ord a, Ord b) => Ord (OrdGr gr a b) where
  compare (OrdGr g1) (OrdGr g2) =
    (compare `on` sort . labNodes) g1 g2
    `mappend` (compare `on` sort . labEdges) g1 g2


{-----------------------------------------------------------------

Copyright (c) 1999-2008, Martin Erwig
              2010, Ivan Lazar Miljenovic
              2022, Norman Ramsey
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice,
   this list of conditions and the following disclaimer.

2. 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.

3. Neither the name of the author 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.

----------------------------------------------------------------}