{-| Module abstracting the peer map implementation. This is abstracted separately since the speed of peermap updates can be a significant part of the total runtime, and as such changing the implementation should be easy in case it's needed. -} {- Copyright (C) 2009, 2011 Google Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. -} module Ganeti.HTools.PeerMap ( PeerMap , Key , Elem , empty , accumArray , Ganeti.HTools.PeerMap.find , add , remove , maxElem ) where import Data.Maybe (fromMaybe) import Data.List import Data.Ord (comparing) import Ganeti.HTools.Types -- * Type definitions -- | Our key type. type Key = Ndx -- | Our element type. type Elem = Int -- | The definition of a peer map. type PeerMap = [(Key, Elem)] -- * Initialization functions -- | Create a new empty map. empty :: PeerMap empty = [] -- | Our reverse-compare function. pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering pmCompare a b = comparing snd b a -- | Add or update (via a custom function) an element. addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap addWith fn k v lst = case lookup k lst of Nothing -> insertBy pmCompare (k, v) lst Just o -> insertBy pmCompare (k, fn o v) (remove k lst) -- | Create a PeerMap from an association list, with possible duplicates. accumArray :: (Elem -> Elem -> Elem) -- ^ function used to merge the elements -> [(Key, Elem)] -- ^ source data -> PeerMap -- ^ results accumArray _ [] = empty accumArray fn ((k, v):xs) = addWith fn k v $ accumArray fn xs -- * Basic operations -- | Returns either the value for a key or zero if not found. find :: Key -> PeerMap -> Elem find k = fromMaybe 0 . lookup k -- | Add an element to a peermap, overwriting the previous value. add :: Key -> Elem -> PeerMap -> PeerMap add = addWith (flip const) -- | Remove an element from a peermap. remove :: Key -> PeerMap -> PeerMap remove _ [] = [] remove k ((x@(x', _)):xs) = if k == x' then xs else x:remove k xs -- | Find the maximum element. -- -- Since this is a sorted list, we just get the value at the head of -- the list, or zero for a null list maxElem :: PeerMap -> Elem maxElem (x:_) = snd x maxElem _ = 0