{-
	Copyright (C) 2012 Dr. Alistair Ward

	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 3 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, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Miscellaneous polymorphic operations on 'Data.Foldable.Foldable' types.
-}

module ToolShed.Data.Foldable(
-- * Functions
	gather,
	gatherBy,
-- ** Predicates
	hasDuplicates
) where

import			Control.Arrow((&&&))
import qualified	Data.Foldable
import qualified	Data.Map
import qualified	Data.Set

{- |
	* Group equal (though not necessarily adjacent; cf. 'Data.List.groupBy') elements, according to the specified comparator.

	* The groups are returned in ascending order, whilst their elements remain in their original order.

	* See 'GHC.Exts.groupWith', 'Data.List.Extra.groupSortOn'.
-}
gatherBy
	:: (Data.Foldable.Foldable foldable, Ord b)
	=> (a -> b)	-- ^ Function to apply before testing for equality.
	-> foldable a	-- ^ The input data.
	-> [[a]]
gatherBy f	= Data.Map.elems . Data.Foldable.foldr (uncurry (Data.Map.insertWith (++)) . (f &&& return {-to List-monad-})) Data.Map.empty

-- | A specific instance of 'gatherBy'.
gather :: (Data.Foldable.Foldable foldable, Ord a) => foldable a -> [[a]]
gather	= gatherBy id

{- |
	* Whether the specified collection contains any equal items.

	* See 'Data.List.Extra.anySame'.
-}
hasDuplicates :: (Data.Foldable.Foldable foldable, Ord a) => foldable a -> Bool
hasDuplicates	= fst . Data.Foldable.foldr (
	\x (result, s)	-> if result || Data.Set.member x s
		then (True, s)
		else (False, Data.Set.insert x s)
 ) (False, Data.Set.empty)