Ordenar e insertar ordenado en TObjectList

[ecfisa]

Hola sebamawa.

Si la lista ya está ordenada podes usar una búsqueda binaria. Tomemos como ejemplo una reducción de la clase que puso de ejemplo roman:

Código Delphi [-]
implementation

type
  TCliente = class
    Nombre: String;
  end;

var
  LstObj : TObjectList;
  Cliente : TCliente;

procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
begin
  LstObj := TObjectList.Create;
  // Demás operaciones de carga
  ...
end;

function TForm1.BinarySearch(OLst: TObjectList; Valor: string): Integer;
var
  Pri, Ult, Med : Integer;
  Esta : boolean;
begin
   Pri  := 0;
   Ult  := OLst.Count-1;
   Esta := False;
   while (Pri <= Ult) and not Esta do
   begin
      Med := (Pri + Ult) div 2;
      if TCliente(OLst.Items[Med]).Nombre = Valor then Esta := true;
      if TCliente(OLst.Items[Med]).Nombre < Valor then Pri  := Med + 1;
      if TCliente(OLst.Items[Med]).Nombre > Valor then Ult  := Med - 1;
   end;
   if Esta then
     Result := Med
   else
     Result := -1;
end;

// Ejemplo de llamada:
procedure TForm1.Button1Click(Sender: TObject);
var
  P : Integer;
begin
  P := BinarySearch(LstObj, 'Juan Perez');
  if P <> -1 then
    ShowMessage('Nombre:   ' + TCliente(LstObj.Items[P]).Nombre+#10#13+
                'Posición: ' + IntToStr(P));
  //  ...
end;

...

procedure TForm1.FormDestroy(Sender: TObject);
begin
  if Assigned(LstObj) then
    LstObj.Free;
end;

Saludos.

[sebamawa]

Muchas gracias ecfisa, algo como lo que planteaste tenía en mente y resulta de mucha ayuda.
Como he comentado, vengo de Pascal Estándar, o sea de arreglos estáticos, crear listas enlazadas desde cero, etc, y estoy tratando de migrar algunas estructuras de datos a Delphi como listas enlazadas y arboles, pero claro, Delphi ya tiene incorporadas muchas de estas estructuras o algunas semejantes que facilitan el tener que empezar a programar desde cero, supongo que esto se da en todo lenguaje moderno.
Me podrías decir donde encontrar descripciones de los métodos y propiedades de las clases de Delphi, es que a veces cuando tengo que realizar una tarea caigo en la duda si, es que tengo una rutina predefinida o no, y en este último caso debo implementar la misma por mi cuenta.
Otra duda, el método FindInstanceOf de la clase TObjectList, qué tarea realiza?
Y lo último, teniendo la posibilidad de realizar búsquedas binarias en una lista (TObjectList por ejemplo), sabiendo que este tipo de búsqueda es muy eficiente, tiene sentido el utilizar árboles para el guardado de datos?
Tal vez más de uno me dirá que use base de datos, pero antes quiero manejar con solvencia las estructuras de datos que menciono antes.

Muchas gracias.
Saludos para todos.

[ecfisa]

Hola sebamawa.

Me podrías decir donde encontrar descripciones de los métodos y propiedades de las clases de Delphi

En la propia ayuda de Delphi encontras descrita las clases, sus propiedades y métodos. Sobre TList,TQueue,TStrings, etc revisa este enlace.

Otra duda, el método FindInstanceOf de la clase TObjectList, qué tarea realiza?

Busca la primera ocurrencia de una clase específica dentro de la lista. Si la clase buscada no existe devuelve el valor -1.

Saludos.

[[Delphius]]

Empezado por sebamawa

tiene sentido el utilizar árboles para el guardado de datos?
Tal vez más de uno me dirá que use base de datos, pero antes quiero manejar con solvencia las estructuras de datos que menciono antes.

Muchas gracias.
Saludos para todos.

¿Árboles? Pasar de un TAD lista a un TAD árbol no es poca cosa. En primer lugar habría que determinar si efectivamente tiene sentido alguno (sobre todo en lo lógico) el almacenar datos en forma de árbol.
Desconozco si Delphi provee de fábrica un TObjectTreeList (por darle un nombre) pero me parece que el que consideres pensar en árboles, y que luego sobre este posiblemente se deba implementar y adaptar los algoritmos de insersión, ordenamiento y búsquda es ya algo exagerado y una pérdida de tiempo.

Lo mejor es que le dejes eso al motor de base de datos... que lo hace estupéndamente. Si ya de hecho los motores por dentro poseen árboles para estructurar los datos. Concretamente los B+ tree.

Luego es que existen tus clase del dominio, y crearás tantos objetos como registros tengas. Al extraer los registros pasas los datos a cada instancia en sus correspondientes campos. Y el paso inverso, desde tu clase del dominio lees sus campos y mandas a ejecutar una instrucción INSERT o UPDATE sea el caso.
A estas alturas y si quieres seguir avanzando de escala ya te vas pensando en un framework de persistencia.

Me parece que te estás complicando las cosas innecesariamente.

Saludos,

[roman]

Empezado por Delphius

¿Árboles? Pasar de un TAD lista a un TAD árbol no es poca cosa. En primer lugar habría que determinar si efectivamente tiene sentido alguno (sobre todo en lo lógico) el almacenar datos en forma de árbol.
Desconozco si Delphi provee de fábrica un TObjectTreeList (por darle un nombre) pero me parece que el que consideres pensar en árboles, y que luego sobre este posiblemente se deba implementar y adaptar los algoritmos de insersión, ordenamiento y búsquda es ya algo exagerado y una pérdida de tiempo.

Aquí ya me perdí. Mis cursos básicos de computación me dicen que los árboles binarios son excelentes candidatos para guardar información ordenada. Es más, yo diría que una lista ordenada con inserción y búsqueda como la que hemos expuesto es esencialmente lo mismo que un árbol binario.

// Saludos

[[Delphius]]

Empezado por roman

Aquí ya me perdí. Mis cursos básicos de computación me dicen que los árboles binarios son excelentes candidatos para guardar información ordenada. Es más, yo diría que una lista ordenada con inserción y búsqueda como la que hemos expuesto es esencialmente lo mismo que un árbol binario.

// Saludos

Pues si roman, pero hay árboles mejores que los binarios Y B+ está pensado justamente para equilibrar: inserción, lectura, navegación, ordenamiento, etc. Y ni que decir... más convenientes si luego se tiene pensado hacer lectura/escritura física en un archivo. Justamente estos son los que utilizan los motores de base de datos.

Sinceramente, pretender llegar a pensar en árboles es demasiado. Es mejor quedarse con la Lista, a como se ha propuesto... y que como bien dices, para este caso es equivalente al árbol binario. Si ya la lista con lo propuesto sirve ¿para que más?
Si en verdad se quiere llevar al TAD árbol, y que se comporte como tal, pues habrá que buscar una clase, si es que ya está. O bien volver a retormar las clases de estructuras de datos.

A mi parecer, creo que se está perdiendo la sintonía del problema y buscar resolverlo de una forma más complicada de la que se podría llevar. Y lo digo precisamente porque algo me dice que sebamawa ha perdido de vista algo, porque algo le hace pensar ahora que árboles le resultará más adecuado.

¿No será mejor invitar a que se descubra y explique ese algo? Yo creo que de algo nos estamos perdiendo.

Saludos,

[roman]

Empezado por Delphius

Pues si roman, pero hay árboles mejores que los binarios Y B+ está pensado justamente para equilibrar: inserción, lectura, navegación, ordenamiento, etc. Y ni que decir... más convenientes si luego se tiene pensado hacer lectura/escritura física en un archivo. Justamente estos son los que utilizan los motores de base de datos.

Sinceramente, pretender llegar a pensar en árboles es demasiado. Es mejor quedarse con la Lista, a como se ha propuesto... y que como bien dices, para este caso es equivalente al árbol binario. Si ya la lista con lo propuesto sirve ¿para que más?
Si en verdad se quiere llevar al TAD árbol, y que se comporte como tal, pues habrá que buscar una clase, si es que ya está. O bien volver a retormar las clases de estructuras de datos.

A mi parecer, creo que se está perdiendo la sintonía del problema y buscar resolverlo de una forma más complicada de la que se podría llevar. Y lo digo precisamente porque algo me dice que sebamawa ha perdido de vista algo, porque algo le hace pensar ahora que árboles le resultará más adecuado.

¿No será mejor invitar a que se descubra y explique ese algo? Yo creo que de algo nos estamos perdiendo.

Saludos,

Sinceramente creo que rizas demasiado el rizo. No he visto que el forista haya pretendido hacer una motor de base de datos ni nada por el estilo. Más bien veo alguien que trata de familiarizarse con delphi implmentando algunas de las estructuras clásicas de datos. Pero una frase como

En primer lugar habría que determinar si efectivamente tiene sentido alguno (sobre todo en lo lógico) el almacenar datos en forma de árbol.

lejos de enriquecer la plática, oscurece el asunto. Si no almacenas datos en un árbol, ¿qué coños almacenas ahí? Desde luego que hay mejores o peores tipos de datos para cada tarea y que muy posiblemente cuando se ponga a la tarea real que le ocupe, pensará en una base de datos, pero considero que hay que tomar los hilos y las respuestas en su justa medida y no hacer una cátedra teórica en cada caso.

// Saludos

[roman]

Empezado por ecfisa

Si la lista ya está ordenada podes usar una búsqueda binaria.

De hecho, modificando un poco, la misma función que se usa para la inserción se puede usar para la búsqueda. Es decir, se hace una sóla función de búsqueda que devuelva el índice donde debe ir el objeto. Ese índice se usa, bien sea para insertar un nuevo objeto, o bien para devolver la posición del objeto buscado.

// Saludos