A book shop has bookshelves with adjustable dividers. When one divider becomes full, the divider could be adjusted to make space. Create a Java program that will reallocate bookshelf space using Garwick's Algorithm.

Can any give me some pointers with this ? thanks.

I don't know what Garwick's algorithm is. Logically, if one section of the shelf needs more room, you will then have to re-divide the other sections so that the whole thing takes up the same amount of room as it did previously. Obviously, your project description is suggesting a method called Garwick's algorithm to do this.

Garwick's algorithm, for repacking LIFO lists stored in a contiguous block of memory, bases the allocation of remaining space upon both sharing and previous stack growth. A system whereby the weight applied to each method can be adjusted according to the current behavior of the stacks.

Garwick's algorithm, for repacking LIFO lists stored in a contiguous block of memory, bases the allocation of remaining space upon both sharing and previous stack growth. A system whereby the weight applied to each method can be adjusted according to the current behavior of the stacks.

To have the bookshelf, i first created and array and this array has a stack. My problem is that i have to subdivide this array to have a multiple stack using base pointer.. I can't quite get the base pointers.. I'm having trouble with creating my 3 stacks inside the array...

This is what i had so far:

import java.io.*;
import java.util.*;

public class MStack {

	/* Default length of the array */
	public static final int CAPACITY = 500;

	/* Length of the array used to implement the stack */
	public static int capacity;

	int d;

	/* Array used to implement the stack*/
	Object S[];

	/* Initialize the stack to default CAPACITY */
	public MStack(){
		this(CAPACITY);
	}
	/* Initialize the stack to be of the given length */
	public MStack(int c){
		capacity = c;
		S = new Object[capacity];
	}

	 public static void main (String []args){
		new MStack();
		System.out.println(CAPACITY);

		for(int i = 0; i < 3; i++){

		}
	 }


	 int T[] = new int[d];
	 int B[]= new int[d];

	 /* Pushes element on top of stack i. this method is for multiple   
          stack  */
	 public void push(int i, Object item) {
		 if (T[i]== B[i+1]) MStack(i);
		 S[++T[i]]= item;
	 }
	 /* Pops the top of stack i. This is for multiple satck */
	 public Object pop(int i) throws StackException{
		 Object item;
		 if (isEmpty(i))throw new StackException("Stack underflow.");
		 item = S[T[i]];
		 S[T[i]--] = null;
		 return item;
	 }
	 public boolean isEmpty(){
			return (T[i] = B[i+1]);
		}
	 class StackException extends RuntimeException{
			public StackException(String err){
			super(err);
	 }

   }
}

I have this lessons ryt now:

2.7.1.1 Three or More Stacks in a Vector S
If three or more stacks share the same vector, there is a need to keep track of several tops and base addresses. Base pointers defines the start of m stacks in a vector S with
size n. Notation of which is B(i):
B = ën/mû * i - 1 0 £ i < m
B[m] = n-1
B points to the space one cell below the stack's first actual cell. To initialize the stack, tops are set to point to base addresses, i.e.,
T = B , 0 £ i £ m

2.7.1.2 Three Possible States of a Stack
The following diagram shows the three possible states of a stack: empty, not full (but
not empty) and full. Stack i is full if T = B[i+1]. It is not full if T < B[i+1] and
empty if T = B.

This is Garwick's algorithm:
1. Strip all the stacks of unused cells and consider all of the unused cells as comprising the available or free space.

2. Reallocate one to ten percent of the available space equally among the stacks.

3. Reallocate the remaining available space among the stacks in proportion to recent
growth, where recent growth is measured as the difference T[j] – oldT[j], where oldT[j] is the value of T[j] at the end of last reallocation. A negative(positive) difference means that stack j actually decreased(increased) in size since last
reallocation.

i think the code i posted isn't any good. (frown)

HAPPY NEW YEAR! every one.. hehe

This article has been dead for over six months. Start a new discussion instead.