Stack based path conversion.

Introduction

The following article explains a simple algorithm to convert absolute path to relative and relative to absolute. Sample code also can be found along with the article. This code can be used free of cost but at your on risk. (Test the functions properly before using.)

The code works for windows as well as Linux. A description of the algorithm is given below.

Absolute path to relative path (Abs2Rel)

Abs2Rel path function takes absolute path as input and returns relative path.

//------------------------------------------------------------------------------

// Method        : Abs2Rel

// Description        : Convert absolute path to relative path.

// Parameter        : pcAbsPath - Input - Absolute path

// Parameter        : pcRelPath - Output - Relative path

// Parameter        : pcCurrDir - Input - Current Dir/Reference dir path

// Return        : Relative path

// Author        : Boby Thomas Pazheparampil April 2006

//------------------------------------------------------------------------------

char * Abs2Rel(char *pcAbsPath, char *pcRelPath, char* pcCurrDir)

Operation.

Following sequence will explain the conversion process.

For example consider the abs path "/cygdrive/d/boby/india/boby.txt", and reference directory "/cygdrive/d/try/path_conv"

Step 1: First extract the path parameters into stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue






boby.txt
india		path_conv
boby		try
d		d
cygdrive		cygdrive

Step 2: Push the size difference of stacks into output stack. If the absolute path stack size is more, push the actual content of the stack "tmpStackAbsPath" into the stack "tmpStackOutput". If the size of the stack "tmpStackCurrPath" is more, add an ellipse ("..") into output path "pcRelPath".

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue






india	path_conv
boby	try
d	d
cygdrive	cygdrive	boby.txt

Step 3: Compare the tops of stacks "tmpStackAbsPath" and "tmpStackCurrPath". If it is matching, add into queue for later possible use. (If there is a mismatch in lower layers of stack, this queue will be used). If it is not matching like in the example above, contents of queue will be pushed to output stack. After pushing queue to "tmpStackOutput", top of "tmpStackAbsPath" will be pushed to stack "tmpStackOutput". Also an ellipse will be added to "pcRelPath", the output relative path.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue







boby	try
d	d	india
cygdrive	cygdrive	boby.txt

pcRelPath = "..\"

Step 4: Repeat the same process till the end of stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue







		boby
D	d	india
cygdrive	cygdrive	boby.txt

pcRelPath = "..\..\"

Step 5: Repeat the same process till the end of stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue





			d

		boby
		india
cygdrive	cygdrive	boby.txt

pcRelPath = "..\..\"

Step 6: Repeat the same process till the end of stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d

				boby
				india
				boby.txt

pcRelPath = "..\..\"

Step 7: Once the "tmpStackAbsPath" and "tmpStackCurrPath" are exhausted, move the content of "tmpStackOutput" to the output string pcRelPath .

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d


				india
				boby.txt

pcRelPath = "..\..\boby\"

Step 8: Once the "tmpStackAbsPath" and "tmpStackCurrPath" are exhausted, move the content of "tmpStackOutput" to the output string pcRelPath .

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d



				boby.txt

pcRelPath = "..\..\boby\India\"

Step 9: Continue the process till the "tmpStackOutput" exhausts.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d

pcRelPath = "..\..\boby\india\ boby.txt"

Relative path to absolute path (Rel2Abs)

Abs2Rel path function takes absolute path as input and returns relative path.

//------------------------------------------------------------------------------

// Method        : Rel2Abs

// Description    : Convert absolute path to relative path.

// Parameter    : pcRelPath - Input - Relative path

// Parameter    : pcAbsPath - Output - Absolute path

// Parameter    : pcCurrDir - Input - Current Dir/Reference dir path

// Return        : Absolute path

// Author        : Boby Thomas Pazheparampil April 2006

//------------------------------------------------------------------------------


char * Rel2Abs(char *pcRelPath, char *pcAbsPath, char* pcCurrDir)

Operation.

Following sequence will explain the conversion process.

For example consider the relative path "../../boby/../temp.txt" and reference directory "/cygdrive/d/try/path_conv"

Step 1: First extract the relative path into queue "tmpQueueRelPath".

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..
..

Step 2: Then convert the reference path into stack "tmpStackCurrPath".

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..		path_conv
..		try
		d
		cygdrive

Step 3: Take entries from the front of the queue "tmpQueueRelPath". If it is an ellipse, pop out the last entry in the stack "tmpStackCurrPath". If the front entry in the queue "tmpQueueRelPath" is not ellipse, push the entry into stack "tmpStackCurrPath".

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..
		try
		d
		cygdrive

Step 4: Continue the same process until the queue "tmpQueueRelPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby


		d
		cygdrive

Step 5: Continue the same process until the queue "tmpQueueRelPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..


		boby
		d
		cygdrive

Step 6: Continue the same process until the queue "tmpQueueRelPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt




		d
		cygdrive

Step 7: Continue the same process until the queue "tmpQueueRelPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput








		temp.txt
		d
		cygdrive

Step 8: Once the queue "tmpQueueRelPath" exhausts, pop the content of the stack "tmpStackCurrPath" and push it to the stack "tmpStackOutput".

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









		d
		cygdrive		temp.txt

Step 9: Repeat the process till the stack "tmpStackCurrPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









				d
		cygdrive		temp.txt

Step 10: Repeat the process till the stack "tmpStackCurrPath" exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput








				cygdrive
				d
				temp.txt

Step 11: Once the stack "tmpStackCurrPath" is empty, take the content into absolute return path string.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









				d
				temp.txt

pcAbsPath = "/cygdrive/"

Step 12: Repeat the process till stack "tmpStackOutput" is empty.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput










				temp.txt

pcAbsPath = "/cygdrive/d/"

Step 13: Repeat the process till stack "tmpStackOutput" is empty.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput

pcAbsPath = "/cygdrive/d/ temp.txt"

Summary

We can think of lots of different methods for the above implementation. Feedback about this method will be greatly appreciated. Contact me at bobypt@gmail.com.

boby

india

cygdrive

boby.txt

pcRelPath = �..\..\�

Step 5: Repeat the same process till the end of stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue





			d

		boby
		india
cygdrive	cygdrive	boby.txt

pcRelPath = �..\..\�

Step 6: Repeat the same process till the end of stacks.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d

				boby
				india
				boby.txt

pcRelPath = �..\..\�

Step 7: Once the �tmpStackAbsPath� and �tmpStackCurrPath� are exhausted, move the content of �tmpStackOutput� to the output string pcRelPath .

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d


				india
				boby.txt

pcRelPath = �..\..\boby\�

Step 8: Once the �tmpStackAbsPath� and �tmpStackCurrPath� are exhausted, move the content of �tmpStackOutput� to the output string pcRelPath .

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d



				boby.txt

pcRelPath = �..\..\boby\India\�

Step 9: Continue the process till the �tmpStackOutput� exhausts.

tmpStackAbsPath tmpStackCurrPath tmpStackOutput tmpMatchQueue




						cygdrive
						d

pcRelPath = �..\..\boby\india\ boby.txt�

Relative path to absolute path (Rel2Abs)

Abs2Rel path function takes absolute path as input and returns relative path.

//------------------------------------------------------------------------------

// Method        : Rel2Abs

// Description    : Convert absolute path to relative path.

// Parameter    : pcRelPath - Input - Relative path

// Parameter    : pcAbsPath - Output - Absolute path

// Parameter    : pcCurrDir - Input - Current Dir/Reference dir path

// Return        : Absolute path

// Author        : Boby Thomas Pazheparampil April 2006

//------------------------------------------------------------------------------


char * Rel2Abs(char *pcRelPath, char *pcAbsPath, char* pcCurrDir)

Operation.

Following sequence will explain the conversion process.

For example consider the relative path �../../boby/../temp.txt" and reference directory �/cygdrive/d/try/path_conv�

Step 1: First extract the relative path into queue �tmpQueueRelPath�.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..
..

Step 2: Then convert the reference path into stack �tmpStackCurrPath�.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..		path_conv
..		try
		d
		cygdrive

Step 3: Take entries from the front of the queue �tmpQueueRelPath�. If it is an ellipse, pop out the last entry in the stack �tmpStackCurrPath�. If the front entry in the queue �tmpQueueRelPath� is not ellipse, push the entry into stack �tmpStackCurrPath�.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby
..
		try
		d
		cygdrive

Step 4: Continue the same process until the queue �tmpQueueRelPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..
boby


		d
		cygdrive

Step 5: Continue the same process until the queue �tmpQueueRelPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt
..


		boby
		d
		cygdrive

Step 6: Continue the same process until the queue �tmpQueueRelPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput




temp.txt




		d
		cygdrive

Step 7: Continue the same process until the queue �tmpQueueRelPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput








		temp.txt
		d
		cygdrive

Step 8: Once the queue �tmpQueueRelPath� exhausts, pop the content of the stack �tmpStackCurrPath� and push it to the stack �tmpStackOutput�.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









		d
		cygdrive		temp.txt

Step 9: Repeat the process till the stack �tmpStackCurrPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









				d
		cygdrive		temp.txt

Step 10: Repeat the process till the stack �tmpStackCurrPath� exhausts.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput








				cygdrive
				d
				temp.txt

Step 11: Once the stack �tmpStackCurrPath� is empty, take the content into absolute return path string.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput









				d
				temp.txt

pcAbsPath = �/cygdrive/�

Step 12: Repeat the process till stack �tmpStackOutput� is empty.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput










				temp.txt

pcAbsPath = �/cygdrive/d/�

Step 13: Repeat the process till stack �tmpStackOutput� is empty.

tmpQueueRelPath tmpStackCurrPath tmpStackOutput

pcAbsPath = �/cygdrive/d/ temp.txt�

Summary

We can think of lots of different methods for the above implementation. Feedback about this method will be greatly appreciated. Contact me at bobypt@gmail.com.

You must Sign In to use this message board.


Per page

Bug on PC - case sensitive
R o n n y

4:48 9 Jun '07

Abs2Rel of c:\temp\xx from C:\Temp\yy returned ..\..\..\c:\temp\xx Error: in line 64: if(strcmp(tmpStackAbsPath.top(),tmpStackCurrPath.top())== 0 ) Fix: #if defined(_MSC_VER) #define STRCMP strcmpi #elif defined(__GNUC__) #define STRCMP strcmp #else #error define your compiler #endif and replacing strcmp by STRCMP. Ronny Sherer
Sign In·View Thread·PermaLink

Very useful, but this algorithm is not always correct
Shura Kotov

21:53 29 Aug '06

The problem is in string comparison type - it should be case not sensitive!
The other thing: the class is not supporting an UNICODE.

Here is my overwieved class version with UNICODE support, that from my point of view little bit universal (with default current directory parameter):

// The class definition:
#define path_separator _T("\\")
#define path_sep_char _T('\\')

typedef queue QueuePtrChar;
typedef stack StackPtrChar;

class CPathConvertor
{
public:
friend struct pathInitializer;
CPathConvertor();
virtual ~CPathConvertor();
static LPCTSTR Relative2Absolute(LPCTSTR pcRelPath, LPTSTR pcAbsPath, LPCTSTR pcCurrDir = _T(""));
static LPCTSTR Absolute2Relative(LPCTSTR pcAbsPath, LPTSTR pcRelPath, LPCTSTR pcCurrDir = _T(""));
static int Relative2Backup(LPCTSTR pcRelPath, LPTSTR pcBackupPath, LPCTSTR pcBackupDir);
protected:
static wstring szCurrentDirectory;
};

struct pathInitializer
{
pathInitializer()
{
TCHAR szCurDir[MAX_PATH];
GetCurrentDirectory(MAX_PATH, szCurDir);
CPathConvertor::szCurrentDirectory = szCurDir;
}
};
// the class implementation
wstring CPathConvertor::szCurrentDirectory = _T("");
pathInitializer once;

CPathConvertor::CPathConvertor()
{

}

CPathConvertor::~CPathConvertor()
{

}

LPCTSTR CPathConvertor::Relative2Absolute(LPCTSTR pcRelPath, LPTSTR pcAbsPath, LPCTSTR pcCurrDir)
{
TCHAR acTmpCurrDir[MAX_PATH];
TCHAR acTmpRelPath[MAX_PATH];

if(_tcslen(pcCurrDir))
_tcscpy(acTmpCurrDir, pcCurrDir);
else
_tcscpy(acTmpCurrDir, szCurrentDirectory.data());

_tcscpy(acTmpRelPath, pcRelPath);

QueuePtrChar tmpQueueRelPath;
StackPtrChar tmpStackCurrPath;
StackPtrChar tmpStackOutPath;

TCHAR *sTmp = _tcstok(acTmpRelPath, path_separator);
while(sTmp)
{
tmpQueueRelPath.push(sTmp);
sTmp = _tcstok(0, path_separator);
}

sTmp = _tcstok(acTmpCurrDir,path_separator);
while(sTmp)
{
tmpStackCurrPath.push(sTmp);
sTmp = _tcstok(0, path_separator);
}

while(tmpQueueRelPath.size() > 0)
{
TCHAR *pcTmp = tmpQueueRelPath.front();
if(0 == _tcsicmp(pcTmp, _T("..")))
tmpStackCurrPath.pop();
else
tmpStackCurrPath.push(pcTmp);
tmpQueueRelPath.pop();
}

while(!tmpStackCurrPath.empty())
{
tmpStackOutPath.push(tmpStackCurrPath.top());
tmpStackCurrPath.pop();
}

sTmp = pcAbsPath;

while(!tmpStackOutPath.empty())
{
TCHAR *pcTmp = tmpStackOutPath.top();
while(*pcTmp != _T('\0'))
*sTmp++ = *pcTmp++;
tmpStackOutPath.pop();
*sTmp++ = path_sep_char;
}
*(--sTmp) = _T('\0');

return pcAbsPath;
}

LPCTSTR CPathConvertor::Absolute2Relative(LPCTSTR pcAbsPath, LPTSTR pcRelPath, LPCTSTR pcCurrDir)
{
TCHAR acTmpCurrDir[MAX_PATH];
TCHAR acTmpAbsPath[MAX_PATH];

if(_tcslen(pcCurrDir))
_tcscpy(acTmpCurrDir, pcCurrDir);
else
_tcscpy(acTmpCurrDir, szCurrentDirectory.data());

_tcscpy(acTmpAbsPath,pcAbsPath);

StackPtrChar tmpStackAbsPath;
StackPtrChar tmpStackCurrPath;
StackPtrChar tmpStackOutput;
QueuePtrChar tmpMatchQueue;

TCHAR *sTmp = _tcstok(acTmpAbsPath,path_separator);
while(sTmp)
{
tmpStackAbsPath.push(sTmp);
sTmp = _tcstok(0, path_separator);
}

sTmp = _tcstok(acTmpCurrDir,path_separator);
while(sTmp)
{
tmpStackCurrPath.push(sTmp);
sTmp = _tcstok(0, path_separator);
}

sTmp = pcRelPath;
while(tmpStackCurrPath.size() > tmpStackAbsPath.size() )
{
*sTmp++ = '.';
*sTmp++ = '.';
*sTmp++ = path_sep_char;
tmpStackCurrPath.pop();
}

while(tmpStackAbsPath.size() > tmpStackCurrPath.size() )
{
TCHAR *pcTmp = tmpStackAbsPath.top();
tmpStackOutput.push(pcTmp);
tmpStackAbsPath.pop();
}

while(!tmpStackAbsPath.empty())
//while(tmpStackAbsPath.size() > 0)
{
if(_tcsicmp(tmpStackAbsPath.top(),tmpStackCurrPath.top())== 0 )
tmpMatchQueue.push(tmpStackAbsPath.top());
else
{
while(!tmpMatchQueue.empty())
//while(tmpMatchQueue.size() > 0)
tmpStackOutput.push(tmpMatchQueue.front());
tmpStackOutput.push(tmpStackAbsPath.top());
*sTmp++ = _T('.');
*sTmp++ = _T('.');
*sTmp++ = path_sep_char;
}
tmpStackAbsPath.pop();
tmpStackCurrPath.pop();
}

while(!tmpStackOutput.empty())
//while(tmpStackOutput.size() > 0)
{
TCHAR *pcTmp = tmpStackOutput.top();
while(*pcTmp != _T('\0'))
*sTmp++ = *pcTmp++;
tmpStackOutput.pop();
*sTmp++ = path_sep_char;
}
*(--sTmp) = _T('\0');

return pcRelPath;
}

Alex Kotliarker
Software Engineer
Magal Security Systems, Israel

simple and functional
Bila1

7:04 28 Aug '06

Good work.

Just what I was looking for: a nice and simple sollution for this problem.

One observation though. Have you maybe considered declaring the "read-only" "char*" function parameters (pcRelPath/pcCurrDir in "Rel2Abs" function and pcAbsPath/pcCurrDir in "Abs2Rel" function) as "const char *"?
This does not provide any significant functionality, only makes the interface clearer, at least to me (and saves a cast or two Smile

).

Bila

These functions exist in the windows shell and CRT
Eric Gur

11:55 18 Apr '06

Nice work FYI, these functions are already implemented: Relative to full path: _fullpath, _wfullpath Windows shell library (shlwapi.h, shlwapi.lib): PathRelativePathTo - create relative path from a source file and target directory. The reverse function can be used from the C runtime library (stdlib): _fullpath, _wfullpath
Sign In·View Thread·PermaLink	1.80/5

Re: These functions exist in the windows shell and CRT
Boby Thomas P

22:53 18 Apr '06

These functions will not work in linux. But the source what I have created can be used (Same files) for windows aswell as linux. An example for platform independant coding.. Regards, Boby
Sign In·View Thread·PermaLink

Re: These functions exist in the windows shell and CRT
Eric Gur

10:46 19 Apr '06

Boby, I know that what I wrote will only work under Windows (maybe _fullpath exists in Linux), and I complement your work and initiative Regards, Eric
Sign In·View Thread·PermaLink

Another way
DavidCrow

4:17 18 Apr '06

For `Abs2Rel()`, have you considered `PathRelativePathTo()`? "Let us be thankful for the fools. But for them the rest of us could not succeed." - Mark Twain "There is no death, only a change of worlds." - Native American Proverb
Sign In·View Thread·PermaLink

Nice logic
prasad_v_k

20:05 17 Apr '06

Hi, Its nice logic. But I think its simpler to cd to directory and getcwd to get absolute path of the directory. Similarly, to get relative path from absolute path cd to absolute path directory and cut off contents of the getcwd. It might look dirty but its easy and works. With regards -- Prasad
Sign In·View Thread·PermaLink

Re: Nice logic
Amr Shahin

22:03 5 Nov '06

there is something is OSs called "permitions" :P... that could prevent u from CDing to the directory, beside that it might be an imginary directory,
Sign In·View Thread·PermaLink

Code is not DBCS-aware
Michael Dunn

7:35 16 Apr '06

Your use of `strtok()` instead of `_tcstok()` will break in DBCS strings where a trail bytes equals 0x5c (the backslash). --Mike-- Visual C++ MVP LINKS~! Ericahist \| NEW!! PimpFish \| CP SearchBar v3.0 \| C++ Forum FAQ
Sign In·View Thread·PermaLink

nice logic
ismail23

22:45 15 Apr '06


Sign In·View Thread·PermaLink

Notes
YoSilver

11:33 15 Apr '06

Nice idea, but why not use PathRelativePathTo (see Shlwapi.h and MSDN)? And please, process your artice with HTMLTidy. Articles should not be written in MS Word, just because your small article weights >500 kB One always gets the deserved. http://www.silveragesoftware.com/hffr.html HandyFile Find And Replace
Sign In·View Thread·PermaLink

Re: Notes
BobyThomasP

22:21 15 Apr '06

thanks for the info. Will that work for linux ?? Anyway let me check. I will check that. Regards, Boby
Sign In·View Thread·PermaLink

great idea
gomas_11

8:57 15 Apr '06

great idea -
Sign In·View Thread·PermaLink