TweetFollow Us on Twitter

July 02 Challenge

Volume Number: 18 (2002)
Issue Number: 07
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

One Time Pad

A one-time pad, used properly, provides a simple and unbreakable method of encryption. The “pad” is a random block of data equal in length to the message to be encoded. Two copies of the pad are needed, one for the message sender and one for the message receiver. The message to be encrypted is combined with the data in the pad by, for example, an exclusive OR; transmitted to the recipient, and decoded by the inverse operation. To be unbreakable, the pad must consist of truly random data, and it must be used only once.

Of course, you still need to securely exchange a one-time pad for each message to be encrypted. Let’s imagine that this is too much trouble, so what we are going to do instead is to use some common text as the basis for our one-time pad. We’ll select the “random” block as an offset from the first character in that text. And we’ll reuse our “one time” over and over again for different messages, with different offsets. Since the text isn’t random, and the one-time pad is used multiple times, we may have compromised security somewhat. This is a Good Thing, because your Challenge is to crack a sequence of messages encrypted with this scheme.

The prototype for the code you should write is:

void InitOneTimePad(
   const char *oneTimePad,
   /* NULL terminated text to be used for the one-time pad */
   /* You should ignore (skip) any characters not in the range 0x20-0x7E, inclusive */
   const char *dictionary[],
   /* list of NULL-terminated words in the vocabulary, sorted in ASCII order */
   long numDictionaryWords
);

char *DecryptMessage(
   /* return decrypted message */
   const char *encryptedMessage,
   /* NULL terminated text to decode */
   /* Guaranteed to contain only characters in the range 0x20-0x7E, inclusive */
   long *offset
   /* offset into the oneTimePad that you determine to be the basis for encryption */
);

void TermOneTimePad(void);

Your InitOneTimePad routine will be called each time our Intelligence Service captures a new one-time pad being used by our adversary. You will also be given a sorted dictionary of words in the vocabulary of our adversary. You can allocate memory and do whatever analysis might be appropriate.

For each intercepted message, your DecryptMessage routine will be called with the encrypted text. Fortunately, we know that our encrypting adversary uses the oneTimePad in a consistent manner. S/he uses a section of the pad starting at an offset known to the sender and receiver, but unknown to us. The section of the pad used is as long as the encrypted message, ignoring any characters in the pad (beyond the offset) outside the range of printable ASCII characters (0x20-0x7E). The nth character x of the clear text is encrypted as x+y-0x20, modulo the legal range of the character set, where y is the nth legal character of the oneTimePad beyond the offset value. So, if the oneTimePad [offset] starts with “When in the Course of human events”, and your clear text is “The British are coming.”, the encrypted text would be “,QKnB\Xt^\N%b[rWUmYUgv”, where denotes a nonprintable (and ignored) carriage return and denotes a space character that you might not otherwise notice. Note that nonprintable characters are counted in determining the starting position (offset) within the pad.

You should determine the section of the one-time pad that was used for encryption, decrypt the message, store the oneTimePad offset used for this message, and return a NULL-terminated string containing the clear text.

Your TermOneTimePad routine should return any dynamically allocated memory.

The winner of this Challenge will be the entry that correctly solves all test cases while incuring the lowest cost. Solutions will incur a cost of 10 points per millisecond of execution time, including the time incurred for initialization, decryption, and termination. You can earn a bonus of up to 25% reduction of incurred cost based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Winner of the February, 2002 Challenge

In February, we asked contestants to defragment a simulated disk drive. Scoring was based on making the fewest number of block moves, regardless of block size. We also awarded a bonus of 25% for incorporating optional features, like an untimed display of defragmentation progress, and another 25% bonus based on elegance of the solution. Congratulations to Jonny Taylor for taking first place in the Disk Defragmentation Challenge.

Six people entered solutions for this Challenge and five of those solved the problem correctly. (The sixth violated the constraint against overlapping the source and destination blocks.) The best scoring solution, by Jan Schotsman, was submitted after the deadline and was therefore not eligible to win. Three entries, including both Jonny’s and the second-place entry from Ernst Munter, provided options to display the evolving solution or to replay the solution. Jonny also provided menu options to control the speed of the display. Jonny’s entry required approximately 25% fewer moves to defragment the disks, although it required nearly three times as much computation time to do so.

Several of the entries chose to defragment the simulated files in ways that also consolidated all free space into one block. This behavior was not required, and Jonny chose not to do that. Instead, he chose to leave large fragments in place where possible, reasoning that these are less likely to be relocated on densely occupied disks without being split up into multiple pieces. Jonny first employs an “intelligent move” algorithm, described in the ConsiderMovingFragment routine, that selects and moves file fragments which, when moved, would allow other fragments to be moved to their final destination. For fragments that remain after applying the intelligent algorithm, the GuaranteedMoveFragment routine moves all remaining file fragments to their final destination.

I evaluated solutions using five test cases, one small and relatively simple, and the others simulating densely populated disks with varying levels of fragmentation. The subjective evaluation of features was based on whether a display option was present, and on other menu options provided to control the solution and the display. The “elegance” criterion was based on code commentary, coding style, cleverness of the algorithm, and on the conciseness of the code. Johnny’s winning entry was downrated a little because of the complexity of the code, but earned points for being well commented. As it turns out, entries were ranked in the same order both with and without considering the subjective criteria.

The table below lists, for each of the solutions submitted, the total number of disk block moves used to defragment the desks, the total execution time in microseconds, the raw score based on moves and execution time, the subjective bonuses based on elegance and features, and the total score after taking the bonuses into consideration. It also lists the programming language used for each entry and the operating system used for the entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name Moves Time Defrag Elegance Features Total Lang OS
(usecs) Score (0-1.0) (0-1.0) Score
Jonny Taylor (37) 5951 108958 786190 0.65 1.00 461886 C++ Classic/9
Ernst Munter (275) 7641 38604 836448 1.00 0.75 470502 C++ Carbon/X
Ludovic Nicolle 8586 279473 1559817 0.75 0.00 1267352 C/ObjC Cocoa/X
Allen Stenger (49) 7733 570203 2290366 1.00 0.00 1717775 C++ Carbon/X
Jan Schotsman (16) (late) 5224 166567 738581 0.75 0.90 433916 C Classic/9
T.S. 4939 426949 1093346 0.65 0.00 915677 C++ Terminal/X

Top Contestants . . .

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 265 9 872
2. Taylor, Jonathan 57 2 83
3. Stenger, Allen 53 1 118
4. Saxton, Tom 52 1 210
5. Rieken, Willeke 46 2 134
6. Wihlborg, Claes 40 2 49
8. Gregg, Xan 20 1 140
9. Mallett, Jeff 20 1 114
10. Cooper, Tony 20 1 20
11. Truskier, Peter 20 1 20

. . .and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

Rank Name Points Total
(24 mo) Points
7. Sadetsky, Gregory 22 24
12. Schotsman, Jan 16 16
13. Shearer, Rob 15 62
14. Hart, Alan 14 39
15. Boring, Randy 11 144
16. Nepsund, Ronald 10 57
17. Day, Mark 10 30
18. Desch, Noah 10 10
19. Flowers, Sue 10 10
20. Nicolle, Ludovic 7 62
21. Leshner, Will 7 7
22. Miller, Mike 7 7

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Jonny’s winning Disk Defragmentation solution:

PROGRAMMER’s Defrag.cp
Copyright © 2002
Jonny Taylor

// #include files omitted because of length; see online archive

/*   The algorithm works as follows:
Load the information from the input file about where on the disk the fragments
            of each file are to begin with
      2.   Choose where on disk we want each file to end up
      3.   “Intelligent” algorithm: where possible, move fragments to their final positions
            with minimal unnecessary moves
      4.   “Guaranteed” algorithm: move any remaining fragments to their final positions 
            whatever additional moves this takes
   
   Three data structures are used by these algorithms.
      FreeRange represents a single contiguous range of disk blocks that are not
      currently occupied by any file fragment. Every FreeRange is as large as possible          
      –  i.e. it is not possible to have
         one FreeRange for blocks 4-9 and another for 10-14 in existance at the same 
         time
      Fragment represents a single contiguous range of disk blocks belonging to the 
         same file
      FileLayout represents a single file, and has a linked list of all the fragments that 
         make it up
   
   In addition, there are four search trees that are maintained. These allow Fragments 
   to be searched by current position and by the final position that they will end up in, 
   and allow  FreeRanges to be searched by position and by length. The tree code is 
   explained and implemented in Trees.cp, but all that really matters is that insertion, 
   deletion and searching can be done in log(N) time.
   
   There are quite a few nasty cases to the algorithms I have used, which need special 
   treatment. This is particularly true for the “guaranteed” algorithm because it must be 
   able to handle anything at all.
   However for the most part the special cases are handled within a single function. 
   Functions that perform tasks such as “move a block out of the way” will do what 
   they are defined to do (though they may be allowed to fail), and will handle any 
   special cases themselves.
   
   The solution is fairly quick on reasonably complex test cases (such as test case 2 in 
   the sample code). It slows down roughly linearly as the number of files and 
   fragments on the disk increases. This results in unacceptably long running times for 
   very nasty test cases with big disks full of tiny files. However I suspect that any 
   solution would do the same.
*/
   
struct FileLayout;
struct Fragment;
struct FreeRange;

typedef struct FreeRange
{
   long   firstBlock;
   long   lastBlock;
   Node   *positionTreeNode;
   Node   *lengthTreeNode;
// method declarations omitted, see online archive
} FreeRange;

typedef struct FileLayout
{
   Fragment   *firstFragment;
   Boolean      placed;
   long      fileLength;
// method declarations omitted, see online archive
} FileLayout;

typedef struct Fragment
{
   long      startBlock;
   long      finalStartBlock;
   long      numBlocks;
   FileLayout   *owningFile;
   Boolean      inFinalPosition;
   Node      *currentStartTreeNode;
   Node      *finalStartTreeNode;
   long      firstFileBlock;
   
   Boolean      blockedBySelf;
   long      fragmentsBlockingThis;
   
   long      processedInThisLoop;
   long      score;
   Fragment   *next;
   Fragment   *nextInMoveList, *prevInMoveList;
   Fragment   *nextInFinalStartList, *prevInFinalStartList;
// method declarations omitted, see online archive
} Fragment;

#define kNotProcessed         -1
#define kMaxArraySize         32768
#define ABS(VAL)            ( (VAL) < 0 ? -(VAL) : (VAL) )
#define MIN(A, B)            ( (A) < (B) ? (A) : (B) )

FileLayout   **theFiles, **unplacedFilesSortedByLength;
Fragment   **sortedFragmentList;   
   /* Sorted array of fragment pointers. 
      Sort key varies depending on which bit of code we are in   */
Fragment   *firstFinalStart;      
   /* Linked list of fragments, ordered by final start   */
Fragment   *prevInList;
   /* Only used when setting up firstFinalStart   */

extern DisplayType      displayProgress;
extern AnimationType   animationType;

/*   Roots for the search trees   */
Node   *fragmentCurrentStartRoot,*fragmentFinalStartRoot;
Node   *freeRangeLengthRoot,*freeRangePositionRoot;
/*   General global variables   */
long      totalFragments, totalBlocks, totalFiles, 
      fragmentsPositioned;
long      uniqueSearchIndex, firstFreeBlock;
/*   Heads of linked lists of fragments that are free to move to their final positions   */
Fragment   *firstFragmentToMove, *firstOverlappingFragmentToMove;

// function prototypes omitted, see online archive

Main Defragmentation Code
// DoTests deleted for length, see online archive

void Defragment(void)
{
// test case loop omitted for length, see online archive
      
      totalFragments = 0;
      totalBlocks = 0;
      totalFiles = 0;
      fragmentsPositioned = 0;
      fragmentCurrentStartRoot = NULL_NODE;
      fragmentFinalStartRoot = NULL_NODE;
      freeRangeLengthRoot = NULL_NODE;
      freeRangePositionRoot = NULL_NODE;

// input logic omitted for length, see online archive

      ChooseFilePositions();

      /*   Rebuild the free range list to represent the current file positions
         (instead of their final positions)   */
      firstFreeBlock = 0;
      InorderTreeWalk(fragmentCurrentStartRoot, BuildFreeRangeTree);

      if (totalBlocks - 1 >= firstFreeBlock)
         new FreeRange(firstFreeBlock, totalBlocks - 1);

      /*   Move the fragments to their final positions      */
      RearrangeFragments();

      /* Release memory   */
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
         delete theFiles[fileNum];
      KillAllFreeRanges(freeRangeLengthRoot);
// test case completion logic omitted for length, see online archive
}

void RearrangeFragments(void)
{   
   Fragment   *fragPtr;

   SetDescriptionString(“Moving fragments (intelligent algorithm)”);

   for (fragPtr = firstFinalStart; fragPtr != NULL; 
            fragPtr = fragPtr->nextInFinalStartList)
   {
      if (!fragPtr->inFinalPosition)
      {
         /*   Check which fragments’ FINAL POSITION is blocked solely by the
            CURRENT position of this one      */
         fragPtr->ForEveryFragmentBlockedByThisOne(
               MarkFragmentAsBlockedBy);
      }
   }
   
   firstFragmentToMove = NULL;
   firstOverlappingFragmentToMove = NULL;
   
   /* First do a check for fragments that can move immediately to their destination 
      square */
   for (fragPtr = firstFinalStart; fragPtr != NULL; fragPtr = 
            fragPtr->nextInFinalStartList)
   {
      if ((!fragPtr->inFinalPosition) &&
         (fragPtr->fragmentsBlockingThis == 0))
      {
         fragPtr->FreeToMoveToFinalPosition();
      }
   }
   MoveFragmentsToDestinationSquares();
   
   uniqueSearchIndex = 0;
   for (fragPtr = firstFinalStart; fragPtr != NULL; 
         fragPtr = fragPtr->nextInFinalStartList)
      ConsiderMovingFragment(fragPtr);
   
   /*   There will probably be fragments left to rearrange (at least if the disk is densely 
      populated). Switch to a simple, but failsafe, algorithm to place these remaining 
      fragments      */
   SetDescriptionString(
         “Moving fragments (guaranteed algorithm)”);
   GuaranteedRearrange();
}

void BuildFreeRangeTree(void *keyPtr)
void KillAllFreeRanges(Node *x)
// these routines omitted for length, see online archive

Choosing File Positions
/*   Before I actually move any fragments, I decide what final position I want each file 
   to end up in. We could just aim to position the first file at the start of the disk, the 
   next one immediately after that, and so on. However in this problem this is not a 
   requirement. Instead we can choose to place the files anywhere we want, as long as 
   each individual file is contiguous. It is advantageous to choose a final position for 
   as many files as possible, such that one of its fragments is already in its final 
   position, and doesn’t have to be moved at all.
   
   I can’t see an easy way of determining the optimum file layout. Instead I employ a 
   greedy algorithm, picking the fragment that looks best as the first “anchor” 
   fragment, and so on. I experimented with several methods of scoring each fragment 
   as a potential anchor, taking into account factors such as:
      - Whether any fragments of the file overlap their final destination (a bad thing as 
         they then can’t be moved in a single step)
      - Whether any other fragments from the same file are also in their final positions 
         (a good thing)
      - Some attempt to determine how much selecting this file would prevent us from 
         selecting several other files
   In the end, I didn’t bother with this. Densely-populated disks are the ones that take 
   longest to solve, and the most moves to rearrange. In those cases the limiting factor 
   is the size of the fragments; a large fragment is likely to be impossible to move 
   around intact, and will have to be split up to move it. I therefore decided to 
   prioritise large fragments when selecting anchors.
   
   Incidentally, a final factor, that I have not tried to take into account at all, is the size 
   of the free spaces that are left in the final layout. I suspect it would be better to 
   select a final layout with fewer, larger spaces since this makes it easier to rearrang 
   the disk.
   
   Once I have selected as many anchor fragments as I can, there will probably be files 
   left unplaced. I don’t try and do anything clever with these. I just put them at the 
   start of the largest empty space that is available. Unfortunately, there is a problem. 
   Choosing the anchor fragments means the remaining free space may be split into a 
   number of ranges. It may be impossible to fit the remaining files into the spaces 
   (remembering the files must be contiguous). Even if it is possible, it may not be 
   possible to quickly find a valid layout. There is no obvious way of seeing when we 
   have chosen too many anchor fragments. Instead, I use a binary search method. I try 
   placing as many anchor fragments as I can, and see if I can position the remaining 
   files. If I can’t, I try with half as many anchor fragments, and continue refining the 
   value until I have a reasonable one.   */

void ChooseFilePositions(void)
{
   long      fileNum;
   Fragment   *theFragment;
   
   SetDescriptionString(“Choosing file positions”);

   /*   Sort the fragments by their length   */
   qsort(sortedFragmentList, totalFragments, sizeof(Fragment*), 
            Fragment::QSCompareByLength);

   /*   Try .........*/
   if (ArrangeFilesWithAnchorLimit(totalFiles) == false)
   {
      long   minimumAnchorCount = 0, maximumAnchorCount = 
         totalFiles + 1;
      long   middle;

      UnplaceAll();
      for (long iter = 0; iter < 5; iter++)
      {
         middle = (minimumAnchorCount + maximumAnchorCount) / 2;
         
         if (ArrangeFilesWithAnchorLimit(middle) == true)
            minimumAnchorCount = middle;
         else
            maximumAnchorCount = middle;
         
         if (maximumAnchorCount - minimumAnchorCount == 1)
            break;
         
         UnplaceAll();
      }
      if (middle != minimumAnchorCount)
      {
         UnplaceAll();
         ArrangeFilesWithAnchorLimit(minimumAnchorCount);
      }
   }   
   
   /*   Now we have settled on an arrangement, build the final start tree and linked list.
      Because this tree remains static, we don’t actually need to do all the red-black 
      insertions. We could just determine the sort order and then build a balanced 
      binary search tree by hand. However, doing RBInsert for every fragment is faster 
      than a quicksort of every fragment. However all we really need to do is a 
      quicksort of every file. If the number of files is less than half the number of 
      fragments, it turns out it is worth building the tree by hand. This will also lead to 
      a slightly better-balanced tree, which will speed up tree searches a little.
      
      We also take the opportunity to see which fragments are already in their final 
      position. If they are we mark them as such; if they aren’t then we add them to the 
      list of fragments (sortedFragmentList), which is ordered by final start. This linked 
      list will remain static until we come to the “guaranteed algorithm”, at which point 
      it may grow as fragments are split   */

   firstFinalStart = NULL;
   prevInList = NULL;
   if (totalFragments / totalFiles >= 2)
   {
      /*   Sort the files by final position and thereby sort the fragments   */
      qsort(theFiles, totalFiles, sizeof(FileLayout*), 
            FileLayout::QSCompareByFinalStart);
      long fragNum = 0;
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
      {
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
         {
            sortedFragmentList[fragNum++] = theFragment;

            theFragment->CheckIfInFinalPosition();
         }
      }
      
      /*   Build the tree, given the sorted fragment list   */
      fragmentFinalStartRoot = BuildBalancedTree(sortedFragmentList,
             0, totalFragments - 1, NULL_NODE);
   }
   else
   {
      for (fileNum = 0; fileNum < totalFiles; fileNum++)
      {
         for (theFragment = theFiles[fileNum]->firstFragment;
             theFragment != NULL;
             theFragment = theFragment->next)
         {
            ASSERT(theFragment->finalStartTreeNode == NULL);

            theFragment->CheckIfInFinalPosition();

            theFragment->finalStartTreeNode = new Node;
            theFragment->finalStartTreeNode->data = theFragment;
            theFragment->finalStartTreeNode->keyLong = 
               theFragment->finalStartBlock;
            theFragment->finalStartTreeNode->keysNodePtr = 
               &theFragment->finalStartTreeNode;
            RBInsert(&fragmentFinalStartRoot, 
               theFragment->finalStartTreeNode);
         }
      }
   }
}

Node *BuildBalancedTree(Fragment ** fragList, long first, 
            long last, Node *parent)
// this routine omitted for length, see online archive

Boolean ArrangeFilesWithAnchorLimit(long maxAnchors)
{
   long   fileNum, frag;
   long   numUnplacedFiles = 0;
   /*   Attempt to come up with a file arrangement that uses up to maxAnchors anchor 
      fragments   */

   /*   We start with no file positions chosen, and the whole disk available   */
   new FreeRange(0, totalBlocks - 1);
   
   /*   We should be able to leave some fragments where they are, and build up around 
      them the file that they are part of. I choose the largest fragments as a priority, 
      since they will be hardest to move around when we are rearranging the disk.
      This is not always ideal. For example, picking the largest fragment might prevent 
      us from picking a large number of slightly smaller ones. However it is the only 
      quick and simple way that I could find   */
   long numPlaced = 0;
   for (frag = totalFragments - 1; 
      (frag >= 0) && (numPlaced < maxAnchors); frag—)
   {
      Fragment   *fragPtr = sortedFragmentList[frag];
                        /* sortedFragmentList is currently sorted by length   */
      FileLayout   *owningFile = fragPtr->owningFile;
               
      if (!owningFile->placed)
      {
         /* This file has not been assigned a position yet Check if any other files we 
            have already positioned are blocking this position   */
         FreeRange *rangeAtStart = 
            (FreeRange*)DATA(TreeSearch(freeRangePositionRoot, 
                  &fragPtr->firstFileBlock,
                  FreeRange::FindRangeContainingBlock));
         if (rangeAtStart->lastBlock >= 
            fragPtr->firstFileBlock + owningFile->fileLength - 1)
         {
            /*   There is no file blocking this position   */
            owningFile->placed = true;
            owningFile->SetFinalPosition(rangeAtStart, 
                  fragPtr->firstFileBlock);
            numPlaced++;
         }
      }
   }
   
   /*   We now probably have some files left over, to try and fit into the gaps that are 
      left. My heuristic here is to start with the largest file, and place it in the largest 
      gap available. This is far from ideal, but I suspect that finding the optimum 
      solution is an NP-complete problem (similar to sack-filling problems), so I’m not 
      too bothered!   */

   /*   Sort the unplaced files in order of total length   */
   for (fileNum = 0; fileNum < totalFiles; fileNum++)
   {
      if (!theFiles[fileNum]->placed)
      {
         unplacedFilesSortedByLength[numUnplacedFiles] = 
            theFiles[fileNum];
         numUnplacedFiles++;
      }
   }
   qsort(unplacedFilesSortedByLength, numUnplacedFiles, 
         sizeof(FileLayout*), FileLayout::QSCompareByLength);
   
   for (fileNum = numUnplacedFiles - 1; fileNum >= 0; fileNum—)
   {
      FreeRange *chosenPosition = 
         (FreeRange*)DATA(TreeMaximum(freeRangeLengthRoot));
      if (chosenPosition->lastBlock - chosenPosition->firstBlock + 1 
                  < unplacedFilesSortedByLength[fileNum]->fileLength)
         chosenPosition = NULL;
      
      if (chosenPosition != NULL)
      {
         /*   Position the file at the start of the free range we have selected   */
         unplacedFilesSortedByLength[
               fileNum]->SetFinalPosition(chosenPosition, 
               chosenPosition->firstBlock);
      }
      else
      {
         /*   Failed to position the file. Break out immediately   */
         break;
      }
   }

   /*   Delete all the free ranges and their search trees. Either we are going to restart the 
      algorithm, or we are going to move on to the next phase, for which we need the 
      INITIAL free ranges, rather than the FINAL ones   */
   KillAllFreeRanges(freeRangeLengthRoot);
   freeRangeLengthRoot = NULL_NODE;
   freeRangePositionRoot = NULL_NODE;      

   if (fileNum >= 0)
   {
      /*   We didn’t manage to position all the files   */
      return(false);
   }
   return(true);
}

void FileLayout::SetFinalPosition(FreeRange *rangeToPlaceIn, 
            long finalStartBlock)
{
   for (Fragment *theFragment = firstFragment;
       theFragment != NULL;
       theFragment = theFragment->next)
   {
      theFragment->finalStartBlock = finalStartBlock;
      finalStartBlock += theFragment->numBlocks;
   }

   rangeToPlaceIn->RangeNotFree(firstFragment->finalStartBlock,
          fileLength);
}

void Fragment::CheckIfInFinalPosition(void)
void UnplaceAll(void)
// these routines omitted for length, see online archive

“Guaranteed” Algorithm
/*   We work through the fragments that have not yet been moved to their final 
   positions. For each one,clear any blocking fragments out of the way and move it to 
   where they were.
   This algorithm must be able to cope with all situations. This means that special 
   handling is necessary when temporary storage elsewhere on the disk is limited, and 
   when the fragment partially overlaps its final position   */

// this section deleted for length, see online archive

“Intelligent” Algorithm
/*   The idea is to identify fragments that, if moved, allow another fragment to be 
   moved to its destination.Hopefully, moving that fragment to its destination frees up 
   the space that another fragment needs to move into, and so on. For a disk with a 
   reasonable amount of free space (around half), this will move nearly all of the 
   fragments. For a disk with a very small amount of free space, it will not generally 
   work very well.

   Each fragment keeps track of how many other fragments are blocking it from being 
   moved to its final position
   
   1.   Find a fragment that is blocked by only one other fragment
   2.   See if it is possible to move that blocking fragment somewhere else
   3.   If THAT fragment could be moved to its destination were it not for one single 
      fragment blocking it, then repeat as many times as possible until we end up with a 
      blocking fragment we can’t move to its final destination
   4.   Move that fragment somewhere out of the way
   5.   Update the blockage information as a result of the move
   6.   While there are unblocked fragments, move them to their destinations, updating 
      the blockage information again
   
   There are two problems with this strategy. We might end up covering the same 
   ground several times. If we consider a long chain of dependencies before giving up, 
   we might follow that chain each time we encountered one of its members. Also, it is 
   possible to have a circular dependency chain where every fragment is waiting for 
   the next one in the loop. Under those circumstances we might end up following the 
   chain round and round for ever. To avoid both these cases I fill in the ‘unique search 
   index’ when I first process a fragment. If I come across a search index smaller than 
   the current one, I abort the search. This is not very elegant, but it works!*/

void ConsiderMovingFragment(Fragment *fragPtr)
{
   if ((!fragPtr->inFinalPosition) &&
      (fragPtr->fragmentsBlockingThis <= 1) &&
      (fragPtr->processedInThisLoop == kNotProcessed))
   {
      /*   This fragment is one that we want to be able to move   */
      Fragment   *fragToMove = fragPtr;
      FreeRange   *longestRangePtr = (FreeRange*)(TreeMaximum(
         freeRangeLengthRoot)->data);
      long      longestFreeRange = longestRangePtr->lastBlock – 
         longestRangePtr->firstBlock + 1;
      
      /*   Given the fragment that we want to move, find the one that is blocking it. 
         Check if that fragment can be moved   ...... continue description......*/
      uniqueSearchIndex++;
      fragPtr->processedInThisLoop = uniqueSearchIndex;
      do
      {
         /*   Find the fragment blocking this one   */
         Fragment *result = (Fragment*)DATA(TreeSearch(
            fragmentCurrentStartRoot, fragToMove,
            Fragment::FindOneBlockingTheKeyFragment));
         ASSERT(result != NULL);

         /*   If there isn’t anywhere we can move that fragment to, stop now   */
         if (result->numBlocks > longestFreeRange)
            break;
         
         /*   Processed in a previous loop, or already in this loop (in which case we have 
            found a ring where every fragment is preventing the next one from being 
            moved - moving any of these will allow all to be moved one after the other). 
            Stop the search   */
         if ((result->processedInThisLoop <= uniqueSearchIndex) &&
            (result->processedInThisLoop != kNotProcessed))
         {
            break;
         }
         
         /*   If we move ‘result’ we will be able to move ‘fragToMove’ into the space it has 
            left   */
         fragToMove = result;
         fragToMove->processedInThisLoop = uniqueSearchIndex;
         
         /*   If we get to a fragment that is blocked by more than one, we have reached 
            the end of the chain. Stop the loop.   */
      } while (fragToMove->fragmentsBlockingThis == 1);

      if ((fragToMove == fragPtr) &&
         (fragToMove->fragmentsBlockingThis != 0))
         return;         /*   Failed to find a place to move the one blocking it   */

      if ((fragToMove->processedInThisLoop < uniqueSearchIndex) &&
         (fragToMove->processedInThisLoop != kNotProcessed))
      {
         return;         /*   Already processed earlier   */
      }
         
      /*   Now we have decided on a fragment to move, make the move. We should have 
         checked earlier on that there a suitable space to move the fragment into. If we 
         are very unlucky, though,the new space we select will still be blocking the 
         range we are trying to free, so the call isn’t 100% guaranteed to allow any other 
         fragments to move.   */
      fragToMove->MoveOutOfTheWay();
      MoveFragmentsToDestinationSquares();
   }
}

void MarkFragmentAsBlockedBy(Fragment *theBlockedFragment, 
      Fragment *theBlocker)
// this routine omitted for length, see online archive

void MoveFragmentsToDestinationSquares(void)
{
   /*   While there are fragments queued as ready to move, move them to their final 
      destinations. Moving one fragment may add extra fragments to the lists. Moving 
      it may occasionally block one of the other fragments that are queued. In that case, 
      the fragment is removed from the queue automatically   */
   Fragment *fragToMove;
   do
   {
      while (firstOverlappingFragmentToMove != NULL)
      {
         fragToMove = firstOverlappingFragmentToMove;
         fragToMove->RemoveFromLists();
         fragToMove->MoveToFinalOverlappingPosition(true);
      }
      
      while (firstFragmentToMove != NULL)
      {
         fragToMove = firstFragmentToMove;
         fragToMove->RemoveFromLists();
         fragToMove->MoveToFinalPosition(true);
      }
   } while (firstOverlappingFragmentToMove != NULL);
}

void Fragment::ForEveryFragmentBlockedByThisOne(
      void (*theCallback)(Fragment *theBlockedFragment, 
      Fragment *theBlocker))
void Fragment::FragmentAboutToUnblock(
      Fragment *theBlockedFragment, Fragment *theBlocker)
void Fragment::FragmentAboutToBlock(Fragment *theBlockedFragment, 
         Fragment *theBlocker)
// these routines omitted for length, see online archive

void Fragment::FreeToMoveToFinalPosition(void)
{
   /*   This function is called when there is nothing preventing the fragment from 
      moving to its final position. We do not immediately move the fragment, though – 
      we just add it to the relevant queue so it will be moved in the next call to 
      MoveFragmentsToDestinationSquares. This function was probably called 
      because another fragment is about to move, unblocking this fragment’s final 
      position. That fragment might move to a new position that is STILL blocking this 
      fragment, though, so we will
      have to wait before we actually move this fragment   */
   ASSERT(nextInMoveList == NULL);
   ASSERT(prevInMoveList == NULL);
   if (blockedBySelf)
   {
      /*   Fragment is only blocked by itself. Add it to the list of ones to move.
         There is a separate list for these as we might want to wait for a bigger gap to be
         available as temporary storage   */
      nextInMoveList = firstOverlappingFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstOverlappingFragmentToMove = this;
   }
   else
   {
      /* Can be moved directly to final position   */
      nextInMoveList = firstFragmentToMove;
      nextInMoveList->prevInMoveList = this;
      prevInMoveList = NULL;
      firstFragmentToMove = this;
   }
}

void Fragment::RemoveFromLists(void)
// this routine omitted for length, see online archive

Moving Fragments
void Fragment::MoveToPosition(long destBlock, Boolean 
         maintainBlockageCount)
{
   /*   Move the fragment as instructed, and inform any interested parties   */
   /*   We may want to keep track of which fragments are being blocked at the moment. 
      If so,maintainBlockageCount is ‘true’   */
   if (maintainBlockageCount)
   {
      /*   Inform other fragments that this fragment’s current position is about to become 
         free   */
      ForEveryFragmentBlockedByThisOne(FragmentAboutToUnblock);
   }
   
   /*   Mark the place it was as free   */
   FreeRange::FragmentRangeIsFree(this);
   
   OutputMoveInstruction(startBlock, destBlock, numBlocks, 
         inFinalPosition);
   startBlock = destBlock;
   
   /*   We might have moved it to its final destination by chance   */
   if (startBlock == finalStartBlock)
      inFinalPosition = true;

   /*   Do the standard processing for when a fragment has moved   */
   FragmentHasMoved(maintainBlockageCount);
}

void Fragment::MoveToPositionNoOutput(long destBlock)
// this routine omitted for length, see online archive

void Fragment::MoveOutOfTheWay(void)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalPosition(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

void Fragment::MoveToFinalOverlappingPosition(Boolean maintainBlockageCount)
{
   /*   We want to find the most efficient way of making the move. Because the source 
      and destination ranges are not allowed to overlap for a move instruction, it cannot 
      be done with a single instruction. We could either move it somewhere completely 
      different and then back to its destination, or we could move it in several chunks, 
      but without using any extra temporary storage. This is treated as a special case 
      because there are several ways of doing it, and a number of nasty catches we need 
      to check for      */
   ASSERT(fragmentsBlockingThis == 0);
   ASSERT(blockedBySelf);
   
   long   movement = ABS(startBlock - finalStartBlock);
   long   blocksAvailable, firstBlockAvailable;

   /*   Start by working out how many steps it would take to move the fragment without 
      using any extra temporary storage.Calculate numBlocks/movement, rounded UP 
      */
   FreeRange   *bestRange = NULL;
   long      bestSteps = (numBlocks + movement - 1) / movement;
   long      blocksAvailableInBestRange, 
            firstBlockAvailableInBestRange;
   long      steps;
   
   if (bestSteps > 2)
   {
      /*   We would take at least two steps to move the fragment via any extra space we 
         might choose, so only consider other options if we can’t do it in two moves */

      /*   Find the biggest space available, and see how many steps it would take to move 
         the fragment via it. Note that this largest range may be the one that includes the 
         destination area, in which case not all
         of it is available as temporary storage   */
      FreeRange   *largestFreeRange = 
      (FreeRange*)DATA(TreeMaximum(freeRangeLengthRoot));
      
      if ((startBlock > finalStartBlock) &&
         (largestFreeRange->lastBlock == startBlock - 1))
      {
         /*   Overlap between source and dest fragment positions is at the end of the 
            destination,and overlap with this free range is at the start of the destination */
         blocksAvailable = finalStartBlock – 
               largestFreeRange->firstBlock;
         firstBlockAvailable = largestFreeRange->firstBlock;
      }
      else if ((startBlock < finalStartBlock) &&
             (largestFreeRange->firstBlock == startBlock + numBlocks))
      {
         /*   Overlap with existing fragment position is at the start of the destination, and 
            overlap with the free range is at the end of the destination */
         blocksAvailable = largestFreeRange->lastBlock – 
               (finalStartBlock + numBlocks) + 1;
         firstBlockAvailable = finalStartBlock + numBlocks;
      }
      else
      {
         /*   The free range we have found is somewhere completely different (the ideal 
            case!)   */
         blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
         firstBlockAvailable = largestFreeRange->firstBlock;
      }

      if (blocksAvailable > 0)
      {
         /*   Work out how many steps it would take to transfer the whole fragment.
            Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
         steps = 2 * ((numBlocks + blocksAvailable - 1) / 
            blocksAvailable);

         if (steps < bestSteps)
         {
            /*   This is the best option so far   */
            bestSteps = steps;
            bestRange = largestFreeRange;
            blocksAvailableInBestRange = blocksAvailable;
            firstBlockAvailableInBestRange = firstBlockAvailable;
         }
         
         if (blocksAvailable != largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1)
         {
            /*   The range we just looked at is the one that includes the destination 
               position. This has been taken into account in the calculations we just made 
               to rate it. However, this means that the second-largest free range may 
               actually be a better choice. Note that since the last range we considered 
               overlapped the destination, we know this
               one doesn’t      */
            largestFreeRange = (FreeRange*) DATA(TreePredecessor(
               largestFreeRange->lengthTreeNode));
            blocksAvailable = largestFreeRange->lastBlock – 
               largestFreeRange->firstBlock + 1;
            
            /* Calculate 2 * (numBlocks / blocksAvailable, rounded UP)   */
            steps = (2 * ((numBlocks + blocksAvailable - 1) / 
               blocksAvailable));

            if (steps < bestSteps)
            {
               /*   This is the best option so far   */
               bestSteps = steps;
               bestRange = largestFreeRange;
               blocksAvailableInBestRange = blocksAvailable;
               firstBlockAvailableInBestRange = 
                  largestFreeRange->firstBlock;
            }
         }
      }
   }
   
   long   offset, blocksToMoveThisTime,
         blocksAlreadyMoved = 0,
         blocksLeftToMove = numBlocks;

   if (bestRange == NULL)
   {
      /*   The best way of moving it doesn’t use any additional storage. We move as 
         much as we can in one go, and this frees up another section that can be moved, 
         until the whole fragment has been moved   */

      /*   Starting from the end of the fragment, move it in chunks of size “movement”
         to its final position   */
      while (blocksLeftToMove > 0)
      {
         blocksToMoveThisTime = MIN(movement, blocksLeftToMove);
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
               blocksToMoveThisTime;
         else
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset,
               finalStartBlock + offset, blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
      }
   }
   else
   {
      /*   The best way of moving it is to move as much as possible into bestRange, and 
         from there to its final position, repeating until the whole fragment has been 
         moved   */

      /*   Starting from the end of the fragment, move it in chunks of size 
         “blocksAvailableInBestRange” to its final position via 
         firstBlockAvailableInBestRange   */
      while (blocksLeftToMove > 0)
      {
         blocksToMoveThisTime = MIN(blocksAvailableInBestRange, 
            blocksLeftToMove);
         if (finalStartBlock > startBlock)
            offset = numBlocks - blocksAlreadyMoved – 
               blocksToMoveThisTime;
         else
            offset = blocksAlreadyMoved;

         OutputMoveInstruction(startBlock + offset, 
               firstBlockAvailableInBestRange,
                           blocksToMoveThisTime, false);
         OutputMoveInstruction(firstBlockAvailableInBestRange, 
               finalStartBlock + offset,
                           blocksToMoveThisTime, true);

         blocksAlreadyMoved += blocksToMoveThisTime;
         blocksLeftToMove -= blocksToMoveThisTime;
      }
   }   
   
   /*   Update the internal information to take account of this move (it doesn’t matter 
      exactly how we achieved the move). Also notify any other fragments affected by 
      the move, so they can update
      their blockage counts   */
   inFinalPosition = true;
   if (maintainBlockageCount)
      ForEveryFragmentBlockedByThisOne(FragmentAboutToUnblock);
   FreeRange::FragmentRangeIsFree(this);

   startBlock = finalStartBlock;
   if (maintainBlockageCount)
      blockedBySelf = false;
   fragmentsPositioned++;
   if ((displayProgress == kDisplayBlocks) &&
      (animationType != kFastestAnimation))
   {
UpdateProgress(((float)(testCase - 1) + 
   ((float)fragmentsPositioned / (float)totalFragments)) / 
         (float)numTestCases, testCase);
   }

   /*   No need to resort the current-position tree as the fragment order hasn’t changed. 
      We do need to update its sort key, though   */
   currentStartTreeNode->keyLong = startBlock;

   if (maintainBlockageCount)
      ForEveryFragmentBlockedByThisOne(FragmentAboutToBlock);

   FreeRange::FragmentRangeNotFree(this);
}

void Fragment::FragmentHasMoved(Boolean maintainBlockageCount)
// this routine omitted for length, see online archive

Fragment *Fragment::SplitToFitLength(long lengthOfFirstPart)
// this routine omitted for length, see online archive

void OutputMoveInstruction(long from, long to, long blocksToMove, Boolean finalPosition)
{
   if (displayProgress == kDisplayBlocks)
      ClearDisplayedBlockRange(from, from + blocksToMove - 1);
   fprintf(outputFile, “%ld,%ld,%ld\n”, from, to, blocksToMove);
   if (displayProgress == kDisplayBlocks)
      SetDisplayedBlockRange(to, to + blocksToMove - 1, true, finalPosition);
}

// Search function section omitted for length, see online archive

// Main.cp, ReadExisting.cp, Trees.cp, Trees.h, Windows.cp omitted because of 
//  length; see online archive

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Duplicate Annihilator 5.7.5 - Find and d...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator... Read more
BusyContacts 1.0.2 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
Capture One Pro 8.2.0.82 - RAW workflow...
Capture One Pro 8 is a professional RAW converter offering you ultimate image quality with accurate colors and incredible detail from more than 300 high-end cameras -- straight out of the box. It... Read more
Backblaze 4.0.0.872 - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac.With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
Little Snitch 3.5.2 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
Monolingual 1.6.4 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. If you use your computer in only one (human) language, you... Read more
CleanApp 5.0 - Application deinstaller a...
CleanApp is an application deinstaller and archiver.... Your hard drive gets fuller day by day, but do you know why? CleanApp 5 provides you with insights how to reclaim disk space. There are... Read more
Fantastical 2.0 - Create calendar events...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event details... Read more
Cocktail 8.2 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Direct Mail 4.0.4 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more

These are All the Apple Watch Apps and G...
The Apple Watch is less than a month from hitting store shelves, and once you get your hands on it you're probably going to want some apps and games to install. Fear not! We've compiled a list of all the Apple Watch apps and games we've been able to... | Read more »
Appy to Have Known You - Lee Hamlet Look...
Being at 148Apps these past 2 years has been an awesome experience that has taught me a great deal, and working with such a great team has been a privilege. Thank you to Rob Rich, and to both Rob LeFebvre and Jeff Scott before him, for helping me... | Read more »
Hands-On With Allstar Heroes - A Promisi...
Let’s get this out of the way quickly. Allstar Heroes looks a lot like a certain other recent action RPG release, but it turns out that while it’s not yet available here, Allstar Heroes has been around for much longer than that other title. Now that... | Read more »
Macho Man and Steve Austin Join the Rank...
WWE Immortals, by Warner Bros. Interactive Entertainment and WWE, has gotten a superstar update. You'll now have access to Macho Man Randy Savage and Steve Austin. Both characters have two different versions: Macho Man Randy Savage Renegade or Macho... | Read more »
Fearless Fantasy is Fantastic for the iF...
I actually had my first look at Fearless Fantasy last year at E3, but it was on a PC so there wasn't much for me to talk about. But now that I've been able to play with a pre-release version of the iOS build, there's quite a bit for me to talk... | Read more »
MLB Manager 2015 (Games)
MLB Manager 2015 5.0.14 Device: iOS Universal Category: Games Price: $4.99, Version: 5.0.14 (iTunes) Description: Guide your favorite MLB franchise to glory! MLB Manager 2015, officially licensed by MLB.com and based on the award-... | Read more »
Breath of Light (Games)
Breath of Light 1.0.1421 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1421 (iTunes) Description: Hold a quiet moment. Breath of Light is a meditative and beautiful puzzle game with a hypnotic soundtrack by... | Read more »
WWE WrestleMania Tags into the App Store
Are You ready to rumble? The official WWE WrestleMania app, by World Wrestling Entertainment, is now available. Now you can get all your WrestleMania info in one place before anyone else. The app offers details on superstar signings, interactive... | Read more »
Bio Inc's New Expansion is Infectin...
Bio Inc., by DryGin Studios, is the real time strategy game where you infect a human body with the worst virus your evil brain can design. Recently, the game was updated to add a whole lot of new features. Now you can play the new “Lethal”... | Read more »
The Monocular Minion is Here! Despicable...
Despicable Me: Minion Rush, by Gameloft, is introducing a new runner to the mix in their latest update. Now you can play as Carl, the prankster minion. Carl has a few new abilities to play with, including running at a higher speed from the start.... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.... Read more
Save up to $80 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $80 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549.99 $50 off - 128GB iPad... Read more
iMacs on sale for up to $205 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1019 $80 off - 21″ 2.7GHz iMac: $1189 $110 off - 21″ 2.9GHz... Read more
Färbe Technik Offers iPhone Battery Charge LI...
Färbe Technik, which manufactures and markets of mobile accessories for Apple, Blackberry and Samsung mobile devices, is offering tips on how to keep your iPhone charged while in the field: •... Read more
Electronic Recyclers International CEO Urges...
Citing a recent story on CNBC about concerns some security professionals have about the forthcoming Apple Watch, John Shegerian, Chairman and CEO of Electronic Recyclers International (ERI), the... Read more
Save up to $380 with Apple refurbished iMacs
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $2119 $... Read more
Mac minis on sale for up to $75 off, starting...
MacMall has Mac minis on sale for up to $75 off MSRP including free shipping. Their prices are the lowest available for these models from any reseller: - 1.4GHz Mac mini: $459.99 $40 off - 2.6GHz Mac... Read more
College Student Deals: Additional $50 off Mac...
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through April 11, 2015. Anyone with a valid .EDU email address can take advantage... Read more
Mac Pros on sale for up to $260 off MSRP
B&H Photo has Mac Pros on sale for up to $260 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2799, $200 off MSRP - 3.5GHz 6-core Mac Pro: $3719.99... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more

Jobs Board

DevOps Software Engineer - *Apple* Pay, iOS...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Lead *Apple* Solutions Consultant - Retail...
**Job Summary** Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.