Subversion Repositories Code-Repo

Compare Revisions

No changes between revisions

Ignore whitespace Rev 94 → Rev 95

/Classwork/CS3114/Project 3/.classpath
0,0 → 1,6
<?xml version="1.0" encoding="UTF-8"?>
<classpath>
<classpathentry kind="src" path=""/>
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/>
<classpathentry kind="output" path=""/>
</classpath>
/Classwork/CS3114/Project 3/.project
0,0 → 1,17
<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
<name>CS3114P3</name>
<comment></comment>
<projects>
</projects>
<buildSpec>
<buildCommand>
<name>org.eclipse.jdt.core.javabuilder</name>
<arguments>
</arguments>
</buildCommand>
</buildSpec>
<natures>
<nature>org.eclipse.jdt.core.javanature</nature>
</natures>
</projectDescription>
/Classwork/CS3114/Project 3/.settings/org.eclipse.jdt.core.prefs
0,0 → 1,12
#Mon Oct 31 11:59:45 EDT 2011
eclipse.preferences.version=1
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
org.eclipse.jdt.core.compiler.compliance=1.6
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
org.eclipse.jdt.core.compiler.debug.localVariable=generate
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
org.eclipse.jdt.core.compiler.source=1.6
/Classwork/CS3114/Project 3/BufferBlock.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/BufferBlock.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/BufferBlock.java
0,0 → 1,60
 
public class BufferBlock {
private long startAddress;
private byte[] bytes;
private int size;
private BufferBlock prev;
private BufferBlock next;
private boolean dirtyBit;
public BufferBlock(int sz) {
setStartAddress(-1);
bytes = new byte[sz];
this.size = sz;
prev = null;
next = null;
setDirtyBit(false);
}
// Copies size bytes starting from address to out
public void getBytes(byte[] out, int address, int size) {
for (int i = 0; i < size; i++) {
out[i] = bytes[address + i];
}
}
// Puts size bytes starting from address from in
public void setBytes(byte[] in, int address, int size) {
for (int i = 0; i < size; i++) {
bytes[address + i] = in[i];
}
}
public BufferBlock getPrev() {
return prev;
}
public void setPrev(BufferBlock prev) {
this.prev = prev;
}
public BufferBlock getNext() {
return next;
}
public void setNext(BufferBlock next) {
this.next = next;
}
public int getSize() {
return size;
}
public boolean isDirtyBit() {
return dirtyBit;
}
public void setDirtyBit(boolean dirtyBit) {
this.dirtyBit = dirtyBit;
}
public long getStartAddress() {
return startAddress;
}
public void setStartAddress(long startAddress) {
this.startAddress = startAddress;
}
}
/Classwork/CS3114/Project 3/Genfile2.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/Genfile2.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/Genfile2.java
0,0 → 1,57
// WARNING: This program uses the Assertion class. When it is run,
// assertions must be turned on. For example, under Linux, use:
// java -ea Genfile
 
/** Generate a data file. The size is a multiple of 4096 bytes.
The records are short ints, with each record having a value
less than 30,000.
*/
 
import java.io.*;
import java.util.*;
import java.math.*;
 
public class Genfile2 {
 
static final int BlockSize = 4096;
static final int NumRecs = 2048; // Because they are short ints
 
/** Initialize the random variable */
static private Random value = new Random(); // Hold the Random class object
 
static int random(int n) {
return Math.abs(value.nextInt()) % n;
}
 
public static void main(String args[]) throws IOException {
 
assert (args.length == 3) && (args[0].charAt(0) == '-') :
"\nUsage: Genfile <option> <filename> <size>" +
"\nOptions ust be '-a' for ASCII, or '-b' for binary." +
"\nSize is measured in blocks of 4096 bytes";
 
int filesize = Integer.parseInt(args[2]); // Size of file in blocks
DataOutputStream file = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(args[1])));
 
int recs = NumRecs * filesize;
 
if (args[0].charAt(1) == 'b') // Write out random numbers
for (int i=0; i<filesize; i++)
for (int j=0; j<NumRecs; j++) {
short val = (short)(random(29999) + 1);
file.writeShort(val);
}
else if (args[0].charAt(1) == 'a') // Write out ASCII-readable values
for (int i=0; i<filesize; i++)
for (int j=0; j<NumRecs; j++) {
short val = (short)((8224 << 16) + random(26) + 0x2041);
file.writeShort(val);
}
else assert false : "Bad parameters";
 
file.flush();
file.close();
}
 
}
/Classwork/CS3114/Project 3/LRUBuffer.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/LRUBuffer.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/LRUBuffer.java
0,0 → 1,214
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.RandomAccessFile;
 
public class LRUBuffer {
private int blockSize = 0;
private int recordSize = 0;
private int cacheHit = 0;
private int cacheMiss = 0;
private int diskReads = 0;
private int diskWrites = 0;
private String dataFile;
private String statFile;
private int bufferSize;
private BufferBlock bufferHead;
private RandomAccessFile file;
public LRUBuffer(String datafile, String statfile, int size, int blocksize, int recordsize) {
this.dataFile = datafile;
this.statFile = statfile;
this.bufferSize = size;
this.blockSize = blocksize;
this.recordSize = recordsize;
// Allocates a new doubly linked list of BufferBlocks
// The buffer will have at least one block
bufferHead = new BufferBlock(blockSize);
BufferBlock cur = bufferHead;
for (int i = 0; i < size-1; i++) {
BufferBlock newBlock = new BufferBlock(blockSize);
cur.setNext(newBlock);
newBlock.setPrev(cur);
cur = newBlock;
}
// Open access to the datafile
try {
file = new RandomAccessFile(dataFile, "rw");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
// Returns recordSize number of bytes to out from record # pos
public boolean getBytes(byte[] out, long pos) {
BufferBlock cur = bufferHead;
// Calculate the address of record
long address = pos * recordSize;
// Check if address is already in a buffer block
while (cur != null && cur.getStartAddress() != -1) {
if (address >= cur.getStartAddress() && address < cur.getStartAddress() + blockSize) {
// Address is in block, get data
cacheHit++;
cur.getBytes(out, (int)address % blockSize, recordSize);
// Bring current block to front of list
bringToFront(cur);
return true;
}
cur = cur.getNext();
}
// Address is not in buffer, read new block from disk
cacheMiss++;
BufferBlock newBlock = readFromDisk(address);
// Get requested bytes from block
newBlock.getBytes(out, (int)address % blockSize, recordSize);
insertToFront(newBlock);
return false;
}
// Puts recordSize number of bytes from in to record # pos
public boolean putBytes(byte[] in, long pos) {
BufferBlock cur = bufferHead;
// Calculate the address of record
long address = pos * recordSize;
// Check if address is already in a buffer block
while (cur != null && cur.getStartAddress() != -1) {
if (address >= cur.getStartAddress() && address < cur.getStartAddress() + blockSize) {
// Address is in block, put data
cacheHit++;
cur.setBytes(in, (int)address % blockSize, recordSize);
cur.setDirtyBit(true);
// Bring current block to front of list
bringToFront(cur);
return true;
}
cur = cur.getNext();
}
// Address is not in buffer, read new block from disk
cacheMiss++;
BufferBlock newBlock = readFromDisk(address);
// Put passed bytes into block
newBlock.setBytes(in, (int)address % blockSize, recordSize);
newBlock.setDirtyBit(true);
insertToFront(newBlock);
return false;
}
// Brings a block currently in the list to the front of the list
private void bringToFront(BufferBlock block) {
// If block is already in front, return
if (block == bufferHead)
return;
if (block.getPrev() != null)
block.getPrev().setNext(block.getNext());
if (block.getNext() != null)
block.getNext().setPrev(block.getPrev());
block.setPrev(null);
bufferHead.setPrev(block);
block.setNext(bufferHead);
bufferHead = block;
}
// Inserts a new block into the front of the list
private void insertToFront(BufferBlock block) {
// Set head as current block
block.setPrev(null);
bufferHead.setPrev(block);
block.setNext(bufferHead);
bufferHead = block;
// Write last block in list to disk if dirty bit is set
// Last block is also removed
BufferBlock cur = bufferHead;
while (cur.getNext() != null) {
cur = cur.getNext();
}
cur.getPrev().setNext(null);
if (cur.isDirtyBit()) {
writeToDisk(cur);
}
}
 
// Reads a new block from disk given an address
private BufferBlock readFromDisk(long address) {
diskReads++;
byte[] data = new byte[blockSize];
long offset = address / blockSize;
offset = offset * blockSize;
try {
file.seek(offset);
file.read(data);
} catch (IOException e) {
e.printStackTrace();
}
// Pass read block into a new block
BufferBlock newBlock = new BufferBlock(blockSize);
newBlock.setBytes(data, 0, blockSize);
newBlock.setStartAddress(offset);
return newBlock;
}
// Writes the specified block to disk
private void writeToDisk(BufferBlock block) {
diskWrites++;
byte[] data = new byte[blockSize];
block.getBytes(data, 0, blockSize);
try {
file.seek(block.getStartAddress());
file.write(data);
} catch (IOException e) {
e.printStackTrace();
}
}
// Flush the buffer by writing all blocks in buffer to disk
public void flushBuffer() {
BufferBlock cur = bufferHead;
while (cur != null) {
if (cur.isDirtyBit()) {
writeToDisk(cur);
}
cur = cur.getNext();
}
try {
file.close();
} catch (IOException e) {
e.printStackTrace();
}
}
// Write stats to stat file
public void writeStats(long time) {
try {
BufferedWriter out = new BufferedWriter(new FileWriter(statFile, true));
StringBuilder str = new StringBuilder();
str.append("Datafile: " + dataFile + " | ");
str.append("Cache Hits: " + cacheHit + " | ");
str.append("Cache Misses: " + cacheMiss + " | ");
str.append("Disk Reads: " + diskReads + " | ");
str.append("Disk Writes: " + diskWrites + " | ");
str.append("Time to Sort: " + time + "\n");
out.write(str.toString());
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/Classwork/CS3114/Project 3/MaxHeap.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/MaxHeap.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/MaxHeap.java
0,0 → 1,139
import java.nio.ByteBuffer;
 
/** Max-heap implementation */
public class MaxHeap {
private LRUBuffer Heap; // Pointer to the heap array
private long size; // Number of things in heap
private byte[] record1 = new byte[4];
private byte[] record2 = new byte[4];
private ByteBuffer buff1;
private ByteBuffer buff2;
/** Constructor supporting preloading of heap contents */
public MaxHeap(LRUBuffer buf, long size) {
this.Heap = buf;
this.size = size;
}
 
/** @return True if pos a leaf position, false otherwise */
public boolean isLeaf(long pos) {
return (pos >= size / 2) && (pos < size);
}
 
/** @return Position for left child of pos */
public long leftchild(long pos) {
assert pos < size / 2 : "Position has no left child";
return 2 * pos + 1;
}
 
/** @return Position for right child of pos */
public long rightchild(long pos) {
assert pos < (size - 1) / 2 : "Position has no right child";
return 2 * pos + 2;
}
 
/** @return Position for parent */
public long parent(long pos) {
assert pos > 0 : "Position has no parent";
return (pos - 1) / 2;
}
 
/** Heapify contents of Heap */
public void buildheap() {
for (long i = size / 2 - 1; i >= 0; i--)
siftdown(i);
}
 
/** Put element in its correct place */
private void siftdown(long pos) {
assert (pos >= 0) && (pos < size) : "Illegal heap position";
while (!isLeaf(pos)) {
long j = leftchild(pos);
// if ((j < (size - 1)) && (Heap[j].compareTo(Heap[j + 1]) < 0))
// j++; // j is now index of child with greater value
if (j < (size-1)) {
Heap.getBytes(record1, j);
buff1 = ByteBuffer.wrap(record1);
short val1 = buff1.getShort();
Heap.getBytes(record2, j+1);
buff2 = ByteBuffer.wrap(record2);
short val2 = buff2.getShort();
if (val1 < val2) {
j++; // j is now index of child with greater value
}
}
// if (Heap[pos].compareTo(Heap[j]) >= 0)
// return;
Heap.getBytes(record2, j);
Heap.getBytes(record1, pos);
buff1 = ByteBuffer.wrap(record1);
buff2 = ByteBuffer.wrap(record2);
short val1 = buff1.getShort();
short val2 = buff2.getShort();
if (val1 >= val2)
return;
 
// DSutil.swap(Heap, pos, j);
Heap.putBytes(record2, pos);
Heap.putBytes(record1, j);
pos = j; // Move down
}
}
 
/** Remove and return maximum value */
public void removemax() {
assert size > 0 : "Removing from empty heap";
//DSutil.swap(Heap, 0, --size); // Swap maximum with last value
Heap.getBytes(record1, 0);
Heap.getBytes(record2, size-1);
Heap.putBytes(record1, size-1);
Heap.putBytes(record2, 0);
size = size - 1;
if (size != 0) // Not on last element
siftdown(0); // Put new heap root val in correct place
}
 
// /** @return Current size of the heap */
// public long heapsize() {
// return size;
// }
// /** Insert val into heap */
// public void insert(E val) {
// assert n < size : "Heap is full";
// int curr = n++;
// Heap[curr] = val; // Start at end of heap
// // Now sift up until curr's parent's key > curr's key
// while ((curr != 0) && (Heap[curr].compareTo(Heap[parent(curr)]) > 0)) {
// DSutil.swap(Heap, curr, parent(curr));
// curr = parent(curr);
// }
// }
// /** Remove and return element at specified position */
// public E remove(int pos) {
// assert (pos >= 0) && (pos < n) : "Illegal heap position";
// if (pos == (n - 1))
// n--; // Last element, no work to be done
// else {
// DSutil.swap(Heap, pos, --n); // Swap with last value
// // If we just swapped in a big value, push it up
// while ((pos > 0) && (Heap[pos].compareTo(Heap[parent(pos)]) > 0)) {
// DSutil.swap(Heap, pos, parent(pos));
// pos = parent(pos);
// }
// if (n != 0)
// siftdown(pos); // If it is little, push down
// }
// return Heap[n];
// }
}
/Classwork/CS3114/Project 3/Old_Test_Files/Outfilea.dat
0,0 → 1,0
N W L R B B M Q B H C D A R Z O W K K Y H I D D Q S C D X R J M O W F R X S J Y B L D B E F S A R C B Y N E C D Y G G X X P K L O R E L L N M P A P Q F W K H O P K M C O Q H N W N K U E W H S Q M G B B U Q C L J J I V S W M D K Q T B X I X M V T R R B L J P T N S N F W Z Q F J M A F A D R R W S O F S B C N U V Q H F F B S A Q X W P Q C A C E H C H Z V F R K M L N O Z J K P Q P X R J X K I T Z Y X A C B H H K I C Q C O E N D T O M F G D W D W F C G P X I Q V K U Y T D L C G D E W H T A C I O H O R D T Q K V W C S G S P Q O Q M S B O A G U W N N Y Q X N Z L G D G W P B T R W B L N S A D E U G U U M O Q C D R U B E T O K Y X H O A C H W D V M X X R D R Y X L M N D Q T U K W A G M L E J U U K W C I B X U B U M E N M E Y A T D R M Y D I A J X L O G H I Q F M Z H L V I H J O U V S U Y O Y P A Y U L Y E I M U O T E H Z R I I C F S K P G G K B B I P Z Z R Z U C X A M L U D F Y K G R U O W Z G I O O O B P P L E Q L W P H A P J N A D Q H D C N V W D T X J B M Y P P P H A U X N S P U S G D H I I X Q M B F J X J C V U D J S U Y I B Y E B M W S I Q Y O Y G Y X Y M Z E V Y P Z V J E G E B E O C F U F T S X D I X T I G S I E E H K C H Z D F L I L R J Q F N X Z T Q R S V B S P K Y H S E N B P P K Q T P D D B U O T B B Q C W I V R F X J U J J D D N T G E I Q V D G A I J V W C Y A U B W E W P J V Y G E H L J X E P B P I W U Q Z D Z U B D U B Z V A F S P Q P Q W U Z I F W O V Y D D W Y V V B U R C Z M G Y J G F D X V T N U N N E S L S P L W U I U P F X L Z B K N H K W P P A N L T C F I R J C D D S O Z O Y V E G U R F W C S F M O X E Q M R J O W R G H W L K O B M E A H K G C C N A E H H S V E Y M Q P X H L R N U N Y F D Z R H B A S J E U Y G A F O U B U T P N I M U W F J Q S J X V K Q D O R X X V R W C T D S N E O G V B P K X L P G D I R B F C R I Q I F P G Y N K R R E F X S N V U C F T P W C T G T W M X N U P Y C F G C U Q U N U B L M O I I T N C K L E F S Z B E X R A M P E T V H Q N D D J E Q V U Y G P N K A Z Q F R P J V O A X D P C W M J O B M S K S K F O J N E W X G X N N O F W L T W J W N N V B W J C K D M E O U U Z H Y V H G V W U J B Q X X P I T C V O G R A I D D V H R R D S Y C Q H K L E E W H X T E M B A Q W Q W P Q H S U E B N V F G V J W D V J J A F Q Z Z X L C X D Z N C Q G J L A P O P K V X F G V I C E T C M K B L J O P G T Q V V H B G S D V I V H E S N K Q X M W R Q I D R V M H L U B B R Y K T H E Y E N T M R O B D E Y Q C R G L U A I I H V E I X W J J R Q O P U B J G U X H X D I P F Z W S W Y B G F Y L Q V J Z H A R V R L Y A U U Z D R C N J K P H C L F F R K E E C B P D I P U F H I D J C X J H R N X C X M J C X O H Q A N X D R M G Z E B H N L M W P M H W D V T H S F Q U E E E X G R U J I G S K M V R Z G F W V R F T W A P D T U T P B Z T Y G N S R X A J J N G C O M I K J Z S D W S S Z N O V D R U Y P C N J U L K F U Z M X N A F A M E S P C K J C A Z X D R T D G Y R Q S C C Z Y B N V Q Q C Q C J I T L V C N V B M A S I D Z G W R A A T Z Z W P W M F B F J K N C V K E L H H Z J C H P D N L U N M P P N L G J Z N K E W W U Y S G E F O N E X P M M S B A O P M D G Z Q M K Q Z X U V T Q V N X B S L Q Z K G L Z A M Z P D N S J O L V Y B W X X T T Q O G N R B A I A K Q L L S Z K H F Z C O N N M O Q K L P E E F S N S M O U W Q H O D S G C F O H E S Y S H M G X W T O A Y U V N O J D J F T Q T W K B A P R I U J I M Q W S P S L G V L C S A Q B D B G W T B S E E T T W D N F N B Y J V P D J X Y U Z Q X S T A T B Z P C T T H O O F R E M G F K R B C V K Z V G B O F T H G O J H D N A Y W P N B I T O R A A I B E D N E Z W F P D A W L O H S S V T Q T K F V S Y L J Z L U C Q X S W Y Q D N T D M F R T Z L Q S E K E J H Z K S K L F E P X C H V C Z Y S V D G C X B B I S W M E A Y L Z I F K T M O I K S S F X T G P O J X Q I Y S R S Q F W Q D J Q N Q C G D Q R N L L U I E A Z V M W N U U F N N X V L O Y V G M L I U Q A N D L Y A V F A U A O S N L N V A C S V P I U M O I A W C Q X S W K Q W G X Y A Z N T N A I K A M E Y B N U Q B C Q A G G X A C H R Y N Q X Q Q M L F O T P Q H V O K I I A M M Q M V X J V B S O A I F Z Y X N J C B E R R N M I X X S Y J H O V E N G B P Y Q R I X Q G W D R Y G X R X K F H I C A I N H W I L K Q M B P E S Z D I G Z N Z X T Z Q S J W A T Y C B M J A W W M N I N E P F D U P L U C L T X M K P V G R R G T U S E U R A G E L T K C A P W P B Q R O M Q A W I X E Z Q K V L F B H W C O C P J M R M B P B E G V S U L U Q T U U V K E S V J T D H V T J M E X F Q B V U F D P A X C W N W Q J T B P L Y Z E D I C W S O D P W T Q R P Y U E A R H W G F N P A Q E L O F R S O T Q I K T X I P Q Z E Q V L Q M U O U B B J B R P M I X F C L B S T N O S V D K U J C P W S D Q H X R K I U E Z I O W O Q J P I E C W X X B J T N M K J G N C P M V A U Q G T A U S O K B F U G J T F I U Q B J C L V L A Z A M U C I M I C N E W D O X J L F U E M D A D G K H U F S U E V J A X R N I V C O R H F R Q Q W N U J Q U O Y E V S L Q P R L Y S K R H U N L J G S O X L E U Y Y F Q U T O Z Q H M G Y E T Y Y E P F A E S J L K Z I V D E V D L L Y G A Z X J N D J R X H R D Y Y D D Q N Q D O A Y S H W X S H X Z J Y W U M B F F A M X D N X J Q O Y I R M I R E R N E K X D L I C J F Q K K V N X U Q M S Z C I X M Z K W S Q O I W Y F A L P E U U U G F R T E O M Q I N U Q N I R X E L P S T O S A O D Q S Z K O G R F B X T N P D B L T Q T M P Y Y E Q T U J U I O K C O W S W Q Y X N T N D X Q Q S G K H V I H B A A W J U G A G L O D D K T D J I Z Y N Y O E S U O Z R Y I T Y J R I F X I M K Y R O K K T V U S U I Q I O J F C K Y A T R Y E K I J K S V U S O K C Y E A V W U F P C T A J X K I X D B X J M I T W C Q Q X F B B F H B A D V F U A A U J X F R W K V U U H E P D I F V F K Y H S F I U L E A F G A A P A H J W T E S P L W E Q F M N M Y M T Q R E L E I N K O P M F P V O M Q U E G H D M X K Y N W X Z Q N S W A X G N J W D X B U U S G K M N Q W Q D V A D I W A H O Q A K Q Z Q G K M L H Q F D I M N W Z G S P L O R O W N P G E H I O X H H F R V Q A L W D T K S S L Y K A J A T A X G P D M Y L D X U K D N F T P R R U M B M E M L R O W R H W O Q N T C L G H L C R O R Z H G S B A E C P L P C C D Y V N X M D M F H A O P L Q I Z K H I Q B J T I M I T D K X I K S X J E C W M K W A B H S L I E V Q V W C Q E Q A Z T K Y D W R B G X D C J P A L S H G E P K Z H H V L X C B X D W J C C G T D O Q I S C Y S P Q Z V U Q I V Z P T L P V O O Y N Y A P G V S W O A O S A G H R F F N X N J Y E E L T Z A I Z N I C C O Z W K N W Y H Z G P Q L W F K J Q I P U U J V W T X L B Z N R Y J D O H B V G H M Y U I G G T Y Q J T M U Q I N N T Q M I H N T K D D N A L W N M S X S A T Q Q E L D A C N N P J F E R M R N Y U Q N W B J J P D J H D E A V K N Y K P O X H X C L Q Q E D Q A V D W Z O I O R R W W X Y R H L S R D G Q K D U V T M Z Z C Z U F V T V F I O Y G K V E D E R V V U D N E G H B C T C B X D X E Z R Z G B P F H Z A N F F E C C B G Q F M Z J Q T L R S P P X Q I Y W J O B S P E F U J L X N M D D U R D D I Y O B Q F S P V C O U L C V D R Z K M K W L Y I Q D C H G H R G Y T Z D N O B Q C V D E Q J Y S T M E P X C A N I E W Q M O X K J W P Y M Q O R L U X E D V Y W H C O G H O T P U S F G I E S T C K R P A I G O C F U F B U B I Y R R F F M W A E E I M I D F N N Z C P H K F L P B Q S V T D W L U D S G A U N G F Z O I H B X I F O P R W C J Z S D X N G T A C W T J Y P W E U X V E G Y B O G S F X Q H I P B O M P U F P X C K I C A G H U F C Z M A C C G W I G M R Q C T E Q K B W B A A M I C O Q L I V N J J O O M W K U C Z N V D G Z T Q A R S A R G K W U A H E Y V O H L E T J Q P O P D J S L K O E L F Y N Z E A V A A C E A Z U I M Y D Y P V M G Y X B L H P P U U N K T T K Q T M V A N U U V J V A H M V V U V S V H Z K Y W H M G C H Q V D C Q D P M Z M X W N E I K Z F G T A N T N L P W Z V A H N V K P L P F A O T X N G E X R F C Z Z D M U S Z L O B I O K V K W K X L R X B L V O T Z O M E Q L F T X Z L Z K B C S Q M N C I A Z V R Z Y E U P Y V D K B T W H P V G C W T E Y L W K B Y U B X R U W S Z S H X P M J R H F A W D I B Z B F Y P D K S B H T A A P Z S O R B N J P Z C X E C V J M W J Q D J H G V Z J C U K F J J Z A C B P N S O P P V T L E I J P Y N Y F V U E F Y Y R D J A D J E G B S Y P J O M F B R N K I L Z H S V B W C Z W T D F V I R B O S V M J F C Y M D R Z Q Z K P G E M J A O J Y J O F E Y W I M Q D A C K D A W I T X Y S J Q Z N C I P T T N C J T J H R T V K W W O J B Q H J J F K B O A C C E N R X I H C S A N B T G X D C T T N U J V F S C R W Q T Y U Y N M X W V B Q X O R Q U O W Z H P M D Z J L R L C N C Y O Y W B M V Z H X P E N H V I V T H F I V K H F X B Q A Q U Y E T W I F T H N S X R G G O Q B H X I Q S V Z Z S C Q U T M S Z F Q J N M T A E Q T M Y K C B R Z K J U H L T Z N L U I Y O K F H V S T O U Z G Q M E A O G R Q S D M Z O H Y D T U O T J Y Y S T T L K N M Q D Y V D P B X F T A T U Q A S T V P H O A H P S D I F N X R F B Q A G H D F O Y H H S X H N T D C C T C M I U P Q Z E Q S J R K M Z R P H F O O O I O Y V J D X N W B Z H V Q Z W U P R G I B S I T J P A Z F R I T P F E S F S Q G R X E K X C G M T M V V G F Q Q W S P D J X Z A D D U K V L Q P K U Z J Z H W S U T P C A F S Y A I B J H A M M E G W B T P Q E L R N K B L D X G U Z G C S E C C I N L I Z Y O G W Q Z L I F X C T H D G M A N J Z T L T A N V I A J S C H H K D X L R F R O H M X M S M M H V O D I H D V F N X O F B X M L C L X V R O J A C J P W X B E U R H C B M Z G Z W W G Y V T L Z E I V X Y G A A P P Z O S D I K K M L W L T X I R D I O Y T N F E I E E P E H G V G V Q J F A V S N T F I Q N B V X P U T C Z Z N F D C M K K H S H X D N Z Y H O R M W J C X F B O B W R C V E H B I T N S D G A C J P E I Y S B M R N O Q S S F V O Y X K E G L M A Y G F G I H Q Z N A Z G D M Z Q C P I U U D J U C V Y J I M L I V Q P D Z H F N H E V K S U D V J L R G R C A V X Z E H L R Q G J H M J Q T Y Z Z T J S N O P Y A G E T J F Q I E X Q R O I A Y R O J H J H G I A R C P G R N I Y S D H Z T P F Q H W H P Y F I O O P X X V G X N I O V A B D A T G J S Z A Z S I W Z Z W E I L U X I R V Q Q K Z E F B H I D D Q M X R M X J W T I W R O G C K D L D A D T K C Z P F H Z I K P U J H J G Q F B B B T R H V C N I F N M B A Q A P Y J R G V G D F P M L I R N J V G A E D E T O K J C L J S N A Q Z R Z U A C B P Q N X J C I E K L L N P E D B P F O Y Y C Z Q D S P X S T B K J Q J T S U Z C F K R W R X Y G C M F A Q G T T Y I T T E U D N K M G E G G I N S B K J Y K S B Y X D R F W K F H F Y L Z B A L Q J P Y R X M J Z Y V X K N Y I M E Z R A M Y J R X W T A X E S G U R X T F I U D F S P S S X G W Z Z Z L Y K E
/Classwork/CS3114/Project 3/Old_Test_Files/Outfileb.dat
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/Old_Test_Files/Outfileb.dat
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/Old_Test_Files/genfile.cpp
0,0 → 1,86
// This program generates test files for external sorting algorithms.
// Output files can be of any multiple of the 4096 byte block size.
// The data records are logically a two byte (short int) key value followed
// by a two byte (short int) data value.
// The values output by this program can either be "binary" or "ascii".
// "Binary" files have key and data values each in the range 1 to 30,000.
// "Ascii" files have their data and key values selected so that they are
// easy to read and test. The data value prints in ascii as two spaces.
// The key value prints in ascii as a space and then a capital letter (A-Z).
// This makes it simple to tell if the sorting algorithm is working.
 
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
#include <cstring>
 
using std::cout;
using std::endl;
using std::string;
using std::ostream;
using std::fstream;
using std::ios;
 
// Random number generator functions
 
inline void Randomize() // Seed the generator
{ srand(1); }
 
// Return a random value in range 0 to n-1
inline int Random(int n)
{ return rand() % (n); }
 
// A block is 4096 bytes, or 1024 logical records
#define NumRec 1024
 
typedef int E;
 
int main(int argc, char** argv) {
int filesize;
E Array[NumRec];
int i, j;
fstream myfile;
bool Ascii; // True if ASCII option, false if binary option.
 
if (argc < 4) {
cout << "Usage: genfile <option> <filename> <size>\n";
cout << "Size is measured in blocks of 4096 bytes.\n";
cout << "Options must be '-a' for ASCII, or '-b' for binary.\n";
cout << "ASCII files have a data value of 8224 (prints as 2 spaces)\n";
cout << "and a key value between 8257 and 8282 (prints as a space\n";
cout << "and a letter).\n";
cout << "Binary files have key and data values between 1 and 30000\n";
exit(-1);
}
 
if (!strcmp(argv[1], "-a"))
Ascii = true;
else if (!strcmp(argv[1], "-b"))
Ascii = false;
else {
cout << "Illegal option '" << argv[1] << "'\n";
cout << "Usage: genfile <option> <filename> <size>\n";
exit(-1);
}
 
myfile.open(argv[2], ios::out | ios::binary);
if (!myfile) {
cout << "Unable to open file :" << argv[2] << ":\n";
exit(-1);
}
filesize = atoi(argv[3]);
 
Randomize();
for (i=0; i<filesize; i++) { // For each block
for (j=0; j<NumRec; j++) // For each record
if (Ascii)
// A record has a 2-byte key that prints as <space><letter>
// and a 2-byte value that prints as <space><space>
Array[j] = (8224 << 16) + Random(26) + 0x2041;
else // Keys and values in range 1 - 30,000.
Array[j] = ((Random(29999) + 1) << 16) + ((Random(29999) + 1));
myfile.write((char*)Array, sizeof(E) * NumRec);
}
return 0;
}
/Classwork/CS3114/Project 3/P3.pdf
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/P3.pdf
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/Schedule.xls
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/Schedule.xls
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/heapsort.class
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/CS3114/Project 3/heapsort.class
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/CS3114/Project 3/heapsort.java
0,0 → 1,121
/*
* CS 3114 Project 3
* Author: Kevin Lee
* Compiler: Eclipse 3.7.0
* Operating System: Windows 7 x64
* Date Completed: 11/1/2011
*
* The following program sorts a specified file on disk using
* heapsort and a buffer pool. The file size must be a multiple
* of 4096 and comprised of key-value records of 2 bytes each
* (4 bytes total per record). The buffer pool uses the least
* recently used scheme and the number of 4096 byte blocks the
* buffer stores is specified in the command line for this
* program. A statistics file is also outputted to show the
* sorted file, cache hits/misses, and disk reads/writes.
*
* On my honor:
*
* - I have not used source code obtained from another student,
* or any other unauthorized source, either modified or
* unmodified.
*
* - All source code and documentation used in my program is
* either my original work, or was derived by me from the
* source code published in the textbook for this course.
*
* - I have not discussed coding details about this project with
* anyone other than my partner (in the case of a joint
* submission), instructor, ACM/UPE tutors or the TAs assigned
* to this course. I understand that I may discuss the concepts
* of this program with other students, and that another student
* may help me debug my program so long as neither of us writes
* anything during the discussion or modifies any computer file
* during the discussion. I have violated neither the spirit nor
* letter of this restriction.
*/
 
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
 
public class heapsort {
 
public static void main(String[] args) {
// Check if correct arguments are supplied
if (args.length != 3) {
System.out.println("Usage: heapsort <data-file-name> <numb-buffers> <stat-file-name>");
return;
}
// Save file paths and buffer size
String dataFile = args[0];
String statFile = args[2];
int buffSize = Integer.parseInt(args[1]);
long fileSize = 0;
RandomAccessFile file = null;
// Check if specified buffer size is within acceptable range
if (buffSize < 1 || buffSize > 20) {
System.out.println("Specified buffer size must be between 1 and 20");
return;
}
// Get the length of the file to sort
try {
file = new RandomAccessFile(dataFile, "r");
fileSize = file.length();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
// Check to make sure file is a multiple of 4096
if (fileSize % 4 != 0) {
System.out.println("Input file size must be a multiple of 4096");
return;
}
// Create a new buffer and heap sort class
LRUBuffer buff = new LRUBuffer(dataFile, statFile, buffSize, 4096, 4);
MaxHeap heap = new MaxHeap(buff, fileSize/4);
// Start sort
long time1 = System.currentTimeMillis();
heap.buildheap();
for (int i = 0; i < fileSize/4; i++) {
heap.removemax();
}
buff.flushBuffer();
long time2 = System.currentTimeMillis();
// Write sort statistics
buff.writeStats(time2 - time1);
// Print the first record from each block in the sorted file
try {
int column = 1;
byte[] data = new byte[4];
ByteBuffer bbuff;
short key, value;
for (long i = 0; i < fileSize; i+=4096) {
file.seek(i);
file.read(data);
bbuff = ByteBuffer.wrap(data);
key = bbuff.getShort();
value = bbuff.getShort();
System.out.printf("%05d %05d ", key, value);
if (column % 8 == 0) {
System.out.println();
}
column++;
}
file.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}