javolution.util.internal.table.FractalTableImpl Class Reference

Collaboration diagram for javolution.util.internal.table.FractalTableImpl:

Public Member Functions
	FractalTableImpl ()
	FractalTableImpl (int shift)
	FractalTableImpl (int shift, Object[] data, int offset)
int	capacity ()
Object	get (int index)
Object	set (int index, Object element)
void	shiftLeft (Object inserted, int last, int length)
void	shiftRight (Object inserted, int first, int length)
FractalTableImpl	upsize ()

Package Attributes
int	offset

Static Package Attributes
static final int	BASE_CAPACITY_MIN = 16
static final int	SHIFT = 8

Private Member Functions
void	copyTo (FractalTableImpl that)
FractalTableImpl	allocate (int i)
FractalTableImpl	F (int i)

Private Attributes
Object[]	data
final int	shift

Static Private Attributes
static final int	BASE_CAPACITY_MAX = 1 << SHIFT

Detailed Description

A fractal-based table with fast insertion/deletion capabilities regardless of the collection size. It is based on a fractal structure with self-similar patterns at any scale (large tables have the same structure as smaller tables which have similar structure as even smaller tables and so on).

Definition at line 19 of file FractalTableImpl.java.

Constructor & Destructor Documentation

FractalTableImpl() [1/3]

javolution.util.internal.table.FractalTableImpl.FractalTableImpl

(

)

Definition at line 35 of file FractalTableImpl.java.

                              {
        this.shift = 0;
        data = new Object[BASE_CAPACITY_MIN];
    }

References javolution.util.internal.table.FractalTableImpl.BASE_CAPACITY_MIN, and javolution.util.internal.table.FractalTableImpl.data.

Referenced by javolution.util.internal.table.FractalTableImpl.allocate(), javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.get(), and javolution.util.internal.table.FractalTableImpl.upsize().

Here is the caller graph for this function:

FractalTableImpl() [2/3]

javolution.util.internal.table.FractalTableImpl.FractalTableImpl

(

int

shift

)

Definition at line 40 of file FractalTableImpl.java.

                                       {
        this.shift = shift;
        data = new Object[2];
    }

References javolution.util.internal.table.FractalTableImpl.data, and javolution.util.internal.table.FractalTableImpl.shift.

FractalTableImpl() [3/3]

javolution.util.internal.table.FractalTableImpl.FractalTableImpl	(	int	shift,
		Object[]	data,
		int	offset
	)

Definition at line 45 of file FractalTableImpl.java.

                                                                  {
        this.shift = shift;
        this.data = data;
        this.offset = offset;
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.offset, and javolution.util.internal.table.FractalTableImpl.shift.

Member Function Documentation

allocate()

FractalTableImpl javolution.util.internal.table.FractalTableImpl.allocate ( int  i )

private

Definition at line 160 of file FractalTableImpl.java.

                                            {
        FractalTableImpl fractal = new FractalTableImpl(shift - SHIFT,
                new Object[1 << SHIFT], 0);
        data[i] = fractal;
        return fractal;
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.SHIFT, and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FractalTableImpl.F().

Here is the call graph for this function:

Here is the caller graph for this function:

capacity()

int javolution.util.internal.table.FractalTableImpl.capacity

(

)

Definition at line 51 of file FractalTableImpl.java.

                          { 
        // Reports lower capacity to ensure that there is no fractal holding 
        // wrapping data (head and tail in the same fractal).
        return (data.length - 1) << shift;
    }

References javolution.util.internal.table.FractalTableImpl.data, and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FastTableImpl< E >.upsize().

Here is the caller graph for this function:

copyTo()

void javolution.util.internal.table.FractalTableImpl.copyTo ( FractalTableImpl  that )

private

Definition at line 147 of file FractalTableImpl.java.

                                               {
        int n = MathLib.min(this.data.length, that.data.length);
        offset &= (data.length << shift) - 1; // Makes it positive.
        int o = offset >> shift;
        if ((o + n) > data.length) { // Wrapping.
            int w = (o + n) - data.length;
            n -= w;
            System.arraycopy(data, 0, that.data, n, w);
        }
        System.arraycopy(data, o, that.data, 0, n);
        that.offset = offset - (o << shift);
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.lang.MathLib.min(), javolution.util.internal.table.FractalTableImpl.offset, and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FractalTableImpl.upsize().

Here is the call graph for this function:

Here is the caller graph for this function:

F()

FractalTableImpl javolution.util.internal.table.FractalTableImpl.F ( int  i )

private

Definition at line 167 of file FractalTableImpl.java.

                                      {
        FractalTableImpl table = (FractalTableImpl) data[i];
        return (table != null) ? table : allocate(i);
    }

References javolution.util.internal.table.FractalTableImpl.allocate(), javolution.util.internal.table.FractalTableImpl.data, and javolution.util.internal.table.FractalTableImpl.FractalTableImpl().

Referenced by javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shiftLeft(), javolution.util.internal.table.FractalTableImpl.shiftRight(), and javolution.util.internal.table.FractalTableImpl.upsize().

Here is the call graph for this function:

Here is the caller graph for this function:

get()

Object javolution.util.internal.table.FractalTableImpl.get

(

int

index

)

Definition at line 57 of file FractalTableImpl.java.

                                 {
        Object fractal = data[((index + offset) >> shift) & (data.length - 1)];
        return (shift == 0) ? fractal : ((FractalTableImpl) fractal).get(index
                + offset);
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.offset, and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FastTableImpl< E >.get(), javolution.util.internal.table.FastTableImpl< E >.IteratorImpl.next(), javolution.util.internal.table.FastTableImpl< E >.remove(), javolution.util.internal.table.FractalTableImpl.shiftRight(), and javolution.util.internal.table.FastTableImpl< E >.writeObject().

Here is the call graph for this function:

Here is the caller graph for this function:

set()

Object javolution.util.internal.table.FractalTableImpl.set	(	int	index,
		Object	element
	)

Definition at line 63 of file FractalTableImpl.java.

                                                 {
        int i = ((index + offset) >> shift) & (data.length - 1);
        if (shift != 0) return F(i).set(index + offset, element);
        Object previous = data[i];
        data[i] = element;
        return previous;
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.offset, javolution.util.internal.table.FractalTableImpl.set(), and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FastTableImpl< E >.addFirst(), javolution.util.internal.table.FastTableImpl< E >.addLast(), javolution.util.internal.table.FastTableImpl< E >.removeFirst(), javolution.util.internal.table.FastTableImpl< E >.removeLast(), javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FastTableImpl< E >.set(), javolution.util.internal.table.FractalTableImpl.shiftLeft(), and javolution.util.internal.table.FractalTableImpl.shiftRight().

Here is the call graph for this function:

Here is the caller graph for this function:

shiftLeft()

void javolution.util.internal.table.FractalTableImpl.shiftLeft	(	Object	inserted,
		int	last,
		int	length
	)

Shifts the specified elements(]last - length, last] modulo capacity) one position to the left. No shift if length (modulo capacity) is zero.

Definition at line 73 of file FractalTableImpl.java.

                                                                 {
        int mask = (data.length << shift) - 1;
        int tail = (last + offset) & mask;
        int head = (last + offset - length) & mask;
        if (shift == 0) {
            int n = tail - head;
            if (head > tail) { // Wrapping
                System.arraycopy(data, head + 1, data, head, mask - head);
                data[mask] = data[0];
                n = tail;
            }
            System.arraycopy(data, tail - n + 1, data, tail - n, n);
            data[tail] = inserted;
        } else if ((head <= tail) && ((head >> shift) == (tail >> shift))) { // Shift local to inner table.
            F(head >> shift).shiftLeft(inserted, tail, length); // (no wrapping).
        } else {
            int low = head >> shift;
            int high = (low != data.length - 1) ? low + 1 : 0;
            F(low).shiftLeft(F(high).get(0), -1, mask - head);
            while (high != (tail >> shift)) {
                low = high;
                high = (low != data.length - 1) ? low + 1 : 0;
                F(low).offset++; // Full shift left.
                F(low).set(-1, F(high).get(0));
            }
            F(high).shiftLeft(inserted, tail, tail);
        }
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.offset, javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shift, and javolution.util.internal.table.FractalTableImpl.shiftLeft().

Referenced by javolution.util.internal.table.FastTableImpl< E >.add(), javolution.util.internal.table.FastTableImpl< E >.remove(), and javolution.util.internal.table.FractalTableImpl.shiftLeft().

Here is the call graph for this function:

Here is the caller graph for this function:

shiftRight()

void javolution.util.internal.table.FractalTableImpl.shiftRight	(	Object	inserted,
		int	first,
		int	length
	)

Shifts the specified element ([first, first + length[ modulo capacity) one position to the right. No shift if length (modulo capacity) is zero.

Definition at line 104 of file FractalTableImpl.java.

                                                                   {
        int mask = (data.length << shift) - 1;
        int head = (first + offset) & mask;
        int tail = (first + offset + length) & mask;
        if (shift == 0) {
            int n = tail - head;
            if (head > tail) { // Wrapping
                System.arraycopy(data, 0, data, 1, tail);
                data[0] = data[mask];
                n = mask - head;
            }
            System.arraycopy(data, head, data, head + 1, n);
            data[head] = inserted;
        } else if ((head <= tail) && ((head >> shift) == (tail >> shift))) { // Shift local to inner table.
            F(head >> shift).shiftRight(inserted, head, length); // (no wrapping).
        } else {
            int high = tail >> shift;
            int low = (high != 0) ? high - 1 : data.length - 1;
            F(high).shiftRight(F(low).get(-1), 0, tail);
            while (low != (head >> shift)) {
                high = low;
                low = (high != 0) ? high - 1 : data.length - 1;
                F(high).offset--; // Full shift right.
                F(high).set(0, F(low).get(-1));
            }
            F(low).shiftRight(inserted, head, mask - head);
        }
    }

References javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.get(), javolution.util.internal.table.FractalTableImpl.offset, javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shift, and javolution.util.internal.table.FractalTableImpl.shiftRight().

Referenced by javolution.util.internal.table.FastTableImpl< E >.add(), javolution.util.internal.table.FastTableImpl< E >.remove(), and javolution.util.internal.table.FractalTableImpl.shiftRight().

Here is the call graph for this function:

Here is the caller graph for this function:

upsize()

FractalTableImpl javolution.util.internal.table.FractalTableImpl.upsize

(

)

Definition at line 133 of file FractalTableImpl.java.

                                     {
        if (data.length >= BASE_CAPACITY_MAX) { // Creates outer fractal.
            FractalTableImpl table = new FractalTableImpl(shift + SHIFT);
            copyTo(table.F(0));
            return table;
        } else {
           FractalTableImpl table = 
                new FractalTableImpl(shift, new Object[data.length << 1], 0);
           copyTo(table);
           return table;
        }
    }

References javolution.util.internal.table.FractalTableImpl.BASE_CAPACITY_MAX, javolution.util.internal.table.FractalTableImpl.copyTo(), javolution.util.internal.table.FractalTableImpl.data, javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.SHIFT, and javolution.util.internal.table.FractalTableImpl.shift.

Referenced by javolution.util.internal.table.FastTableImpl< E >.upsize().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

BASE_CAPACITY_MAX

final int javolution.util.internal.table.FractalTableImpl.BASE_CAPACITY_MAX = 1 << SHIFT

staticprivate

Definition at line 23 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FractalTableImpl.upsize().

BASE_CAPACITY_MIN

final int javolution.util.internal.table.FractalTableImpl.BASE_CAPACITY_MIN = 16

staticpackage

Definition at line 21 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FractalTableImpl.FractalTableImpl().

data

Object [] javolution.util.internal.table.FractalTableImpl.data

private

An array of data elements or fractal tables (recursion). Data length varies from 2 to BASE_CAPACITY_MAX

Definition at line 30 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FractalTableImpl.allocate(), javolution.util.internal.table.FractalTableImpl.capacity(), javolution.util.internal.table.FractalTableImpl.copyTo(), javolution.util.internal.table.FractalTableImpl.F(), javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.get(), javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shiftLeft(), javolution.util.internal.table.FractalTableImpl.shiftRight(), and javolution.util.internal.table.FractalTableImpl.upsize().

offset

int javolution.util.internal.table.FractalTableImpl.offset

package

Offset value, it is the index of the first element (modulo data.length).

Definition at line 26 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FastTableImpl< E >.add(), javolution.util.internal.table.FastTableImpl< E >.addFirst(), javolution.util.internal.table.FractalTableImpl.copyTo(), javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.get(), javolution.util.internal.table.FastTableImpl< E >.remove(), javolution.util.internal.table.FastTableImpl< E >.removeFirst(), javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shiftLeft(), and javolution.util.internal.table.FractalTableImpl.shiftRight().

SHIFT

final int javolution.util.internal.table.FractalTableImpl.SHIFT = 8

staticpackage

Definition at line 22 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FractalTableImpl.allocate(), and javolution.util.internal.table.FractalTableImpl.upsize().

shift

final int javolution.util.internal.table.FractalTableImpl.shift

private

The index shift, zero if base table.

Definition at line 33 of file FractalTableImpl.java.

Referenced by javolution.util.internal.table.FractalTableImpl.allocate(), javolution.util.internal.table.FractalTableImpl.capacity(), javolution.util.internal.table.FractalTableImpl.copyTo(), javolution.util.internal.table.FractalTableImpl.FractalTableImpl(), javolution.util.internal.table.FractalTableImpl.get(), javolution.util.internal.table.FractalTableImpl.set(), javolution.util.internal.table.FractalTableImpl.shiftLeft(), javolution.util.internal.table.FractalTableImpl.shiftRight(), and javolution.util.internal.table.FractalTableImpl.upsize().

---

The documentation for this class was generated from the following file:

• FractalTableImpl.java