From: Khalid Zarigue
Subject: help
Date: 
Message-ID: <3E09C92F.572413CD@emi.u-bordeaux.fr>
can you explain me what mean "vector with hole"

think

From: JP Massar
Subject: Re: help
Date: 
Message-ID: <3e0a11b8.220492241@netnews.attbi.com>
On Wed, 25 Dec 2002 16:05:19 +0100, Khalid Zarigue
<·······@emi.u-bordeaux.fr> wrote:

>can you explain me what mean "vector with hole"
>
 
Not unless you provide more context.  I'm not
familiar with the expression and I can't think of
what it might be referring to.

Where did you find the expression and what is the
surrounding context?
From: Robert STRANDH
Subject: Re: help
Date: 
Message-ID: <6wel85u3ne.fsf@serveur3.labri.fr>
······@alum.mit.edu (JP Massar) writes:

> On Wed, 25 Dec 2002 16:05:19 +0100, Khalid Zarigue
> <·······@emi.u-bordeaux.fr> wrote:
> 
> >can you explain me what mean "vector with hole"
> 
> Where did you find the expression

Most likely in my text book (in French) on Common Lisp. 
-- 
Robert Strandh
From: Robert STRANDH
Subject: Re: help
Date: 
Message-ID: <6wisxhu3qj.fsf@serveur3.labri.fr>
Khalid Zarigue <·······@emi.u-bordeaux.fr> writes:

> can you explain me what mean "vector with hole"

What you are referring to is an implementation technique for certain
containers, and has nothing directly to do with Common Lisp.  

When you have a mutable sequence of objects, there are several
possible implementation techniques with various computational
complexity:

  - A linear list or a vector.  Takes O(n) to insert and delete.
  - A tree.  Takes O(log n) to insert and delete.
  - etc.

Now, if you know that inserting and deleting elements are not done
randomly, but around a particular local region of the sequence (you
could use a first order Markov model to approximate these operations,
I guess), a "vector with hole" could be used.  It is (at least was)
the technique used by GNU Emacs to implement buffers.  Essentially,
you organize your elements in a vector which is larger than the number
of elements in it, and divide the sequence into two subsequences,
before and after the hole.  It is assumed that the hole will not move
very often, and usually not very long distances.  If that is true, you
get mostly O(1) complexity for insert and delete operations.  Insert
and delete operations are always done around the hole (before it or
after it).  When an operation is attempted at a position other than
that of the hole, the hole is first moved to the position of the
operation.  Moving the hole can take O(n) in the worst case, but if
the distance is small, it is much faster.

Good luck with your take-home exam, 
-- 
Robert Strandh
From: Rahul Jain
Subject: Re: help
Date: 
Message-ID: <87r8c59r2l.fsf@localhost.localdomain>
Robert STRANDH <·······@labri.u-bordeaux.fr> writes:

> Khalid Zarigue <·······@emi.u-bordeaux.fr> writes:
> 
> > can you explain me what mean "vector with hole"
[...]
> Now, if you know that inserting and deleting elements are not done
> randomly, but around a particular local region of the sequence (you
> could use a first order Markov model to approximate these operations,
> I guess), a "vector with hole" could be used.

I think the traditional English term used for this data structure is
"gap buffer".

--
Rahul Jain
From: Tom Lord
Subject: Re: help
Date: 
Message-ID: <v0lj90jc53tc38@corp.supernews.com>
	I think the traditional English term used for this data
	structure is "gap buffer".


The modern English term for "gap buffer" is "That thing I implemented
because I was too lazy to do a splay-tree-based data structure."

-t