From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,dff686f95f235879 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-01-18 04:31:16 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!cyclone.bc.net!skynet.be!skynet.be!fu-berlin.de!uni-berlin.de!dialin-145-254-036-225.arcor-ip.NET!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Composing sequences (interesting to solve) Date: Sat, 18 Jan 2003 13:31:55 +0100 Organization: At home Message-ID: References: <3e2620ad$0$33930$bed64819@news.gradwell.net> <3e2880fa$1$33930$bed64819@news.gradwell.net> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: dialin-145-254-036-225.arcor-ip.net (145.254.36.225) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7Bit X-Trace: fu-berlin.de 1042893074 24707700 145.254.36.225 (16 [77047]) User-Agent: KNode/0.7.1 Xref: archiver1.google.com comp.lang.ada:33173 Date: 2003-01-18T13:31:55+01:00 List-Id: Victor Porton wrote: > In article , > "Dmitry A. Kazakov" writes: > > Reversely, I want to not copy these as copying would probably slow > things down. I just shown that if I would not use access types as > constructor functions arguments I would need to copy the objects. > >> And so you probably need no heap allocation, which is used when automatic >> deallocation is undesirable or when the number and types of the objects >> are unknown. There is an obvious rule about pointers: avoid copying >> objects if you use pointers to them. > > I want heap allocation by another reasons: > > 1. Class wide objects cannot be parts of a record. So I need to > allocate these by "new". > > 2. I see in Ada no natural and yet efficient syntax for creating trees > (see below) by constructors with syntax like "A(A(X,Y), B(Z))" without > using heap allocation. So it is a tree, a binary one. > Exactly, I construct a tree (or, more generally, it will be probably a > directed graph). Objects of type Base_Element'Class are tree nodes. > Pair is a node with two subnodes. > > In fact these trees are representation of programs in some programming > language. > > Do I undersood you correctly that you suggest to use access > discriminants instead of access fields. I see no advantages of > discriminants over fields in my case. Generally there is only one advantage: you do not have to care if pointer is null. >> I suppose Base_Element is limited. (?) > > No, but probably in a future version it will be limited. > >> I almost sure that you rather have a case of some well-known problem, >> which definitely can be solved in Ada. > > Let's forgot about of my original problem and discuss constructing and > deallocating trees (or directed graphs) in Ada. Ideologically the best > solution would be to use controlled types with reference counting or > like for full automation, but I want also efficiency. A simple solution could look like this: with Ada.Finalization; package Trees is type Node is abstract new Ada.Finalization.Limited_Controlled with null record; type Node_Ptr is access all Node'Class; procedure Delete (N : in out Node_Ptr); type Branch (Left, Right : access Node'Class) is new Node with null record; type Branch_Ptr is access all Branch'Class; function "&" (L, R : access Node'Class) return Node_Ptr; procedure Finalize (N : in out Branch); type Leaf (No : Integer) is new Node with null record; type Leaf_Ptr is access all Leaf'Class; function New_Leaf (No : Integer) return Node_Ptr; end Trees; --------------- with Ada.Unchecked_Deallocation; package body Trees is procedure Free is new Ada.Unchecked_Deallocation (Node'Class, Node_Ptr); procedure Delete (N : in out Node_Ptr) is begin Free (N); end Delete; function "&" (L, R : access Node'Class) return Node_Ptr is begin return new Branch (L, R); end "&"; procedure Finalize (N : in out Branch) is Ptr : Node_Ptr; begin Ptr := N.Left.all'Unchecked_Access; Free (Ptr); Ptr := N.Right.all'Unchecked_Access; Free (Ptr); end Finalize; function New_Leaf (No : Integer) return Node_Ptr is begin return new Leaf (No); end New_Leaf; end Trees; --------------- with Text_IO; use Text_IO; with Trees; use Trees; procedure Test_Trees is procedure Put (N : Node'Class; I : String := "") is begin if N in Leaf'Class then Put_Line (I & Integer'Image (Leaf'Class (N).No)); else Put (Branch'Class (N).Left.all, I & " "); Put (Branch'Class (N).Right.all, I & " "); end if; end Put; A_Tree : Node_Ptr; begin A_Tree := (New_Leaf (1) & New_Leaf (2)) & New_Leaf (3); Put (A_Tree.all); Delete (A_Tree); end Test_Trees; ------------------- As for general problem "efficient graphs", it an endless story. Everything depends on which graph operations have to be most efficient. For instance, in the project I am working on, the nodes of a fuzzy graph are created and deleted more seldom than accessed. Then they are referenced by other objects (classifiers, features etc). Then they has to be archived in a data base. Then ... -- Regards, Dmitry A. Kazakov www.dmitry-kazakov.de