Opened 15 years ago

Closed 15 years ago

Last modified 10 months ago

#8378 closed patch

common/list enhancement

Reported by: SF/h00ligan Owned by: fingolfin
Priority: normal Component: --Other--
Keywords: Cc:
Game:

Description

This patch extends Common:List template in
following ways:
- adds methods for items insertion/rearrangment by
specified comparision function (reorder_up,
reorder_down,insert)
- adds optimized memory allocation List assignment
- adds locate,remove & some other usefull methods
- adds explicit inline

Ticket imported from: #1083548. Ticket imported from: patches/483.

Attachments (2)

List.patch.bz2 (1.9 KB) - added by SF/h00ligan 15 years ago.
List.patch
List.2.patch.bz2 (363 bytes) - added by SF/h00ligan 15 years ago.

Download all attachments as: .zip

Change History (14)

Changed 15 years ago by SF/h00ligan

Attachment: List.patch.bz2 added

List.patch

comment:1 Changed 15 years ago by SF/h00ligan

- some methods renamed to right form
(e.g push_back -> pushBack)

comment:2 Changed 15 years ago by sev-

Fingolfin, may you, please, take a look at it? SAGA patch
depends on this.

comment:3 Changed 15 years ago by sev-

Owner: set to fingolfin

comment:4 Changed 15 years ago by fingolfin

The method names are actually the way they are on purpose, even
though that's a violation of our code formatting conventions --
one of the few exceptions.
Reasoning: the names/methods match the Std C++ lib. I still want
to go over to using the Std C++ lib one day, and this way it's
relatively easy.

comment:5 Changed 15 years ago by fingolfin

* Adding an explicit "inline" keyword is not necessary. Method
definitions done inside the class declaration are normally
automatically inlined by any conformant ANSI C++ compiler. The
Std C++ lib doesn't use the inline keyword for std::list either.

* It's not 100% clear to me what the reorderUp/reorderDown
methods are supposed to do. They need to be documented /
explained. Or just move them to a subclass of List<T> which you
then make local to saga.

* You added a List<T>::locate method. It returns "0" as an
iterator. This is not correct -- 0 is not a valid iterator
object!

* Besides, I'd prefer to emulate the Std C++ lib, and not add
this locate method -- rather add a global find() template
function which can be used with anything that implements
iterators, not just lists

comment:6 Changed 15 years ago by SF/h00ligan

- if method "locate" returns "0" as iterator - that means
"0" as _node for returning iterator - so you may compare
such iterator with NULL to understand that locate - finds
nothing ( return 0; construct iterator(0) )
- scummvm own "list" will be more flexible & extendable -
it's not relying on custom Std C++ realization. So
"emulation" apply restriction - it's all one that Std C++
List should be extended
- I'm agree that reorderUp, reorderDown and comparitive
Insert may be moved to List successor in saga section
(and "locate" if You insist)
- You quite right with inline usage - (it should be
removed ) It helps me to see how inline works in debug
version
- reorderUp/reorderDown - sort existing list element
according to comparison function

comment:7 Changed 15 years ago by fingolfin

- I still don't like returning a "0" iterator, at least not in
the fashion you did. To make use of it, client code would have to
implicitly rely on how precisely we implement the list iterators,
which would be bad. In fact I just checked in code which fixes
the "leak" in the implementation -- client code can't anymore
compare a List::iterator to NULL.

- And I simply don't see the value of the locate() method, it
does so little, and nothing which is not easily achieved by 1-2
lines of client code. ut if we add it, we should at least do it
right.

- Note that ScummVMs own "List" may eventually be replaced by the
std::list

- reorderUp / reorderDown don't seem to actually sort the list --
rather I think they are meant to be on a previously sorted list,
after one item was changed (thus changing where it should be
within the list).
I.e. they allow to keep a sorted list sorted in a relatively
efficient way.
This is indeed a very special behaviour and should be moved to a
subclass.

- Likewise, all the "CompareFunction" related stuff should be in
a subclass.

- I checked in your optimized assigment operator, thanks!

Summing it up, your best route to go on from here is to move all
the remaining stuff (assuming I am not overlooking anything here)
into a "SortedList" subclasss in saga. Which would mean nothing
is touched in common, so you could stick it back into your SAGA
patch

Changed 15 years ago by SF/h00ligan

Attachment: List.2.patch.bz2 added

comment:8 Changed 15 years ago by SF/h00ligan

here is implementation of remove method (it works like
stl list), it's not need for saga - only remove unfinished
code

all other stuff was moved to saga/list.h
thanks for recomendations

comment:9 Changed 15 years ago by SF/h00ligan

clarification:
List.2.patch contains implementation of "remove"
method.
it is not required by saga engine, just makes List class
more complete and conformant to STL

comment:10 Changed 15 years ago by fingolfin

Thanks, I added to CVS.

comment:11 Changed 15 years ago by fingolfin

Status: newclosed

comment:12 Changed 10 months ago by digitall

Component: --Other--
Note: See TracTickets for help on using tickets.