Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they
should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places
on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since
many libraries are now computerized, you can write a program to help.
When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians
will ask your program for a list of books that have been returned so the books can be returned to their correct
places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then
title using the ASCII collating sequence. Your program should output the list of returned books in the same order
as they should appear on the shelves. For each book, your program should tell the librarian which book (including
those previously shelved) is already on the shelf before which the returned book should go.
Input
First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the
shelves. No two books have the same title. The format of each line will be:
"title" by author
The end of the stock listing will be marked by a line containing only the word:
END
Following the stock list will be a series of records of books borrowed and returned, and requests from librarians
for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:
BORROW "title"
RETURN "title"
SHELVE
The list will be terminated by a line containing only the word:
END
Output
Each time the SHELVE command appears, your program should output a series of instructions for the librarian,
one per line, in the format:
Put "title1" after "title2"
or, for the special case of the book being the first in the collection:
Put "title" first
After the set of instructions for each SHELVE, output a line containing only the word:
END
Assumptions & Limitations
1. A title is at most 80 characters long.
2. An author is at most 80 characters long.
3. A title will not contain the double quote (") character.
Sample Input
"The Canterbury Tales" by Chaucer, G.
"Algorithms" by Sedgewick, R.
"The C Programming Language" by Kernighan, B. and Ritchie, D.
END
BORROW "Algorithms"
BORROW "The C Programming Language"
RETURN "Algorithms"
RETURN "The C Programming Language"
SHELVE
END
Output for the Sample Input
Put "The C Programming Language" after "The Canterbury Tales"
Put "Algorithms" after "The C Programming Language"
END
What I have tried:
#include <stdio.h>
#include <iostream>
#include <string.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _CharT, typename _Traits>
class basic_filebuf : public basic_streambuf<_CharT, _Traits>
{
public:
typedef _CharT char_type;
typedef _Traits traits_type;
typedef typename traits_type::int_type int_type;
typedef typename traits_type::pos_type pos_type;
typedef typename traits_type::off_type off_type;
typedef basic_streambuf<char_type, traits_type> __streambuf_type;
typedef basic_filebuf<char_type, traits_type> __filebuf_type;
typedef basic_file<char>_file_type;
typedef typename traits_type::state_type __state_type;
typedef codecvt<char_type, char, __state_type> __codecvt_type;
friend class ios_base;
protected:
__c_lock _M_lock;
__file_type _M_file;
ios_base::openmode _M_mode;
__state_type _M_state_beg;
__state_type _M_state_cur;
__state_type _M_state_last;
char_type* _M_buf;
size_t _M_buf_size;
bool _M_buf_allocated;
bool _M_reading;
bool _M_writing;
char_type _M_pback;
char_type* _M_pback_cur_save;
char_type* _M_pback_end_save;
bool _M_pback_init;
const __codecvt_type* _M_codecvt;
char* _M_ext_buf;
streamsize _M_ext_buf_size;
const char* _M_ext_next;
char* _M_ext_end;
void
_M_create_pback()
{
if (!_M_pback_init)
{
_M_pback_cur_save = this->gptr();
_M_pback_end_save = this->egptr();
this->setg(&_M_pback, &_M_pback, &_M_pback + 1);
_M_pback_init = true;
}
}
void
_M_destroy_pback() throw()
{
if (_M_pback_init)
{
_M_pback_cur_save += this->gptr() != this->eback();
this->setg(_M_buf, _M_pback_cur_save, _M_pback_end_save);
_M_pback_init = false;
}
}
public:
basic_filebuf();
virtual
~basic_filebuf()
{ this->close(); }
bool
is_open() const throw()
{ return _M_file.is_open(); }
__filebuf_type*
open(const char* __s, ios_base::openmode __mode);
#if __cplusplus >= 201103L
__filebuf_type*
open(const std::string& __s, ios_base::openmode __mode)
{ return open(__s.c_str(), __mode); }
#endif
__filebuf_type*
close();
protected:
void
_M_allocate_internal_buffer();
void
_M_destroy_internal_buffer() throw();
virtual streamsize
showmanyc();
virtual int_type
underflow();
virtual int_type
pbackfail(int_type __c = _Traits::eof());
virtual int_type
overflow(int_type __c = _Traits::eof());
bool
_M_convert_to_external(char_type*, streamsize);
virtual __streambuf_type*
setbuf(char_type* __s, streamsize __n);
virtual pos_type
seekoff(off_type __off, ios_base::seekdir __way,
ios_base::openmode __mode = ios_base::in | ios_base::out);
virtual pos_type
seekpos(pos_type __pos,
ios_base::openmode __mode = ios_base::in | ios_base::out);
pos_type
_M_seek(off_type __off, ios_base::seekdir __way, __state_type __state);
int
_M_get_ext_pos(__state_type &__state);
virtual int
sync();
virtual void
imbue(const locale& __loc);
virtual streamsize
xsgetn(char_type* __s, streamsize __n);
virtual streamsize
xsputn(const char_type* __s, streamsize __n);
bool
_M_terminate_output();
void
_M_set_buffer(streamsize __off)
{
const bool __testin = _M_mode & ios_base::in;
const bool __testout = (_M_mode & ios_base::out
|| _M_mode & ios_base::app);
if (__testin && __off > 0)
this->setg(_M_buf, _M_buf, _M_buf + __off);
else
this->setg(_M_buf, _M_buf, _M_buf);
if (__testout && __off == 0 && _M_buf_size > 1 )
this->setp(_M_buf, _M_buf + _M_buf_size - 1);
else
this->setp(0, 0);
}
};
template<typename _CharT, typename _Traits>
class basic_ifstream : public basic_istream<_CharT, _Traits>
{
public:
typedef _CharT char_type;
typedef _Traits traits_type;
typedef typename traits_type::int_type int_type;
typedef typename traits_type::pos_type pos_type;
typedef typename traits_type::off_type off_type;
typedef basic_filebuf<char_type, traits_type> __filebuf_type;
typedef basic_istream<char_type, traits_type> __istream_type;
private:
__filebuf_type _M_filebuf;
public:
basic_ifstream() : __istream_type(), _M_filebuf()
{ this->init(&_M_filebuf); }
explicit
basic_ifstream(const char* __s, ios_base::openmode __mode = ios_base::in)
: __istream_type(), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#if __cplusplus >= 201103L
explicit
basic_ifstream(const std::string& __s,
ios_base::openmode __mode = ios_base::in)
: __istream_type(), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#endif
~basic_ifstream()
{ }
__filebuf_type*
rdbuf() const
{ return const_cast<__filebuf_type*>(&_M_filebuf); }
bool
is_open()
{ return _M_filebuf.is_open(); }
bool
is_open() const
{ return _M_filebuf.is_open(); }
void
open(const char* __s, ios_base::openmode __mode = ios_base::in)
{
if (!_M_filebuf.open(__s, __mode | ios_base::in))
this->setstate(ios_base::failbit);
else
this->clear();
}
#if __cplusplus >= 201103L
void
open(const std::string& __s, ios_base::openmode __mode = ios_base::in)
{
if (!_M_filebuf.open(__s, __mode | ios_base::in))
this->setstate(ios_base::failbit);
else
this->clear();
}
#endif
void
close()
{
if (!_M_filebuf.close())
this->setstate(ios_base::failbit);
}
};
template<typename _CharT, typename _Traits>
class basic_ofstream : public basic_ostream<_CharT,_Traits>
{
public:
typedef _CharT char_type;
typedef _Traits traits_type;
typedef typename traits_type::int_type int_type;
typedef typename traits_type::pos_type pos_type;
typedef typename traits_type::off_type off_type;
typedef basic_filebuf<char_type, traits_type> __filebuf_type;
typedef basic_ostream<char_type, traits_type> __ostream_type;
private:
__filebuf_type _M_filebuf;
public:
basic_ofstream(): __ostream_type(), _M_filebuf()
{ this->init(&_M_filebuf); }
explicit
basic_ofstream(const char* __s,
ios_base::openmode __mode = ios_base::out|ios_base::trunc)
: __ostream_type(), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#if __cplusplus >= 201103L
explicit
basic_ofstream(const std::string& __s,
ios_base::openmode __mode = ios_base::out|ios_base::trunc)
: __ostream_type(), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#endif
~basic_ofstream()
{ }
__filebuf_type*
rdbuf() const
{ return const_cast<__filebuf_type*>(&_M_filebuf); }
bool
is_open()
{ return _M_filebuf.is_open(); }
bool
is_open() const
{ return _M_filebuf.is_open(); }
void
open(const char* __s,
ios_base::openmode __mode = ios_base::out | ios_base::trunc)
{
if (!_M_filebuf.open(__s, __mode | ios_base::out))
this->setstate(ios_base::failbit);
else
this->clear();
}
#if __cplusplus >= 201103L
void
open(const std::string& __s,
ios_base::openmode __mode = ios_base::out | ios_base::trunc)
{
if (!_M_filebuf.open(__s, __mode | ios_base::out))
this->setstate(ios_base::failbit);
else
this->clear();
}
#endif
void
close()
{
if (!_M_filebuf.close())
this->setstate(ios_base::failbit);
}
};
template<typename _CharT, typename _Traits>
class basic_fstream : public basic_iostream<_CharT, _Traits>
{
public:
typedef _CharT char_type;
typedef _Traits traits_type;
typedef typename traits_type::int_type int_type;
typedef typename traits_type::pos_type pos_type;
typedef typename traits_type::off_type off_type;
typedef basic_filebuf<char_type, traits_type> __filebuf_type;
typedef basic_ios<char_type, traits_type> __ios_type;
typedef basic_iostream<char_type, traits_type> __iostream_type;
private:
__filebuf_type _M_filebuf;
public:
basic_fstream()
: __iostream_type(), _M_filebuf()
{ this->init(&_M_filebuf); }
explicit
basic_fstream(const char* __s,
ios_base::openmode __mode = ios_base::in | ios_base::out)
: __iostream_type(0), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#if __cplusplus >= 201103L
explicit
basic_fstream(const std::string& __s,
ios_base::openmode __mode = ios_base::in | ios_base::out)
: __iostream_type(0), _M_filebuf()
{
this->init(&_M_filebuf);
this->open(__s, __mode);
}
#endif
~basic_fstream()
{ }
__filebuf_type*
rdbuf() const
{ return const_cast<__filebuf_type*>(&_M_filebuf); }
bool
is_open()
{ return _M_filebuf.is_open(); }
bool
is_open() const
{ return _M_filebuf.is_open(); }
void
open(const char* __s,
ios_base::openmode __mode = ios_base::in | ios_base::out)
{
if (!_M_filebuf.open(__s, __mode))
this->setstate(ios_base::failbit);
else
this->clear();
}
#if __cplusplus >= 201103L
void
open(const std::string& __s,
ios_base::openmode __mode = ios_base::in | ios_base::out)
{
if (!_M_filebuf.open(__s, __mode))
this->setstate(ios_base::failbit);
else
this->clear();
}
#endif
void
close()
{
if (!_M_filebuf.close())
this->setstate(ios_base::failbit);
}
return 0;
}
Submit an article or tip