help

Khalid Zarigue

unread,

Dec 25, 2002, 10:05:19 AM12/25/02

to

can you explain me what mean "vector with hole"

think

JP Massar

unread,

Dec 25, 2002, 3:17:04 PM12/25/02

to

On Wed, 25 Dec 2002 16:05:19 +0100, Khalid Zarigue
<zar...@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?

Robert STRANDH

unread,

Dec 25, 2002, 5:36:53 PM12/25/02

to

mas...@alum.mit.edu (JP Massar) writes:

> On Wed, 25 Dec 2002 16:05:19 +0100, Khalid Zarigue
> <zar...@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

Robert STRANDH

unread,

Dec 25, 2002, 5:35:00 PM12/25/02

to

Khalid Zarigue <zar...@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

Rahul Jain

unread,

Dec 26, 2002, 2:28:49 AM12/26/02

to

Robert STRANDH <str...@labri.u-bordeaux.fr> writes:

> Khalid Zarigue <zar...@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

Tom Lord

unread,

Dec 26, 2002, 4:34:24 AM12/26/02

to

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