Commits

Yujie Wu  committed 699a7b0

Implemented basic set operations.

  • Participants
  • Parent commits 09bf1f7
  • Branches feature/set

Comments (0)

Files changed (1)

+/******************************************************************************************************************************
+ * Implementation of the set data structure
+ *
+ * Copyright (c) 2012  Yujie Wu
+ *
+ * Distributed under the MIT License
+ * (See accompanying file LICENSE or copy at http://www.opensource.org/licenses/mit-license.php)
+ */
+
+
+
+/******************************************************************************************************************************
+ * A quick sort that removes duplicated members.
+ * - Gives a list in the ascending order.
+ */
+
+% Trivial pivot selection algorithm: Select the first element as the pivot.
+pivot( [Elem | Tail], Elem, Tail ).
+
+partition( [],            _,     [],            []               ).
+partition( [Elem | Tail], Pivot, [Elem | Less],         Greater  ) :- Elem <  Pivot, partition( Tail, Pivot, Less, Greater ).
+partition( [Elem | Tail], Pivot,         Less,  [Elem | Greater] ) :- Elem >  Pivot, partition( Tail, Pivot, Less, Greater ).
+partition( [Elem | Tail], Pivot,         Less,          Greater  ) :- Elem == Pivot, partition( Tail, Pivot, Less, Greater ).
+
+quick_sort( [],   []     ).
+quick_sort( List, Sorted ) :-
+   pivot( List, Pivot, Reduced ),
+   partition( Reduced, Pivot, Less, Greater ),
+   quick_sort( Less,    L ),
+   quick_sort( Greater, G ),
+   append( L, [Pivot | G], Sorted ).
+
+
+
+% A function to create initial set.
+% We use ordered list to represent set.
+list_to_set( List, Set ) :- quick_sort( List, Set ).
+
+
+
+% Adds an item into the given set.
+add( Item, [],            [Item]               ).
+add( Item, [Elem | Tail], [      Elem | Added] ) :- Item  > Elem, add( Item, Tail, Added ).
+add( Item, [Elem | Tail], [Item, Elem | Tail ] ) :- Item  < Elem.
+add( Item, [Elem | Tail], [      Elem | Tail ] ) :- Item == Elem.
+
+
+
+% Deletes an item from the given set.
+del( _,    [],            []             ).
+del( Item, [Elem | Tail], [Elem | Added] ) :- Item  > Elem, del( Item, Tail, Added ).
+del( Item, [Elem | Tail], [Elem | Tail ] ) :- Item  < Elem.
+del( Item, [Elem | Tail],         Tail   ) :- Item == Elem.
+
+
+
+
+% True if the set contains the item.
+has( _,    []            ) :- fail.
+has( Item, [Elem | Tail] ) :- Item  > Elem, has( Item, Tail ).
+has( Item, [Elem | _   ] ) :- Item  < Elem, fail.
+has( Item, [Elem | _   ] ) :- Item == Elem.
+
+
+
+% Union
+union( [], S,  S ).
+union( S,  [], S ) :- S \= [].
+
+union( [Elem | Tail], [Elem | T], [Elem | U] ) :-            union(         Tail,       T,  U ).
+union( [Elem | Tail], [E    | T], [E    | U] ) :- Elem > E,  union( [Elem | Tail],      T,  U ).
+union( [Elem | Tail], [E    | T], [Elem | U] ) :- Elem < E,  union(         Tail,  [E | T], U ).
+
+
+
+% Intersection
+intersection( [], _,  [] ).
+intersection( S,  [], [] ) :- S \= [].
+
+intersection( [Elem | Tail], [Elem | T], [Elem | U] ) :-           intersection(         Tail,       T,  U ).
+intersection( [Elem | Tail], [E    | T],         U  ) :- Elem > E, intersection( [Elem | Tail],      T,  U ).
+intersection( [Elem | Tail], [E    | T],         U  ) :- Elem < E, intersection(         Tail,  [E | T], U ).
+
+
+
+% Difference
+difference( [], S,  S ).
+difference( S,  [], S ) :- S \= [].
+
+difference( [Elem | Tail], [Elem | T],         U  ) :-           difference(         Tail,       T,  U ).
+difference( [Elem | Tail], [E    | T], [E    | U] ) :- Elem > E, difference( [Elem | Tail],      T,  U ).
+difference( [Elem | Tail], [E    | T], [Elem | U] ) :- Elem < E, difference(         Tail,  [E | T], U ).
+
+
+
+% Select
+% Learning: if-then-else construct: if A then B else C is written as (A -> B ; C).
+%           To Prolog this means: try A. If you can prove it, go on to prove B and ignore C. If A fails, however, go on to
+%           prove C ignoring B.
+
+select( [],            X, Cond, []       ).
+select( [Elem | Tail], X, Cond, Selected ) :-
+   copy_term( X-Cond, XC-CondC ),
+   H = XC,
+   (call( CondC ) -> Sel = [Elem | R]; Sel = R),
+   select( Tail, X, Cond, R ).
+
+
+