AvlTree 2.4 → 3.0

raw patch · 14 files changed

+164/−129 lines, 14 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

- Data.Tree.AVL: instance (Eq e) => Eq (AVL e)

- Data.Tree.AVL: instance (Ord e) => Ord (AVL e)

+ Data.Tree.AVL: addHeight :: Int# -> AVL e -> Int#

+ Data.Tree.AVL: compareHeight :: AVL a -> AVL b -> Ordering

+ Data.Tree.AVL: height :: AVL e -> Int#

Files

AvlTree.cabal +10/−10
CHANGELOG +10/−0
Data/Tree/AVL.hs +5/−1
Data/Tree/AVL/Height.hs +99/−0
Data/Tree/AVL/Internals/HAVL.hs +1/−1
Data/Tree/AVL/Internals/HeightUtils.hs +0/−98
Data/Tree/AVL/Join.hs +1/−1
Data/Tree/AVL/Set.hs +1/−1
Data/Tree/AVL/Size.hs +1/−1
Data/Tree/AVL/Test/AllTests.hs +2/−2
Data/Tree/AVL/Types.hs +7/−11
Data/Tree/AVL/Zipper.hs +1/−1
Data/Tree/AVLX.hs +0/−2
MasterTable.txt +26/−0

AvlTree.cabal view

@@ -1,5 +1,5 @@ Name:               AvlTree-Version:            2.4+Version:            3.0 Cabal-Version:      >= 1.2 Build-Type:         Simple License:            BSD3@@ -10,16 +10,16 @@ Stability:          Stable Homepage:           http://www.haskell.org/haskellwiki/AvlTree Package-Url:-Synopsis:           Balanced binary trees using AVL algorithm.+Synopsis:           Balanced binary trees using the AVL algorithm. Description:        A comprehensive library and efficient implementation of AVL trees. The raw AVL-                    API has been designed with efficiency and generality in mind, not elagance. It-                    contains all the stuff you really don't want to write yourself if you can avoid-                    it. This library may be useful for rolling your own Sets, Maps, Sequences, Queues-                    (for example).+                    API has been designed with efficiency and generality in mind, not elagance or+                    safety. It contains all the stuff you really don't want to write yourself if you+                    can avoid it. This library may be useful for rolling your own Sets, Maps, Sequences,+                    Queues (for example). Category:           Data Structures Tested-With:        GHC == 6.8.2, GHC == 6.8.1 Data-Files:-Extra-Source-Files: AUTHORS, CHANGELOG, Test/Test.hs, include/ghcdefs.h, include/h98defs.h+Extra-Source-Files: AUTHORS, CHANGELOG, MasterTable.txt, Test/Test.hs, include/ghcdefs.h, include/h98defs.h Extra-Tmp-Files: Author:             Adrian Hey @@ -37,6 +37,7 @@                      Data.Tree.AVL.Read,                      Data.Tree.AVL.Set,                      Data.Tree.AVL.Size,+                     Data.Tree.AVL.Height,                      Data.Tree.AVL.Split,                      Data.Tree.AVL.Types,                      Data.Tree.AVL.Write,@@ -47,12 +48,11 @@                      Data.Tree.AVL.Internals.HAVL,                      Data.Tree.AVL.Internals.HJoin,                      Data.Tree.AVL.Internals.HPush,-                     Data.Tree.AVL.Internals.HSet,-                     Data.Tree.AVL.Internals.HeightUtils+                     Data.Tree.AVL.Internals.HSet  Extensions:         CPP  Hs-Source-Dirs:     .  Build-Tools:- Ghc-Options:        -O -Wall -split-objs+ Ghc-Options:        -Wall  Ghc-Prof-Options:  Ghc-Shared-Options:  Hugs-Options:

CHANGELOG view

@@ -2,3 +2,13 @@ ---
 * Initial Hackage/Cabal release.
   Version set to 2.4 to distinguish from the 2.3 (non-cabal) release on my home page.
+
+3.0
+---
+* Included MasterTable.txt in the distro.
+* Eq and Ord Instances now based on strict structural equality (derived)
+* Exposed height related functions
+
+
+
+

Data/Tree/AVL.hs view

@@ -33,7 +33,6 @@ -- mySelector :: (key,val) -> COrdering val    Tree elements are (key,val) pairs -- @ ----- Please read the notes in the "Data.Tree.AVL.Types" module documentation too. ----------------------------------------------------------------------------- module Data.Tree.AVL (module Data.Tree.AVL.Types,@@ -47,6 +46,7 @@  map2AVL,avl2Map,   module Data.Tree.AVL.Size,+ module Data.Tree.AVL.Height,  module Data.Tree.AVL.Read,  module Data.Tree.AVL.Write,  module Data.Tree.AVL.Push,@@ -71,6 +71,7 @@  import Data.Tree.AVL.Types hiding (E,N,P,Z) import Data.Tree.AVL.Size+import Data.Tree.AVL.Height import Data.Tree.AVL.Read import Data.Tree.AVL.Write import Data.Tree.AVL.Push@@ -116,6 +117,7 @@ avl2Map :: AVL (key,val) -> BaseMap.Map key val avl2Map avl = BaseMap.fromDistinctAscList (asListL avl) +{- Not any more! -- | Eq is based on equality of the lists produced by 'asListL'. This definition has been placed here -- to avoid introducing cyclic dependency between Types.hs and List.hs instance Eq e => Eq (AVL e) where@@ -125,6 +127,8 @@ -- to avoid introducing cyclic dependency between Types.hs and List.hs instance Ord e => Ord (AVL e) where  x `compare` y =  asListL x `compare` asListL y+-}+  -- | Show is based on showing the list produced by 'asListL'. This definition has been placed here -- to avoid introducing cyclic dependency between Types.hs and List.hs

+ Data/Tree/AVL/Height.hs view

@@ -0,0 +1,99 @@+{-# OPTIONS_GHC -fglasgow-exts #-}+-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Tree.AVL.Height+-- Copyright   :  (c) Adrian Hey 2004,2005+-- License     :  BSD3+--+-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png+-- Stability   :  stable+-- Portability :  portable+--+-- AVL tree height related utilities.+--+-- The functions defined here are not exported by the main Data.Tree.AVL module+-- because they violate the policy for AVL tree equality used elsewhere in this library.+-- You need to import this module explicitly if you want to use any of these functions.+-----------------------------------------------------------------------------+module Data.Tree.AVL.Height+        (-- * AVL tree height utilities.+         height,addHeight,compareHeight, -- heightInt,+        ) where++import Data.Tree.AVL.Types(AVL(..))++#ifdef __GLASGOW_HASKELL__+import GHC.Base+#include "ghcdefs.h"+#else+#include "h98defs.h"+#endif++-- {-# INLINE heightInt #-} -- Don't want this+-- heightInt :: AVL e -> Int+-- heightInt t = ASINT(addHeight L(0) t)++-- | Determine the height of an AVL tree.+--+-- Complexity: O(log n)+{-# INLINE height #-}+height :: AVL e -> UINT+height t = addHeight L(0) t++-- | Adds the height of a tree to the first argument.+--+-- Complexity: O(log n)+addHeight :: UINT -> AVL e -> UINT+addHeight h  E        = h+addHeight h (N l _ _) = addHeight INCINT2(h) l+addHeight h (Z l _ _) = addHeight INCINT1(h) l+addHeight h (P _ _ r) = addHeight INCINT2(h) r++-- | A fast algorithm for comparing the heights of two trees. This algorithm avoids the need+-- to compute the heights of both trees and should offer better performance if the trees differ+-- significantly in height. But if you need the heights anyway it will be quicker to just evaluate+-- them both and compare the results.+--+-- Complexity: O(log n), where n is the size of the smaller of the two trees.+compareHeight :: AVL a -> AVL b -> Ordering+compareHeight = ch L(0) where                       -- d = hA-hB+ ch :: UINT -> AVL a -> AVL b -> Ordering+ ch d  E           E          = COMPAREUINT d L(0)+ ch d  E          (N l1 _ _ ) = chA DECINT2(d) l1+ ch d  E          (Z l1 _ _ ) = chA DECINT1(d) l1+ ch d  E          (P _  _ r1) = chA DECINT2(d) r1+ ch d (N l0 _ _ )  E          = chB INCINT2(d) l0+ ch d (N l0 _ _ ) (N l1 _ _ ) = ch          d  l0 l1+ ch d (N l0 _ _ ) (Z l1 _ _ ) = ch  INCINT1(d) l0 l1+ ch d (N l0 _ _ ) (P _  _ r1) = ch          d  l0 r1+ ch d (Z l0 _ _ )  E          = chB INCINT1(d) l0+ ch d (Z l0 _ _ ) (N l1 _ _ ) = ch  DECINT1(d) l0 l1+ ch d (Z l0 _ _ ) (Z l1 _ _ ) = ch          d  l0 l1+ ch d (Z l0 _ _ ) (P _  _ r1) = ch  DECINT1(d) l0 r1+ ch d (P _  _ r0)  E          = chB INCINT2(d) r0+ ch d (P _  _ r0) (N l1 _ _ ) = ch          d  r0 l1+ ch d (P _  _ r0) (Z l1 _ _ ) = ch  INCINT1(d) r0 l1+ ch d (P _  _ r0) (P _  _ r1) = ch          d  r0 r1+ -- Tree A ended first, continue with Tree B until hA-hB<0, or Tree B ends+ chA d tB = case COMPAREUINT d L(0) of+            LT ->             LT+            EQ -> case tB of+                  E        -> EQ+                  _        -> LT+            GT -> case tB of+                  E        -> GT+                  N l _ _  -> chA DECINT2(d) l+                  Z l _ _  -> chA DECINT1(d) l+                  P _ _ r  -> chA DECINT2(d) r+ -- Tree B ended first, continue with Tree A until hA-hB>0, or Tree A ends+ chB d tA = case COMPAREUINT d L(0) of+            GT ->             GT+            EQ -> case tA of+                  E        -> EQ+                  _        -> GT+            LT -> case tA of+                  E        -> LT+                  N l _ _  -> chB INCINT2(d) l+                  Z l _ _  -> chB INCINT1(d) l+                  P _ _ r  -> chB INCINT2(d) r+

Data/Tree/AVL/Internals/HAVL.hs view

@@ -19,7 +19,7 @@         ) where  import Data.Tree.AVL.Types(AVL(..))-import Data.Tree.AVL.Internals.HeightUtils(addHeight)+import Data.Tree.AVL.Height(addHeight) import Data.Tree.AVL.Internals.HJoin(spliceH,joinH) import Data.Tree.AVL.Internals.HPush(pushHL,pushHR)

− Data/Tree/AVL/Internals/HeightUtils.hs

@@ -1,98 +0,0 @@-{-# OPTIONS_GHC -fglasgow-exts #-}--------------------------------------------------------------------------------- |--- Module      :  Data.Tree.AVL.Internals.HeightUtils--- Copyright   :  (c) Adrian Hey 2004,2005--- License     :  BSD3------ Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png--- Stability   :  stable--- Portability :  portable------ AVL tree height related utilities.------ The functions defined here are not exported by the main Data.Tree.AVL module--- because they violate the policy for AVL tree equality used elsewhere in this library.--- You need to import this module explicitly if you want to use any of these functions.-------------------------------------------------------------------------------module Data.Tree.AVL.Internals.HeightUtils-        (height,addHeight,compareHeight, -- heightInt,-        ) where--import Data.Tree.AVL.Types(AVL(..))--#ifdef __GLASGOW_HASKELL__-import GHC.Base-#include "ghcdefs.h"-#else-#include "h98defs.h"-#endif---- {-# INLINE heightInt #-} -- Don't want this--- heightInt :: AVL e -> Int--- heightInt t = ASINT(addHeight L(0) t)---- | Determine the height of an AVL tree.------ Complexity: O(log n)-{-# INLINE height #-}-height :: AVL e -> UINT-height t = addHeight L(0) t---- | Adds the height of a tree to the first argument.------ Complexity: O(log n)-addHeight :: UINT -> AVL e -> UINT-addHeight h  E        = h-addHeight h (N l _ _) = addHeight INCINT2(h) l-addHeight h (Z l _ _) = addHeight INCINT1(h) l-addHeight h (P _ _ r) = addHeight INCINT2(h) r---- | A fast algorithm for comparing the heights of two trees. This algorithm avoids the need--- to compute the heights of both trees and should offer better performance if the trees differ--- significantly in height. But if you need the heights anyway it will be quicker to just evaluate--- them both and compare the results.------ Complexity: O(log n), where n is the size of the smaller of the two trees.-compareHeight :: AVL a -> AVL b -> Ordering-compareHeight = ch L(0) where                       -- d = hA-hB- ch :: UINT -> AVL a -> AVL b -> Ordering- ch d  E           E          = COMPAREUINT d L(0)- ch d  E          (N l1 _ _ ) = chA DECINT2(d) l1- ch d  E          (Z l1 _ _ ) = chA DECINT1(d) l1- ch d  E          (P _  _ r1) = chA DECINT2(d) r1- ch d (N l0 _ _ )  E          = chB INCINT2(d) l0- ch d (N l0 _ _ ) (N l1 _ _ ) = ch          d  l0 l1- ch d (N l0 _ _ ) (Z l1 _ _ ) = ch  INCINT1(d) l0 l1- ch d (N l0 _ _ ) (P _  _ r1) = ch          d  l0 r1- ch d (Z l0 _ _ )  E          = chB INCINT1(d) l0- ch d (Z l0 _ _ ) (N l1 _ _ ) = ch  DECINT1(d) l0 l1- ch d (Z l0 _ _ ) (Z l1 _ _ ) = ch          d  l0 l1- ch d (Z l0 _ _ ) (P _  _ r1) = ch  DECINT1(d) l0 r1- ch d (P _  _ r0)  E          = chB INCINT2(d) r0- ch d (P _  _ r0) (N l1 _ _ ) = ch          d  r0 l1- ch d (P _  _ r0) (Z l1 _ _ ) = ch  INCINT1(d) r0 l1- ch d (P _  _ r0) (P _  _ r1) = ch          d  r0 r1- -- Tree A ended first, continue with Tree B until hA-hB<0, or Tree B ends- chA d tB = case COMPAREUINT d L(0) of-            LT ->             LT-            EQ -> case tB of-                  E        -> EQ-                  _        -> LT-            GT -> case tB of-                  E        -> GT-                  N l _ _  -> chA DECINT2(d) l-                  Z l _ _  -> chA DECINT1(d) l-                  P _ _ r  -> chA DECINT2(d) r- -- Tree B ended first, continue with Tree A until hA-hB>0, or Tree A ends- chB d tA = case COMPAREUINT d L(0) of-            GT ->             GT-            EQ -> case tA of-                  E        -> EQ-                  _        -> GT-            LT -> case tA of-                  E        -> LT-                  N l _ _  -> chB INCINT2(d) l-                  Z l _ _  -> chB INCINT1(d) l-                  P _ _ r  -> chB INCINT2(d) r-

Data/Tree/AVL/Join.hs view

@@ -18,7 +18,7 @@ import Data.Tree.AVL.Size(addSize) import Data.Tree.AVL.List(asTreeLenL,toListL) import Data.Tree.AVL.Internals.DelUtils(popHLN,popHLZ,popHLP)-import Data.Tree.AVL.Internals.HeightUtils(height,addHeight)+import Data.Tree.AVL.Height(height,addHeight) import Data.Tree.AVL.Internals.HJoin(joinH',spliceH)  import Data.List(foldl')

Data/Tree/AVL/Set.hs view

@@ -46,7 +46,7 @@ import Prelude -- so haddock finds the symbols there  import Data.Tree.AVL.Types(AVL(..))-import Data.Tree.AVL.Internals.HeightUtils(addHeight)+import Data.Tree.AVL.Height(addHeight) import Data.Tree.AVL.Internals.HJoin(spliceH) import Data.Tree.AVL.Internals.HSet(unionH,unionMaybeH,                                     intersectionH,intersectionMaybeH,

Data/Tree/AVL/Size.hs view

@@ -17,7 +17,7 @@         ) where  import Data.Tree.AVL.Types(AVL(..))-import Data.Tree.AVL.Internals.HeightUtils(addHeight)+import Data.Tree.AVL.Height(addHeight)  #ifdef __GLASGOW_HASKELL__ import GHC.Base

Data/Tree/AVL/Test/AllTests.hs view

@@ -1042,7 +1042,7 @@                                                    mn = min (ls-1) (2*rs-1)                                                in isBalanced u  &&                                                   (asListL u == filter even [0..mn] ++ [mn+1..ls-1]) &&-                                                  isBalanced u_ && (u_ == l_)+                                                  isBalanced u_ && (asListL u_ == asListL l_)                              difference = genDifference compare  -- | Test the genDifferenceMaybe function@@ -1075,7 +1075,7 @@                                 mx = max (mn+1) 0                                 listfil = filter odd [0..mn]                                 listrem = [mx..ls-1]-                            in isBalanced u && isBalanced u_ && (u_ == l_) &&+                            in isBalanced u && isBalanced u_ && (asListL u_ == asListL l_) &&                                (asListL u == listfil ++ listrem)  -- | Test the genIsSubsetOf function

Data/Tree/AVL/Types.hs view

@@ -82,23 +82,19 @@ -- where appropriate), or using strict variants of the combinators defined in "Data.COrdering", -- or using 'seq' etc. in your own code (in any combining comparisons you define, for example). ----- A note about 'Eq' and 'Ord' class instances.+-- The Eq and Ord instances. ----- For 'AVL' trees the defined instances of 'Ord' and 'Eq' are based on the lists that are produced using--- the 'Data.Tree.AVL.List.asListL' function (it could just as well have been 'Data.Tree.AVL.List.asListR',--- the choice is arbitrary but I can only chose one). This means that two trees which contain the same elements--- in the same order are equal regardless of detailed tree structure. The same principle has been applied to--- the instances of 'Read' and 'Show'. Unfortunately, this has the undesirable and non-intuitive effect--- of making \"equal\" trees potentially distinguishable using some functions (such as height).--- All such functions have been placed in the Data.Tree.AVL.Internals modules, which are not--- included in the main "Data.Tree.AVL" wrapper. For all \"normal\" functions (f) exported by "Data.Tree.AVL"--- it is safe to assume that if a and b are 'AVL' trees then (a == b) implies (f a == f b), provided the same--- is true for the tree elements.+-- Begining with version 3.0 these are now derived, and hence are defined in terms of+-- strict structural equality, rather than observational equivalence. The reason for+-- this change is that the observational equivalence abstraction was technically breakable+-- with the exposed API. But since this change, some functions which were previously+-- considered unsafe have become safe to expose (those that measure tree height). -- data AVL e = E                      -- ^ Empty Tree            | N (AVL e) e (AVL e)    -- ^ BF=-1 (right height > left height)            | Z (AVL e) e (AVL e)    -- ^ BF= 0            | P (AVL e) e (AVL e)    -- ^ BF=+1 (left height > right height)+           deriving(Eq,Ord)  -- A name for the AVL type constructor, fully qualified avlTyConName :: String

Data/Tree/AVL/Zipper.hs view

@@ -111,8 +111,8 @@  import Data.Tree.AVL.Types(AVL(..)) import Data.Tree.AVL.Size(size,addSize)+import Data.Tree.AVL.Height(height,addHeight) import Data.Tree.AVL.Internals.DelUtils(deletePath,popRN,popRZ,popRP,popLN,popLZ,popLP)-import Data.Tree.AVL.Internals.HeightUtils(height,addHeight) import Data.Tree.AVL.Internals.HJoin(spliceH,joinH) import Data.Tree.AVL.Internals.HPush(pushHL,pushHR) import Data.Tree.AVL.Internals.BinPath(BinPath(..),genOpenPath,writePath,insertPath,sel,goL,goR)

Data/Tree/AVLX.hs view

@@ -14,7 +14,6 @@ module Data.Tree.AVLX (module Data.Tree.AVL -- The normal user AVL API -- + Normally Hidden Modules-,module Data.Tree.AVL.Internals.HeightUtils ,module Data.Tree.AVL.Internals.DelUtils ,module Data.Tree.AVL.Internals.HPush ,module Data.Tree.AVL.Internals.HSet@@ -30,7 +29,6 @@ import Data.Tree.AVL hiding (AVL) import Data.Tree.AVL.Types(AVL(..))        -- We want constructors exposed -import Data.Tree.AVL.Internals.HeightUtils import Data.Tree.AVL.Internals.DelUtils import Data.Tree.AVL.Internals.HPush import Data.Tree.AVL.Internals.HSet

+ MasterTable.txt view

@@ -0,0 +1,26 @@+Change in Height as a function of change in BF.+These figures are correct even if rebalancing has occurred.+Cases marked "--" are impossible.++Figures are given for insertion/deletion from left and+right sub-trees separately, and a combined figure for+where it's unknown which sub-tree was modified.++         InsL  InsR   Insert  |  DelL  DelR   Delete+ E->E      0     0       0    |    0     0       0+ E->N     --    --      --    |   --    --      --+ E->Z     +1    +1      +1    |   --    --      --+ E->P     --    --      --    |   --    --      --+ N->E     --    --      --    |   --    --      --+ N->N      0     0       0    |    0     0       0+ N->Z      0     0       0    |   -1    -1      -1+ N->P     --    --      --    |    0    --       0+ Z->E     --    --      --    |   -1    -1      -1+ Z->N     --    +1      +1    |    0    --       0+ Z->Z      0     0       0    |    0     0       0+ Z->P     +1    --      +1    |   --     0       0+ P->E     --    --      --    |   --    --      --+ P->N     --    --      --    |   --     0       0+ P->Z      0     0       0    |   -1    -1      -1+ P->P      0     0       0    |    0     0       0+