Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3691

Re: in-place reverse?

Show all headers | View raw

On Friday, October 22, 2021 at 7:13:13 PM UTC-5, luser droog wrote:
> On Friday, October 22, 2021 at 1:24:52 AM UTC-5, luser droog wrote: 
> > I was reading through some old code and found this function to 
> > reverse an array. 
> > 
> > reverse { 
> > dup xcheck exch 
> > [ exch dup length 1 sub -1 0 { 2 copy get 3 1 roll pop } for pop ] 
> > exch {cvx} if } 
> > 
> > And I wondered if it were possible to do it in-place, without creating 
> > a new array. I'm primarily using this for my args-begin function 
> > which does an {exch def} forall to assign names to local variables 
> > and parameters. The reverse is used to pre-process the array 
> > of names so it can be written left-to-right but operated top-down 
> > against the stack. 
> > 
> > I wrote it two ways but both are ugly. Is there a nicer way to do it? 
> > Does it require the invention of a fancy new control structure for 
> > a super "for" loop with 2 indices? I've almost done that with the 
> > second try here. It looks almost ready to factor out a new kind 
> > of loop. 
> > 
> > { 
> > %dup length 2 idiv -1 0 { % [A B C ..] idx(C) 
> > 0 1 2 index 2 idiv { % [A B C ..] idx(A) 
> > 1 index length 1 index sub % [A B C ..] idx(A) dst(A) 
> > 3 copy 3 copy pop get % [] i(C) d(C) [] i d A 
> > 4 copy pop % [] i d [] i d A [] i d 
> > 3 copy exch pop get % [] i d [] i d A [] i d . 
> > exch pop put % [] i d [] i d A ([. B C ..]) 
> > 3 -1 roll pop put % [] i d ([. B C .. A]) 
> > pop pop % [] 
> > } for 
> > } @pop 
> > { % [A B C ..] 
> > dup length 0 exch dup 2 div exch 1 sub % [ABC..] lo mid hi 
> > { % [ABC..] lo mid hi 
> > 3 copy gt exch % [] lo mid hi mid>hi lo 
> > 3 index gt or % [] lo mid hi mid>hi||lo>mid 
> > {exit} if 
> > 4 copy exch pop % [] l m h [] l h 
> > 3 copy 6 copy % [] l m h [] l h [] l h [] l h [] l h 
> > exch pop get % [] l m h [] l h [] l h [] l h [h] 
> > 4 1 roll pop get % [] l m h [] l h [] l h [h] [l] 
> > 5 1 roll exch pop put % [h] l m h [h] l h [l] 
> > 3 -1 roll pop put % [hl] l m h 
> > 3 2 roll 1 add 3 1 roll 1 sub 
> > } loop 
> > }
> Alright. Had to sleep on it. Two loops, sequentially. No new arrays 
> created. It uses a fancy loop I already wrote called "fortuple" 
> 
> array n proc fortuple -- 
> for each invocation of proc, the stack contains successive n-tuples 
> of elements from array using getinterval. 
> 
> So, by doing `1 {} fortuple` on the array, I fill the stack with little one- 
> element subarrays of the original array. Then a little stack juggling 
> to grab a copy of the original array. And then a regular old forall 
> loop to put each value in its target box, consuming one of the 
> subarrays on each iteration. 
> 
> { 
> [ 1 index 1 {} fortuple counttomark 1 add index { % [...] [ [0] [1] .. [n-1] 0 
> 0 exch put 
> } forall pop 
> } 
> 
> Aside: I considered "dup [ exch" instead of "[ 1 index" but that executes 
> two operators instead of just one. Probably an insignificant useless 
> microoptimization but that's why I did that. 
> 
> Aside, aside: I haven't actually run and tested this. I'm 90% sure that 
> "counttomark 1 add index" correctly grabs the thing just below the mark, 
> but I reckon there's a 10% chance I'm wrong about that.

I rewrote it again to avoid using my fancy loop, since the fancy loop is itself
defined using /reverse.

     {
	dup                         % [] []
        0 1  2 index length 1 sub { % [] ... [] 0
	    2 copy 1 getinterval    % [] ... [] 0 [0]
	    3 1 roll pop            % [] [0] ... []
        } for                       % [] [0] [1] .. [n-1] []
	{ 0 exch put } forall
    }

So now I don't need the `mark ... counttomark` stuff because I can simply
carry along the original array in the loop and keep it close.
Finally, it becomes easier to see that the first loop isn't necessary.
All we truly need to do is calculate the target index and carry it along
on the stack.

    {
	dup length 1 sub 1 index { % [] n-1  0
	    3 copy put pop
            1 sub
        } forall pop
    }

And this one, I think I'm happy with.

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-21 23:24 -0700
  Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:13 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:42 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-23 16:54 -0700
  Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-22 17:16 -0700
  Re: in-place reverse? James <news@oxdrove.co.uk> - 2021-10-24 11:04 +0100
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-10-24 17:59 -0700
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2021-11-08 10:08 -0800
  Re: in-place reverse? David Newall <davidn@davidnewall.com> - 2022-01-21 21:10 +1100
    Re: in-place reverse? luser droog <luser.droog@gmail.com> - 2022-01-21 21:22 -0800
      Re: in-place reverse? jdaw1 <jdawiseman@gmail.com> - 2022-08-10 13:11 -0700

csiph-web