defining "in" What is the proper way in D2?

[Jonathan M Davis]

On Sunday, September 11, 2011 15:28:38 Charles Hixson wrote:
> On 09/11/2011 02:12 PM, Jonathan M Davis wrote:
> > On Sunday, September 11, 2011 14:00:55 Charles Hixson wrote:
> >> On 09/11/2011 01:25 PM, Vladimir Panteleev wrote:
> >>> On Sun, 11 Sep 2011 23:02:37 +0300, Charles Hixson
> >>> 
> >>> <charleshixsn at earthlink.net>  wrote:
> >>>> I can't figure it out from
> >>>> http://www.digitalmars.com/d/2.0/operatoroverloading.html#Binary
> >>> 
> >>> // I assume your data structure looks like this
> >>> class Node(Key, Data)
> >>> {
> >>> Key k;
> >>> Node!(Key, Data) left, right;
> >>> int level;
> >>> // ...
> >>> 
> >>> void opBinary!("in")(Key k)
> >>> {
> >>> if (level == 0) return false;
> > 
> > Path: digitalmars.com!not-for-mail
> > From: Charles Hixson<charleshixsn at earthlink.net>
> > Newsgroups: digitalmars.D.learn
> > Subject: Re: defining "in"  What is the proper way in D2?
> > Date: Sun, 11 Sep 2011 14:09:57 -0700
> > Organization: Digital Mars
> > Lines: 15
> > Message-ID:<j4j83k$ree$1 at digitalmars.com>
> > References:<j4j45h$iti$1 at digitalmars.com> 
> > <op.v1nu0fdrtuzx1w at cybershadow.mshome.net> 
> > <j4j5uq$m8n$1 at digitalmars.com> Mime-Version: 1.0
> > Content-Type: text/plain; charset=UTF-8; format=flowed
> > Content-Transfer-Encoding: 8bit
> > X-Trace: digitalmars.com 1315775412 28110 66.245.57.66 (11 Sep 2011
> > 21:10:12 GMT) X-Complaints-To: usenet at digitalmars.com
> > NNTP-Posting-Date: Sun, 11 Sep 2011 21:10:12 +0000 (UTC)
> > User-Agent: Mozilla/5.0 (X11; U; Linux i686 (x86_64); en-US;
> > rv:1.9.2.21) Gecko/20110831 Iceowl/1.0b2 Icedove/3.1.13
> > In-Reply-To:<j4j5uq$m8n$1 at digitalmars.com>
> > Xref: digitalmars.com digitalmars.D.learn:29434
> > 
> > On 09/11/2011 01:33 PM, David Nadlinger wrote:
> >> On 9/11/11 10:25 PM, Vladimir Panteleev wrote:
> >>> void opBinary!("in")(Key k)
> >> 
> >> Shouldn't that be »void opBinary(string op : "in")(Key k)«? Also, you
> >> probably want to use opBinaryRight, because opBinary hooks »if
> >> (container in key)«.
> >> 
> >> David
> > 
> > And thanks for THIS, too.  I'd just started to wonder about the order of
> > the syntax.  After all, the key is in the container, but not conversely.
> > 
> >>> if (k<  key) return k in left;
> >>> if (key<  k) return k in right;
> >>> return true;
> >>> }
> >>> }
> >> 
> >> VOID??  I'm going to presume that this should have been bool.
> >> Otherwise, thanks.  That was they syntax I couldn't figure out from
> >> the
> >> docs.
> >> 
> >> And, yeah.  That's what it looks like.  My find code was wrong,
> >> because
> >> it should have referenced the node, so what I need to do is move the
> >> cod
> >> into the node class.  But it was the syntax of defining the opBinary
> >> specialization that was hanging me up.  (For some reason I have a hard
> >> time wrapping my mind around template code.)
> > 
> > The "in" operator normally returns a pointer to the value that you're
> > trying to find (and returns null if it's not there). Making it return
> > bool may work, but it's going to be a problem for generic code. That's
> > like making opBinary!"*" return a type different than the types being
> > multiplied. It's just not how the operator is supposed to be used and
> > could cause problems.
> > 
> > - Jonathan M Davis
> 
> OK, but what if the container is supposed to be opaque to external
> observers, but you still want to be able to tell whether it contains a
> particular item?  Doesn't returning a pointer violate encapsulation?

Yes and no. It does provide direct access to an element in the container, 
which could cause issues if they keep the pointer around (just like with any 
iterator or range which has been invalidated by a container being altered). 
But if you're looking to stop the element from being altered, all you'd have 
to do is make it a pointer to const.

> Also, the compiler complained about the declaration, causing me to
> currently substitute, thus:
> 
> // bool opBinaryRight!("in")(Key k)
>     bool opBinaryRight(string op)(Key k) if (op == "in")
> 
> I swiped that code from std.container.d  (which also returns a bool).
> As what I'm doing is pretty much like a standard container, this seemed
> like a reasonable place to look.  I sure hope that this doesn't mean I
> need to instantiate every use of in.  If that's the case I might be
> better off just staying with find.

I'm a bit surprised that std.container would have it returning bool, but that 
would work for any case where you're just checking for existence. It _is_ 
inefficient in many cases though, and is not great design IMHO. It may mean that 
templated code is ultimately going to have to use static ifs or template 
constraints to check where in returns a pointer, but the value of in is 
certainly reduced (albeit not eliminated) when it returns bool.

As for template instantiations, you get a new template instantiation for every 
type you try and instantiate a template with a new set of template arguments. 
If the only argument to opBinaryRight is the string for the operator, then 
it's only going to be instantiated once per operator.

As for sticking with find, you can't implement in such that it's at least as 
efficient as searching in balance binary tree (O(log n) I believe), then you 
shouldn't implement n. Ideally, it would be O(1), but that's obviously not 
always possible. Still, in really needs to be more efficient than find, or it 
shouldn't be there. But you shouldn't be having to use find just because of 
template bloat.

- Jonathan M Davis