Ordenar e insertar ordenado en TObjectList

[sebamawa]

Hola a todos.

Me estoy iniciando en Delphi y me gustaría saber como ordenar una lista TObjectList según un campo clave de los objetos insertados en la lista. Leí por algún lado que se dispone del método Sort, pero no tengo claro su utilización.

Además me gustaría saber si hay algún método para insertar un objeto de forma ordenada en una lista TObjectList, también con respecto a un campo (propiedad) clave del objeto a insertar.

Muchas gracias.

Saludos.

[roman]

El método Sort de TObjectList recibe como parámetro una función (que tú defines) que le indica cómo debe comparar tus objetos. La función debe devolver un número positivo si el primer objeto es "mayor" que el primero, 0 si son iguales y un número negativo si el primer objeto es "menor" que el segundo.

Te pongo un ejemplo:

Código Delphi [-]
// Clase de los objetos que conforman la lista
TCliente = class
  Nombre: String;
  Telefono: String;
end;

// Función para comparar dos objetos (en este caso, compara los clientes por su nombre)
function ComparaClientes(Item1, Item2: Pointer): Integer;
begin
  if TCliente(Item1).Nombre > TCliente(Item2).Nombre then
    Result := 1 // > 0
  else if TCliente(Item1).Nombre = TCliente(Item2).Nombre then
    Result := 0
  else
    Result := -1 // < 0;
end;

// Ejemplo de uso:
Lista.Sort(ComparaClientes);

Me parece que TObjectList no tiene forma de insertar ordenadamente.

// Saludos

[sebamawa]

Gracias roman por tu respuesta.
Al hacer el llamado con (según tu ejemplo):

Lista.Sort(ComparaClientes);

el IDE me dice que no le estoy pasando la cantidad correcta de parámetros a la función ComparaClientes.
¿Cuál es el problema?. Yo vengo de Pascal estándar, y estoy aprendiendo no hace tanto programación a objetos. Para mi habría que pasarle a la función dos punteros como parámetros, pero en este caso tal vez no sea así.

Otra pregunta, ¿ se dispone en Delphi de alguna lista "dinámica" predefinida para insertar objetos de forma ordenada ?.

Muchas gracias.

Saludos.

[roman]

Empezado por sebamawa

Para mi habría que pasarle a la función dos punteros como parámetros

No, porque entonces estarías pasando al método Sort el resultado de comparar dos objetos en específico. El parámetro de Sort es una función (no el resultado de una función). Pasar funciones o procedimientos como parámetros se usa desde el pascal estándar.

Necesitaría ver el código exacto que estás usando para ver porqué el compilador te marca ese error.

// Saludos

[sebamawa]

Entiendo roman, es clara tu explicación y mala mi interpretación previa.
Haber si con parte del código se logra detectar el error.

En una unidad (UPersona) declaro un objeto persona de la siguiente forma:

TPersona = class
   private
     documento: Integer;
     nombre: String;
   public
     (* Constructores *)
     Constructor Create(doc: Integer; nom: String);
     
      (* Selectoras *)
      Function GetDocumento: Integer;
      Function GetNombre: String;

      (* Modificadoras *)
      Procedure SetDocumento(doc: Integer);
      Procedure SetNombre(nom: String);
   end;

implementation
  ...
end.

Luego en un TForm aparecen estos procedimientos asociados a dos botones.
Primero declaro las variables

var
  Form1: TForm1;
  p: TPersona;
  listaPersonas: TObjectList;

Primer botón:

procedure TForm1.Button1Click(Sender: TObject);
begin
  p:=TPersona.Create(StrToInt(Edit1.Text),Edit2.Text);
  listaPersonas:=TObjectList.Create(True);

  // Agregamos el objeto persona a la lista
  listaPersonas.Add(p);

  Edit1.Text:='';
  Edit2.Text:='';
end;

La idea es que cada vez que se presiona el botón Button1 se agrege un objeto persona a la lista TObectList, cuyos campos (documento y nombre) se leen desde dos TEdits.

Ahora el segundo botón:

procedure TForm1.Button2Click(Sender: TObject);
 function OrdenarPorDocumento(a: Pointer;b: Pointer): Integer;
 begin
   if TPersona(a).GetDocumento > TPersona(b).GetDocumento then
     result:=-1
   else
     if TPersona(a).GetDocumento < TPersona(b).GetDocumento then
       result:=1
     else
       result:=0;
 end;

begin
  ListaPersonas.Sort(OrdenarPorDocumento);
end;

La idea es que cuando se apreta el segundo botón (Button2) se ordene la lista.

Desde ya muy agredecido por cualquier comentario.

Saludos.

[roman]

Así, a bote pronto, lo único que se me ocurre es que declares la función OrdenarPorDocumento fuera del evento Button2Click. Es posible que los procedimientos locales no se puedan pasar como parámetros. Nunca lo he intentado.

// Saludos

[sebamawa]

Gracias roman por tu orientación.
Veré si puedo solucionar el problema.
Saludos.

[roman]

Desempolvando los algoritmos de inserción binaria, podemos hacer una rutina que inserte los objetos en orden:

Código Delphi [-]
procedure InsertaOrdenado(Lista: TObjectList; Comparar: TListSortCompare; Item: Pointer);
var
  Primero, Ultimo, Central, Resultado: Integer;

begin
  Primero := 0;
  Ultimo := Lista.Count - 1;

  while Primero <= Ultimo do
  begin
    Central := (Primero + Ultimo) div 2;
    Resultado := Comparar(Item, Lista[Central]);

    if Resultado < 0
      then Ultimo := Central - 1
      else Primero := Central + 1;
  end;

  Lista.Insert(Primero, Item);
end;

Por ejemplo, puedes definir la función comparadora:

Código Delphi [-]
function CompararDocumentos(P1, P2: Pointer): Integer;
begin
  if TPersona(P1).Documento > TPersona(P2).Documento then
    Result := 1
  else if TPersona(P1).Documento = TPersona(P2).Documento then
    Result := 0
  else
    Result := -1;
end;

al momento de insertar:

Código Delphi [-]
P := TPersona.Create(StrToIntDef(txtDocumento.Text, 0),  txtNombre.Text);
InsertaOrdenado(ListaPersonas, CompararDocumentos, P);

// Saludos

[sebamawa]

Excelente roman. Personalmente yo usaba búsqueda e inserción binaria en Pascal estándar con arreglos (listas estáticas), pero no con listas dinámicas (listas enlazadas). El hecho de tener en TObjectList un campo que indiza cada nodo facilita mucho las cosas.

Por otro lado, el inconveniente que tenia con la función comparadora lo solucioné con el llamado

Lista.Sort(@ComparaClientes);

en lugar de

Lista.Sort(ComparaClientes);

tomando el llamado de tu ejemplo del principio.

Saludos.

[Neftali [Germán.Estévez]]

Otra opción que a veces utilizo yo y que resulta más rápida de implementar, aunque es posible que no tan eficiente, cuando se requiere algo similar a lo que planteas (objetos + campo de ordenación) es utilizar un TStringList.

Utilizo el campo como String (para definir la ordenación) y los objetos se almacenan en la propiedad Objects.
Sólo se puede utilizar si la conversión del campo se puede hacer a un string y la ordenación de este tipo es la correcta para el resultado esperado.

Código Delphi [-]
var
  TS:TStringList;
  key:String;
begin

  TS := TStringList.Create;
  TS.Sorted := True;
  TS.Duplicates := dupError;   // esto dependiendo de lo que se necesite

  ...

  // Añadir
  key :=   <--  Campo clave para ordenación
  i := TS.AddObject(key, obj)
  ...

[ecfisa]

Hola.

Hice unas pruebas y si la función pasada como argumento está fuera del procedimiento/función (que es como la he usado anteriormente) se la puede llamar:

Código Delphi [-]
  Lista.Sort(Compare);

Ahora, enviando como argumento la dirección de la función como menciona sebamawa, y figura en el ejemplo de la ayuda de Delphi:

Código Delphi [-]
  Lista.Sort(@Compare);

la llamada trabaja tanto si la función es anidada como si es externa.


También es muy interesante tu enfoque Neftali

Saludos.

[roman]

Empezado por sebamawa

Por otro lado, el inconveniente que tenia con la función comparadora lo solucioné con el llamado

Lista.Sort(@ComparaClientes);

en lugar de

Lista.Sort(ComparaClientes);

tomando el llamado de tu ejemplo del principio.

¿Qué versión de Delphi usas?

// Saludos

[roman]

Empezado por Neftali

Otra opción que a veces utilizo yo y que resulta más rápida de implementar, aunque es posible que no tan eficiente, cuando se requiere algo similar a lo que planteas (objetos + campo de ordenación) es utilizar un TStringList.

En realidad, yo casi siempre termino usando un TStringList precisamente por lo que dices. Es de lo más común que un objeto tenga un identificador natural de tipo cadena, además de que el TStringList también permite la ordenación personalizada con el método CustomSort. Desafortunadamente, la inserción ordenada sólo es posible para la ordenación regular. Claro que, ya bien visto, la rutina que puse para el TObjectList puede adaptarse para el TStringList.

En otro tenor de cosas, no sé si el compañero sebamawa ha considerado el uso de una bse de datos. A veces se enreda uno implementando estructuras de datos para guardar información que perfectamente podría manejarse con una base.

// Saludos

[sebamawa]

Estimados amigos, agradezco de sobremanera la ayuda y las sugerencias proporcionadas por parte de ustedes.

Respecto a

En otro tenor de cosas, no sé si el compañero sebamawa ha considerado el uso de una bse de datos. A veces se enreda uno implementando estructuras de datos para guardar información que perfectamente podría manejarse con una base.

les comento que como menciono al principio de este hilo me estoy iniciando en Delphi, mi base previa es Pascal estándar. Por eso foros como este son de mucha ayuda para mi. Y respecto a la utilización de base de datos, todavía no llego a tanto jeje. Tal vez sea algo relativamente sencillo de implementar, pero por ahora estoy tratando de migrar algunas estructuras de Pascal estándar a Delphi, aunque tal vez no sea la mejor idea a veces según me da a entender roman.

Ya que estoy en este tema, me podrán recomendar un buen manual de Delphi donde pueda estudiar. Si estuviera su versión digital para descarga sería fantástico.

Gracias y saludos.

[roman]

Empezado por sebamawa

Ya que estoy en este tema, me podrán recomendar un buen manual de Delphi donde pueda estudiar. Si estuviera su versión digital para descarga sería fantástico.

¡Claro! En nuestro Repositorio de archivos hay mucho material. Busca en Delphi/Manuales. Entre otros, encontrarás La cara oculta de delphi 4, que en gran medidad, sigue vigente aún para las versiones actules de delphi.

// Saludos

[roman]

¡Ah! También está el mismo libro pero para la versión 6. Tiene su título en inglés (The Dark Side of Delphi) pero el libro está en español.

// Saludos

[[Delphius]]

Roman tengo una duda sobre tu propuesta, que dicho sea de paso, es altamente ingeniosa como acostumbras.
La inserción binaria, al menos lo que yo tengo entendido y recuerdo de cátedra (de hace ya años...) sólo tiene sentido si la lista ya está está ordenada. Es decir que para poder insertar de forma ordenada, se debe ejecutar el método Sort() previamente.
No si es que he analizado mal el algoritmo que propones, pero creo ese InsertaOrdenado() falla cuando se intenta insertar el 1er item y el vez de colocarlo en el índice 0, va a parar en el índice 1.

Como nota: No sería de extrañar que en las nuevas versiones de Delphi el algoritmo de ordenamiento "base" o "kernel" de TList deje de ser QuickSort. Existe un algoritmo, relativamente reciente, que es más rápido y además permite hacer inserciones de forma directa. Se llama TimSort. Java, Python ya lo tienen implementado como el algoritmo de ordenamiento por defecto en sus últimas versiones.

Por otro lado nada impide hacer un TOrderObjectList que implemente justamente tanto ordenamiento como inserción ordenada.

Saludos,

[roman]

Empezado por Delphius

La inserción binaria, al menos lo que yo tengo entendido y recuerdo de cátedra (de hace ya años...) sólo tiene sentido si la lista ya está está ordenada.

Así es. Por eso hay que usarla desde el principio . Cuando la lista está vacía, no hay nada qué ordenar y por tanto llamar a Sort está de más. Pero si se intenta usar sobre una lista desordenada, ciertamente hay que llamar a Sort primero.

Empezado por Delphius

No si es que he analizado mal el algoritmo que propones, pero creo ese InsertaOrdenado() falla cuando se intenta insertar el 1er item y el vez de colocarlo en el índice 0, va a parar en el índice 1.

Si la lista está vacía, Primero = 0 y Ultimo = -1 así que el ciclo while no se ejecuta y se hace la inserción en el índice 0.

Empezado por Delphius

Existe un algoritmo, relativamente reciente, que es más rápido y además permite hacer inserciones de forma directa.

No entiendo que significa que un algoritmo de ordenamiento permita hacer inserciones directas.

Empezado por Delphius

Por otro lado nada impide hacer un TOrderObjectList que implemente justamente tanto ordenamiento como inserción ordenada.

Así es, sería lo óptimo, pero hice el procedimiento para facilitar las cosas y no tener que implementar una clase derivada.

// Saludos

[[Delphius]]

Empezado por roman

Así es. Por eso hay que usarla desde el principio . Cuando la lista está vacía, no hay nada qué ordenar y por tanto llamar a Sort está de más. Pero si se intenta usar sobre una lista desordenada, ciertamente hay que llamar a Sort primero.

Es que a como entendí de las palabras de sebamawa es que quería evitarse el ordenamiento y hacer inserciones ordenadas directamente sobre la lista, con los datos previamente almacenados.

Empezado por roman

Si la lista está vacía, Primero = 0 y Ultimo = -1 así que el ciclo while no se ejecuta y se hace la inserción en el índice 0.

Marche unos lentes para Delphius... no vi ese .Count -1

Empezado por roman

No entiendo que significa que un algoritmo de ordenamiento permita hacer inserciones directas.

Si... admito que lo dije muy flojo y que no se entendería bien... Como TimSort() es un algoritmo híbrido, posee una combinación del Merge() con Insertion() por lo que posee la particularidad de ofrecer internamente una insercción ordenada.
Con TimSort, de lo poco que le entendí de su funcionamiento, es capaz de determinar cuando aplicar un Merge() y cuando aprovechar una insercción. Si se tuviera TimSort por defecto, al hacer un Add, Insert, Move, etc de forma "automática" se hacen las cosas con un único algoritmo y es posible que en ningún momento se ejecute la parte del Merge().

Empezado por roman

Así es, sería lo óptimo, pero hice el procedimiento para facilitar las cosas y no tener que implementar una clase derivada.
// Saludos

No sería extraño que en las nuevas versiones ya existiera una clase como esta. Lo más "cercano" a ésta que veo en D6 es TOrderedList, la clase base para TStack y TQueue, que ofrece el método virtual y abstracto PushItem() que está pensado para determinar como ha de tener lugar la inserción del ítem. Tanto TStack como TQueue sobrescriben a éste para conseguir la inserción por pila y cola respectivamente.

Saludos,

[roman]

Empezado por Delphius

Es que a como entendí de las palabras de sebamawa es que quería evitarse el ordenamiento y hacer inserciones ordenadas directamente sobre la lista

Eso mismo entendí yo.

Empezado por Delphius

con los datos previamente almacenados.

Bueno, es que esto sería imposible

// Saludos