collections-0.3: Data/Tree/AVL/Size.hs

{-# OPTIONS_GHC -fglasgow-exts #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Tree.AVL.Size
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png
-- Stability   :  stable
-- Portability :  portable
--
-- AVL Tree size related utilities.
-----------------------------------------------------------------------------
module Data.Tree.AVL.Size
        (-- * AVL tree size utilities.
         size,addSize,
        ) where 

import Data.Tree.AVL.Types(AVL)
import Data.Tree.AVL.Internals.HeightUtils(fastAddSize)

#ifdef __GLASGOW_HASKELL__
import GHC.Base
#include "ghcdefs.h"
#else
#include "h98defs.h"
#endif

-- | Counts the total number of elements in an AVL tree.
--
-- Complexity: O(n)
{-# INLINE size #-}
size :: AVL e -> Int
size = addSize 0

-- | Adds the size of a tree to the first argument.
--
-- Complexity: O(n)
{-# INLINE addSize #-}
addSize :: Int -> AVL e -> Int
addSize ASINT(n) t = ASINT(fastAddSize n t)