Re: On state and sorting.

[Chris <chris@starforge.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

#Saturday 12 January 2002 14:18# Message from Adam D. Moss:

> Well, I'm beginning to intuitively suspect that grouping
> of an arbitrarily-sized range /has/ to be gotten as
> a side-effect of sorting, or the algorithm won't know
> how to find the group to put the value in, if you see
> what I mean.  Unless someone has some great ideas I'll
> stick with actual sorting.  But it IS an interesting
> problem.  Or maybe it isn't!

Just thinking aloud.. this could be optimised a lot, and it is fairly 
memory-wasting and it may even be completely wrong but...

I assume that you have your "unsorted" poly structures in a linked list or 
some other kind of linear structure. If so, how does this sound:

- - in each poly structure, have a number that corresponds the the poly "type":
  all polys with the same state have the same id (probably can precalculate
  this while setting up the poly list or even as part of the object).

  So say you'd have

struct Poly
{
    gint type;
    .... etc...
};

- - Now do something like (off the top of my head, probably not correct C, I'm
  fairly sure I'm getting the level of pointers wrong.. )

  Poly **typeList[MAX_TYPE];
  gint typePos[MAX_TYPE];

  for(i = 0; i < MAX_TYPE; i++) {
      typeList[i] = (Poly **)g_malloc0(MAX_POLYS);
  }

- - When calculating the grouping, do something like

  Poly *current;

  for(i = 0; i < MAX_TYPE; i++) typePos[i] = 0;
  ....
  
  while(current = next_poly()) {
      typeList[current -> type][typePos[current -> type]++] = current;
  }

I think that doing that should group all the polys with a given type. Now 
when you're doing your redraw you can do

  for(i = 0; i < MAX_TYPE; i++) {
      if(typePos[i]) {
          do state change...
          for(y = 0; y < typePos[i]; y++) drawPoly(typeList[i][y]);
      }
  }

I've probably missed something obvious, but I think it'll work. If you don't 
know NUM_POLYS ahead of time then you may need linked lists of Poly pointers
or something like that.. Well, I think its a start anyway..

Chris
- -- 
 .------{ http://www.starforge.co.uk }-----. .---------------------------.  
=[     Explorer2260, Designer and Coder     \=\ P: TexMaker, Draktar      \ 
=[_____[ Quod nesciunt eos interficiet ]____]==[ Stack: EEOeOeOeTmTmDD---- ]
- --
The gods gave man fire and he invented fire engines.  They gave him
love and he invented marriage.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8QF+Otwxr0HXns0wRAlm1AJ9Dh8/hfkOeD43f74kWIWk21tm2QACfThma
3bOIrMniFJTzCMHzvJYehnI=
=Nr93
-----END PGP SIGNATURE-----