0 | module Data.SortedSet
  1 |
  2 | import Data.Maybe
  3 | import Data.SortedMap
  4 | import Data.SortedMap.Dependent
  5 |
  6 | export
  7 | data SortedSet k = SetWrapper (Data.SortedMap.SortedMap k ())
  8 |
  9 | export
 10 | empty : Ord k => SortedSet k
 11 | empty = SetWrapper Data.SortedMap.empty
 12 |
 13 | export
 14 | insert : k -> SortedSet k -> SortedSet k
 15 | insert k (SetWrapper m) = SetWrapper (Data.SortedMap.insert k () m)
 16 |
 17 | public export %inline
 18 | insert' : SortedSet k -> k -> SortedSet k
 19 | insert' = flip insert
 20 |
 21 | export
 22 | delete : k -> SortedSet k -> SortedSet k
 23 | delete k (SetWrapper m) = SetWrapper (Data.SortedMap.delete k m)
 24 |
 25 | public export %inline
 26 | delete' : SortedSet k -> k -> SortedSet k
 27 | delete' = flip delete
 28 |
 29 | export
 30 | contains : k -> SortedSet k -> Bool
 31 | contains k (SetWrapper m) = isJust (Data.SortedMap.lookup k m)
 32 |
 33 | public export %inline
 34 | contains' : SortedSet k -> k -> Bool
 35 | contains' = flip contains
 36 |
 37 | export
 38 | fromList : Ord k => List k -> SortedSet k
 39 | fromList l = SetWrapper (Data.SortedMap.fromList (map (\i => (i, ())) l))
 40 |
 41 | export
 42 | Foldable SortedSet where
 43 |   foldr f z = foldr f z . toList
 44 |   foldl f z = foldl f z . toList
 45 |
 46 |   null (SetWrapper m) = null m
 47 |
 48 |   foldMap f = foldMap f . toList
 49 |
 50 |   toList (SetWrapper m) = keys m
 51 |
 52 | -- Remove as soon as 0.8.0 (or greater) is released
 53 | ||| Use `Prelude.toList` instead
 54 | %deprecate
 55 | public export %inline
 56 | toList : SortedSet k -> List k
 57 | toList = Prelude.toList
 58 |
 59 | ||| Set union. Inserts all elements of x into y
 60 | export
 61 | union : (x, y : SortedSet k) -> SortedSet k
 62 | union x y = foldr insert x y
 63 |
 64 | ||| Set difference. Delete all elements in y from x
 65 | export
 66 | difference : (x, y : SortedSet k) -> SortedSet k
 67 | difference x y = foldr delete x y
 68 |
 69 | ||| Set symmetric difference. Uses the union of the differences.
 70 | export
 71 | symDifference : (x, y : SortedSet k) -> SortedSet k
 72 | symDifference x y = union (difference x y) (difference y x)
 73 |
 74 | ||| Set intersection. Implemented as the difference of the union and the symetric difference.
 75 | export
 76 | intersection : (x, y : SortedSet k) -> SortedSet k
 77 | intersection x y = difference x (difference x y)
 78 |
 79 | ||| Returns the leftmost (least) value
 80 | export
 81 | leftMost : SortedSet k -> Maybe k
 82 | leftMost (SetWrapper m) = fst <$> leftMost m
 83 |
 84 | ||| Returns the rightmost (greatest) value
 85 | export
 86 | rightMost : SortedSet k -> Maybe k
 87 | rightMost (SetWrapper m) = fst <$> rightMost m
 88 |
 89 | export
 90 | Ord k => Semigroup (SortedSet k) where
 91 |   (<+>) = union
 92 |
 93 | export
 94 | Ord k => Monoid (SortedSet k) where
 95 |   neutral = empty
 96 |
 97 | export
 98 | Eq k => Eq (SortedSet k) where
 99 |   SetWrapper x == SetWrapper y = x == y
100 |
101 | export
102 | Show k => Show (SortedSet k) where
103 |    show m = "fromList " ++ show (Prelude.toList m)
104 |
105 | export
106 | keySet : SortedMap k v -> SortedSet k
107 | keySet = SetWrapper . map (const ())
108 |
109 | namespace Dependent
110 |
111 |   export
112 |   keySet : SortedDMap k v -> SortedSet k
113 |   keySet = SetWrapper . cast . map (const ())
114 |
115 | ||| Removes all given keys from the given map
116 | export
117 | differenceMap : SortedMap k v -> SortedSet k -> SortedMap k v
118 | differenceMap x y = foldr delete x y
119 |
120 | ||| Leaves only given keys in the given map
121 | export
122 | intersectionMap : SortedMap k v -> SortedSet k -> SortedMap k v
123 | intersectionMap x y = differenceMap x (keySet $ differenceMap x y)
124 |
125 | export
126 | singleton : Ord k => k -> SortedSet k
127 | singleton = insert' empty
128 |
129 | export %inline
130 | toSortedMap : SortedSet k -> SortedMap k ()
131 | toSortedMap (SetWrapper m) = m
132 |
133 | export %inline
134 | fromSortedMap : SortedMap k () -> SortedSet k
135 | fromSortedMap = SetWrapper
136 |
137 | ||| Pops the leftmost element from the set
138 | export
139 | pop : SortedSet k -> Maybe (k, SortedSet k)
140 | pop (SetWrapper m) = bimap fst fromSortedMap <$> pop m
141 |