{-# LANGUAGE Safe #-}

{-
  This module is part of Chatty.
  Copyleft (c) 2014 Marvin Cohrs

  All wrongs reversed. Sharing is an act of love, not crime.
  Please share Chatty with everyone you like.

  Chatty is free software: you can redistribute it and/or modify
  it under the terms of the GNU Affero General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  Chatty 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 Affero General Public License for more details.

  You should have received a copy of the GNU Affero General Public License
  along with Chatty. If not, see <http://www.gnu.org/licenses/>.
-}

-- | Provides a ternary search trie
module Data.Chatty.TST where

import Control.Arrow
import Data.Maybe
import Data.Chatty.None

-- | A ternary search trie
data TST a = EmptyTST | TST Char (Maybe a) (TST a) (TST a) (TST a)

-- | Insert something into the TST
tstInsert :: String -> a -> TST a -> TST a
tstInsert (c:[]) a EmptyTST = TST c (Just a) EmptyTST EmptyTST EmptyTST
tstInsert (c:cs) a EmptyTST = TST c Nothing (tstInsert cs a EmptyTST) EmptyTST EmptyTST
tstInsert cs a (TST c1 a1 f l r)
  | head cs < c1 = TST c1 a1 f (tstInsert cs a l) r
  | head cs > c1 = TST c1 a1 f l (tstInsert cs a r)
  | cs == [c1] = TST c1 (Just a) f l r
  | otherwise = TST c1 a1 (tstInsert (tail cs) a f) l r

-- | Lookup some string in the TST
tstLookup :: String -> TST a -> Maybe a
tstLookup _ EmptyTST = Nothing
tstLookup cs (TST c1 a1 f l r)
  | head cs < c1 = tstLookup cs l
  | head cs > c1 = tstLookup cs r
  | cs == [c1] = a1
  | otherwise = tstLookup (tail cs) f

-- | Check if the TST contains the given key
tstContains :: String -> TST a -> Bool
tstContains cs = isJust . tstLookup cs

-- | Traverse TST
tstTraverse :: TST a -> [(String, a)]
tstTraverse EmptyTST = []
tstTraverse (TST c1 Nothing l f r) = tstTraverse l ++ map (first (c1:)) (tstTraverse f) ++ tstTraverse r
tstTraverse (TST c1 (Just a) l f r) = tstTraverse l ++ [([c1],a)] ++ map (first (c1:)) (tstTraverse f) ++ tstTraverse r

instance None (TST a) where
  none = EmptyTST