Advertisement
Guest User

Untitled

a guest
Apr 4th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Prolog 2.82 KB | None | 0 0
  1. % ---------- QUICK SORT
  2. splitItems([], _, [], [], []).
  3. splitItems([First|List], Pivot, Lower, [First|Equal], Higher) :-
  4.     ma_order((=), First, Pivot), splitItems(List, Pivot, Lower, Equal, Higher).
  5. splitItems([First|Tail], Pivot, [First|Lower], Equal, Higher) :-
  6.     ma_order((<), First, Pivot), splitItems(Tail, Pivot, Lower, Equal, Higher).
  7. splitItems([First|Tail], Pivot, Lower, Equal, [First|Higher]) :-
  8.     ma_order((>), First, Pivot), splitItems(Tail, Pivot, Lower, Equal, Higher).
  9.  
  10. fixedTail(0, Res - X, Res - X).
  11. fixedTail(Length, [_|Org] - X, Result - X) :-
  12.     Length > 0,
  13.     NewLength is Length - 1,
  14.     fixedTail(NewLength, Org - X, Result - X).
  15.  
  16. equalD([], X-X).
  17. equalD([F|D], [F|T] - X) :- equalD(D, T-X).
  18.  
  19. qs([], X-X).
  20. qs([First|List], Sorted-X) :-
  21.     splitItems([First|List], First, Lower, Equal, Higher),
  22.     length(Lower, L1), length(Equal, L2),
  23.     fixedTail(L1, Sorted-X, Sorted2-X), fixedTail(L2, Sorted2-X, Sorted3-X),
  24.     qs(Lower, Sorted-Sorted2),
  25.     equalD(Equal, Sorted2-Sorted3),
  26.     qs(Higher, Sorted3-X).
  27.  
  28. % /--------- QUICK SORT
  29.  
  30.  
  31. ma_type(ma([type(X)|_], _), X).
  32. ma_type(ma([Cur | Next], _), X) :-
  33.     Cur \= type(X),
  34.     ma_type(ma(Next, _), X).
  35.  
  36. ma_size(ma([size(X)|_], _), X).
  37. ma_size(ma([Cur | Next], _), X) :-
  38.     Cur \= type(X),
  39.     ma_size(ma(Next, _), X).
  40.  
  41. ma_order(Pred, Doll1, Doll2) :-
  42.     ma_type(Doll1, Type1),
  43.     ma_type(Doll2, Type2),
  44.     compare(Pred1, Type1, Type2),
  45.     (   Pred1\==(=)
  46.     ->  Pred=Pred1
  47.     ;   ma_size(Doll1, Size1),
  48.         ma_size(Doll2, Size2),
  49.         compare(Pred, Size2, Size1)
  50.     ).
  51.  
  52.  
  53. unnest_dolls([], []).
  54. unnest_dolls([empty|Tail], R) :- unnest_dolls(Tail, R).
  55. unnest_dolls([ma(L, Next)|Tail], [ma(L, empty)|R]) :- unnest_dolls([Next|Tail], R).
  56.  
  57. uniq([], []).
  58. uniq([Elem], [Elem]).
  59. uniq([In|[NextIn|Input]], [Out|Output]) :-
  60.     ma_type(In, Type1), ma_type(NextIn, Type2), ma_size(In, Size1), ma_size(NextIn, Size2),
  61.     (   (Size1 = Size2, Type1 = Type2) ->
  62.         uniq([NextIn|Input], [Out|Output]) ;
  63.         Out = In,
  64.         uniq([NextIn|Input], Output)
  65.     ).
  66.  
  67. ordered_dolls_list(Input, Result) :-
  68.     unnest_dolls(Input, Unnested),
  69.     qs(Unnested, Result-[]).
  70. %    uniq(SubRes, Result).
  71.  
  72. % takes unnested ordered dolls, output = result
  73. nest_dolls(Input, Output) :-
  74.     nest_dolls(unknown, Input, [_|Output]).
  75.  
  76. nest_dolls(_, [], [Next]) :- Next = empty.
  77. nest_dolls(Prev, [ma(Inf, _)|Input], [Cur|Output]) :-
  78.     ma_type(ma(Inf, _), Prev),
  79.     Cur = ma(Inf, Next),
  80.     nest_dolls(Prev, Input, [Next|Output]).
  81.  
  82. nest_dolls(Prev, [ma(Inf, _)|Input], [Cur|Output]) :-
  83.     ma_type(ma(Inf, _), NotPrev),
  84.     NotPrev \= Prev,
  85.     Cur = empty,
  86.     nest_dolls(NotPrev, [ma(Inf, _)|Input], Output).
  87.  
  88. ma_clean(Mess, Order) :-
  89.     ordered_dolls_list(Mess, Ordered_list),
  90.     nest_dolls(Ordered_list, Order).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement