%!PS

% begin included library code
% see https://codeberg.org/Firedrake/postscript-libraries/
/quicksort.cmp {
    2 copy
    lt {
        pop pop -1
    } {
        gt {
            1
        } {
            0
        } ifelse
    } ifelse
} bind def

/quicksort.main { % lo hi -> (null)
    3 dict begin
    /hi exch def
    /lo exch def
    /xit false def
    lo 0 lt {
        /xit true def
    } if
    hi 0 lt {
        /xit true def
    } if
    lo hi ge {
        /xit true def
    } if
    xit not {
        /p quicksort.partition def
        lo p quicksort.main
        p 1 add hi quicksort.main
    } if
    end
} bind def

/quicksort {
    { quicksort.cmp } quicksort.with_comparator
} bind def

/test.start {
    print (:) print
    /test.pass 0 def
    /test.count 0 def
} bind def

/quicksort.partition {
    3 dict begin
    /pivot arr hi lo add 2 idiv get def
    /i lo 1 sub def
    /j hi 1 add def
    {
        {
            /i i 1 add def
            arr i get pivot cmp 0 ge {
                exit
            } if
        } loop
        {
            /j j 1 sub def
            arr j get pivot cmp 0 le {
                exit
            } if
        } loop
        i j ge {
            j
            exit
        } if
        i j quicksort.swap
    } loop
    end
} bind def

/quicksort.swap {
    2 dict begin
    /bi exch def
    /ai exch def
    arr ai get
    arr bi get
    arr exch ai exch put
    arr exch bi exch put
    end
} bind def

/quicksort.with_comparator { % [ a c b ] { comparator } -> [ a b c ]
    2 dict begin
    /cmp exch def
    /arr exch def
    arr length 0 gt {
        0 arr length 1 sub quicksort.main
    } if
    arr
    end
} bind def

/test {
    /test.count test.count 1 add def
    {
        /test.pass test.pass 1 add def
    } {
        ( ) print
        test.count (....) cvs print
        (-fail) print
    } ifelse
} bind def

/test.end {
    ( ) print
    test.count 0 gt {
        (Passed ) print
        test.pass (...) cvs print
        (/) print
        test.count (...) cvs print
        ( \() print
        test.pass 100 mul test.count idiv (...) cvs print
        (%\)) print
        (\r\n) print
    } if
} bind def

/reverse {
    1 dict begin
    dup length /l exch def
    [ exch
      aload pop
      2 1 l {
          -1 roll
      } for
    ]
    end
} bind def


% end included library code

/reserve.new {
    0 dict begin
    /self 3 dict def
    quicksort reverse self exch /values exch put
    self /counts [ self (values) get length { 0 } repeat ] put
    /vm self (values) get length dict def
    0 1 self (values) get length 1 sub {
        dup
        self (values) get exch get
        exch
        vm 3 1 roll
        put
    } for
    self (vm) vm put
    self
    end
} bind def

/reserve.makechange {
    0 dict begin
    /tendered exch def
    /price exch def
    /self exch def
    /val 0 def
    true
    1 {
        tendered {
            /note exch def
            self (vm) get note known not {
                pop false
                exit
            } if
            self (counts) get self (vm) get note get get 1 add
            self (counts) get self (vm) get note get 3 -1 roll put
            /val val note add def
        } forall
        dup not {
            exit
        } if
        val price lt {
            pop false
            exit
        } if
        /val val price sub def
        0 1 self (values) get length 1 sub {
            /bid exch def
            {
                val self (values) get bid get lt {
                    exit
                } if
                self (counts) get bid get 0 le {
                    exit
                } if
                /val val self (values) get bid get sub def
                self (counts) get dup bid get 1 sub bid exch put
            } loop
        } for
    } repeat
    val 0 eq and
    end
} bind def

/exactchange {
    0 dict begin
    /reserve [5 10 20] reserve.new def
    true exch
    {
        /tendered exch def
        reserve 5 [ tendered ] reserve.makechange not {
            pop false
            exit
        } if
    } forall
    end
} bind def

[ 5 10 20 ] reserve.new

(exactchange) test.start
[5 5 5 10 20] exactchange test
[5 5 10 10 20] exactchange not test
[5 5 5 20] exactchange test
test.end