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 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Multiple keys for a map Date: Wed, 18 Sep 2013 09:22:33 +0200 Organization: cbb software GmbH Message-ID: <10z06jaj3ok8l$.tmrmqhwjgloi.dlg@40tude.net> References: <4f66d847-d030-4aa9-8bdf-9bcc5f3a0852@googlegroups.com> <3al7xx87ldc3.67wd6mjqten8.dlg@40tude.net> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: IenaDxMXK2hi7fvYcb+MlQ.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: 40tude_Dialog/2.0.15.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: news.eternal-september.org comp.lang.ada:17199 Date: 2013-09-18T09:22:33+02:00 List-Id: On Tue, 17 Sep 2013 10:49:15 -0700 (PDT), Peter Brooks wrote: > On Tuesday, 17 September 2013 18:52:37 UTC+2, Dmitry A. Kazakov wrote: >> >> Maps can be used to index such a table, or red-black trees, or whatever. >> >> You could also take an existing light-weight RDBMS, e.g. SQLite3 or >> Berkeley DB. There exist many Ada bindings to SQLite3. >> > Thank you, yes, I'm hoping to avoid that overhead. If you want a better than O(n) search you need a map (or an equivalent of) for each search criterion. With wildcarded triplets it gives 7 maps/indices: x,y,z -> Element *,y,z -> Bucket of (x,y,z) keys or other references to elements in above x,*,z x,y,* x,*,* *,y,* *,*,z It is quite straightforward to implement. An alternative could be a kd-tree. (I am not sure how good a kd-tree is for search in a plane, which would be an equivalent of wildcard search). -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de