Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- % ---------- QUICK SORT
- splitItems([], _, [], [], []).
- splitItems([First|List], Pivot, Lower, [First|Equal], Higher) :-
- ma_order((=), First, Pivot), splitItems(List, Pivot, Lower, Equal, Higher).
- splitItems([First|Tail], Pivot, [First|Lower], Equal, Higher) :-
- ma_order((<), First, Pivot), splitItems(Tail, Pivot, Lower, Equal, Higher).
- splitItems([First|Tail], Pivot, Lower, Equal, [First|Higher]) :-
- ma_order((>), First, Pivot), splitItems(Tail, Pivot, Lower, Equal, Higher).
- fixedTail(0, Res - X, Res - X).
- fixedTail(Length, [_|Org] - X, Result - X) :-
- Length > 0,
- NewLength is Length - 1,
- fixedTail(NewLength, Org - X, Result - X).
- equalD([], X-X).
- equalD([F|D], [F|T] - X) :- equalD(D, T-X).
- qs([], X-X).
- qs([First|List], Sorted-X) :-
- splitItems([First|List], First, Lower, Equal, Higher),
- length(Lower, L1), length(Equal, L2),
- fixedTail(L1, Sorted-X, Sorted2-X), fixedTail(L2, Sorted2-X, Sorted3-X),
- qs(Lower, Sorted-Sorted2),
- equalD(Equal, Sorted2-Sorted3),
- qs(Higher, Sorted3-X).
- % /--------- QUICK SORT
- ma_type(ma([type(X)|_], _), X).
- ma_type(ma([Cur | Next], _), X) :-
- Cur \= type(X),
- ma_type(ma(Next, _), X).
- ma_size(ma([size(X)|_], _), X).
- ma_size(ma([Cur | Next], _), X) :-
- Cur \= type(X),
- ma_size(ma(Next, _), X).
- ma_order(Pred, Doll1, Doll2) :-
- ma_type(Doll1, Type1),
- ma_type(Doll2, Type2),
- compare(Pred1, Type1, Type2),
- ( Pred1\==(=)
- -> Pred=Pred1
- ; ma_size(Doll1, Size1),
- ma_size(Doll2, Size2),
- compare(Pred, Size2, Size1)
- ).
- unnest_dolls([], []).
- unnest_dolls([empty|Tail], R) :- unnest_dolls(Tail, R).
- unnest_dolls([ma(L, Next)|Tail], [ma(L, empty)|R]) :- unnest_dolls([Next|Tail], R).
- uniq([], []).
- uniq([Elem], [Elem]).
- uniq([In|[NextIn|Input]], [Out|Output]) :-
- ma_type(In, Type1), ma_type(NextIn, Type2), ma_size(In, Size1), ma_size(NextIn, Size2),
- ( (Size1 = Size2, Type1 = Type2) ->
- uniq([NextIn|Input], [Out|Output]) ;
- Out = In,
- uniq([NextIn|Input], Output)
- ).
- ordered_dolls_list(Input, Result) :-
- unnest_dolls(Input, Unnested),
- qs(Unnested, Result-[]).
- % uniq(SubRes, Result).
- % takes unnested ordered dolls, output = result
- nest_dolls(Input, Output) :-
- nest_dolls(unknown, Input, [_|Output]).
- nest_dolls(_, [], [Next]) :- Next = empty.
- nest_dolls(Prev, [ma(Inf, _)|Input], [Cur|Output]) :-
- ma_type(ma(Inf, _), Prev),
- Cur = ma(Inf, Next),
- nest_dolls(Prev, Input, [Next|Output]).
- nest_dolls(Prev, [ma(Inf, _)|Input], [Cur|Output]) :-
- ma_type(ma(Inf, _), NotPrev),
- NotPrev \= Prev,
- Cur = empty,
- nest_dolls(NotPrev, [ma(Inf, _)|Input], Output).
- ma_clean(Mess, Order) :-
- ordered_dolls_list(Mess, Ordered_list),
- nest_dolls(Ordered_list, Order).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement