Skip to main content
sketching a broader picture
Source Link
greybeard
  • 7.8k
  • 3
  • 21
  • 56

I(Please see effectiviology on what to avoid in investing in implementation efficiency.)
I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    private static class unboundedUnbounded extends Nodes {}

Decrementing i in size() and returning -1i looks off -


The problem of coming up with a decent implementation of java.util.Deque<E>'s fat interface starts in the infancy of Java (before introduction of the collections framework), if not in language design (no distinction between public derivation (is a) and private (silently exploits); derived classes getting to replace methods instead of contributing (Simula inner)):
While a resizeable array is useful to implement an unbounded stack, exposing java.util.Stack being a java.util.Vector goes way beyond push() and pop() (even isEmpty() and top() are conveniencies).
Similarly, deriving java.util.Deque<E> from java.util.Collection<E> (java.util.SequencedCollection<E> since 21) inherits a fat interface.
The collections framework resorts to providing the likes of java.util.AbstractCollection<E>, significantly reducing the set of methods mandatory to implement.

Which you should exploit.
Extend java.util.AbstractCollection<E>, and where you don't need&have a better implementation idea just don't waste effort.
(If you feel iteration using an iterator is just too inefficient and needs inlining at the source code level: JIT compilers do a lot of amazing things, and keep getting better.)
This should take care of size() and contains() as well as of Deque<F>'s bulk operations.


Space efficiency: A regular doubly linked list takes three references per item in Java (yours, too).
ArrayDeque<E> style implementations don't usually grow their arrays by factors above 2: without removals (other than at one of the end, e.g. via iterator()), such an array based implementation never uses more per item space, and less with high probability.
Plus advantages in memory access patterns and garbage handling.
Removals from the middle present a - manageable - challenge.

I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    private static class unbounded extends Nodes {}

Decrementing i in size() and returning -1 looks off -

(Please see effectiviology on what to avoid in investing in implementation efficiency.)
I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    private static class Unbounded extends Nodes {}

Decrementing i in size() and returning -i looks off -


The problem of coming up with a decent implementation of java.util.Deque<E>'s fat interface starts in the infancy of Java (before introduction of the collections framework), if not in language design (no distinction between public derivation (is a) and private (silently exploits); derived classes getting to replace methods instead of contributing (Simula inner)):
While a resizeable array is useful to implement an unbounded stack, exposing java.util.Stack being a java.util.Vector goes way beyond push() and pop() (even isEmpty() and top() are conveniencies).
Similarly, deriving java.util.Deque<E> from java.util.Collection<E> (java.util.SequencedCollection<E> since 21) inherits a fat interface.
The collections framework resorts to providing the likes of java.util.AbstractCollection<E>, significantly reducing the set of methods mandatory to implement.

Which you should exploit.
Extend java.util.AbstractCollection<E>, and where you don't need&have a better implementation idea just don't waste effort.
(If you feel iteration using an iterator is just too inefficient and needs inlining at the source code level: JIT compilers do a lot of amazing things, and keep getting better.)
This should take care of size() and contains() as well as of Deque<F>'s bulk operations.


Space efficiency: A regular doubly linked list takes three references per item in Java (yours, too).
ArrayDeque<E> style implementations don't usually grow their arrays by factors above 2: without removals (other than at one of the end, e.g. via iterator()), such an array based implementation never uses more per item space, and less with high probability.
Plus advantages in memory access patterns and garbage handling.
Removals from the middle present a - manageable - challenge.

added 8 characters in body
Source Link
greybeard
  • 7.8k
  • 3
  • 21
  • 56

I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    /** adds capacity limiting */
    private static class Bounded extends Nodes {
        private final int bound;

        public Bounded(int boundry) {
        //  super();  // implicit
            bound = boundry;
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean append(Object element) {
            if (size() >= bound) { return false; }
            return super.append(element);
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean prepend(Object element) {
            if (size() == bound) { return false; }
            return super.prepend(element);
        }
    }

This does not read extends Unbounded:
from C++ I feel extends should mean is a - not given here.
Unbounded should be even less effort:

    private static class unbounded extends Nodes {}

In Point I like next(), fore() and element() for abstracting from any implementation. Not checking for "needle" null in the contains-iterations is a nice touch.

Decrementing i in size() and returning -1 looks off -

        public int size() {
            int n = 0;
            for (Object[] point = peak ; leaf != (point = Point.next(peakpoint)) ; n++)
                ;
            return n;
        }

I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    /** adds capacity limiting */
    private static class Bounded extends Nodes {
        private final int bound;

        public Bounded(int boundry) {
        //  super();  // implicit
            bound = boundry;
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean append(Object element) {
            if (size() >= bound) { return false; }
            return super.append(element);
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean prepend(Object element) {
            if (size() == bound) { return false; }
            return super.prepend(element);
        }
    }

This does not read extends Unbounded:
from C++ I feel extends should mean is a - not given here.
Unbounded should be even less effort:

    private static class unbounded extends Nodes {}

In Point I like next(), fore() and element() for abstracting from any implementation. Not checking for "needle" null in the contains-iterations is a nice touch.

Decrementing i in size() and returning -1 looks off -

        public int size() {
            int n = 0;
            for (Object[] point ; leaf != (point = Point.next(peak)) ; n++)
                ;
            return n;
        }

I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    /** adds capacity limiting */
    private static class Bounded extends Nodes {
        private final int bound;

        public Bounded(int boundry) {
        //  super();  // implicit
            bound = boundry;
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean append(Object element) {
            if (size() >= bound) { return false; }
            return super.append(element);
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean prepend(Object element) {
            if (size() == bound) { return false; }
            return super.prepend(element);
        }
    }

This does not read extends Unbounded:
from C++ I feel extends should mean is a - not given here.
Unbounded should be even less effort:

    private static class unbounded extends Nodes {}

In Point I like next(), fore() and element() for abstracting from any implementation. Not checking for "needle" null in the contains-iterations is a nice touch.

Decrementing i in size() and returning -1 looks off -

        public int size() {
            int n = 0;
            for (Object[] point = peak ; leaf != (point = Point.next(point)) ; n++)
                ;
            return n;
        }
Source Link
greybeard
  • 7.8k
  • 3
  • 21
  • 56

I see a lot of undocumented code that I feel I have seen somewhere else in the file - take the classes implements Point: Bounded&Unbounded.
The one difference I can see is Bounded comparing size() and bound:

    /** adds capacity limiting */
    private static class Bounded extends Nodes {
        private final int bound;

        public Bounded(int boundry) {
        //  super();  // implicit
            bound = boundry;
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean append(Object element) {
            if (size() >= bound) { return false; }
            return super.append(element);
        }

        /** no faster than <code>size()</code> */
        @Override
        public boolean prepend(Object element) {
            if (size() == bound) { return false; }
            return super.prepend(element);
        }
    }

This does not read extends Unbounded:
from C++ I feel extends should mean is a - not given here.
Unbounded should be even less effort:

    private static class unbounded extends Nodes {}

In Point I like next(), fore() and element() for abstracting from any implementation. Not checking for "needle" null in the contains-iterations is a nice touch.

Decrementing i in size() and returning -1 looks off -

        public int size() {
            int n = 0;
            for (Object[] point ; leaf != (point = Point.next(peak)) ; n++)
                ;
            return n;
        }