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

 
AAPL
$102.47
Apple Inc.
+2.71
MSFT
$44.88
Microsoft Corpora
+0.80
GOOG
$526.54
Google Inc.
+5.70

MacTech Search:
Community Search:

Software Updates via MacUpdate

EyeTV 3.6.6 - Watch and record TV on you...
EyeTV brings a rich TV experience to your Mac. Watch live TV on your Mac. Pause, rewind, and record whenever you want. EyeTV gives you powerful control over what you watch and how you watch it. Put... Read more
RapidWeaver 6.0 - Create template-based...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
NTFS 12.0.39 - Provides full read and wr...
Paragon NTFS breaks down the barriers between Windows and OS X. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS, providing full read and write access to... Read more
RestoreMeNot 2.0.3 - Disable window rest...
RestoreMeNot provides a simple way to disable the window restoration for individual applications so that you can fine-tune this behavior to suit your needs. Please note that RestoreMeNot is designed... Read more
Macgo Blu-ray Player 2.10.9.1750 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple iOS 8.1 - The latest version of Ap...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PDFKey Pro 4.0.2 - Edit and print passwo...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Yasu 2.9.1 - System maintenance app; per...
Yasu was originally created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks... Read more
Hazel 3.3 - Create rules for organizing...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a... Read more

Latest Forum Discussions

See All

Infuse Pro (Photography)
Infuse Pro 3.0 Device: iOS Universal Category: Photography Price: $9.99, Version: 3.0 (iTunes) Description: ** All-new version 3 includes fully licensed and certified DTS® and DTS-HD® audio! ** | Read more »
Swap Heroes (Games)
Swap Heroes 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: **Half price for a limited time only** Swap Heroes is a casual turn-based strategy adventure. Form a group of heroes and guide them... | Read more »
Ghost Blade (Games)
Ghost Blade 1.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.1 (iTunes) Description: Get the most outstanding 3D Action Game from App Store NOW! For those who dare pursue dreams. Masterpiece of Yu Shi Game ---China... | Read more »
Fiete – A Day on a Farm Review
Fiete – A Day on a Farm Review By Amy Solomon on October 21st, 2014 Our Rating: :: A MEMORABLE EXPERIENCEUniversal App - Designed for iPhone and iPad Fiete – A day on a farm in an interactive app for young children full of... | Read more »
Tilt to Live: Gauntlet’s Revenge is Almo...
Tilt to Live: Gauntlet’s Revenge is Almost Here Posted by Jessica Fisher on October 21st, 2014 [ permalink ] One Man Left has announced the official release date of Tilt to Live: Gauntlet’s Re | Read more »
Sago Mini Monsters Celebrates Halloween...
Sago Mini Monsters Celebrates Halloween with Fun Costumes and Special Treats. Posted by Jessica Fisher on October 21st, 2014 [ permal | Read more »
Inferno 2 Review
Inferno 2 Review By Andrew Fisher on October 21st, 2014 Our Rating: :: TWIN STICK GOODNESSUniversal App - Designed for iPhone and iPad With tight controls and awesome, stark visuals, Inferno 2 is loads of fun.   | Read more »
Clips Review
Clips Review By Jennifer Allen on October 21st, 2014 Our Rating: :: CONVENIENT PASTINGUniversal App - Designed for iPhone and iPad Making copying and pasting more powerful than usual, Clips is a great way to move stuff around.   | Read more »
MonSense Review
MonSense Review By Jennifer Allen on October 21st, 2014 Our Rating: :: ORGANIZED FINANCESiPhone App - Designed for the iPhone, compatible with the iPad Organize your finances with the quick and easy to use, MonSense.   | Read more »
This Week at 148Apps: October 13-17, 201...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »

Price Scanner via MacPrices.net

Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... 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.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Strong iPhone, Mac And App Store Sales Drive...
Apple on Monday announced financial results for its fiscal 2014 fourth quarter ended September 27, 2014. The Company posted quarterly revenue of $42.1 billion and quarterly net profit of $8.5 billion... Read more
Apple Posts How-To For OS X Recovery
OS X 10.7 Lion and later include OS X Recovery. This feature includes all of the tools you need to reinstall OS X, repair your disk, and even restore from a Time Machine backup. OS X Recovery... Read more
Mac OS X Versions (Builds) Supported By Vario...
Apple Support has posted a handy resource explaining which Mac OS X versions (builds) originally shipped with or are available for your computer via retail discs, downloads, or Software Update. Apple... Read more
Deals on 2011 13-inch MacBook Airs, from $649
Daily Steals has the Mid-2011 13″ 1.7GHz i5 MacBook Air (4GB/128GB) available for $699 with a 90 day warranty. The Mid-2011 13″ 1.7GHz i5 MacBook Air (4GB/128GB SSD) is available for $649 at Other... Read more
2013 15-inch 2.0GHz Retina MacBook Pro availa...
B&H Photo has leftover previous-generation 15″ 2.0GHz Retina MacBook Pros now available for $1599 including free shipping plus NY sales tax only. Their price is $400 off original MSRP. B&H... Read more
Updated iPad Prices
We’ve updated our iPad Air Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers, including the new iPad Air 2 and the... Read more
Apple Pay Available to Millions of Visa Cardh...
Visa Inc. brings secure, convenient payments to iPad Air 2 and iPad mini 3as well as iPhone 6 and 6 Plus. Starting October 20th, eligible Visa cardholders in the U.S. will be able to use Apple Pay,... Read more
Textkraft Pocket – the missing TextEdit for i...
infovole GmbH has announced the release and immediate availability of Textkraft Pocket 1.0, a professional text editor and note taking app for Apple’s iPhone. In March 2014 rumors were all about... Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.